10400 - Game Show Math
Moderator: Board moderators
-
- New poster
- Posts: 39
- Joined: Wed Jan 22, 2003 11:02 am
10400 math game show..TLE using DP?
hi all..I use DP to solve it.
could anyone figure out why..TLE?
[cpp]
#include <stdio.h>
int i,j,k,l,m,n,p;
int input[105];
int q[101][20000];
int parenti[101][20000];
int parentj[101][20000];
char op[101][20000];
int qcounter[101];
int qto[101];
int tempnum;
int ok;
int need;
int needtobreak;
int needi,needj;
int nowi,nowj,oi,oj;
char ans[101];
int ct;
void main(void)
{
scanf("%d",&n);
for (m=1;m<=n;m++)
{
scanf("%d",&p);
for (i=1;i<=p;i++)
{
scanf("%d",&input);
}
scanf("%d",&need);
q[1][1]=input[1];
qto[1]=1;
for (i=2;i<=p;i++)
{
qto=0;
for (j=1;j<=qto[i-1];j++)
{
tempnum=q[i-1][j]+input;
ok=1;
if (tempnum>-32000 && tempnum<32000)
{
for (k=1;k<=qto;k++)
{
if (q[k]==tempnum)
{
ok=0;
break;
}
}
if (ok==1)
{
qto++;
op[qto]='+';
q[qto]=tempnum;
parenti[i][qto[i]]=i-1;
parentj[i][qto[i]]=j;
}
needtobreak=0;
if (tempnum==need && i==p)
{
needtobreak=1;
break;
}
}
tempnum=q[i-1][j]-input[i];
ok=1;
if (tempnum>-32000 && tempnum<32000)
{
for (k=1;k<=qto[i];k++)
{
if (q[i][k]==tempnum)
{
ok=0;
break;
}
}
if (ok==1)
{
qto[i]++;
op[i][qto[i]]='-';
q[i][qto[i]]=tempnum;
parenti[i][qto[i]]=i-1;
parentj[i][qto[i]]=j;
}
needtobreak=0;
if (tempnum==need && i==p)
{
needtobreak=1;
break;
}
}
tempnum=q[i-1][j]*input[i];
ok=1;
if (tempnum>-32000 && tempnum<32000)
{
for (k=1;k<=qto[i];k++)
{
if (q[i][k]==tempnum)
{
ok=0;
break;
}
}
if (ok==1)
{
qto[i]++;
op[i][qto[i]]='*';
q[i][qto[i]]=tempnum;
parenti[i][qto[i]]=i-1;
parentj[i][qto[i]]=j;
}
needtobreak=0;
if (tempnum==need && i==p)
{
needtobreak=1;
break;
}
}
if (q[i][j] % input[i]==0)
{
tempnum=q[i-1][j]/input[i];
ok=1;
if (tempnum>-32000 && tempnum<32000)
{
for (k=1;k<=qto[i];k++)
{
if (q[i][k]==tempnum)
{
ok=0;
break;
}
}
if (ok==1)
{
qto[i]++;
op[i][qto[i]]='/';
q[i][qto[i]]=tempnum;
parenti[i][qto[i]]=i-1;
parentj[i][qto[i]]=j;
}
needtobreak=0;
if (tempnum==need && i==p)
{
needtobreak=1;
break;
}
}
}
}
if (needtobreak==1)
break;
}
if (tempnum!=need)
{
printf("NO EXPRESSION\n");
continue;
}
nowi=i;
nowj=qto[i];
ct=0;
while (1)
{
if (op[nowi][nowj]=='\0')
break;
ans[++ct]=op[nowi][nowj];
oi=nowi;
oj=nowj;
nowi=parenti[oi][oj];
nowj=parentj[oi][oj];
}
for (i=p-1;i>=1;i--)
printf("%d%c",input[p-i],ans[i]);
printf("%d=%d\n",input[p],need);
}
}
[/cpp]
thanks
could anyone figure out why..TLE?
[cpp]
#include <stdio.h>
int i,j,k,l,m,n,p;
int input[105];
int q[101][20000];
int parenti[101][20000];
int parentj[101][20000];
char op[101][20000];
int qcounter[101];
int qto[101];
int tempnum;
int ok;
int need;
int needtobreak;
int needi,needj;
int nowi,nowj,oi,oj;
char ans[101];
int ct;
void main(void)
{
scanf("%d",&n);
for (m=1;m<=n;m++)
{
scanf("%d",&p);
for (i=1;i<=p;i++)
{
scanf("%d",&input);
}
scanf("%d",&need);
q[1][1]=input[1];
qto[1]=1;
for (i=2;i<=p;i++)
{
qto=0;
for (j=1;j<=qto[i-1];j++)
{
tempnum=q[i-1][j]+input;
ok=1;
if (tempnum>-32000 && tempnum<32000)
{
for (k=1;k<=qto;k++)
{
if (q[k]==tempnum)
{
ok=0;
break;
}
}
if (ok==1)
{
qto++;
op[qto]='+';
q[qto]=tempnum;
parenti[i][qto[i]]=i-1;
parentj[i][qto[i]]=j;
}
needtobreak=0;
if (tempnum==need && i==p)
{
needtobreak=1;
break;
}
}
tempnum=q[i-1][j]-input[i];
ok=1;
if (tempnum>-32000 && tempnum<32000)
{
for (k=1;k<=qto[i];k++)
{
if (q[i][k]==tempnum)
{
ok=0;
break;
}
}
if (ok==1)
{
qto[i]++;
op[i][qto[i]]='-';
q[i][qto[i]]=tempnum;
parenti[i][qto[i]]=i-1;
parentj[i][qto[i]]=j;
}
needtobreak=0;
if (tempnum==need && i==p)
{
needtobreak=1;
break;
}
}
tempnum=q[i-1][j]*input[i];
ok=1;
if (tempnum>-32000 && tempnum<32000)
{
for (k=1;k<=qto[i];k++)
{
if (q[i][k]==tempnum)
{
ok=0;
break;
}
}
if (ok==1)
{
qto[i]++;
op[i][qto[i]]='*';
q[i][qto[i]]=tempnum;
parenti[i][qto[i]]=i-1;
parentj[i][qto[i]]=j;
}
needtobreak=0;
if (tempnum==need && i==p)
{
needtobreak=1;
break;
}
}
if (q[i][j] % input[i]==0)
{
tempnum=q[i-1][j]/input[i];
ok=1;
if (tempnum>-32000 && tempnum<32000)
{
for (k=1;k<=qto[i];k++)
{
if (q[i][k]==tempnum)
{
ok=0;
break;
}
}
if (ok==1)
{
qto[i]++;
op[i][qto[i]]='/';
q[i][qto[i]]=tempnum;
parenti[i][qto[i]]=i-1;
parentj[i][qto[i]]=j;
}
needtobreak=0;
if (tempnum==need && i==p)
{
needtobreak=1;
break;
}
}
}
}
if (needtobreak==1)
break;
}
if (tempnum!=need)
{
printf("NO EXPRESSION\n");
continue;
}
nowi=i;
nowj=qto[i];
ct=0;
while (1)
{
if (op[nowi][nowj]=='\0')
break;
ans[++ct]=op[nowi][nowj];
oi=nowi;
oj=nowj;
nowi=parenti[oi][oj];
nowj=parentj[oi][oj];
}
for (i=p-1;i>=1;i--)
printf("%d%c",input[p-i],ans[i]);
printf("%d=%d\n",input[p],need);
}
}
[/cpp]
thanks
-
- Learning poster
- Posts: 95
- Joined: Mon Apr 26, 2004 1:23 pm
- Location: Hong Kong and United States
- Contact:
i got TLE even though i cut those values i visited.
Plz help!!!
[cpp]
#include <iostream>
#include <string>
using namespace std;
int l[100],i,b;
bool sky;
bool used[102][64002]={0};
void hp(int,int,string);
string str(int h)
{
string p="";
while (h>0)
{
p=(char)(h%10+48)+p;
h/=10;
}
return p;
}
int main()
{
int p;
cin>>p;
for (int h=0;h<p;h++)
{
cin>>i;
sky=0;
for (int y=0;y<i;y++)
cin>>l[y];
cin>>b;
hp(1,l[0],str(l[0]));
if (!sky)
cout<<"NO EXPRESSION\n";
}
return 0;
}
void hp(int s,int k,string y)
{
if (used[s][k+32000])
return;
else
used[s][k+32000]=1;
if ((k==b)&&(s==i))
{
cout<<y<<'='<<k<<endl;
sky=1;
return ;
}
else if (s==i)
return;
if (k+l[s]<=32000)
hp(s+1,k+l[s],y+'+'+str(l[s]));
if (sky)
return;
if (k-l[s]>=-32000)
hp(s+1,k-l[s],y+'-'+str(l[s]));
if (sky)
return;
if ((k*l[s]<=32000)&&(k*l[s]>=-32000))
hp(s+1,k*l[s],y+'*'+str(l[s]));
if (sky)
return;
if (k%l[s]==0)
hp(s+1,k/l[s],y+'/'+str(l[s]));
} [/cpp]
Plz help!!!
[cpp]
#include <iostream>
#include <string>
using namespace std;
int l[100],i,b;
bool sky;
bool used[102][64002]={0};
void hp(int,int,string);
string str(int h)
{
string p="";
while (h>0)
{
p=(char)(h%10+48)+p;
h/=10;
}
return p;
}
int main()
{
int p;
cin>>p;
for (int h=0;h<p;h++)
{
cin>>i;
sky=0;
for (int y=0;y<i;y++)
cin>>l[y];
cin>>b;
hp(1,l[0],str(l[0]));
if (!sky)
cout<<"NO EXPRESSION\n";
}
return 0;
}
void hp(int s,int k,string y)
{
if (used[s][k+32000])
return;
else
used[s][k+32000]=1;
if ((k==b)&&(s==i))
{
cout<<y<<'='<<k<<endl;
sky=1;
return ;
}
else if (s==i)
return;
if (k+l[s]<=32000)
hp(s+1,k+l[s],y+'+'+str(l[s]));
if (sky)
return;
if (k-l[s]>=-32000)
hp(s+1,k-l[s],y+'-'+str(l[s]));
if (sky)
return;
if ((k*l[s]<=32000)&&(k*l[s]>=-32000))
hp(s+1,k*l[s],y+'*'+str(l[s]));
if (sky)
return;
if (k%l[s]==0)
hp(s+1,k/l[s],y+'/'+str(l[s]));
} [/cpp]
10400 TLE with backtracking
I'm using backtracking to solve this problem and still I get TLE. For most inputs I've tried it finishes instantly, but some inputs take over a minute. I prune the search as suggested in the problem (stop at outer limits of -32000 and 32000, stop when division results in non-integer). I even keep track of the result of the expression on the first k integers rather than calculating the whole thing over and over again. I can't think of how to improve the speed any more. I've read other posts on this problem, but I am fairly new and don't understand a few of the suggestions that were made (people referencing DFS, DP, etc..). Here is my code:
Also, one of the inputs that causes a long wait (about 1 or 2 minutes on my 1.9ghz machine) is the following:
1*2*3*4*5/6*7*8*9/10*11/12*13/14*15-16-17-18-19/20*21-22-23-24-25-26-27-28-29-30/31*32-33-34-35-36-37-38-39-40-41-42-43-44-45-46-47-48-49-50-50-49-48-47-46/45*44-43-42-41-40-39-38-37-36-35-34/33*32-31-30-29-28-27+26-25/24-23*22+21+20/19-18-17+16/15-14-13-12*11*10+9*8*7+6/5*4-359+411-7819=-31999
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUMBERS 100
#define FALSE 0
#define TRUE 1
/* Function Prototypes */
void backtrack( char a[], int k, int numbers[], int num_numbers, int target, int sum );
int is_a_solution( int k, int num_numbers );
void process_solution( char a[], int k, int numbers[], int num_numbers, int target, int sum );
void construct_candidates( char a[], int k, int numbers[], char c[], int *ncandidates, int result );
/* Globals */
int finished; /* found all solutions yet? */
main() {
int num_cases, num_numbers, target, i, j;
int numbers[MAX_NUMBERS];
char a[MAX_NUMBERS]; /* Soln vector to send to backtrack */
/* Get number of cases */
scanf("%d\n", &num_cases);
/* Loop through all cases */
for( i = 0; i < num_cases; i++ ) {
/* Get num of numbers */
scanf("%d ", &num_numbers);
/* Get all numbers */
for( j = 0; j < num_numbers; j++ ) {
scanf("%d ", &numbers[j]);
}
/* Get target number */
scanf("%d", &target);
/* Call backtrack algorithm on these numbers */
finished = FALSE;
backtrack( a, 0, numbers, num_numbers, target, numbers[0] );
if( finished == FALSE )
printf("NO EXPRESSION");
printf("\n");
}
}
/* Backtrack algo */
void backtrack( char a[], int k, int numbers[], int num_numbers, int target, int sum ) {
char c[4]; /* candidates for next position */
int ncandidates; /* next position candidate count */
int i; /* counter */
int sum2;
if( is_a_solution( k, num_numbers ) == TRUE )
process_solution( a, k, numbers, num_numbers, target, sum );
else {
k = k + 1;
construct_candidates( a, k, numbers, c, &ncandidates, sum );
for ( i = 0; i < ncandidates; i++ ) {
a[k] = c[i];
switch( c[i] ) {
case '+': sum2 = sum + numbers[k]; break;
case '-': sum2 = sum - numbers[k]; break;
case '*': sum2 = sum * numbers[k]; break;
case '/': sum2 = sum / numbers[k]; break;
}
backtrack( a, k, numbers, num_numbers, target, sum2 );
if (finished == TRUE) return; /* terminate early */
}
}
}
int is_a_solution( int k, int num_numbers ) {
if( k == num_numbers - 1 ) {
return TRUE;
}
return FALSE;
}
void process_solution( char a[], int k, int numbers[], int num_numbers, int target, int sum ) {
int i;
if( sum == target ) {
for( i = 0; i < num_numbers - 1; i++ ) {
printf("%d%c", numbers[i], a[i+1]);
}
printf("%d=%d", numbers[num_numbers-1], target);
finished = TRUE;
}
}
void construct_candidates( char a[], int k, int numbers[], char c[], int *ncandidates, int result ) {
*ncandidates = 0;
/* Check '/' */
if( result % numbers[k] == 0 ) {
c[*ncandidates] = '/';
*ncandidates = *ncandidates + 1;
}
/* Check '*' */
if( result * numbers[k] <= 32000 && result * numbers[k] >= -32000 ) {
c[*ncandidates] = '*';
*ncandidates = *ncandidates + 1;
}
/* Check '-' */
if( result - numbers[k] >= -32000 ) {
c[*ncandidates] = '-';
*ncandidates = *ncandidates + 1;
}
/* Check '+' */
if( result + numbers[k] <= 32000 ) {
c[*ncandidates] = '+';
*ncandidates = *ncandidates + 1;
}
}
1*2*3*4*5/6*7*8*9/10*11/12*13/14*15-16-17-18-19/20*21-22-23-24-25-26-27-28-29-30/31*32-33-34-35-36-37-38-39-40-41-42-43-44-45-46-47-48-49-50-50-49-48-47-46/45*44-43-42-41-40-39-38-37-36-35-34/33*32-31-30-29-28-27+26-25/24-23*22+21+20/19-18-17+16/15-14-13-12*11*10+9*8*7+6/5*4-359+411-7819=-31999
-
- New poster
- Posts: 8
- Joined: Mon Aug 11, 2003 4:51 pm
- Location: Suceava, Romania
Hi Cruzer
I've solved this problem using optimized Backtracking.
Optimization in this case refers to following: if you have passed through a partial solution once at step k in Back() (I mean a target number, not the final target number), which is in the range (-32000..32000), and the algo came back to this partial solution, you shouldn't move again forward because with this partial solution you won't reach the final target number). The partial target numbers (part of partial solutions) you can keep them in an array with 64000-1 elements for each step k in Back(), so array[k][5000]=1 means that you've passed thrugh the value 5000 at step k and you shouldn't move forward once again.
So you must have an array[100][64000-1] of elements which can have values 0 or 1.
Don't forget that for each step k in Back() you must have retain the operator you have chosen => operators[100-1] with elements which can have the values +, -, *, / .
Goodluck!
Optimization in this case refers to following: if you have passed through a partial solution once at step k in Back() (I mean a target number, not the final target number), which is in the range (-32000..32000), and the algo came back to this partial solution, you shouldn't move again forward because with this partial solution you won't reach the final target number). The partial target numbers (part of partial solutions) you can keep them in an array with 64000-1 elements for each step k in Back(), so array[k][5000]=1 means that you've passed thrugh the value 5000 at step k and you shouldn't move forward once again.
So you must have an array[100][64000-1] of elements which can have values 0 or 1.
Don't forget that for each step k in Back() you must have retain the operator you have chosen => operators[100-1] with elements which can have the values +, -, *, / .
Goodluck!
Nothing is lost because everything is transforming.
Several test cases below.
Hope they will be useful !
I've used the symbol
to mark the end of lines in the input and output files.
INPUT
OUTPUT
Note that the answers produced by different programs
may differ and still be correct. The answers depend
on the order in which you try the operations
during the backtracking process.
Hope they will be useful !
I've used the symbol
Code: Select all
#
INPUT
Code: Select all
9#
3 5 7 4 3#
2 1 1 2000#
5 12 2 5 1 2 4#
2 32000 2 16000#
2 32000 32000 1#
9 9 1 2 -10 33 3 3 2 2 23#
50 9 1 2 -10 33 3 3 2 2 23 9 1 2 -10 33 3 3 2 2 23 9 1 2 -10 33 3 3 2 2 23 9 1 2 -10 33 3 3 2 2 23 9 1 2 -10 33 3 3 2 2 23 109#
2 31998 2 32000#
3 -31997 -2 1 -32000#
OUTPUT
Code: Select all
5+7/4=3#
NO EXPRESSION#
12+2-5-1/2=4#
32000/2=16000#
32000/32000=1#
9+1+2+-10*33+3/3+2-2=23#
9+1+2+-10+33+3+3+2+2+23+9+1+2+-10+33+3+3+2+2+23+9+1+2+-10+33+3+3+2+2+23+9+1+2+-10+33+3+3+2+2+23+9+1+2--10-33-3/3+2-2+23=109#
31998+2=32000#
-31997+-2-1=-32000#
may differ and still be correct. The answers depend
on the order in which you try the operations
Code: Select all
+ - * /
-
- Experienced poster
- Posts: 161
- Joined: Tue Oct 25, 2005 8:38 pm
- Location: buet, dhaka, bangladesh
i can't understand, why still getting tle. i memorized the values after reaching any point during the backtracking process. i prune only in the common cases, if expression goes below -32000 or above 32000, if dividing by zero occurs or not divisible. is there any cases else where i should prune? the time limit in UVA is as long as 1 min, but still getting tle. all input i tried runs instantly in my computer.
![:cry:](./images/smilies/icon_cry.gif)
Code: Select all
#include <stdio.h>
char sign[] = "+-*/", stack[110];
int top, x[110], t, k, found, n;
int expression(int a, int b, char c)
{
int z;
if(c == '+')
z = a+b;
else if(c == '-')
z = a-b;
else if(c == '*')
z = a*b;
else
{
if(!b || a%b)
return -99999;
z = a/b;
}
if(z > 32000 || z < -32000)
return -99999;
return z;
}
void printStack()
{
int i;
for(i = 0; i < top; ++i)
printf("%d%c", x[i], stack[i]);
printf("%d=%d\n", x[i], t);
}
void solve(int p, int sum)
{
int i, z, val;
if(found)
return;
val = x[k];
z = expression(sum, val, sign[p]);
if(z == -99999)
return;
stack[top++] = sign[p];
if(top == n-1 && z != t)
{
--top;
return;
}
if(top == n-1 && z == t)
{
printStack();
found = 1;
return;
}
k++;
for(i = 0; sign[i]; ++i)
if(!found)
solve(i, z);
--k;
--top;
}
void main()
{
int test, tc, i;
scanf("%d", &test);
for(tc = 0; tc < test; ++tc)
{
scanf("%d", &n);
for(i = 0; i < n; ++i)
scanf("%d", &x[i]);
scanf("%d", &t);
if(n == 1)
{
if(x[0] == t)
printf("%d=%d\n", t);
else
printf("NO EXPRESSION\n");
continue;
}
k = 1;
found = top = 0;
for(i = 0; sign[i]; ++i)
if(!found)
solve(i, x[0]);
if(found == 0)
printf("NO EXPRESSION\n");
}
}
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
----------------
the world is nothing but a good program, and we are all some instances of the program
-
- New poster
- Posts: 19
- Joined: Sun Jun 18, 2006 4:07 pm
- Contact:
I am aquainted with Bit masking concept.. but here in this situation, i could not imagine how bits can be used to mark the reached position ( as mentioned by Adrian )
if we do it by an array we need a 64000 x 100 size of array.. but masking can be done only for integers upto 64.
Can anybody explain this concept to me ? so that i could improve upon my runtime in this problem.
if we do it by an array we need a 64000 x 100 size of array.. but masking can be done only for integers upto 64.
Can anybody explain this concept to me ? so that i could improve upon my runtime in this problem.
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
Hi, I got TLE for this code :
Is it because of using STL vector ? or is it because of wrong DP implementation ? Thx. ![:)](./images/smilies/icon_smile.gif)
Code: Select all
ACed...
![:)](./images/smilies/icon_smile.gif)
Surprisingly, when I use bitmasksumantbhardvaj wrote:I am aquainted with Bit masking concept.. but here in this situation, i could not imagine how bits can be used to mark the reached position ( as mentioned by Adrian )
if we do it by an array we need a 64000 x 100 size of array.. but masking can be done only for integers upto 64.
Can anybody explain this concept to me ? so that i could improve upon my runtime in this problem.
the runtime is much better than using bool array.
Maybe the bottleneck is about "memset()"..
-
- Learning poster
- Posts: 84
- Joined: Fri Jan 09, 2009 4:37 pm
- Location: IRAN
Re: 10400 - Game Show Math
I got Accepted 12.960 with dfs method ( a 2-d Array to keep track )
Is there any faster solution to solve that ?
Is there any faster solution to solve that ?
Impossible says I`m possible