## 10400 - Game Show Math

Moderator: Board moderators

[c]if( res>32000 || res<-32000 ) return;
else if (used[n][res+32000] ) return;[/c]

hank
Experienced poster

Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

You can do this:
[c]if ( res > 32000 || res < -32000 || used[n][res+32000] ) return;[/c]

Because if any of the first two conditions is true, it will evaluate to true without going through the list..
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

### 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[i]);
}
scanf("%d",&need);

q[1][1]=input[1];
qto[1]=1;

for (i=2;i<=p;i++)
{
qto[i]=0;
for (j=1;j<=qto[i-1];j++)
{
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;
}
}

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
SilVer DirectXer
New poster

Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

backtracking
bugzpodder
Experienced poster

Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

with prunning.

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

There is another topic with lots of discussion. Search it and read it. Hope it will help you.
--
Anupam
"Everything should be made simple, but not always simpler"
anupam
A great helper

Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm

i got TLE even though i cut those values i visited.
Plz help!!! :cry:

[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]

cytmike
Learning poster

Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States

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

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

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
Cruzer
New poster

Posts: 11
Joined: Thu Feb 10, 2005 4:18 am

### 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!
Nothing is lost because everything is transforming.
JackDaniels
New poster

Posts: 8
Joined: Mon Aug 11, 2003 4:51 pm
Location: Suceava, Romania

Several test cases below.

Hope they will be useful !

I've used the symbol
Code: Select all
`#`

to mark the end of lines in the input and output files.

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#`

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
Code: Select all
`+  -  *  / `

during the backtracking process.

Sedefcho
A great helper

Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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.
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
ayon
Experienced poster

Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm

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.
sumantbhardvaj
New poster

Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm

Hi, I got TLE for this code :

Code: Select all
`ACed...`

Is it because of using STL vector ? or is it because of wrong DP implementation ? Thx.
jan_holmes
Experienced poster

Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore

sumantbhardvaj 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()"..
kn
New poster

Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

### 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 ?
Impossible says I`m possible

vahid sanei
Learning poster

Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

PreviousNext