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

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker »

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

Post by midra »

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

Post by 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~ :wink:). 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

Post by 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
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

10364 Square getting TLE

Post by 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
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by 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
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince »

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 ?

Post by 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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Code: Select all

1
6 1 3 3 3 3 3

Sumon
New poster
Posts: 17
Joined: Fri May 30, 2003 8:14 pm
Location: Bangladesh
Contact:

Post by Sumon »

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.
Change your view,your life will be changed.

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by 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
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage

jainal cse du
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm
Location: University of Dhaka,Bangladesh

Post by 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
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind »

your code fails for this input

Code: Select all

1
8
1 1 1 1 1 1 1 1

Post Reply

Return to “Volume 103 (10300-10399)”