PROBLEM LINK:
Practice
Division 1 Contest
Division 2 Contest
Video Editorial
Author: Utkarsh Pandey
Tester: Suchan Park
Editorialist: Utkarsh Pandey
DIFFICULTY:
Easy
PREREQUISITES:
Observation, Elementary Combinatorics, Modulo properties
PROBLEM:
A game is played between two players, each with a pile of N \leq 10^5 cards. In each turn, both players draw a card from top of their piles. The player having higher card value wins this round, gets both cards and inserts those to the bottom of his pile. If the value of drawn cards is equal, both players insert their card at the bottom of their respective piles. For each transfer, the value of card decreases by 1 and when it becomes 0, it is discarded from the game. The player ending up without any card loses the game. If the game is a non-ending game, the player having higher sum of cards win. If even the sum of cards is equal, the match ends in draw.
Find the number of ways to distribute the cards between the players before the start of the game such that there should be a winner.
QUICK EXPLANATION:
- Observe that the card with the maximum value will not be transferred in the whole game.
- The player having maximum number of maximum-valued cards wins the game.
- We can assign the cards which are not maximum to any of the players, it will not matter(2 ways).
- Suppose the frequency of the maximum valued card is X. Observe that if X is even, there are 2^X - {X\choose 2} ways of distributing and if X is odd, there are 2^X ways of distributing the X cards.
- Calculate the final answer by combining the above two points.
EXPLANATION:
Observe the following facts:
-
The card with the maximum value will not be transferred in the whole game because there is no other card which is valued higher than this. So if we assign a maximum valued card to player A, it will belong to player A throughout the game.
-
All the non-maximum valued cards are transferable.
-
If the maximum valued card(s) belongs to only one player, after a finite number of rounds, he will be able to make the other player cardless.
-
If we assign the maximum valued cards to both players(some cards to Chef and some to Chefu), then all the non-maximum valued cards will be transferred between the players a finite number of times till their value become 0 and those are discarded from the game.
-
If we assign the maximum valued cards to both players, then at the end of the game(after a finite number of rounds), only the maximum valued cards will be left in the game and hence, the winner will be the player who has more maximum valued cards(since his sum of value of cards will be higher)
So, for the game to end in draw, the only condition is that we have to distribute the maximum valued cards equally between Chef and Chefu.
Case 1 (The maximum valued card has odd frequency):
In this case, there is no way by which we can distribute the maximum valued cards equally between the players and hence, the game will not end in a draw in any possible distribution. So our answer for this case is 2^N.
Case 2 (The maximum valued card has even frequency):
Suppose the frequency of maximum valued card is X. Now, we can give all the non-maximum valued (N - X) cards to any of the players, it doesn’t matter. (2 ways for one card and 2^{N - X} ways for all these cards).
Now out of the maximum valued X cards, we have to select at least more than half of these and at most all the cards, and assign the cards to either Chef or Chefu. The number of ways to do this can be expressed as:
2 \cdot \sum_{i = X/2 + 1}^{X} {X\choose i}
This can also be written as 2 \cdot ( ( 2^X - {X\choose X/2}) / 2) which is equal to ( 2^X - {X\choose X/2}).
So the final answer for this case will be: 2^{N - X} \cdot ( 2^X - {X\choose X/2})
View the content below in case you didn’t understand the above statement.
Click to view
Observations:
\sum_{i = 0}^{X} {X\choose i} = 2^X
Proof
From Binomial expansion, we know that
(1+y)^X = \sum_{i = 0}^{X} {X\choose i} \cdot y^i
substituting ‘y’ with 1, we get
2^X = \sum_{i = 0}^{X} {X\choose i}
{X\choose i} = {X\choose X - i}
Explanation
Number of ways of selecting i objects out of X objects is same as number of ways of not selecting other (X - i) objects.
You may also prove it by yourself.
Some more explanation
\sum_{i = X/2 + 1}^{X} {X\choose i} = \sum_{i = 0}^{X} {X\choose i} - \sum_{i = 0}^{X/2} {X\choose i}
\sum_{i = X/2 + 1}^{X} {X\choose i} = 2^X - {X\choose X/2} - \sum_{i = X/2 + 1}^{X} {X\choose i}
\sum_{i = X/2 + 1}^{X} {X\choose i} = (2^X - {X\choose X/2})/2
Note that factorials, their inverses and powers needs to be computed modulo 10^9 + 7
Time Complexity:
The time complexity is O(n) per test case.
Solutions:
Setter's Solution (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i,a,n) for(ll i=a;i<n;i++)
#define rfo(i,n,a) for(ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define M 1000000007
//Credits of binary exp and nCr in O(1):GeeksForGeeks
const int N = 100001;
using namespace std;
ll factorialNumInverse[N + 1];
ll naturalNumInverse[N + 1];
ll fact[N + 1];
void InverseofNumber(ll p)
{
naturalNumInverse[0] = naturalNumInverse[1] = 1;
for (int i = 2; i <= N; i++)
naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
}
void InverseofFactorial(ll p)
{
factorialNumInverse[0] = factorialNumInverse[1] = 1;
for (int i = 2; i <= N; i++)
factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
}
void factorial(ll p)
{
fact[0] = 1;
for (int i = 1; i <= N; i++) {
fact[i] = (fact[i - 1] * i) % p;
}
}
ll nCr(ll N, ll R, ll p)
{
ll ans = ((fact[N] * factorialNumInverse[R])
% p * factorialNumInverse[N - R])
% p;
return ans;
}
long long binpow(long long a, long long b) {
a %= M;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % M;
a = a * a % M;
b >>= 1;
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t,n,i,j;
// freopen("inp3.in", "rb", stdin);
// freopen("out3.in", "wb", stdout);
InverseofNumber(M);
InverseofFactorial(M);
factorial(M);
cin>>t;
while(t--){
cin>>n;
ll a[n],mx=0;
fo(i,0,n){
cin>>a[i];
mx=max(mx,a[i]);
}
int mxCnt=0;
fo(i,0,n)
if(a[i]==mx)
mxCnt++;
ll ans=0;
if(mxCnt&1)
ans=binpow(2,n);
else{
ll even_count = (binpow(2,mxCnt)-nCr(mxCnt,mxCnt/2,M)+M)%M;
ans=(binpow(2,n-mxCnt)* even_count)%M;
}
cout<<ans<<endl;
}
}
Tester's Solution (Kotlin)
class CRDGAME2_SOLVER (val br: java.io.BufferedReader, val bw: java.io.BufferedWriter) {
var sumN = 0
val fac: LongArray
val inv: LongArray
val invfac: LongArray
init {
fac = LongArray(MAX_N+1)
inv = LongArray(MAX_N+1)
invfac = LongArray(MAX_N+1)
fac[0] = 1
fac[1] = 1
inv[1] = 1
invfac[0] = 1
invfac[1] = 1
for(n in 2..MAX_N) {
fac[n] = (fac[n-1] * n) % MOD
inv[n] = (MOD - MOD / n) * inv[MOD % n] % MOD
invfac[n] = invfac[n-1] * inv[n] % MOD
}
}
private fun comb (n: Int, r: Int) = ((fac[n] * invfac[r]) % MOD * invfac[n-r]) % MOD
fun check() {
require(sumN <= 1000000)
}
fun run() {
val N = br.readLine()!!.toInt()
require(N in 1..MAX_N)
sumN += N
val C = br.readLine()!!.split(' ').map(String::toInt)
val maxC = C.max()!!
val numMax = C.count{ it == maxC }
var ans = 0L
for(k in 0 .. numMax) {
if(k+k != numMax) {
ans += comb(numMax, k)
}
}
ans %= MOD
repeat(N - numMax) {
ans = (ans * 2) % MOD
}
bw.write("${ans}\n")
}
companion object {
const val MAX_N = 100000
const val MOD = 1000000007
}
}
fun main (args: Array<String>) {
val br = java.io.BufferedReader(java.io.InputStreamReader(System.`in`))
val bw = java.io.BufferedWriter(java.io.OutputStreamWriter(System.`out`))
val T = br.readLine()!!.toInt()
require(T in 1..200)
val solver = CRDGAME2_SOLVER(br, bw)
repeat(T) {
solver.run()
}
solver.check()
bw.flush()
require(br.readLine() == null)
}
Video Editorial
Bonus problem: What if the cards are identified by their value instead of their number in the distribution?
