10364 - Square

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10364 - Square

Post by cyfra » Wed Sep 25, 2002 2:16 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Sep 25, 2002 2:58 pm

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

Post by Ivan Golubev » Wed Sep 25, 2002 5:03 pm

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

Post by cyfra » Thu Sep 26, 2002 3:51 pm

Thanks for help...

I got it Accepted at last..

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

Thanks for reading...

Alexandru Mosoi
New poster
Posts: 5
Joined: Wed Feb 20, 2002 2:00 am

????

Post by Alexandru Mosoi » Thu Sep 26, 2002 4:43 pm

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

Post by cyfra » Thu Sep 26, 2002 5:17 pm

Don't ask me...

I have got more than 3 sec :D

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

Post by galois_godel » Sat Sep 28, 2002 9:19 am

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:

Post by gvcormac » Sat Sep 28, 2002 4:45 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Shahid » Thu Oct 31, 2002 5:15 pm

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]

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Thu Nov 07, 2002 7:08 pm

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

Bistromath
New poster
Posts: 16
Joined: Fri Oct 11, 2002 11:03 pm
Location: France

Post by Bistromath » Wed Nov 20, 2002 4:46 pm

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

Post by SoLtRiX » Mon Apr 14, 2003 1:46 am

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

Post by SoLtRiX » Tue Apr 15, 2003 12:56 am

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:

Post by turuthok » Tue Apr 15, 2003 1:59 am

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:

Post by SoLtRiX » Wed Apr 16, 2003 12:03 am

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 :wink: )

[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

Post Reply

Return to “Volume 103 (10300-10399)”