PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Nadeem Shaikh
Tester & Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
Probability and Expectation, Dynamic Programming
PROBLEM
Chef invented a new game named Quick Battle Royale. n people play the game. There are several rounds in the game. In each round, some players are eliminated. The game ends when there is only one player left. The description of a round is explained below.
Say there are x players at the start of the round. Let’s number them from 1 to x. At the start of the round each player i will choose a number p_{i} (1 \le p_{i} \le x, p_{i} \ne i). Each player chooses his number equiprobably randomly.
The game within a round process goes like this: for each i from 1 to x in order:
-
if the player i is still in the game, the player p_i is eliminated from the game immediately.
-
if the player i was eliminated from the game, nothing happens.
You have to find the expected number of rounds the game will last modulo (10^9 + 7). It can be shown that the expected number of rounds can be written as \frac{p}{q}.
You have to print p \cdot q^{-1} \bmod (10^9 + 7) where q^{-1} is the modular multiplicative inverse of q modulo (10^9 + 7).
QUICK EXPLANATION
We can represent the state of the game by tuple (N, P, Q) where N is the number of players at the start of the round, P is the number of alive players who already played their turns, and Q is the number of alive people yet to play their turn.
While some rounds have Q > 0, we can pick the first alive player, and consider three possibilities of that person killing an already dead person, killing an alive person who has played its turn, or killing an alive person yet to play its turn. Multiplying by appropriate probabilities and the expected number of turns in each case. The final answer is represented by tuple (N, 0, N)
EXPLANATION
Exponential approach
Let us consider the start of a round, with say N players.
Let’s make two sets A and B, where A denotes a set of alive people who have played their turn, and B denotes the set of alive people who are yet to play their turn. Initially, all people are in set B, and set A is empty.
We can see that within the round, we repeat the following process until the set B is empty.
We pick the first alive player x yet to play turn (smallest index in set B), eliminate the person with index equal to P_x if not already eliminated, and add x to A and remove it from B. Person P_x can either be dead or in set A or in set B.
The probabilities of each case can be calculated as
- P_x is alive and played its turn with probability \displaystyle \frac{|A|}{N-1}
- P_x is alive and yet to play its turn with probability \displaystyle \frac{|B|-1}{N-1}
- P_x is dead with probability \displaystyle \frac{(N-1)-(|A|+|B|-1)}{N-1}
When the set B becomes empty, we can check if set A contains only one element implying game over. Otherwise, we play one more round with |A| players, set A empty, and set B containing indices present in set A.
If we implement a recursive function f(N, A, B) denote the number of expected rounds needed, then we can solve this problem with exponential time complexity since we would be exploring,
Observation
We only care about the number of elements in set A and B.
Still an Exponential approach
Hence, let’s denote a function g(N, P, Q) denote the expected number of rounds needed excluding the current round, where N is the number of players at the start of a round, P denote the number of alive people who played their turn and Q denotes the number of people who are yet to play their turn.
While we have Q > 0, we pick one person x from set B and consider the following cases
-
P_x is alive and has played its turn
The probability of this happening is \displaystyle \frac{P}{N-1}. In this case, the number of expected rounds is g(N, P, Q-1), since x is added to A, P_x is removed from A and x is removed from B. -
P_x is alive and yet to play its turn
The probability of this happening is \displaystyle \frac{Q-1}{N-1} as a player cannot choose itself. In this case, the number of expected rounds is g(N, P+1, Q-2), since player x is added to set A and player x and P_x are removed from the set B -
P_x is dead
The probability of this happening is \displaystyle \frac{(N-1)-(P+Q-1)}{N-1}. The expected number of players is g(N, P+1, Q-1) since x is removed from B and added to A
Hence, we can write
\displaystyle g(N, P, Q) = \frac{P}{N-1}*g(N, P, Q-1) + \frac{Q-1}{N-1} * g(N, P+1, Q-2) + \frac{(N-1)-(P+Q-1)}{N-1} * g(N, P+1, Q-1)
Now, let’s suppose we have Q = 0. This means that all players have played their turns. Two cases arise
If we have P = 1, in which case, only one player is alive, and the game is over.
Otherwise, the number of rounds needed is 1+g(P, 0, P)
Hence, the number of needed rounds is g(N, 0, N)+1 (To count the first round, as g function was defined to exclude the current round).
Optimization
Implementing this function naively would get the time limit exceeded verdict. Since the function depends only on three parameters and there are overlapping subproblems, we can store their results in a three-dimensional array, so that we compute the answer for each tuple (N, P, Q) only once. It takes O(1) time to compute answers from values from other states.
Hence, this whole table can be computed in O(N^3) where N = 100. We can precompute this table and answer the queries in O(1) time.
Note that the solutions computing this table for each test would get TLE as their time complexity would be O(T*N^3) which is too much.
TIME COMPLEXITY
The time complexity is O(T+N^3) where N = 100
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define int long long
const int mod = 1e9+7;
int modpower(int x, int y, int p=mod)
{
int res = 1;
x = x % p;
if (y==0)return 1;
if(x==0)return 0;
while (y > 0)
{
if (y & 1)
res = (res*x) % p;
y = y>>1;
x = (x*x) % p;
}
return res;
}
int modinv(int a,int p=mod){return modpower(a,p-2,p);}
const int N = 1e2+5;
vector<vector<vector<int>>> dp(N, vector<vector<int>>(N, vector<int>(N, 0)));
vector<vector<vector<bool>>> vis(N, vector<vector<bool>>(N, vector<bool>(N, 0)));
// dp[i][j][k]
// i ppl at the start of the round,
// j ppl alive and used their power,
// k ppl alive and not used their power
int n = 100;
int doit(int i=n, int j=0, int k=n){
if(vis[i][j][k] == 0){
dp[i][j][k] = 0;
if(i == 1){
}
else if(k == 0 and j > 0){
doit(j, 0, j);
(dp[i][j][k] = (dp[j][0][j]+1)%mod)%=mod;
}
else {
if(i - j - k > 0){
doit(i, j+1, k-1);
(dp[i][j][k] += (i-j-k)*dp[i][j+1][k-1]%mod*modinv(i-1)%mod)%=mod;
}
if(j > 0){
doit(i, j, k-1);
(dp[i][j][k] += (j)*dp[i][j][k-1]%mod*modinv(i-1)%mod)%=mod;
}
if(k-1 > 0){
doit(i, j+1, k-2);
(dp[i][j][k] += (k-1)*dp[i][j+1][k-2]%mod*modinv(i-1)%mod)%=mod;
}
}
vis[i][j][k] = 1;
}
return dp[i][j][k];
}
void solve(){
cin >> n;
cout << doit(n, 0, n) << "\n";
return ;
}
main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
for(int c=1; c <= T; c++){
solve();
}
return 0;
}
Tester's Solution
import java.util.*;
import java.io.*;
class BattleRoyale{
//SOLUTION BEGIN
long MOD = (long)1e9+7;
int MAXN = 100;
long[][][] exp;
void pre() throws Exception{
exp = new long[1+MAXN][1+MAXN][1+MAXN];
for(int i = 0; i<= MAXN; i++)for(int j = 0; j<= MAXN; j++)Arrays.fill(exp[i][j], -1);
}
void solve(int TC) throws Exception{
int N = ni();
if(N == 1)pn(0);
else pn(1+calc(N, 0, N));
}
long calc(int total, int played, int toPlay){
if(total == 1)return 0;
if(toPlay == 0){
if(played == 1)return 0;
return 1+calc(played+toPlay, 0, played+toPlay);
}
if(exp[total][played][toPlay] != -1)return exp[total][played][toPlay];
//Considering the first alive person yet to play
//kills someone already dead: calc(start, played+1, toPlay-1) (total-1-(played+toPlay-1))/(total-1)
//kills someone who is alive and has played: calc(start, played, toPlay-1) played/(total-1)
//kills someone who is alive and hasn't played: calc(start, played+1, toPlay-2) (toPlay-1)/(total-1)
long val = 0;
if((total-played-toPlay) > 0)val += (total-played-toPlay) * calc(total, played+1, toPlay-1)%MOD;
if(val >= MOD)val -= MOD;
if(played > 0)val += (played) * calc(total, played, toPlay-1)%MOD;
if(val >= MOD)val -= MOD;
if((toPlay-1) > 0)val += (toPlay-1) * calc(total, played+1, toPlay-2)%MOD;
if(val >= MOD)val -= MOD;
return exp[total][played][toPlay] = val*inv(total-1)%MOD;
}
long inv(long a){
long o = 1;
for(long p = MOD-2; p > 0; p>>=1){
if((p&1) == 1)o = o*a%MOD;
a = a*a%MOD;
}
return o;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new BattleRoyale().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
