307 - Sticks
Moderator: Board moderators
-
- Learning poster
- Posts: 71
- Joined: Thu Aug 21, 2003 1:56 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.
I think the best way of solving this is to work out a few examples by hand and then try to find an optimization.
WA...how large can n be?
In 307 how large can n, number of sticks be?Im getting WA ...
My code is:
Help....
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]
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.
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.
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 *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
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
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 *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.
[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.
-
- 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.
You can't expect anyone to answer your post if he knows same question was asked before and answered.
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.
-
- Learning poster
- Posts: 71
- Joined: Thu Aug 21, 2003 1:56 am
Try these cases:
input:
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!
input:
output: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
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).3755
3775
841
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!
Can some help to me ??????
I need a solve it in pascal !!!!!!!!!
that is my solve where i have a bug?????
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.
Another solve +bug
Help me !!!!!!!!!!!!!!!!!!!!!!!!!!!!
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.
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.
I am trying to use backtracking but I find no way to optimize, any hints???
best regards,
Yandry.