LECARDS - Editorial

Problem Link:

Practice

Contest

Difficulty:

Simple

Pre-requisites:

Simple Math.

Problem:

There are N cards, each having one of 1000 colors. Little Elephant (lets abbreviate him LE) and Big Hippo (similarly, BH) play a game. LE chooses some subset of cards and then they play a game, consisting of 1000 rounds. In round k, if LE has “a” cards of color k, and BH has “b” cards of color k, then their scores are updated as follows: if a > b, then LE scores |a-b| points, else BH scores |a-b| points. Find how many subsets of the N cards result in LE winning (if he chose that subset).

Explanation:

Make a slightly modified game, in which each person in round k, scores the number of cards of that color that they have. Lets call this G2, and lets call the original G1. Now compare the scoring schemes.


	G1		G2
a>b:
LE	a-b		a
BH	0		b

b>=a:
LE	0		a
BH	b-a		b

The thing to notice is, in both cases, the point-difference is the same. Thus, after all rounds, LE had more points than BH due to G1 iff LE had more points than BH due to G2.

But in G2, the total score is simply the total number of cards chosen. This gives us,

LE wins the game iff he chooses more cards than BH ! This is independent of which colors he chooses the cards from, it only depends on the total number.

The answer is thus simply Σ i=floor(N/2)+1N NCi.

Algorithm:

Precompute (A C B modulo 1E9+7) for all A, B <= 1000. Then, given N, take the sum from i = floor(N/2)+1 to N of the precomputed values NCi.

Time Complexity: O(T * N).

One last observation. Using N choose i = N choose (N-i), we can get that the answer for odd N is 2N-1, and for even N, it is 2N-1 - 1/2 * (N choose N/2). By precomputing N choose N/2, it seems that we have a O(1) per test-case algorithm. However, in all cases, we do need to take O(N) time for Input itself, so this isn’t really an improvement.

Setter’s Solution:

Can be found here

Tester’s Solution:

Can be found here

4 Likes

Good editorial.

I figured out that the colors are immaterial (did some brute forcing on small N). I couldn’t explain why?
Once I figured this out, all I did was read N, skip the next line (read it as a string and leave it) and find the answer using precomputed values.

The author did a good job here. :slight_smile:

I am getting wrong answer using other approach(2^(N-1) - c(N, N/2)/2). please help me out
http://www.codechef.com/viewsolution/1833727

Answer to @anil09
It could be useful for others as well.
Let MOD = 1000000007,
pow[N] contains value 2^N mod MOD and
comb[N][K] is N!/K!/(N-K)! mod MOD (the value of N choose K modulo MOD).

One of the possible ways to output the answer in case of even N is

print pow[N-1] - comb[N][N/2]/2

But this is wrong. The first reason is that comb[N][N/2]/2 could be not equal to (N choose N/2) / 2 mod MOD. Indeed, since MOD is odd then due to modulo operations comb[N][N/2] could be odd number for some N though number (N choose N/2) is always even. Just output values of comb[N][N/2], say, for first 50 values of N and you will see. And then of course division by 2 leads to incorrect value. One of the correct ways is to write comb[N][N/2] * (MOD + 1LL)/2 % MOD.
Here, (MOD + 1LL)/2 is modulo inverse of 2 modulo MOD. We use 1LL to make calculations in long long to avoid overflow. One may think now, that the correct way is

res = comb[N][N/2] * (MOD + 1LL)/2 % MOD
print pow[N-1] - res

But this is still wrong. Number pow[N-1] - res could be negative. Again try first 50 values of N and you will see. One of the correct ways is to write (pow[N] + MOD - res) % MOD. Here MOD - res is positive since 0 <= res < MOD. But the sum could be >= MOD and we should take it modulo MOD to get the correct value. Therefore, the corrected version of the above code is

res = comb[N][r] * (MOD + 1LL)/2 % MOD
print (pow[N-1] + MOD - res) % MOD
3 Likes

plz help,i cannot find the mistake…
http://www.codechef.com/viewsolution/1837093

Hello,
I wanted to ask if this problem is only based on observations or is there any logic also behind them.
I had figured out that the cards were of no use any combination was giving same answer for a specific N.
I had also figured out for odd N that the answer was 2^(N-1) but was unable to do so for even N. Please tell me how to arrive at the above solution. It is just written “By observation” at two places. But how do I prove the correctness of my observation? How do I come to that observation??
thanks

i tried two ways. Both the times i got time limited exceeded.
http://www.codechef.com/viewsolution/1828931
http://www.codechef.com/viewsolution/1829470

Detailed explanation of the even case

According to the editorial for the even N = 2 * X we need to count the number of subsets that has more than X elements. Let’s iterate over the size of the subset (let it be K). So K should be from X + 1 to N inclusive. For the fixed K the number of subsets of K elements is exactly N choose K = N! / K! / (N-K)!. Hence the answer is just the sum of these values over all K:

Sum[N choose K : X+1 <= K <= N]

This is enough to solve the problem. You can now precalculate values of N choose K modulo 1000000007 for all N and K using Pascal triangle identity and then for each test case directly calculate this sum and output it modulo 1000000007.

To derive the formula 2^(N-1) − (N choose X) / 2 one should observe the following.
Since N choose K = N choose (N−K) then

S = Sum[N choose K : X+1 <= K <= N] = Sum[N choose K : 0 <= K <= X-1]

Also

Sum[N choose K : 0 <= K <= N] = 2^N

as follows by expanding binomial (1 + 1)^N.

But then S + (N choose X) + S = 2^N and the formula for S follows.

2 Likes

My Solution in python : http://www.codechef.com/viewplaintext/1787310

Same Algorithm. Just looked simpler :). Accepting color of N cards as string.

@anton_lunyov
It works now with the above change.Thanks a lot :slight_smile:

You are missing a newline at the end of the answer, when n%2 != 0

still getting wrong answer…http://www.codechef.com/viewsolution/1837553

Refer to my answer:
http://discuss.codechef.com/answer_link/6455/
Hope it helps.

Cool…thanks

Your “N is even” part is completely wrong. There is no division as such, in modular arithmetic. For calculating nCr modulo some p, check this out: http://discuss.codechef.com/questions/3869/best-known-algos-for-calculating-ncr-m