10164 - Number Game

[Red Scorpion]

Hi,

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 ?

regards,
Red Scorpion

[Red Scorpion]

Please Help me ......

[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!!!!!!!

[Red Scorpion]

Oh, Finally i got it.

Thanks.

[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

[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?

[titid_gede]

never mind... got AC now... thank you

[I LIKE GN]

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??

[I LIKE GN]

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.

[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?

[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..

[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?

[TISARKER]

I used DP for this problem.
But getting TLE
Can any one tell me why am i getting TLE?
Either check my code or give me prunning idea please

Code: Select all

#include<stdio.h>
//#include<math.h>
//#include<string.h>
#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;
for(k=0;k<Total;k++)
	{
	i=val+sum[k]; i%=N; j=item[k]+1; if(j>N)continue;
	if(status[i][j]==t)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;
for(i=0;((status[0][N]<t)&&(i<n));i++)memo(x[i],N);
}

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);
if(sum<0)sum+=N;
dispaly(sum,n-1,N);
printf(" %d",val);
}

void main()
{
type n,N;
//clrscr();
//freopen("E:\\input.cpp","r",stdin);
//freopen("E:\\myput.cpp","w",stdout);
while(scanf("%d",&N)==1)
	{
	if(N==0)break; n=2*N-1; input(n,N);
	if(status[0][N]<t)printf("No\n");
	else { printf("Yes\n"); dispaly(0,N,N); }
	printf("\n"); t++;
	}

[serur]

Hi Mr. ALU !

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!

[minskcity]

Could anybody explain me why backtracking can possibly work for this problem?