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

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

Post by CodeMaker » Sun Apr 03, 2005 7:40 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:

Post by midra » Mon Apr 04, 2005 1:14 am

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 » Mon Apr 04, 2005 7:11 am

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

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

10364

Post by Yu Fan » Mon May 02, 2005 1:08 am

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!

User avatar
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 » Tue May 24, 2005 4:51 pm

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


User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Tue May 24, 2005 7:25 pm

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

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

Post by mohiul alam prince » Thu May 26, 2005 11:25 am

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

MAP

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

10364 - why WA ?

Post by Spykaj » Fri Jun 30, 2006 5:45 pm

#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 » Fri Jun 30, 2006 11:04 pm

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 » Fri Dec 01, 2006 2:38 pm

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 » Sat Jan 27, 2007 2:40 pm

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 » Sat Oct 13, 2007 6:22 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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Oct 13, 2007 10:29 am

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

User avatar
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 » Thu Mar 20, 2008 12:53 pm

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;

}

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu Mar 20, 2008 7:05 pm

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)”