## 10364 - Square

Moderator: Board moderators

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### 10364 - Square

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 ??

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Thanks for help...

I got it Accepted at last..

it is not such a good time as 0.00 but it is Accepted Alexandru Mosoi
New poster
Posts: 5
Joined: Wed Feb 20, 2002 2:00 am

### ????

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

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

I have got more than 3 sec ( I will have to think about more optimalizations )

galois_godel
New poster
Posts: 17
Joined: Wed Jul 17, 2002 5:00 pm

### 10364(I can understand this problem.who can help me??)

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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
The sticks have no width. You are to
form a square (that is, an equilateral
and equiangular 4-sided polygon)..

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Contact:
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, used1, coin, temp2,temp1, 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), 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
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France
I can't understand this problem . can anybody help me plz?

Bistromath
New poster
Posts: 16
Joined: Fri Oct 11, 2002 11:03 pm
Location: France
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 ;

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 ;
} ;

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 ;
s1.m_L += nextStick ;
if ( s1.m_L <= length && Solve( idx+1, s1 ) )
return true ;
s1.m_L -= nextStick ;

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

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

if ( s1.m_L != last )
{
s1.m_L += nextStick ;
if ( s1.m_L <= 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
New poster
Posts: 10
Joined: Tue Dec 03, 2002 1:17 am
Location: Portugal
Contact:
i understood the problem. i just can

SoLtRiX
New poster
Posts: 10
Joined: Tue Dec 03, 2002 1:17 am
Location: Portugal
Contact:

### 10364 - WA

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
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
They are correct.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

SoLtRiX
New poster
Posts: 10
Joined: Tue Dec 03, 2002 1:17 am
Location: Portugal
Contact:
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;
int livre;

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