10400 - Game Show Math

[eloha]

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.

[Adrian Kuegel]

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]

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]

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[0]);
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[0];l=cnt=0,w=0;
rec(1);
if(!w) printf("NO EXPRESSION\n");
}
return 0;
}[/code]

[Ghost77 dimen]

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?

[Adrian Kuegel]

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

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

--anupam is waiting for your reply

[Larry]

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]

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.

[hank]

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]

If you keep track of where you've been already, it should already cut down enough paths to avoid TLE..

[hank]

I got accepted ! thanks a lot!

[ttwu]

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[1]);
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[1]);
if (foundans==0) printf("NO EXPRESSION\n");
}
}
[/cpp]

[mido]

Check your if statement:

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

if res is out of range, you'll check outside the bounds of the array

[Larry]

Ya, you can fix that by putting that if statement in different order.. =)