![:-?](./images/smilies/icon_confused.gif)
10364 - Square
Moderator: Board moderators
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.
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:](./images/smilies/icon_wink.gif)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
-
- Experienced poster
- Posts: 120
- Joined: Sat Nov 01, 2003 6:16 am
- Location: Dhaka (EWU)
10364 Square getting TLE
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.
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;
}
-
- Experienced poster
- Posts: 120
- Joined: Sat Nov 01, 2003 6:16 am
- Location: Dhaka (EWU)
10364 - why WA ?
#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
#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
![:(](./images/smilies/icon_frown.gif)
Code: Select all
1
6 1 3 3 3 3 3
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:
Thanks a lot!
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;
}
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.
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
HomePage
-
- New poster
- Posts: 23
- Joined: Thu Jul 27, 2006 2:43 pm
- Location: University of Dhaka,Bangladesh
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;
}
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
your code fails for this input
Code: Select all
1
8
1 1 1 1 1 1 1 1