## 10400 - Game Show Math

Moderator: Board moderators

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

### 10400 - Game Show Math

I use DFS to solve this problem and I got TLE.
Can you tell me how can I reduce the running time?
Or tell me what algorithm you guys use? Thanks.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I use dfs, but I memorize which values I reached after using the first k integers. And when I reach the values again, I don't search again.

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan
Adrian Kuegel wrote:I use dfs, but I memorize which values I reached after using the first k integers. And when I reach the values again, I don't search again.
I just do what you said. It is so wonderful! I got AC in 2 second.
Thank you very much!

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
I can't understand why i got tle in this program. I use simple recursion.Can anybody help me in details the method of solving this problem in minimum time.Thanks in advance.
[code]
#include<stdio.h>
#define N 200
long long int n,p,m,q,w,cnt,l,r,res,b[N],a[N],u;
char c[N];
void rec(int t)
{
int i,j;
if(r==res && t==n)
{
printf("%d",a);
for(i=0;i<n-1;i++)
{
printf("%c",c[i]);
printf("%lld",b[i]);
}
printf("=%lld\n",res);
w++;
cnt=1;
return;
}
if(t>=n) return ;
if(t)
for(j=0;j<4;j++)
{
u=0;
if(j==0) {r=r+a[t];c[p++]='+';u=1;}
else if(j==1) {r=r-a[t];c[p++]='-';u=1;}
else if(j==2) {r=r*a[t];c[p++]='*';u=1;}
else if(r && r>=a[t] && (!(r%a[t]))) {u=1;r=r/a[t];c[p++]='/';}
if(u)
{
b[q++]=a[t];
rec(t+1);
if(cnt) break;
c[--p]=b[--q]=0;
if(j==0) r=r-a[t];
else if(j==1) r=r+a[t];
else if(j==2) r=r/a[t];
else r=r*a[t];
}
}
}

main()
{
long long int i,z;
scanf("%lld",&m);
for(z=0;z<m;z++)
{
scanf("%lld",&n);
for(i=0;i<n;i++)
scanf("%lld",&a[i]);
scanf("%lld",&res);
p=q=0;
r=a;l=cnt=0,w=0;
rec(1);
if(!w) printf("NO EXPRESSION\n");
}
return 0;
}[/code]

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
Well , better strategy is not to do the same thing more than once.

Is it too simple ? But it really works.

I don't know what method Adrian Kuegel use to solve it.

Maybe his is more better than this.

Because his using memory is 1MB and time is much lower than 1 second. (I guess: he can achieve the goal by using bit unit)  Can you understand what I said?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
(I guess: he can achieve the goal by using bit unit)
You are right, I store only one bit to mark a reached position. A big part of the runtime is the initialization of the visited-array. By reducing the size I have less to initialize, that is making the program a lot faster.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
hello kuegel,
will u tell me the way of bfs elaborately, not by only touching the word,
i tried all the codes of me and it is similar that of yahoo. so getting tle.

--anupam is waiting for your reply  "Everything should be made simple, but not always simpler"

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I use dfs, but I memorize which values I reached after using the first k integers. And when I reach the values again, I don't search again.
Since you only need to find one solution, and the restrictions makes it possible cache all results..

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
hello,
i don't think yahoo's program catch all the solutions.
it only catch a sol then it exits from recurssion.
what will be the problem. i can't guess.
--thanks.
"Everything should be made simple, but not always simpler"

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

### 10400 Game Show Math :-)

I got TLE in this problem.
But I heard somebody use bit unit to solve problem.
Does anybody know what's the method?
Thanks!!:-)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
If you keep track of where you've been already, it should already cut down enough paths to avoid TLE..

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
I got accepted ! thanks a lot!

ttwu
New poster
Posts: 8
Joined: Tue May 13, 2003 4:31 pm
I've tried to keep track of the value, but got Runtime Error.. but I don't have any idea why?? can someone help? Thanks! [cpp]
#include<stdio.h>
#define NUMS 102
#define NUMS2 64001
int p,found[NUMS],num[NUMS],target,foundans;
char used[NUMS][NUMS2];
void dig(int n,int res)
{
int i;
if (foundans==1) return;
if (used[n][res+32000] || res>32000 || res<-32000) return;
used[n][res+32000]=1;

if (n==p)
{
if (res==target)
{
printf("%d",num);
for (i=2;i<=n;i++)
{
switch(found)
{
case 1: printf("+"); break;
case 2: printf("-"); break;
case 3: printf("*"); break;
case 4: printf("/"); break;
}
printf("%d",num);
}
printf("=%d\n",target);
foundans=1;
}
}
else
{
for (i=1;i<=4;i++)
{
found[n+1]=i;
switch (found[n+1])
{
case 1: dig (n+1,res+num[n+1]); break;
case 2: dig (n+1,res-num[n+1]); break;
case 3: dig (n+1,res*num[n+1]); break;
case 4: if (res%num[n+1]==0) dig (n+1,res/num[n+1]); break;
}

found[n+1]=0;
}
}
}

void main()
{
int i,setnum,j,k;

scanf("%d",&setnum);
for (j=1;j<=setnum;j++)
{
for (i=0;i<NUMS;i++) for (k=0;k<NUMS2;k++) used[k]=0;
foundans=0;
scanf("%d",&p);
for (i=1;i<=p;i++) scanf("%d",&num);
scanf("%d",&target);

dig (1,num);
if (foundans==0) printf("NO EXPRESSION\n");
}
}
[/cpp]

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt