CRDGAME2 - Editorial

Thanks for the clarification. Seems like an easier problem than the original one.

done, Thanks a lot for pointing out the mistake…

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define MAXN 100001

ll modex(ll n, ll p) {
  ll ans = 1;
  n %= mod;
  while (p) {
    if (p & 1)
      ans = (ans * n) % mod;
    p >>= 1;
    n = (n * n) % mod;
  }
  return ans;
}

ll fact[MAXN];
void computeFact() {
  fact[0]=1;
  for (int i = 1; i < MAXN; i++) {
    fact[i]=(fact[i-1]*i)%mod;
  }
}

ll ncr(ll n, ll r) {
  if (n < r) return 0;
  ll num = fact[n], den = (fact[n - r] * fact[r]) % mod;
  ll inv = modex(den, mod - 2);
  return (num * inv) % mod;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  // cin.ignore();
  computeFact();
  int q = 1;
  cin >> q;
  while (q--) {
    int n, k = 1;
    cin >> n;
    vector<ll> v(n);
    ll maxElement=0, freq=0;
    for (int i = 0; i < n; i++) {
      cin >> v[i];
      if (v[i]>maxElement) {
        maxElement=v[i];
        freq=1;
      } else if (v[i]==maxElement) {
        freq++;
      }
    }
    ll a=modex(2,n-freq),b=modex(2,freq);
    if (!(freq&1)) b-=ncr(freq,freq/2);
    cout << (a*b)%mod<<endl;
  }
  return 0;
}

Why is my solution failing. I am only getting partially correct.

@rishabh510 Read Jay’s comment above.

I think you logic is wrong
Let we have 4 cards 6,5,5,5
Here maximum card=6
MX=1
So according to you ans=2^n=2^4=16
But its wrong if 5,5 belong to one player and 6, 5 belong to other player the match will be draw and hence here ans=10

The problem is in these lines -

ll no = ((power(2, n - count) * calculate(count) % M + M)) % M;
cout << (power(2, n) - no) % M << endl;

The value of no can be greater than power(2, n) which will result in a negative value in the answer. As, I have mentioned in the video, you need to add M to make the final value positive. This is always done after subtracting during a MODULUS operation, to get a positive value.

So, the correct code would be -

ll no = ((power(2, n - count) * calculate(count) % M + M)) % M;
cout << (power(2, n) - no + M) % M << endl;

This is how the game progresses, if 5, 5 belongs to one player and 6, 5 belongs to the other player -

First player - 5 5
Second player - 6 5

Second player wins the round.

First player - 5
Second player - 5 6 4

The round is a draw, so both player keep their cards at the bottom of their piles.

First player - 5
Second player - 6 4 5
Second player wins the round.

First player -
Second player - 4 5 6 4

First player has no card left, so second player wins the came. The game will not end in a draw.