PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: yash_daga
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
simple
PREREQUISITES:
Modular inverse, elementary probability
PROBLEM:
Alice and Bob play a game of nim. However, they don’t move alternately: instead, on their turn, they each roll a D-sided die and the person with a higher number plays; if it’s a tie then Alice moves.
The winner is whoever removes the last stone.
Under optimal play, find the probability that Alice wins.
EXPLANATION:
The random nature of the game makes it seemingly hard to analyze, especially if you look at moves one at a time.
However, looking at things globally makes things much simpler.
Note that the only thing that really matters is the final pile, because:
- If there’s more than one pile remaining, no matter whose turn it is, and no matter what move they make, there will always be another pile remaining; meaning the game won’t be over.
- If there’s exactly one pile remaining, the player whose turn it is can simply remove all stones from that pile and win instantly.
Every move reduces the number of stones by at least one, so no matter how the game proceeds, there will be a first instant of time when there’s exactly one pile of stones remaining.
Once this state is reached, the player whose turn it is will win.
The player is decided by a die roll, completely independent of how previous rolls went.
So, all we really want to do is find the probability that Alice wins the final die roll!
This is fairly simple:
- If Alice rolls x, she wins only if Bob rolls something between 1 and x; for x winning rolls.
- So, Alice has a total of 1 + 2 + \ldots + D = \frac{D\cdot (D+1)}{2} winning rolls.
- The total number of rolls is D^2. So, the answer is simply
To divide by 2D under mod, compute the modular multiplicative inverse and multiply by that.
TIME COMPLEXITY:
\mathcal{O}(\log{MOD}) per testcase.
CODE:
Author's code (C++)
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14
//Check ans for n=1
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007ll //998244353ll
#define lld long double
#define mii map<int, int>
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=500005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
int g=__gcd(a, b);
return a/g*b;
}
int power(int a, int b, int p)
{
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int getRand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
int fact[N],inv[N];
void pre()
{
fact[0]=1;
inv[0]=1;
for(int i=1;i<N;i++)
fact[i]=(i*fact[i-1])%mod;
for(int i=1;i<N;i++)
inv[i]=power(fact[i], mod-2, mod);
}
int nCr(int n, int r, int p)
{
if(r>n || r<0)
return 0;
if(n==r)
return 1;
if (r==0)
return 1;
return (((fact[n]*inv[r]) % p )*inv[n-r])%p;
}
int32_t main()
{
IOS;
pre();
int t, inv2=power(2, mod-2, mod);
cin>>t;
while(t--)
{
int n, d;
cin>>n>>d;
for(int i=0;i<n;i++)
{
int a;
cin>>a;
}
int prob_turn=((d+1)*power((2*d), mod-2, mod))%mod;
cout<<prob_turn<<"\n";
}
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define md 1000000007
#define int long long
int modex(int a, int b){
if(b == 0){
return 1;
}
a %= md;
int temp = modex(a, b / 2);
temp *= temp;
temp %= md;
if(b % 2){
temp *= a;
temp %= md;
}
return temp;
}
int mod(int a, int b){
return ((a % md) * modex(b, md - 2)) % md;
}
int32_t main() {
int t;
cin>>t;
while(t--){
int n, d;
cin>>n>>d;
int temp;
while(n--){
cin>>temp;
}
cout<<mod(d * d + d, 2 * d * d)<<"\n";
}
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, d = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
# Only the last pile matters
# When there's one pile: Alice has a (1 + 2 + ... + D) / D^2 prob of winning
ans = d * (d + 1) // 2
ans = ans * pow(d*d, mod-2, mod)
print(ans % mod)