PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Sergey Kulik
Editorialist: Adury Surya Kiran
DIFFICULTY:
Medium-hard
PREREQUISITES:
dynamic programming
PROBLEM:
There are N participants participating in an election and voting both. Each person will vote uniformly randomly vote to any person except to who its neighbours have voted. Finally, after the election, all the persons with highest votes are selected as presidents. You have to find expected number of presidents.
EXPLANATION:
Subtask 1
This part was simply to simulate the whole voting system. A simple brute force generating all possible valid voting processes and then counting number of presidents in each case can be done easily.
Subtask 2
Dynamic programming over state as multi-set of votes information
Let us say the people are voting one by one starting from 1 to N. Whenever i’th person is voting he will vote a person who is not voted by i-1th person. This ensures that no two neighbors vote the same person.
Let’s say after the ith person has voted his vote, there are a[0] people with 0 votes, a1 people with 1 vote, a2 people with 2 votes, so on till a[K] people with K votes and let us assume i’th person gave his vote to a person who had j - 1 votes before i’th person voted him. It can be easily proved that sum of x * a[x] for all 1 <= x <= K will be equal to i.
Now, when i + 1’th person is voting, there are two cases:
- He can vote a person with j votes, in this case he will have a[j] - 1 choices. Because he cannot vote the person who was voted by i’th person.
- He can vote a person with x votes(x != j), in this case he will have a[x] choices.
If we observe, the partition of N votes into K + 1 parts and j are the only two things that matter when i + 1th person is voting. If we see, we can find that the number of all possible partitions is very less. Sum of number of partitions of all N into any number of parts from 1 to 36 is 99132. We can generate all of them and store them in a map or we can hash the partition and then store it in a map.
So we can maintain these two things as our dp state for the voting process till i’th person. Our dp array will be a 3D array with current state as dp[i][j][p], which means, i people have voted till now, i’th person voted to a person with j - 1 votes before he voted him, the partition now has index p in the map. Initial condition will be dp[1][1][1] = N.
After all DP values are computed, we can iterate through dp[N][j][p] for all j, p and find the expected number of presidents.
Alternate Solution
Let a_1, a_2, a_k be an increasing partition of N into K different positive integers such that a_i represents number of votes received by i^{th} ranked (from lowest to highest ranked in non zero voted persons) person. For a fixed partition, we need to count number of ways of having votes leading to this partition. This problem can be equivalently stated as follows : Find the number of ways of arranging a_i balls of color i(i from 1 to k), in such a way that no two balls of same color are adjacent. Solving this part can be done by a beautiful dynamic programming which is already occurred as codechef problem AMBALLS. Note that complexity of this solution will be (number of partitions of N) * N^3.
Note that you can implement this solution and pass the entire problem online without need of precomputing answers.
Strictly Polynomial solution
Now instead of generating of partitions completely, you can merge the internal dp with another few parameters, eg. value of a_i, sum of all a_i's up to now.