Editorial for CCC '15 J5 - π-day


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: xiaowuc1

To rephrase the problem directly, we want to count the number of lists of k sorted positive integers that sum to exactly n.

To get 5 out of 15 marks, we can implement a recursive solution that attempts to enumerate all of these lists directly. Add in the elements one at a time, making sure that we only add elements that are greater than or equal to the last element we added in.

To get 10 out of 15 marks, we can improve this recursion by short-circuiting a list that can never be extended to meet the sum requirements. For example, if n=10 and k=5, then the smallest element must be less than or equal to 2, so we never need to consider any list where the smallest element is 3 or larger.

To get full marks, we can memoize the above state - the state is the number of elements we have left to insert, the sum left that must be accounted for, and the minimum value every element in the list must take on. This solution looks like it has complexity O(n^3k), but in practice a lot of the states are not reachable since the minimum value for every element must be at most \frac{n}{k}.

Finally, there is a more efficient solution that has complexity O(nk) and has a simpler implementation than the above solution.

Let us define f(n, k) to be the number of lists of k sorted positive integers that sum to exactly n.

If we consider the structure of any list of k sorted positive integers, we can partition the lists into those which contain a 1 and those which don't. We can biject the lists that contain a 1 to every list of k-1 sorted positive integers that sum to n-1, since we can just add/remove a 1 as necessary. We can biject the lists that do not contain a 1 to every list of k sorted positive integers that sum to n-k, since we can increase/decrease every integer in the list by 1 as necessary.

There are O(nk) possible states here and O(1) transitions for each state, for a final complexity of O(nk).


Comments


  • 0
    JohnstonLiu  commented on Feb. 11, 2020, 10:14 p.m.

    What does he mean by biject?


  • -59
    Jeffmagma  commented on Feb. 18, 2017, 10:46 a.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


  • -25
    Osukaa  commented on Jan. 25, 2016, 1:55 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.