What I did right

1. I recognize that to advance to round 2, I have to solve B-large

2. When seeing a cycle, I realize that I should add the first item in the list to the end of list again, so that all segments are covered

3. I see the greedy insights

What I did wrong

I was not able to prove the greedy insights!!!

Proof

There are 3 types of intervals, a C-J interval, a J-J interval, and C-C interval. Note that our target function is the sum of switches introduced in each intervals.

Obviously, for each C-J interval, we increase the final answer by one

For each J-J interval, we don’t have to increase final answer at all,if we can plug in the gap with the same interval when we have enough J time left. Otherwise, we will have to increase the number of swtiches by 2. Similar argument applies to C-C interval.

Therefore, our greedy solution can give the best value in each category at the SAME time (This is what I couldn’t convince myself!!!) => our overall solution is optimal.

Proof: When we have filled maximum number of J-J interval, but still some J-J interval there. Since each miunte is covered, we know C-C interval doesn’t contribute any to the final result, and we have miniized J-J’s contributions

When we have filled all J-J interval, with more Js remaining, it is the exactly same case as above, except

Now in retrospect, for greedy problems during contest, I should probably go directly for solution instead of spending all time trying to prove it.