Editorial for COCI '09 Contest 4 #5 Kaboom


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.

The best way to approach this task is using dynamic programming. We ask ourselves the following question: How many ways are there to fold the left part of the strip into a spiral with L segments with the smallest non-folded piece having length K (K \ge A)? And then the same question for the right part. If we know how to answer that, we use the information to answer this: How many ways are there to fold the left (or right) part of the strip into a spiral with the last two non-folded pieces length D? Summing on D gives us the number of ways to fold the strip into a spiral of length L with at least two equal pieces having the last two pieces of length at least one. We can now extend this even more to: How many ways are there to fold a spiral of length L with the last two non-folded pieces equal, that doesn't explode (i.e. the smallest segment is at least A or B)? Note this number as dpA[L] and dpB[L].

Now note that there are 3 cases:

  1. left or right end of the strip is folded into a spiral of length L with the last two segments equal, and the other end is not folded at all.
  2. both ends are folded into two spirals with the last two segments equal, and there is a non-folded segment of length M between them.
  3. the strip is not folded at all.

For 1, we sum on all lengths so the total is \sum_{L=1}^N (dpA[L] + dpB[L]). For 2, we sum on the length of M so the total is \sum_{M=0}^N \sum_{L=1}^N (dpA[L] \times dpB[N-M-L]). For 3, there is only one way to to that. Sum of both these sums plus one is the solution.


Comments

There are no comments at the moment.