Page 2 of 3
Posted: Sat Jul 05, 2003 4:49 pm
by hank
[c]if( res>32000 || res<-32000 ) return;
else if (used[n][res+32000] ) return;[/c]
Posted: Sat Jul 05, 2003 5:33 pm
by 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..
10400 math game show..TLE using DP?
Posted: Wed Jul 30, 2003 8:22 pm
by 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);
}
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
Posted: Sun Sep 21, 2003 12:14 am
by bugzpodder
backtracking
Posted: Wed Feb 25, 2004 12:00 pm
by sohel
with prunning.
Posted: Thu Feb 26, 2004 7:55 am
by anupam
There is another topic with lots of discussion. Search it and read it. Hope it will help you.
--
Anupam
Posted: Sat Jun 12, 2004 9:58 am
by cytmike
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]
10400 TLE with backtracking
Posted: Sat Feb 26, 2005 12:25 am
by 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
Hi Cruzer
Posted: Sat Apr 16, 2005 11:12 am
by 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!
Posted: Thu Jun 09, 2005 5:01 pm
by Sedefcho
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
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
during the backtracking process.
Posted: Sun Jan 01, 2006 7:51 pm
by 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");
}
}
Posted: Sat May 19, 2007 10:41 pm
by 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.
Posted: Mon Jun 18, 2007 8:02 pm
by jan_holmes
Hi, I got TLE for this code :
Is it because of using STL vector ? or is it because of wrong DP implementation ? Thx.
Posted: Mon Feb 11, 2008 5:02 pm
by kn
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()"..
Re: 10400 - Game Show Math
Posted: Sun Sep 06, 2009 8:33 pm
by 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 ?
