307 - Sticks

All about problems in Volume 3. 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
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Tue Aug 19, 2003 11:33 am

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

Post by howardcheng » Sat Apr 17, 2004 7:50 am

care to share the tricks?

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Tue Apr 20, 2004 10:11 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?

Post by helmet » Wed Jun 16, 2004 12:02 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Jun 16, 2004 12:11 pm

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

Post by helmet » Wed Jun 16, 2004 12:29 pm

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??

Post by orojas » Tue Jul 20, 2004 7:11 pm

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
New poster
Posts: 5
Joined: Tue Jul 20, 2004 6:44 pm

307 - WA been greedy

Post by orojas » Mon Jul 26, 2004 1:14 am

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

Post by Adrian Kuegel » Mon Jul 26, 2004 9:23 am

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
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Post by howardcheng » Thu Jan 27, 2005 7:10 pm

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:

Post by yiuyuho » Sat May 07, 2005 6:16 am

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 :o :-?

I am drafting...

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Mon May 09, 2005 12:03 am

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

Post by LavR » Fri Jun 17, 2005 1:54 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;
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
New poster
Posts: 2
Joined: Fri Jun 17, 2005 1:51 am

Post by LavR » Sat Jun 18, 2005 4:57 pm

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
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

How to solve...???

Post by neno_uci » Wed Jun 29, 2005 5:49 am

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. :roll:

Post Reply

Return to “Volume 3 (300-399)”