Hints: Sending a Sequence Over the Network

Come up with a straightforward O(n^2) DP. It will TLE on TC12, but you should still implement it.

dp[i] is true if the prefix a[0...i] can be sent over a network.

How do you perform the transitions?

Consider the last segment inclusive of length. Let it be [j, i]. Then, you can verify if a[i] or a[j] is equal to the length of the segment, i.e i - j. If yes, you can take contribution from dp[j - 1].

How do we optimize the above DP? Notice that i-th element takes contribution from several values that are to the left of it. However, one element can only provide contribution to a single element to the right. Think about Push DP vs Pull DP.

An element can take contribution from several elements to its left, but let’s change our perspective and focus on an element a[i] and the elements that it provides contribution to. You can see that one element can only provide contribution to a single element in the forward direction. Hence, instead of searching for the elements to the left from which we can take contribution, while we are iterating over the elements from left to right, we’ll keep on providing contribution to the future elements so that we don’t have to come back.