last example is wrong

It is not O(n^3): the expected number of tests for each sub-interval is 2 and thus DP is O(n^2).

What seems to be O(n^3) DP is AC as far as you remember to use "break"

Beauty of this problem in that it looks like trivial DP but can be solved using original algorithm much more effective.

There is no much sense in having one more standard DP problem. But there is much more benefit for solvers in creating absolutely new algorithm and obtaining new knowledge.

I think that current state is fault of people who 2 years ago increased ML for almost all problems not thinking of side effects. As result some problems become meaningless and silly.

I think that 2 years is not so long time, and its possible to return meaning to problems that lost it after ML increase.

I considered this idea. To create new problem with the same statement and greater limitations. But after problem statistics analysis (<10% solutions would fail that new problem) I came to conclusion that it would be better to remove AC from 10% than force 90% to submit identical solutions to two problems.

Solution is 0.
There is edge with 2 blue vertices: BGBGR[BB]GRG