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.

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 \mathcal 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 \mathcal 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 \mathcal O(nk) possible states here and \mathcal O(1) transitions for each state, for a final complexity of \mathcal O(nk).

Comments


  • 0
    Ong_coc  commented on Nov. 2, 2022, 1:03 a.m.

    it is to dificult to understand.Any one can explain how to build up this code?


  • 4
    DynamicSquid  commented on Jan. 30, 2021, 11:55 p.m.

    I'm having a little trouble memoizing my solution. I keep getting WA when I do it. What am I doing wrong?


    • 2
      AustinBray05  commented on Dec. 13, 2021, 11:34 p.m.

      Your solution likely does not include all relevant factors in the memoization, I had the same problem and it was for this reason.


  • 3
    JohnstonLiu  commented on Feb. 12, 2020, 3:14 a.m.

    What does he mean by biject?


  • -133
    Jeffmagma  commented on Feb. 18, 2017, 3:46 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.