# BTTLRYL - Editorial

Tester & Editorialist: Taranpreet Singh

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
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 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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always.

2 Likes

Why are we defining the recursion in this way? How to make recursion if we want to include the current round? Can’t we just add 1 in g(N, P, Q) and return answer as g(N, 0, N)?

2 Likes

This was a great contest, but I don’t understand how this is an easy-medium problem. Who decides the difficulty of these? And does easy medium imply that it is mostly solvable by people with 2200 rating and above?

14 Likes

Can you suggest some problems like this (cf or cc any platform), I got the logic but when doing in iterative dp i couldn’t write proper loop conditions. Thanks in advance

This is probably a bit dated, but I believe it’s just a matter of poor wording in the editorial. When the editorialist says ‘without the current round’ he probably refers to the last round being redundant. To convey what I mean by this, let a state be described by number of people at the start. We could model these states and transitions as a graph so that the expected number of rounds is the number of edges (transitions) rather than vertices (states). So basically, leaving out the current round just means that when 1 person is left answer is 0, which comes off as ambiguous because we are used to referring to this as a base case, rather than explain the logic behind it.

So to conclude, the editorial, at least to my understanding, does exactly what you describe in your post. It’s also clear from the provided setter’s solution which follows the editorial line by line. If it were the other way around, editorial and solution would be contradictory. You probably figured this out on your own already, but in case some lower rated person gets stuck on this thought, there goes my view on it.