Page 1 of 3

10164 - Number Game

Posted: Thu Dec 12, 2002 7:58 am
by Red Scorpion

I have try to solve this problem with generate all the combination that possible (Recursive),
but i still get WA!

Can anyone tell me the other method ?

Red Scorpion 8)


Posted: Wed Jan 08, 2003 7:15 am
by Red Scorpion
Please Help me ......


Posted: Tue Jan 28, 2003 10:57 am
by newhh2002
would you help me about the algorithm of #10164? it might be a easy problem, but i don't know how to solve it. (my method use much memory and results in "tle" :( i wonder how those guys on the ranklist did it) thanks!!!!!!!

Posted: Wed Feb 05, 2003 11:15 am
by Red Scorpion
Oh, Finally i got it.


Posted: Wed Feb 05, 2003 11:23 am
by Red Scorpion
Hai ..

You just need to get a combination of number and print it.
I Use recurence, and get it in less then 1S.

Good Luck,
Red Scorpion

10164 - number game

Posted: Mon Aug 18, 2003 1:39 pm
by titid_gede
this problem looks easy, but i always got WA ... what is the tricky input here? if answer is Yes what we have to output, the number or the index of the number?

Posted: Mon Aug 18, 2003 1:54 pm
by titid_gede
never mind... got AC now... thank you

Posted: Mon Aug 01, 2005 5:33 pm
we to consider up to 2N-1(2*2^10-1 = 2*1024-1 = 2047) numbers
of which to choose 1000 numbers...
a terrific backtrack would get TL...
how urs is so fast!!!!!
m'i missing something??


Posted: Fri Sep 16, 2005 5:43 pm
I LIKE GN wrote: a terrific backtrack would get TL...
No "a terrific backtrack" would NEVER get TL...
but a very simple "search all possibility" recursion now solves the problem
in 0.035 sec
also it needs MEMOIZATION( and MOD operation to help MEMO...)
thanks to all of uuuuu.

Posted: Wed Mar 22, 2006 11:04 pm
by Moha
I have written a DP code for it. But I got TLE. Can anybody help me. Is there any faster algorithm that DP exists for this problem?

10164 want your help

Posted: Mon Apr 17, 2006 5:09 pm
by Wei-Ming Chen
I got WA on this problem, can someone give me some strict I/O?
Thanks very much... :-?

By the way, I don't know when "No" happened...
Can someone tell me? Or the answer is always "Yes"? Thanks..

Yes, let's discuss it!

Posted: Wed Apr 26, 2006 11:12 am
by serur
Hello fellows!

10164- "Number Game".
Has this:
N=2^k, k=1,2,3,4,5,6,7,8,9,10

some mysterious meaning? Has it something to do with bits=>binary representation of sets and so on? Has it any crucial meaning at all?

Please help

Posted: Tue May 02, 2006 9:17 pm
I used DP for this problem.
But getting TLE :evil:
Can any one tell me why am i getting TLE?
Either check my code or give me prunning idea please :(

Code: Select all

#define range 1100005
#define drange 2100
#define crange 1100
#define type int

type sum[range],item[range],Total,x[drange],track[crange][crange];

type status[crange][crange],t=1;

void memo(type val,type N)
type k,i,j,count=Total;
	i=val+sum[k]; i%=N; j=item[k]+1; if(j>N)continue;
	status[i][j]=t; track[i][j]=val; if(status[0][N]==t)return;
	sum[count]=i; item[count]=j; count++;
Total=count; i=val%N; j=1; if(status[i][j]==t)return ;
status[i][j]=t; track[i][j]=val; sum[Total]=i; item[Total]=j; Total++;

void input(type n,type N)
type i,j; for(i=0;i<n;i++)scanf("%d",&x[i]); Total=0;

void dispaly(type sum,type n,type N)
if(n==1){ printf("%d",track[sum][1]); return; }
type val; val=track[sum][n]; sum-=(val%N);
printf(" %d",val);

void main()
type n,N;
	if(N==0)break; n=2*N-1; input(n,N);
	else { printf("Yes\n"); dispaly(0,N,N); }
	printf("\n"); t++;

Posted: Sun May 07, 2006 9:11 am
by serur
Hi Mr. ALU :D !

Ignore my message above - divested of everything it turned out to be easy backtracking problem, and I was disappointed. How you can use DP - only to do mod N, eh?

Good luck!

Posted: Sat Sep 23, 2006 5:08 am
by minskcity
Could anybody explain me why backtracking can possibly work for this problem?