CRDGAME2 - Editorial

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:

  1. Observe that the card with the maximum value will not be transferred in the whole game.
  2. The player having maximum number of maximum-valued cards wins the game.
  3. We can assign the cards which are not maximum to any of the players, it will not matter(2 ways).
  4. 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.
  5. Calculate the final answer by combining the above two points.

EXPLANATION:

Observe the following facts:

  1. 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.

  2. All the non-maximum valued cards are transferable.

  3. 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.

  4. 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.

  5. 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?

11 Likes

Save your time and Check out the speed solve editorial here:: https://www.youtube.com/watch?v=7TqIwgxDUgg


Subscribe for more such videos!
3 Likes

Check out Screencast Tutorial for this problem: https://www.youtube.com/watch?v=W5mrf_8lIY8&list=PLz-fHCc6WaNJa2QJq7qULBBV0YOJunq75&index=6

1 Like

Why is this wrong?

if the number of maximum card is even we take out one card and we can distribute rest of the cards in 2^(n-1) ways and now we can add one remaining maximum card to the pile which have maximum number of maximum card(1 way). so final answer is 1*2^(n-1)

Video Editorial for CRDGAME2 - https://www.youtube.com/watch?v=VDVOJNo57RQ

Simple explanation of the problem and solution, with code :

I didn’t understand how the match will end in a draw in this case

thanks for the fast editorial,
interesting problem, able to get 5points

Let’s call
maximum card = card which has maximum integer written on it
MX = frequency of maximum card
n=no of cards

Case 1:MX is odd
answer is simply 2^(n)

case2: MX is even
we take out one maximum card which will make frequency of maximum card odd (i.e. MX-1) and total cards will be n-1
we can distribute this cards in 2^(n-1) ways without any draw.
and after distributing we can add remaining one maximum card to the chef or chefu which ever one has higher number of maximum cards(i.e. in one way)

so final answer is 2^(n-1)*1

Your analysis of giving that 1 taken card to the pile having greater freq of max element is wrong.
Say for a case-
You have four cards and give 1st, 2nd, 3rd to chef and now according your analysis last card should go to chef and yes this is a valid case for no draw but if last card goes to other person, then also there’ll be no draw since the distribution is uneven.

2 Likes

Got my answer. thanks

1 Like

we have to find total possible way to end not in draw

please help me in finding the error in this code
Thanks in advance

Checkout video solution in Hindi here :

1 Like

Can someone explain to me what the bonus problem means?

Can anyone point out what is wrong with my code?

#include<bits/stdc++.h>
using namespace std;
#define Mod 1000000007
int mul(int a, int b)
{
return ((a1llb)% Mod);
}
int fact(int a)
{
int res = 1;
for (int i=2;i<=a;i++)
res = mul(res,i);
return res;
}
int power(int x,int y)
{
int res = 1;
while(y)
{
if (y&1)
res = mul(res,x);
y = y>>1;
x = mul(x,x);
}
return res;
}
int inv(int a)
{
return power(a,Mod-2);
}
int comb(int a)
{
return mul(fact(a),mul(inv(fact(a/2)),inv(fact(a/2))));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
int n,x,s = 0;
cin>>n;
map<int,int>mp;
for (int i=0;i<n;i++)
{
cin>>x;
mp[x]++;
}
map<int,int>::iterator it = mp.begin();
for (it = mp.begin(); it!= mp.end();it++)
s+=it->second;
it–;
int ans;
if (it->second%2)
ans = power(2,s);
else
{
s = s - it->second;
ans = power(2,s);
int r = ((power(2,it->second)%Mod - comb(it->second)%Mod)%Mod);
ans = mul(ans,r);
}
cout<<ans<<endl;
}
}

The problem is in line no 70. Whenever you need to calculate (A-B)%M, use (A-B+M)%M because if A<B then you will get a negative remainder.

1 Like

Same mistake in your code also. Whenever you need (A-B)%M use (A-B+M)%M.

2 Likes

In the current version of the problem, two cards at different indices are considered different. The bonus problem asks to calculate the number of distributions possible to make the game end in a non-draw when all the cards having same value are indistinguishable.