Page 2 of 4
Posted: Wed Apr 16, 2003 2:43 am
Okay, based on your code, looks like you're implementing a greedy-algorithm ... it won't work for this problem.

Consider these parts:
5 5 5 5
4 4 4 4
3 3 3 3

Just by looking at it, you know it's possible to construct 4 x (5 + 4 + 3) square. But, using greedy, you will be forced to take 5 and 5 first, and then the algorithm asks you to find 2 which doesn't exist. You would return "no" instead of "yes".

-turuthok-

Posted: Wed Apr 16, 2003 6:55 pm
hi. i'm soltrix (i don't know why i can't login since i changed some info in my profile )
you're right. i tested your input and i've seen that the output is "no" instead of "yes"

But, i'm not seing another way to solve this problem. can you give some instructions ???

I've been thinking, but i've not reached any solution yet

Thanks

Posted: Wed Apr 23, 2003 3:06 pm
i've been modifying my code and now it solves turuthok's input, but i still get WA. Can someone help me?

My new code is:
[cpp]

#include <iostream>

int val[20];
int livre[20];

int tentar(int ind, int parc)
{
if (parc==0) return 1;
if (ind<0) return -1;
if (val[ind]>parc) return (tentar(ind-1,parc));
if (val[ind]<=parc && livre[ind])
{
livre[ind]=2;
return tentar(ind-1,parc-val[ind]);
}
}

void limpa(){for (int i=0;i<20;i++) if (livre==2) livre=1;}
void corrige(){for (int i=0;i<20;i++) if (livre==2) livre=0;}

int main()
{
int n;
int num;
cin>>n;
for (int i=0;i<n;i++)
{
for (int aaa=0;aaa<20;aaa++)
{livre[aaa]=1;
}
cin>>num;
int cum=0;
for (int j=0;j<num;j++)
{
int aux;
cin>>aux;
cum+=aux;
int r=j;
while(r>0 && val[r-1]>aux)
{
val[r]=val[r-1];
r--;
}
val[r]=aux;
}
int valor=0;
int j,total=0;
int parcela=cum/4;
if (cum && cum%4) cout <<"no"<<endl;
else
{
total=0;
j=num-1;
while (j>=0 && total<=num)
{
if (livre[j]){
int au=j;
while(au-->=0){
if (tentar(au,parcela-val[j])>=0)
{
livre[j]=0;
corrige();
total+=parcela;
break;
}
else limpa();}
}
j--;
}
if (cum && total<num) cout<<"no"<<endl;
else cout << "yes"<<endl;
}
}
}

[/cpp]

Can someone at least show me some example that my program doesn't solve?
Thanks.

Posted: Wed Apr 23, 2003 7:49 pm
Hello Vitor, I used backtracking to solve this problem. In order not to unnecessarily process a known sub-tree that has no solution, I also keep track of what combination of objects we have visited. If my recursive function is entered with an already visited combination, that means it is useless to go on since it won't give us any solution, so I return immediately.

This visited combination is possible since the maximum number of sticks is only 20.

I hope it's not too confusing ...

This problem reminds me of 307-Sticks ... *sigh* ...

-turuthok-

Posted: Thu Apr 24, 2003 10:35 am
thanks for your help, but i didn't understand very well your explanation .

You used a graph or a tree? Can you post or send to my email a sort of algorithm to see if i really understand?

I've tried to solve 307 too, but i didn't solve it too .

Thanks

Posted: Thu Apr 24, 2003 7:57 pm
Vitor, ... I'm sorry for the confusion, ... No, I don't use graph nor tree. Actually, my code looks pretty similar than yours, it's just that we have to prevent the recursive function from going deeper and deeper unless it's necessary.

The way I prevented it was to record all combination that I passed already, and when I encountered it the second time, I won't bother to go deeper.

-turuthok-

Posted: Thu Apr 24, 2003 8:17 pm
ok. now i think that i understood it. but that is only to get the program faster it isn't? since i try all the possible combinations, i should get AC, don't you think?

if you have some input cases, please post it here.

Thanks,

Vitor

Posted: Fri Apr 25, 2003 7:49 pm
Vitor, try this:

Code: Select all

``````1
8 9 3 3 1 1 1 1 1``````
Also, regarding your tentar() function, don't you think you need a return -1 at the end of it ... I don't quite understand your algo, though ... probably I'm wrong ....

-turuthok-

Posted: Tue May 20, 2003 10:04 pm
Can someone past here some tricky input cases?? My program runs well in my pc, and solves 20 sticks input quiqly, however, wen i submit my code, i get TLE, maybe because a infinite loop caused by some tricky input.

Thanks for any help

Posted: Sun May 25, 2003 7:27 am
try this:
8 1 2 3 4 5 6 7 8
10 21 14 13 11 9 6 4 3 2 1
output:
yes
yes

by the way...
I got accepted now,and I use backtracking.
But when I use the same method to solve Problem 307 "Sticks"
,I got TLE!!
(I guess problem307 must be solved by Knapsack...)

Posted: Thu May 29, 2003 12:33 am
i' really can

Posted: Tue Oct 28, 2003 5:49 am
SoLtRiX, you counted the number 5 by mistake. It means the number of sticks, and it's not a stick length.

10+20+30+40+50 = 150
and 150/4 = 37,5

But anyway, answer to case 2 in sample input is "no".

Posted: Tue Oct 28, 2003 12:37 pm
I assume you're not supposed to bend or break sticks
Anyway, sounds like a nice problem.. I am going to have a try at it

Posted: Tue Oct 28, 2003 1:44 pm
When backtracking, why should I sort them and start from bigger sticks? Why should this be faster?

In Shahid's code, why do you check if sum==half ?

My simplest version of the problem gets Time Limit Exceeded, but I will improve it. It checks if the size of the square's wall that has been just increased has exceeded 1/4 of total sum of lengths of sticks. (Sum = TotalSum/4)

[cpp]int Select (int n) {
int i;
for (i=0;i<4;i++) {
Size += Stick[n];
if (Size <= Sum) {
if (n == Sticks-1) {
if (Size[0]==Size[1] && Size[0]==Size[2] && Size[0]==Size[3]) return 1;
}
else if (Select(n+1)) return 1;
}
Size -= Stick[n];
}
return 0;
}[/cpp]
I will put sticks with same length at once, with other function. If needed, I will also try sorting the sticks and starting from the bigger ones. I may make the function non-recursive, but I don't think this should make it much faster. When you guys say "dynamic programming", do you mean non-recursive?

### 10364 TLE

Posted: Fri Apr 01, 2005 6:02 am
Hi! I don't know how to make faster the problem 10364
here is my code:

Code: Select all

``````#include <stdio.h>
int r,s[22],tmp[22],m;
enum bool {FALSE,TRUE};
typedef enum bool boolean;

process(int p,int i,boolean *q){
int k=0;
*q=FALSE;
if(p>r) return 0;
else if(p==r && i==4) {
printf("yes\n");
*q=TRUE;
}
else if(p==r) process(0,i+1,q);
while(k<m && *q!=TRUE){
if(tmp[k]!=0){
p+=tmp[k];
tmp[k]=0;
process(p,i,q);
tmp[k]=s[k];
p-=tmp[k];
}
k++;
}
}

int main(){
int n,i,j;
boolean q;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&m);
r=0;
for(j=0;j<m;j++){
scanf("%d",&s[j]);
r+=s[j];tmp[j]=s[j];
}
if(r%4!=0) printf("no\n");
else{
r/=4;
process(0,1,&q);
if(!q) printf("no\n");
}
}
return 0;
}``````
I just use backtracking ,but maybe there is another way to do it
if someone can help me I would appreciate
thanks! bye!