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.
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.
#define rep(i,a,b) for(long long i=a; i<b; i++)
using namespace std;
typedef long long ll;
typedef vector vll;
typedef pair<int, int> pii;
typedef unsigned long int uli;
typedef vector<vector> matrix;
const ll MOD = 1000000007;
const vll arr = {1,2,5,10};
vll sums;
ll fastExpModulo(ll x, ll y, ll m) {
if( y== 0)return 1;
else if (y == 1) return x % m;
else if ( y & 1 ) return (x % m * fastExpModulo(x % m * x % m, (y - 1) / 2, m)) % m;
else return (fastExpModulo(x % m * x % m, y / 2, m)) % m;
}
uli binomialCoefficient(uli n, uli k) {
uli res = 1;
//nCr = nCn-r
if (k > n - k)k = n - k;
for (int i = 0; i < k; i++) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
void solve() {
ll n=1,a=1,k=1,minVal=LLONG_MAX,maxVal=LLONG_MIN,ans=LLONG_MAX,b=1,c=1;
ll x,y,lx,rx,ly,ry;
lx = 0,ly=0,rx=INT_MAX,ry=INT_MAX;
cin>>n;
maxVal = 0;
c=1;
rep(i,0,n){
cin>>a;
if(a==maxVal)c++;
else if(a>maxVal){maxVal = a;c = 1;}
}
if(c&1)cout<<fastExpModulo(2,n,MOD)<<endl;
else cout<<(fastExpModulo(2,n-c,MOD)*(fastExpModulo(2,c,MOD) - binomialCoefficient(c,c/2)%MOD + MOD)%MOD)%MOD<<endl;
}
int main() {
// your code goes here
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif // ONLINE_JUDGE
int t=1;
string str;
cin >> t;
while (t) {
solve();
t--;
}
return 0;
}
Solution Url
Can someone tell me what’s wrong with this code?