10400 - Game Show Math

All about problems in Volume 104. 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
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Sat Jul 05, 2003 4:49 pm

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

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

Post by Larry » Sat Jul 05, 2003 5:33 pm

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
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

10400 math game show..TLE using DP?

Post by SilVer DirectXer » Wed Jul 30, 2003 8:22 pm

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

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

Post by bugzpodder » Sun Sep 21, 2003 12:14 am

backtracking

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Wed Feb 25, 2004 12:00 pm

with prunning.
:wink:

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Thu Feb 26, 2004 7:55 am

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"

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Sat Jun 12, 2004 9:58 am

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
New poster
Posts: 11
Joined: Thu Feb 10, 2005 4:18 am
Location: Waterloo, ON, Canada

10400 TLE with backtracking

Post by Cruzer » Sat Feb 26, 2005 12:25 am

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
New poster
Posts: 8
Joined: Mon Aug 11, 2003 4:51 pm
Location: Suceava, Romania

Hi Cruzer

Post by JackDaniels » Sat Apr 16, 2005 11:12 am

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Thu Jun 09, 2005 5:01 pm

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
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sun Jan 01, 2006 7:51 pm

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:

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

sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:

Post by sumantbhardvaj » Sat May 19, 2007 10:41 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.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Mon Jun 18, 2007 8:02 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. :)

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

Post by kn » Mon Feb 11, 2008 5:02 pm

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.
Surprisingly, when I use bitmask
the runtime is much better than using bool array.

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

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 10400 - Game Show Math

Post by vahid sanei » Sun Sep 06, 2009 8:33 pm

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

Post Reply

Return to “Volume 104 (10400-10499)”