## 10364 - Square

Moderator: Board moderators

turuthok
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 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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

VitorRodrigues
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

VitorRodrigues
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(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.

turuthok
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 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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

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

turuthok
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 fear of the LORD is the beginning of knowledge (Proverbs 1:7).

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

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

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

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
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...)

VitorRodrigues
New poster
Posts: 9
Joined: Wed Apr 16, 2003 6:50 pm
Location: Braga, Portugal
Contact:
i' really can

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:
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".

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 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

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
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 == 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?

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

### 10364 TLE

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!