PROBLEM LINK
Author: Pranjal Jain
Tester: Mayank Pugalia
Editorialist: Mayank Pugalia
DIFFICULTY:
MEDIUM
PREREQUISITES:
Fair Idea about DP
PROBLEM:
There is going to be an election in Chefland between Alice and Bob. In an election, all voters stand in a queue and vote one by one. Voter at position i in the queue votes at the beginning of i-th minute.
After the results were declared, Alice got A votes and Bob got B votes. Thus, the voting happens for A+B minutes. Chef, being an statistician, decided to play with election results. He wants to calculate the duration for which Alice was ahead of Bob at the time of voting, but he does not remember the initial arrangement of voters in queue.
Help him to calculate the expected value of the duration, in minutes, if the voters are arranged randomly, that is, every arrangement is equally likely. If the answer is P/Q where P,Q are co-prime integers and Q≠0, output R such that 0≤R≤10^9+6 and R×Q≡P%(109+7).
EXPLANATION:
We have to find that after a certain arrangement of all voters, at how many instances will Alice have strictly more votes than Bob. Lets call the number of instances where Alice has more votes as X. Then we have to report the average value of X over all the permutations of the voters.
Total permutations will be (A+B)!, So a brute is out of the question!!
So we Approach DP. The DP will store the number of ways to arrange voters using past information.
the Memory and Time required here is AxB and it is given that AxB will be less that 10^7, so this is feasible solution.
Now lets define the state of the dp array and how to build it.
dp[i][j] represents the number of ways to arrange i people who voted for Alice and j people who voted for Bob.
Base condition is dp[0][0]=1
when i==0 that means only “Bob Voters” are present. so if the jth voter is also Bob voter then the number of ways to select a new Bob voter is
dp[i][j]=dp[i][j-1]x(B-(j-1)) (number of ways to select a person who yet has not voted for Bob)
Similarly when j==0
dp[i][j]=dp[i-1][j]x(A-(i-1)) (number of ways to select a person who yet has not voted for Alice)
when i>0 && j>0
now we can reach the state dp[i][j] in two ways:
First: the last added person is a Bob voter (lets denote it as ADDA)
Second: the last person added is a Alice voter (lets denote it as ADDB)
so dp[i][j]=ADDA+ADDB
ADDB = dp[i][j-1]x(b-(j-1)) (First Case)
ADDA = dp[i-1][j]x(A-(i-1)) (Second Case)
now we have to add dp[i][j] to the answer only when i>j which would mean that after after adding i+j people Alice has more votes!
But just adding dp[i][j] won’t do we still have (A+B-i-j) voters left
so we add dp[i][j]*factorial[A+B-i-j] to the answer
The factorial can be precalculated till 10^7
Also we have to use % at proper places so that answer never overflows
Finally we have to find the modular multiplicative inverse of factorial[A+B] (total number of permutations)
and then multiply it by the answer and print it!
Another corner case is that when A=0 OR B=0, We have to handle these cases separately
because it is said that AB <= 10^7 but if A=0 then even if B=10^18 AB<=10^7 holds in such case we might get a TLE so we can keep them as corner cases!
When A=0 that means Alice never will be in lead so the answer is 0
When B=0 that means Alice never will be in lead so the answer is A+B
SOLUTION:
can be found here