APIO 2016 Boats vs Topcoder SRM 728 Medium

Revision en1, by ricardogg, 2019-07-17 13:43:30

I was trying to solve this problem from APIO 2016 (link here) and I found that it is very similar to the second problem on Topcoder SRM 728 Medium (link here)

Namely, in the topcoder we only want to count the valid sequences of length $$$N$$$, but for the APIO version we want to count all valid sequences of length from $$$1$$$ to $$$N$$$ instead of just the whole array.

I have read the tutorial for the Topcoder version and I understand how it works, however I cannot understand how to make this DP solution work for each subset of the array instead of working for the whole array.

Here is link for the tutorial for the Topcoder problem

Tags apio 2016, apio, topcoder, help needed

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ricardogg 2019-07-17 13:43:30 877 Initial revision (published)