10364 - Square

[turuthok]

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-

[VitorRodrigues]

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]

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]

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-

[VitorRodrigues]

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]

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-

[VitorRodrigues]

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]

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-

[VitorRodrigues]

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]

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]

i' really can

[Algoritmo]

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]

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]

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]

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:

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!