## 10364 - Square

Moderator: Board moderators

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm This is a DP (Dynamic Programming) problem. Backtrack will give u nothing but TLE.
Jalal : AIUB SPARKS

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:
thanks...
any idea of how to do it?
because I am really stuck on this!

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Hi,

You really can use backtracking for this problem. My old program (written about a year ago) used backtracking and got AC with < 2 sec.

Sadly I've no time to look at your code (Call me lazy~ ). You may want to visit http://plg.uwaterloo.ca/~acm00/ for help.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

### 10364

i solved it in 0.08 with but the top is 0.00 ,
and i saw someone says that its could solve with dp,
but .... how to do this?
i cant understand!

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

### 10364 Square getting TLE

Hi
I am getting TLE But in my home made data it take's very short time.
I can not realise what is my problem.
Can any body find out in my code's problem.

Code: Select all

``````#include <stdio.h>
#include <time.h>

int Table;
int Visit;
int M, Q, SquareSide, Test, Sumation;

void Dfs(int Dfs_no, int Sum ) {
int i;
if ( Sum > SquareSide || Q || Dfs_no > 3 ) return ;
if ( Sum == SquareSide ) {
if ( Dfs_no == 3 ){ Q = 1; return ;}
Dfs(Dfs_no + 1, 0 );
return ;
}
for ( i = 0; i < M; i++ )
if ( Visit[i] == 0 )
Visit[i] = 1, Dfs(Dfs_no, Sum + Table[i]), Visit[i] = 0;
}

int main () {

int i, g = 0, s= clock();
//freopen("D:\\10364in.txt", "r", stdin);
//freopen("D:\\10364out.txt", "w", stdout);
scanf("%d", &Test);
while (Test--) {
scanf("%d", &M);
Sumation = Q = g = 0;
for ( i = 0; i < M; i++ ) scanf("%d", &Table[i]), Sumation += Table[i], Visit[i] = 0;
SquareSide = Sumation/4;
if ( SquareSide * 4 != Sumation ) {printf("no\n"); continue;}
for ( i = 0; i < M; i++ ) if ( Table[i] > SquareSide ) { g = 1; break;}
if (g) {printf("no\n"); continue;}
Dfs(0, 0);
if ( Q ) printf("yes\n"); else printf("no\n");
}
//printf("%.3f\n", (clock()-s)/1000.0);
return 0;
}

``````

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
Try this test case:

input:

Code: Select all

``````1
19 3 3 3 9 9 9 10 17 17 17 18 18 18 19 19 19 20 20 20``````

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Thanks dumb dan.
I have found my mistake.Now i am tring to solve this problem.

MAP

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

### 10364 - why WA ?

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

int main(){

int Z,W,i,o,s,T,p;

scanf("%d",&Z);
while(Z--){
scanf("%d",&W);
o = 0;
for(i=0; i<W; i++){
scanf("%d",&T);
o += T;
}
if(o%4){
puts("no");
} else{
s = o/4;
p=1;
for(i=0; i<W; i++){
if(T>s){
p=0;
break;
}
}
if(p)puts("yes");
else puts("no");
}
}

return 0;

}

I think it should be good help, give me tests

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

Code: Select all

``````1
6 1 3 3 3 3 3
``````

Sumon
New poster
Posts: 17
Joined: Fri May 30, 2003 8:14 pm
Contact:
CodeMaker wrote: This is a DP (Dynamic Programming) problem. Backtrack will give u nothing but TLE.
May be you don't like backtracking or you are very good in DP. But your statement is not correct. I got ACCEPTED using backtrack and it took .008 sec.

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am
0.08 sec with backtrack? I must be missing something in mine then...

I have a backtrack solution with a lot of cropping. 1.1~ seconds...

I'd like to know how do you use dp here? I tried to but the max size of the sticks is quite massive to allow it.

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am
I'm also trying to use backtracking but I got TLE.

This is my reasoning:

Check if you have already found a solution
If not, check if you have already use all elements of the vector
If not, cycle over the elements that haven't been used
check if the element plus an accumulated total is exactly the length of the side of the square.
If it is, make recursive call, resetting the accumulated
else make recursive call adding to the accumulated

If I didn't make myself understood, the code is:

Code: Select all

``````#include <cstdio>

void makeSquare(const int vector[], const int size, const int side, const int total, const int idx, bool& possible, bool used[])
{
if(possible)
return;
else if(total>side)
return;
else if(idx==size)
{
if(total==0)
{
possible = true;
return;
}
}
else
{
for(int i=0; i<size; ++i)
{
if(!used[i])
{
used[i] = true;
int l = total+vector[i]==side ? 0 : total+vector[i];
makeSquare(vector, size, side, l, idx+1, possible, used);
used[i] = false;
}
}
}
}

int main(int argc, char** argv)
{
int n=0;
scanf("%d",&n);

for(int times=n; times>0; --times)
{
scanf("%d",&n);
int* vector = new int[n];

int sides = 0;
for(int i=0; i<n; ++i)
{
scanf("%d",&vector[i]);
sides += vector[i];
}

if(sides%4!=0)
{
printf("no\n");
}
else
{
bool* used = new bool[n];
for(int i=0; i<n; ++i)
used[i] = false;

bool possible = false;
makeSquare(vector,n,sides/4,0,0,possible,used);
printf(((possible) ? "yes\n" : "no\n"));
delete[] used;
}
delete[] vector;
}

return 0;
}``````
Thanks a lot!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
You should add some other prunings too

1. Each element has to be included in a group. So, set one element fixed and search for the rest to fill.

2. When searching maintain an order. Because the index 1, 2, 5, 3 and 1, 2, 3, 5 both are same.

Hope these help.
Ami ekhono shopno dekhi...
HomePage

jainal cse du
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm

Code: Select all

``````#include <stdio.h>

int input;

int expectedSum,count,stick;

void comb(int now, int index,int sum)

{

int i;

if(sum == expectedSum)

{

count++;

return;

}

else if(count == 4)

return;

else if(sum > expectedSum)

return;

else

{

for(i = now; i < stick;i++)

{

comb(i+1,index+1,sum+input[i]);

}

}

}

int main()

{

//freopen("in.txt","rt",stdin);

int test,i,sum,length;

scanf("%d",&test);

while(test--)

{

scanf("%d",&stick);

sum = 0;

count = 0;

for(i = 0; i < stick; i++)

{

scanf("%d",&length);

input[i] = length;

sum += length;

}

expectedSum = sum / 4;

comb(0,0,0);

if(count == 4)

printf("yes\n");

else

printf("no\n");

}

return 0;

}
``````

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
``````1