## 307 - Sticks

Moderator: Board moderators

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
yeah...I already solved the problem and got accepted!!
I use recursion and some tricks to avoid Time Limit Exceeded.

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am
care to share the tricks?

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
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
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

### WA...how large can n be?

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;
int tsum,max;
cin>>n;
while(n)
{
int sum={0},copy;
tsum=0;

cin>>array;
max=tsum=array;
for(i=1;i<n;i++)
{
cin>>array[i];
tsum+=array[i];
if(max<array[i])
max=array[i];
}
sum=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....
Just another brick in the wall...

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

### Oops

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?
Just another brick in the wall...

orojas
New poster
Posts: 5
Joined: Tue Jul 20, 2004 6:44 pm

### 307(Sticks) TLE why??

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 *stickSize;

int 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++) {
total-= stickSize[k];
acum+=stickSize[k];
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);
}
}
total+= stickSize[k];
acum-=stickSize[k];
}
}
}

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

stickSize = NULL;
while(scanf("%d",&N)==1) {
if(N==0) break;
solucion = 0;
minLenght=maxLenght=0;
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;
if((maxLenght%i)==0)
tryIt(i,0,maxLenght,N);
}
printf("%d\n",lenghtSol);
}
return 0;
}[/c]

Any Help appreciated

orojas
New poster
Posts: 5
Joined: Tue Jul 20, 2004 6:44 pm

### 307 - WA been greedy

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 *stickSize;

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

int 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++) {
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;*/

stickSize = NULL;
/* in = fopen("sticks.in","r");*/
while(scanf("%d",&N)==1) {
if(N==0) break;
solucion = 0;
minLenght=maxLenght=0;
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;
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.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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.

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am
I still don't have any more ideas. Nothing I try seems to work.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
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
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
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
New poster
Posts: 2
Joined: Fri Jun 17, 2005 1:51 am
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;
for i:=1 to n do
for j:=1 to m do
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);
end.``````

LavR
New poster
Posts: 2
Joined: Fri Jun 17, 2005 1:51 am
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;
for i:=1 to n do
for j:=1 to m do
if s=0 then
Begin
sum:=0 ;
max1:=1 ;
min1:=mas;
min2:=mas2;
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);

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

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

### How to solve...???

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. 