DEVVOTE - Editorial

PROBLEM LINK:

Practice
Contest

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:

  1. 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.
  2. 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.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

3 Likes

What is meant by partition and partition index p ?
Also please post the author and testers solutions

I am not sure why the alternate solution is correct. You reduce the problem to - “Find the number of ways of arranging ai balls of color i(i from 1 to k), in such a way that no two balls of same color are adjacent.” But doesn’t each color here represent multiple persons.

Can you please explain polynomial solution in more detail?

What is its complexity? Can someone provide a link to submission?

Meaning of partition can be found here http://en.wikipedia.org/wiki/Partition_(number_theory). When we store each partition in a map we allot a distinct integer from 1 to 99132 to each partition. That is called partition index for each partition.

@karan173 : yes, each ai represents that ai people voted to ith ranked person. For simplicity let us assume person 1 got highest votes, i.e a[1], and person 2 getting second highest votes a[2], so on till person K and all others (N - K persons) getting zero votes.
So now let all those who voted person 1 wear blue shirts, and all those who voted person 2 wear red shirts and so on till K. Now no two persons who are neighbors can wear same color shirt. So isn’t this just equivalent the AMBALLS?

Thanks, I had misinterpreted.