10364  Square
Moderator: Board moderators

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
Okay, based on your code, looks like you're implementing a greedyalgorithm ... 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
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
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

 New poster
 Posts: 9
 Joined: Wed Apr 16, 2003 6:50 pm
 Location: Braga, Portugal
 Contact:
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
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

 New poster
 Posts: 9
 Joined: Wed Apr 16, 2003 6:50 pm
 Location: Braga, Portugal
 Contact:
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(ind1,parc));
if (val[ind]<=parc && livre[ind])
{
livre[ind]=2;
return tentar(ind1,parcval[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[r1]>aux)
{
val[r]=val[r1];
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=num1;
while (j>=0 && total<=num)
{
if (livre[j]){
int au=j;
while(au>=0){
if (tentar(au,parcelaval[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.
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(ind1,parc));
if (val[ind]<=parc && livre[ind])
{
livre[ind]=2;
return tentar(ind1,parcval[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[r1]>aux)
{
val[r]=val[r1];
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=num1;
while (j>=0 && total<=num)
{
if (livre[j]){
int au=j;
while(au>=0){
if (tentar(au,parcelaval[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.

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
Hello Vitor, I used backtracking to solve this problem. In order not to unnecessarily process a known subtree 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 307Sticks ... *sigh* ...
turuthok
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 307Sticks ... *sigh* ...
turuthok
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

 New poster
 Posts: 9
 Joined: Wed Apr 16, 2003 6:50 pm
 Location: Braga, Portugal
 Contact:

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
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
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
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

 New poster
 Posts: 9
 Joined: Wed Apr 16, 2003 6:50 pm
 Location: Braga, Portugal
 Contact:

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
Vitor, try this:
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
Code: Select all
1
8 9 3 3 1 1 1 1 1
turuthok
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

 New poster
 Posts: 9
 Joined: Wed Apr 16, 2003 6:50 pm
 Location: Braga, Portugal
 Contact:

 New poster
 Posts: 9
 Joined: Wed Apr 16, 2003 6:50 pm
 Location: Braga, Portugal
 Contact:
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 == Sticks1) {
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 nonrecursive, but I don't think this should make it much faster. When you guys say "dynamic programming", do you mean nonrecursive?
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 == Sticks1) {
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 nonrecursive, but I don't think this should make it much faster. When you guys say "dynamic programming", do you mean nonrecursive?
10364 TLE
Hi! I don't know how to make faster the problem 10364
I have read the other posts about this problem but I can't get the correct idea to solve it in better way
here is my code:
I just use backtracking ,but maybe there is another way to do it
if someone can help me I would appreciate
thanks! bye!
I have read the other posts about this problem but I can't get the correct idea to solve it in better way
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;
}
if someone can help me I would appreciate
thanks! bye!