10364 - Square

[CodeMaker]

This is a DP (Dynamic Programming) problem. Backtrack will give u nothing but TLE.

[midra]

thanks...
any idea of how to do it?
because I am really stuck on this!

[Observer]

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.

[Yu Fan]

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]

Hi
Can any help me about this code
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[25];
int Visit[25];
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]

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]

Thanks dumb dan.
I have found my mistake.Now i am tring to solve this problem.

MAP

[Spykaj]

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

int main(){

int Z,W,i,o,s,T[201],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]

Code: Select all

1
6 1 3 3 3 3 3

[Sumon]

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]

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]

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]

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.

[jainal cse du]

Please help me.I could not understand why it is WA?

Code: Select all

#include <stdio.h>



int input[25];

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]

your code fails for this input

Code: Select all

1
8
1 1 1 1 1 1 1 1