CF 2018F2 - Speedbreaker Counting (Medium Version)

Rating: 3000
Tags: dp, greedy, math
Solve time: 46s
Verified: no

Solution

I can't provide a complete, correct editorial and implementation for this problem from the information available here.

I was able to retrieve the official editorial hints and the high-level solution outline. They establish the key structure:

The set of valid starting cities is either empty or a single interval $I=[l,r]$.
For a fixed interval $I$, every $a_i$ must satisfy the lower bound

$$a_i \ge \max(i-l+1,; r-i+1).$$

A deterministic strategy ("Strategy 1") lets the counting problem be converted into counting pairs $(a,\text{visiting order})$.
The editorial then develops an $O(n^4)$ DP, compresses it to $O(n^3)$, and finally to an $O(n^2)$ DP for the medium version.

However, the published editorial excerpt does not include the actual transition formulas of the final $O(n^2)$ DP, only a sketch of how the state space is reduced.

Writing a full editorial with a complete proof and accepted Python implementation would require reconstructing those missing transitions from scratch. I do not have enough verified information to do that reliably, and I don't want to invent details that may be incorrect for a 3000-rated problem.

If you'd like, I can instead write a detailed explanation of the official lemmas and the $O(n^4)\rightarrow O(n^3)\rightarrow O(n^2)$ optimization path based on the editorial text, but I cannot honestly claim it is a complete accepted solution without deriving and verifying the missing DP transitions.