10364 - Square

[cyfra]

Hi

I have no idea how is it posiible to solve this task in 0.00 sec.

My program worked too slow (TLE) or gave Wrong Answers...


Could anyone give me a hint how to solve this task efficient ??


Thanx in advance

[Adrian Kuegel]

I can't think how it is possible to solve it in 0.00 sec (I assume it is a sort of greedy that does not work in all cases). The only way I know is backtracking, because this problem is NP-complete. You can make your program fast enough, if you sort the sticks by length and in each recursion step consider equal lengths only once.

[Ivan Golubev]

I don't know how about 0.000 but I've got 0.010 with backtracking. Actually I've reused code for P307 (which looks harder than this problem).

[cyfra]

Thanks for help...

I got it Accepted at last..

it is not such a good time as 0.00 but it is Accepted

Thanks for reading...

[Alexandru Mosoi]

How did you do the backtracking?? I got only 3sec and something using back. What optimisation did you do??

[cyfra]

Don't ask me...

I have got more than 3 sec

( I will have to think about more optimalizations )

[galois_godel]

I can understand this problem.
what is the width of the stick?
why the case 2(5 10 20 30 40 50) can't be "Yes"?

[gvcormac]

The sticks have no width. You are to
form a square (that is, an equilateral
and equiangular 4-sided polygon)..

[Shahid]

hi,

i submitted my solution for 10364, but got WA......i test my program wit dataset i downloaded from waterloo site and my program gave correct output for that dataset... but i got WA in acm.. can anyone plz help me to find out the glitch......

here is my code:




[cpp]





/*@BEGIN_OF_SOURCE_CODE*/




#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>


long half, sum, sum1, total;
int used[22], used1[22], coin[22], temp2[22],temp1[22], N, flag, k, n;
void divncon(int now, int prev);
void divncon1(int now, int prev);
int sort_function( const void *a, const void *b);

void main()
{
int i, j, m;

// freopen("C:\\c.out", "r", stdin);
// freopen("C:\\g.out", "w+", stdout);

scanf("%d", &m);

for(i = 0; i < m; i++)
{
scanf("%d", &N);

memset(coin, 0, sizeof(coin));
memset(used, 0, sizeof(used));
sum = total = 0;

for(j = 0; j < N; j++)
{
scanf("%d", &coin[j]);
total += coin[j];
}

if(total%4)
printf("no\n");
else
{
qsort(coin, N, sizeof(coin[0]), sort_function);
half = total/2;
flag = 0;
divncon(0, 0);

if(flag == 1)
printf("yes\n");
else
printf("no\n");
}
}
}



void divncon(int now, int prev)
{
int i;

if(flag)
return;

if(now == N)
{
// prev = 0;
return;
}

if(sum == half)
{
memset(temp1, 0, sizeof(temp1));
memset(temp2, 0, sizeof(temp2));

k = n = 0;
for(i = 0; i < N; i++)
if(!used)
{
temp2[k] = coin;
k++;
}

else
{
temp1[n] = coin;
n++;
}
memset(used1, 0, sizeof(used1));
sum1 = 0;
divncon1(0, 0);

if(flag)
{
flag = 0;
memcpy(temp1, temp2, sizeof(temp2));
memset(used1, 0, sizeof(used1));

n = k;
sum1 = 0;
divncon1(0, 0);

if(flag)
return;
}
}


if(sum > half)
return;

for(i = N-1; i >= 0; i--)
{
if(now && i >= prev)
continue;

used = 1;
sum += coin;
prev = i;

divncon(now+1, prev);
used = 0;
if(flag)
return;
sum -= coin;
if(sum+coin > half)
i = 0;
}
}




void divncon1(int now, int prev)
{
int i;

if(flag)
return;

if(now == n)
{
// prev = 0;
return;
}

if(sum1 == half/2)
{
flag = 1;
return;
}

if(sum1 > half/2)
return;

for(i = n-1; i >= 0; i--)
{

if(now && i >= prev)
continue;

used1 = 1;
sum1 += temp1;
prev = i;

divncon1(now+1, prev);
used1[i] = 0;

if(flag)
return;
sum1 -= temp1[i];

if(sum1+temp1[i] > half/2)
i = 0;
}
}



int sort_function( const void *a, const void *b)
{
return( strcmp((char *)a,(char *)b) );
}


/*@END_OF_SOURCE_CODE*/

[/cpp]

[rakeb]

I can't understand this problem . can anybody help me plz?

[Bistromath]

Hi,

i think i have used all tips discussed in this forum for problem 10364 but judge replies TLE.
i sort the sticks by length and treat equal lengths only once.

Can someone help me improve this code ?

Thanks for help

[cpp]

#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <functional>


int Sticks[20] ;

struct Sol
{
Sol()
{
for ( int i = 0 ; i < 4 ; ++i )
m_L = 0 ;

}
Sol( const Sol& s )
{
memcpy( m_L, s.m_L, sizeof( m_L ) ) ;
}
void Sort()
{
std::sort( m_L, m_L+4, std::greater<int>() ) ;
}
int m_L[4] ;
} ;

int n, length ;
bool Solve( int idx, const Sol& s )
{
int i ;

if ( idx == n )
{
for ( i = 0 ; i < 4 ; ++i )
if ( s.m_L != length )
return false ;
return true ;
}

Sol s1(s) ;
s1.Sort() ;

int nextStick = Sticks[idx] ;

int last = s1.m_L[0] ;
s1.m_L[0] += nextStick ;
if ( s1.m_L[0] <= length && Solve( idx+1, s1 ) )
return true ;
s1.m_L[0] -= nextStick ;

if ( s1.m_L[1] != last )
{
last = s1.m_L[1] ;
s1.m_L[1] += nextStick ;
if ( s1.m_L[1] <= length && Solve( idx+1, s1 ) )
return true ;
s1.m_L[1] -= nextStick ;
}

if ( s1.m_L[2] != last )
{
last = s1.m_L[2] ;
s1.m_L[2] += nextStick ;
if ( s1.m_L[2] <= length && Solve( idx+1, s1 ) )
return true ;
s1.m_L[2] -= nextStick ;
}

if ( s1.m_L[3] != last )
{
s1.m_L[3] += nextStick ;
if ( s1.m_L[3] <= length && Solve( idx+1, s1 ) )
return true ;
}
return false ;
}

int main()
{
int testCase ;
scanf("%d", &testCase ) ;
while ( testCase-->0)
{
length = 0 ;
scanf("%d", &n ) ;
for ( int i = 0 ; i < n ; ++i )
{
int l ;
scanf("%d", &l ) ;
Sticks = l ;
length+= l ;
}

if ( n < 4 || length%4!=0 )
printf("no\n");
else
{
Sol s ;
std::sort( Sticks, Sticks+n, std::greater<int>() ) ;
length /= 4 ;
printf( Solve( 0, s ) ? "yes\n" : "no\n") ;
}
}
return 0;
}

[/cpp]

[SoLtRiX]

i understood the problem. i just can

[SoLtRiX]

What should be the output to this input?
7
2 2 2
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5
6 1 1 1 1 1 3
9 1 7 2 2 6 3 5 4 2
5 0 0 0 0 0

My output is:
no
yes
no
yes
no
yes
yes


Were is it wrong? there are any special cases?
Thanks

[turuthok]

They are correct.

-turuthok-

[SoLtRiX]

yeah, i know that the output is the correct one. but i'm asking if there are any special case that i've to test, because i don't know why i'm getting WA.

i don't like to post code, but i can't really understand what's wrong, so i'll post it in order to you check and try to tell me whats wrong. (And if someone copy and paste my code, at least that person has to do the correction first, since it gets WA just like it 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]=0;
return tentar(ind-1,parc-val[ind]);
}
}



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]){
if (tentar(j-1,parcela-val[j])>=0)
{
livre[j]=0;
total+=parcela;
}
else break;}
j--;
}
if (cum && total<num) cout<<"no"<<endl;
else cout << "yes"<<endl;
}
}
}


[/cpp]
my algorithm is something like:
1. read the values and insert it into an ordered array
2. starts by the highest values, trying to complete it (it already knows what's the value of each side)
3. do step 2 while there are free sticks

Note: function "tentar" try to find the stick(s) that left to complete the square size.

Thanks for any help