Problem Link:
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
