 # 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=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.

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.