Practice

Contest

Simple

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

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

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

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.

http://www.codechef.com/viewsolution/1833727

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

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

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

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

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