10400 - Game Show Math

[hank]

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

[Larry]

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..

[SilVer DirectXer]

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

[bugzpodder]

backtracking

[sohel]

with prunning.

[anupam]

There is another topic with lots of discussion. Search it and read it. Hope it will help you.
--
Anupam

[cytmike]

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]

[Cruzer]

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

[JackDaniels]

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!

[Sedefcho]

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.

[ayon]

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

[sumantbhardvaj]

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.

[jan_holmes]

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.

[kn]

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.

Surprisingly, when I use bitmask
the runtime is much better than using bool array.

Maybe the bottleneck is about "memset()"..

[vahid sanei]

I got Accepted 12.960 with dfs method ( a 2-d Array to keep track )

Is there any faster solution to solve that ?