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

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

10400 - Game Show Math

Post by eloha » Fri Nov 08, 2002 7:48 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Nov 08, 2002 12:38 pm

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

Post by eloha » Sat Nov 09, 2002 5:17 pm

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!

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo » Sat Nov 23, 2002 5:22 pm

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]

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Sat Nov 23, 2002 7:59 pm

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.
:P (I guess: he can achieve the goal by using bit unit)

8) 8) Can you understand what I said?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Nov 23, 2002 8:31 pm

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

Post by anupam » Wed Nov 27, 2002 11:50 am

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 :oops: :oops:
"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:

Post by Larry » Thu Nov 28, 2002 5:43 am

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:

Post by anupam » Sat Nov 30, 2002 8:12 am

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"

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

10400 Game Show Math :-)

Post by hank » Thu May 15, 2003 10:39 am

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:

Post by Larry » Thu May 15, 2003 6:18 pm

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

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

Post by hank » Fri May 16, 2003 5:30 am

I got accepted ! thanks a lot!

ttwu
New poster
Posts: 8
Joined: Tue May 13, 2003 4:31 pm

Post by ttwu » Wed Jun 18, 2003 2:30 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[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
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Fri Jul 04, 2003 8:08 pm

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
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 4:32 am

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

Post Reply

Return to “Volume 104 (10400-10499)”