## 10164 - Number Game

Moderator: Board moderators

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
I heard that it can be solved by XOR. but i dont know how???
I solved it using simple DP. I do mod sum of number by N into every step of my recur(int sum,int t) function. May be thats the main point for acceptance. Nothing tricky.
Pseudo Code:

Code: Select all

``````int recur(int sum,int t){
if(t==n) print those numbers
if(cache[sum][t]) return...........
cache[sum][t]=..........
for(.....){
if not in USED the number then
.......
if(recur((sum+num[i])%n,t+1)) return....
.......
}
return.....
}
``````
Hope you got it!

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
I did not get it . How do you check if a number is "USED"? Why is it guarateed to find an answer if you are not memoizing on the numbers that are "USED"? I mean, isn't it possible that you put "impossible" into your table just because you've got to a state (pair <sum, t>) using the numbers that you should not have used, while it might still be possible if you've chosen a different set of numbers?

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
ok. USED is a 1-dimensional boolean array which keeps the used numbers and cache is a 2-dimensional boolean array for memoization. i memo two things.
1) sum of all numbers that i have used
2) how many numbers i have taken coz i have limit for taking.
(cache returns 0 always when this combination is used. just flag with true if its used)
Finally i return 1 when

Code: Select all

``````if(t==n)
if(sum%n==0){
....print those numbers ......
return 1;
}
return 0;
``````
now should be clear.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
That does not explain why your solution is guarateed to find an answer (see my previous post).

What prevents you from marking a cashe entry as "impossible" just because you got to that state with a wrong set of numbers?

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
If i got wrong set of numbers then my program always return 0 otherwise
return 1.

Code: Select all

``````if(t==n){
if(sum%n==0) return 1......find the solution
else return 0.....not find the solution
}
``````
And i always cache[][] every step. So i think if it again got that kind of set of numbers then it return 0. Not go to further step.(mentioned it early)

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
asif_rahman0 wrote:And i always cache[][] every step. So i think if it again got that kind of set of numbers then it return 0. Not go to further step.(mentioned it early)
Let's assume that you have a set of numbers

Code: Select all

``1 3 2 2 X Y Z ...``
there are two ways of getting sum of 4 with two numbers (1 + 3 and 2 + 2), only one of which might be correct. What prevents your code from choosing 1 + 3 first and, if it does not work out, marking cache[4][2] as "impossible", while it might be still possible to get to the target number if you've chosen 2 + 2 instead?

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
According to the problem statement :

Code: Select all

``````Can you choose N of them, and add them all to   a integer S, to make that S/N is a integer? If there are many solutions, you can only find one of them.
``````
I do the following:
Input:

Code: Select all

``````4
1 2 3 4 5 6 7
``````
Then i mod all numbers by 4. So we get

Code: Select all

``````1 2 3 0 1 2 3
``````
After this by program produce the following output:

Code: Select all

``````Yes
1 2 3 6
``````
Execution Step

Code: Select all

``````Step 1: take number 1(sum=1)
Step 2: take number 2(sum=3)
Step 3: take number 3(sum=6)
Step 4: take number 0(sum=6) so return 0
Again,
Step 4: take number 1(sum=7) so (sum%N!=0) return 0
Again,
Step 4: take number 2(sum=8) so 8%4==0 return 1
Finally i got a solution for 1 2 3 6``````
When i found a VALID answer instantly i return 1 for YES. Nothing else. Any confusion still? tell me.
N.B:- cache[][] doesn't return any value just keep 1 for every step.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
I don't have problem understanding what your algorithm/code is. I don't understand why it works correctly.

1) Do you think your algorithm would still work for the problem: given N numbers, choose K of them such that their sum is divisible by M? (N, K and M are not related).

2) Are you using the fact that M == K and N = M*2 - 1 in the actual problem statement?

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
minskcity wrote: 1) Do you think your algorithm would still work for the problem: given N numbers, choose K of them such that their sum is divisible by M? (N, K and M are not related).

2) Are you using the fact that M == K and N = M*2 - 1 in the actual problem statement?
YES

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Is it yes for 1) or for 2)?

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
for both

Biks
New poster
Posts: 6
Joined: Sat Jun 03, 2006 12:55 pm

### 10164 RTE , help please

I am getting RTL for 10164
But I am finding no reason for getting Runtime error

I am here sending my code

Code: Select all

``````#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define sz 3000

long num[sz];
bool finished;
void subset(long a[],long k,long n,long N);
void con_candidate(long a[],long k,long c[],long n,long *ncan);

void main()
{
long tot,i,a[sz],N;
while(scanf("%ld",&N)==1 && N)
{
tot = 2*N - 1;

memset(num,0,sizeof(num));
memset(a,0,sizeof(a));
for(i=1;i<=tot;i++)scanf("%ld",&num[i]);

for(i=0;i<sz-1;i++)a[i]=1;

finished = false;
subset(a,0,tot,N);
if(finished == false)printf("No\n");
}
}

void subset(long a[],long k,long n,long N)
{
long i,j,ncan,c[sz];
long sum;

if(k==n)return;
if(k>N)	return;
if(k==N)
{
sum = 0;
for(i=1;i<=k;i++)
{
sum+=num[a[i]];
}
if(sum%N==0)
{
printf("Yes\n");
for(i=1;i<k;i++)printf("%ld ",num[a[i]]);
printf("%ld\n",num[a[k]]);
finished = true;
return;
}
}
else
{
k++;
con_candidate(a,k,c,n,&ncan);
for(j=0;j<ncan;j++)
{
a[k] = c[j];
subset(a,k,n,N);
if(finished == true)return;
}
}
}

void con_candidate(long a[],long k,long c[],long n,long *ncan)
{
long i;
*ncan = 0;

if(k==1)
{
for(i=1;i<=n;i++)
c[(*ncan)++]=i;

}
else
{
for(i = a[k-1]+1;i<=n;i++)c[(*ncan)++]=i;
}

}
``````

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST
>>Biks

U used long c[sz] in subset function i think it's gives u RE. When the depth of recursion is more it caused stack overflow.

Better try to avoid storing the next availables just check if the current number is already used or not. A simple bool array.

Hope it helps.

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Contact:
I get TLE. How i can improve......

Code: Select all

``````CUT AFTER AC
``````
Last edited by shakil on Mon Jul 09, 2007 8:23 am, edited 1 time in total.
SHAKIL

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST
>>shakil
This 2 lines causes TLE.

Code: Select all

``````bool sa[1009][1009];
long yes,n,x[2009],temp[2009];``````

Code: Select all

``N=2^k, k=1,2,3,4,5,6,7,8,9,10``
ur array size is small. resize the array & get AC.

Hope this helps.
[/code]