307 - Sticks

[hank]

yeah...I already solved the problem and got accepted!!
I use recursion and some tricks to avoid Time Limit Exceeded.

[howardcheng]

care to share the tricks?

[junbin]

I used brute force checking and my time was 0:00.563s so that should be enough... I don't think there's any other creative way of solving this (eg: DP, etc.) since this question is NP-complete.

I think the best way of solving this is to work out a few examples by hand and then try to find an optimization.

[helmet]

In 307 how large can n, number of sticks be?Im getting WA ...
My code is:

Code: Select all

[cpp]
#include<iostream.h>

int main()
{
	int n,i,j;
	int array[1000];
	int tsum,max;
	cin>>n;
	while(n)
	{
		int sum[50001]={0},copy[50001];
		tsum=0;
		
		cin>>array[0];
		max=tsum=array[0];
		for(i=1;i<n;i++)
		{
			cin>>array[i];
			tsum+=array[i];
			if(max<array[i])
				max=array[i];
		}
		sum[0]=1;
		for(i=0;i<n;i++)
		{
			for(j=0;j<=tsum;j++)
			{
				copy[j]=sum[j];
			}
			for(j=array[i];j<=tsum;j++)
			{
				if(copy[j-array[i]])
					sum[j]=1;
			}
		}
		for(i=max;i<=tsum;i++)
		{
			if(sum[i]&&tsum%i==0)
			{
				for(j=2*i;j<tsum;j=j+i)
				{
					if(sum[j]==0)
						break;
				}
				if(j>=tsum)
					break;
			}
		}
		cout<<i<<endl;
		cin>>n;
	}
	return 0;
}[/cpp]

Help....

[Adrian Kuegel]

Please try the test cases given in a thread before posting a wrong program.
Your program fails on several test cases of Yarin. And I think you can figure out really fast why your program fails.
It seems you assume it is sufficient to check if you can reach the sum i, 2*i, ...
but 2*i could be reached with another summation as i+i.
You can use your program only to check if some value cannot be the solution, but in other cases you need backtracking to verify if it is really possible.

[helmet]

I found the problem but have no idea how to correct...any ideas?

I dont think backtracking can u used coz it will cause TLE...or is it possible?

[orojas]

I get TLE for this problem: why?
total time 10.0something secs, limit 10 secs.

Here is the code:

[c]#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solucion;
int failed;
int lenghtSol;
int *usado;
int *stickSize;


int allUsed(int *usado,int N) {
int i;
for(i=0;i<N && usado==1;i++);
if(i==N)
return 1;
else
return 0;
}

void tryIt(int lenght,int acum,int total,int n) {
int k;
for(k=0;k<n && failed==0 && solucion==0;k++) {
if(usado[k]==0 && (acum+stickSize[k])<=lenght) {
usado[k]=1;
total-= stickSize[k];
acum+=stickSize[k];
if(allUsed(usado,n)==1 && acum==lenght) {
solucion = 1;
lenghtSol=acum;
}
else {
if(acum==lenght) {
if(total%lenght==0) {
tryIt(lenght,0,total,n);
}
else {
failed =1;
}
}
else {
tryIt(lenght,acum,total,n);
}
}
usado[k]=0;
total+= stickSize[k];
acum-=stickSize[k];
}
}
}

int main() {
int i,N;
int minLenght,maxLenght;

usado = NULL;
stickSize = NULL;
while(scanf("%d",&N)==1) {
if(N==0) break;
solucion = 0;
minLenght=maxLenght=0;
if(usado!=NULL)
free(usado);
usado = (int *)malloc(sizeof(int)*N);
if(stickSize!=NULL)
free(stickSize);
stickSize = (int *)malloc(sizeof(int)*N);
for(i=0;i<N;i++) {
scanf("%d",&stickSize);
maxLenght += stickSize;
if(stickSize>minLenght)
minLenght = stickSize;
}
lenghtSol = maxLenght;
for(i=minLenght;i<maxLenght && solucion==0;i++) {
failed = 0;
memset(usado,0,sizeof(int)*N);
if((maxLenght%i)==0)
tryIt(i,0,maxLenght,N);
}
printf("%d\n",lenghtSol);
}
return 0;
}[/c]

Any Help appreciated

[orojas]

I changed the code posted earlier(that one gave me TLE), to a Greedy aproach in which I sort the sticks sizes first and then search in all possible lenghts of the original sticks, beginning from the minimun length possible to the max posible which is the sum of all sticks' length. I think is the right aproach since the sticks sizes are ordered in descendant order and once i choose a stick to form a set I don't take it anymore. Now it gives me W.A.. I've though every input i can imagine, I don't see what's wrong. Here is the code:

[c]#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solucion;
int failed;
int lenghtSol;
int *usado;
int *stickSize;

int compara(const void *a,const void *b) {
int A,B;
A = *(int *)a;
B = *(int *)b;
return(B-A);
}

int allUsed(int *usado,int N) {
int i;
for(i=0;i<N && usado==1;i++);
if(i==N)
return 1;
else
return 0;
}

void tryIt(int lenght,int acum,int total,int n) {
int k;
for(k=0;k<n && solucion==0;k++) {
if(usado[k]==0 && (acum+stickSize[k])<=lenght) {
usado[k]=1;
acum+=stickSize[k];
total-=stickSize[k];
}
}
if(acum==lenght) {
if(total==0) {
solucion=1;
lenghtSol=acum;
}
else {
if((total%lenght)==0) {
tryIt(lenght,0,total,n);
}
}
}
}

int main() {
int i,N;
int minLenght,maxLenght;
/* FILE *in;*/

usado = NULL;
stickSize = NULL;
/* in = fopen("sticks.in","r");*/
while(scanf("%d",&N)==1) {
if(N==0) break;
solucion = 0;
minLenght=maxLenght=0;
if(usado!=NULL)
free(usado);
usado = (int *)malloc(sizeof(int)*N);
if(stickSize!=NULL)
free(stickSize);
stickSize = (int *)malloc(sizeof(int)*N);
for(i=0;i<N;i++) {
scanf("%d",&stickSize);

if(stickSize<=50) {
maxLenght += stickSize;
if(stickSize>minLenght)
minLenght = stickSize;
}
else {
i--;
N--;
}
}
lenghtSol = maxLenght;
qsort(stickSize,N,sizeof(int),compara);
/* printf("# %d\n** ",maxLenght);
for(i=0;i<N;i++) {
printf("%d ",stickSize);
}
printf("\n");*/
for(i=minLenght+1;i<maxLenght && solucion==0;i++) {
failed = 0;
memset(usado,0,sizeof(int)*N);
qsort(stickSize,N,sizeof(int),compara);
tryIt(i,0,maxLenght,N);
}
printf("%d\n",lenghtSol);
}
/* fclose(in);
system("pause");*/
return 0;
}[/c]

Any help would be appreciated. maybe ther's a tricky input i didn't take into account.

[Adrian Kuegel]

Please use search function before posting:
http://online-judge.uva.es/board/search.php

When searching for 307, you can also find this post:
http://online-judge.uva.es/board/viewtopic.php?t=1332
It contains a tricky test case.

You can't expect anyone to answer your post if he knows same question was asked before and answered.

[howardcheng]

I still don't have any more ideas. Nothing I try seems to work.

[yiuyuho]

Per wrote:

57
50 49 48 43 32 29 28 17 14 13 12 12 9 8 6 28 29 12 32 48 40 8 13 9 49 12 43 17 14 50 2 3 3 2 1 2 37 30 19 2 31 3 12 31 31 23 9 5 49 4 23 49 43 50 25 24 8 8

Is there not 58 values? I counted few times and I get 58..I must be really tired

I am drafting...

[yiuyuho]

Try these cases:
input:

99
10 10 10 10 10 10 10 10 10 10
20 20 20 20 20 20 20 20 20 20
40 40 40 40 40 40 40 40 40 40
40 40 40 40 40 40 40 40 40 40
40 40 40 40 40 40 40 40 40 40
30 30 30 30 30 30 30 30 31 37
50 50 50 50 50 50 50 50 50 50
50 47 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50
99
10 10 10 10 15 10 19 10 17 10
20 20 20 20 21 20 20 27 20 20
40 40 40 40 40 40 40 40 47 40
40 40 40 40 40 40 40 40 40 40
40 40 40 40 40 40 40 40 41 40
30 30 30 30 30 30 30 30 31 37
50 50 50 50 50 50 50 50 50 50
50 47 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 33 50
50 50 50 50 50 50 50 50 50
99
10 7 1 10 15 10 19 2 17 10
20 20 20 20 21 20 3 27 20 20
40 40 40 17 40 40 4 27 47 40
40 40 11 15 40 40 42 25 40 40
40 40 40 5 40 40 40 40 41 40
30 30 30 30 30 30 9 30 31 37
50 50 17 50 31 50 50 50 50 50
50 47 50 50 50 50 50 47 50 50
33 50 6 50 19 50 50 18 33 50
50 50 50 50 50 50 50 50 50
0

output:

3755
3775
841

They are interesting, my AC code didn't find the solution (giving long long time), but my TLE code did. So the TLE code is better at these cases while AC code is better at judge data. It seems backtracking algorithms are very data dependent (most solution cant solve the problem, but can solve the judge data).

Try running these cases with your AC code and see if they give the solution in good time. I would like to see some program that can solve both the judge and the above cases. Thank You!

[LavR]

Can some help to me ??????
I need a solve it in pascal !!!!!!!!!
that is my solve where i have a bug?????

Code: Select all

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var mas:array [1..255] of integer;
mas2:array [1..255] of integer;
n,m,i,j,s,zx,zz,sum,zx2,zz2,sum2,best2,zy,best,max1,zy2,max2:integer;
begin
best:=1;
best2:=1;
readln(n) ;
for i:=1 to n do
read(mas[i]) ;
readln(m);
for j:=1 to m do
read(mas2[j]);
readln(s)  ;
if s=0 then
Begin
sum:=0 ;
max1:=1 ;
for zx:=1 to n do
if mas[zx]>max1 then max1:=mas[zx];
 for zz:=1 to n do
  sum:=sum+mas[zz];
best:=sum ;
   for zy:=1 to n do
    if (sum mod zy)=0 then
    if (sum div zy)>max1 then
    if best>(sum div zy)  then
      best:=sum div zy ;


sum2:=0;
max2:=1 ;
for zx2:=1 to m do
if mas[zx2]>max2 then max2:=mas2[zx2];
 for zz2:=1 to m do
  sum2:=sum2+mas2[zz2];
best2:=sum2 ;
   for zy2:=1 to m do
    if (sum2 mod zy2)=0 then
    if (sum2 div zy2)>max2 then
     if best2>(sum2 div zy2) then
      best2:=sum2 div zy2;
END ;
writeln(best);
writeln(best2);
readln ;
  end.

[LavR]

Another solve +bug
Help me !!!!!!!!!!!!!!!!!!!!!!!!!!!!

Code: Select all

var mas:array [1..255] of integer;
mas2:array [1..255] of integer;
n,m,i,j,s,zx,zz,sum,zx2,flag,flag2,zz2,sum2,best2,zy,best,max1,min1,min2,zy2,max2:integer;
begin
best:=1;
best2:=1;
readln(n) ;
for i:=1 to n do
read(mas[i]) ;
readln(m);
for j:=1 to m do
read(mas2[j]);
readln(s)  ;
if s=0 then
Begin
sum:=0 ;
max1:=1 ;
min1:=mas[1];
min2:=mas2[1];
for zx:=1 to n do
if mas[zx]>max1 then max1:=mas[zx]
                  else if (mas[zx]<min1)and(mas[zx]<>0) then min1:=mas[zx];
 for zz:=1 to n do
  sum:=sum+mas[zz];
best:=sum ;
   zy:=(max1) ;
   repeat
     inc(zy) ;
   until  (((sum mod (zy-1))=0)and (zy-1>=(3*min1)))or((zy-1)=1) ;
 best:=zy-1;


 sum2:=0 ;
max2:=1 ;

for zx2:=1 to m do
if mas2[zx2]>max2 then max2:=mas2[zx2]
                  else if (mas2[zx2]<min2)and(mas2[zx2]<>0) then min2:=mas2[zx2];
 for zz2:=1 to m do
  sum2:=sum2+mas2[zz2];
best2:=sum2 ;
   zy2:=(max2) ;
   repeat
     inc(zy2) ;
   until  (((sum2 mod (zy2-1))=0 )and (zy2-1>=(3*min2)))or((zy2-1)=1);
 best2:=zy2-1;

END ;
writeln(best);
writeln(best2);
readln ;

  { TODO -oUser -cConsole Main : Insert code here }
end.

[neno_uci]

To the solvers->How did you solve this problem???

I am trying to use backtracking but I find no way to optimize, any hints???

best regards,

Yandry.