10721 - Bar Codes

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Tue Nov 02, 2004 12:30 am

I use a recursive formula:
f(n, k, m) = sum (1 .. m) f(n - i, k - 1, m)

muvee
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

Post by muvee » Tue Nov 02, 2004 1:25 am

That's it??!?!?!

And here I am doing it in such a complex way. I got every single valid sequence and then found all the combinations/permutations (never knew the difference :D ) of them...

vivander
New poster
Posts: 8
Joined: Sat May 21, 2005 2:13 am

10721 - TLE

Post by vivander » Mon May 23, 2005 2:46 pm

I have TLE for this problem, because I use a Formula to calculate recursively the final number for this problem. How can I quit TLE?

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Mon May 23, 2005 3:49 pm

If you solve it by a recursive formula, instead of coding a simple recursive function, you should store the value you get into a table so that you don't need to compute everything again and again each time.

vivander
New poster
Posts: 8
Joined: Sat May 21, 2005 2:13 am

I have TLE

Post by vivander » Mon May 23, 2005 4:34 pm

My problem persist. I don't know how to reduce time.

This is my code for this problem

Code: Select all

#include <stdio.h>
#include <stdlib.h>

long contador;

void Formula(int tot,int sep,int max){
	int i;
	
	if (tot<sep) return;
	else if ((tot<=max)&&(sep==1)) { contador++; return;}
	else if (sep==1) return;
		
	for(i=1;i<=max;i++) Formula(tot-i,sep-1,max);
}


int main (int car, char** v) {

	char linea[100];
	int total,separaciones,maximo;
		
	while(fgets(linea,100,stdin)!=NULL){
		sscanf(linea,"%d %d %d",&total,&separaciones,&maximo);
		
		contador=0;
		
		Formula(total,separaciones,maximo);
		
		printf("%ld\n",contador);
	}

	
	return 1;	
}

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Mon May 23, 2005 5:09 pm

You misunderstand what I mean. You should store the value in a 3D-table like:

Code: Select all

int table[50][50][50];

int Formula(int tot,int sep,int max){ 
   if(table[tot][sep][max]==-1)
   {
      // compute the value of Formula(int tot,int sep,int max)
      // recursively here and assign it to table[tot][sep][max]
   }
   return table[tot][sep][max];
} 

int main (int car, char** v) { 
   char linea[100]; 
   int total,separaciones,maximo; 

   initialize all entries of the table to be -1;
   
   while(fgets(linea,100,stdin)!=NULL) { 
      sscanf(linea,"%d %d %d",&total,&separaciones,&maximo); 
      printf("%ld\n", Formula(total,separaciones,maximo)); 
   } 
    
   return 1;    
}
This is a standard technique called dynamic programming. If you are computer science major, you will learn it in some intermediate/advanced algorithm course.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Mon May 23, 2005 8:15 pm

Hello.
This problem also can be solved using 2D matrix or just can be found a formula using PIE.
Eduard.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Sun Jun 19, 2005 11:40 am

Can you explain a bit what's the 2D approach. I've done it using a 4D array with dimensions [50][2][50][50].


Regards
Sanny

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sat Dec 15, 2007 5:48 pm

I have used 3D memo .. I am getting WA ..
can u give me some I/O where my code fails ..?? Thanks in advance ...

Code: Select all

removed after AC..
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

talizmelf
New poster
Posts: 3
Joined: Thu Oct 15, 2009 5:54 am

Re:

Post by talizmelf » Mon Oct 19, 2009 10:36 am

I matched the very all outputs from Krzysztof Duleba and I get WA...
Why would that be?

matrix2220
New poster
Posts: 9
Joined: Mon Jul 07, 2014 3:37 pm
Contact:

Re: 10721 - Bar Codes

Post by matrix2220 » Sat Aug 02, 2014 5:42 pm

Hints:
-------
Complete search over all bar widths, in each recursive call you should try to add a bar with all allowed width.
Recursively do that until all your bars width = n and number of bars = k Here you found a solution.

You can use a 2D array to store answers. in order not to re-calculate any of them (DP).
Abdelrahman Ali (MaTrix)

anando_du
New poster
Posts: 10
Joined: Sun Mar 01, 2015 3:11 pm

Re: 10721 - Bar Codes

Post by anando_du » Tue Mar 17, 2015 7:01 am

got ac on 1st submission :) actually 2D array is enough . as 'm' is not changing so we don't need 'm' as dp state

Post Reply

Return to “Volume 107 (10700-10799)”