I have seen many correct submissions and most of them have directly printed the answer. I tried the brute force solution myself and it took me a whole day to go to the 12th value and i couldnt take it anymore… I think time complexity will be O(n^n) approx…am i missing something?
1 Like
Write a DP solution, where state of DP is multiset of number of received votes for every person and how many votes got person, choosen by last one in a row (like “right now 3 people got 4 votes, 2 people got 2 votes, 6 people got 1 vote, and last person gave her vote to someone with 2 votes”). This information is enough for you to calculate number of transitions in all other states, and it completely describes current state; also number of states is pretty low (because if you forget about “who got last vote” part for a while - it is something like all partitions of N into sorted sequence of addends, and not even all of them are reachable). Even with a messy implementation this solution runs in 2-3 seconds for N=34.
3 Likes
thanks for clearing this
To lebron: how the solution you described accounts for the fact that there can be no 2 neighbors with the same vote?
To alexeykasatkin: there is and how many votes got person, choosen by last one in a row part. We are interested in number of ways to move from given state to another one, right? Every move is decreasing number of people with X votes by 1 and increasing number of people with X+1 votes by 1 (it means that last person voted for somebody with X votes, and now that lucky guy have X+1). If we know that right now there are Y people with X votes - we have 2 possibilities. Either last person voted for someone with X votes, then we have Y-1 more candidates; or last person voted for some candidate with Z!=X votes, then all Y of them are good now.
My solution for 40 points was working this way, if you want to look at code.