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
In topcoder problem, you compute $$$dp_i$$$ using $$$dp_{i-1}$$$. In schools, compute $$$dp_i$$$ using all previous $$$dp_j$$$ for $$$j < i$$$. That is, there are transitions from one school to any school with bigger index, not just the next one.
In topcoder problem, $$$dp_i$$$ is not computed only from $$$dp_{i-1}$$$, because the transitions are done by iterating over the number of elements that are covered in segment of type $$$j$$$ in $$$dp_{i, j}$$$. Then in the problem from APIO we are not sure that between two elements all of them will be covered, in fact we should consider each possible combination.
By $$$dp_i$$$ I mean something computed for number $$$i$$$.
The problem "count the number of ways to get from 1 to N" in topcoder version would be like that:
for(int i = 2..n) dp[i] += dp[i-1];In apio version it would be
for(int i = 2..n) for(int j = 1..i-1) dp[i] += d[j];. You should iterate over the previous used element (school).In case my trainees submissions help
About this repo