10164 - Number Game

[asif_rahman0]

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]

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]

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]

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]

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]

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]

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]

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]

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]

Is it yes for 1) or for 2)?

[asif_rahman0]

for both

[Biks]

I am getting RTL for 10164
But I am finding no reason for getting Runtime error
I am getting mad
Can anyone help me, Please!!!

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]

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

I get TLE. How i can improve......

Code: Select all

CUT AFTER AC

[mmonish]

>>shakil
This 2 lines causes TLE.

Code: Select all

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

Read the problem statement carefully.

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]