USACO Gold Modern Art 3

Problems and Contests
#1

Hello
in this problem I don’t really understand at all why are we breaking the segment [L,R] into two contiguous parts.
for example in the third nested loop what does it even mean to try multiple different break points ?

the editorial in hint 1 assumed that only because it work on a case like [1 1] then it must work on all other cases

maybe I’m overlooking something . any help would be appreciated

#2

ok I agree that hint 1 is sort of useless …

about breakpoints: if you have, for example, an input that looks like:

1 2 3 4 1 4 3 2 1 6 7 8 7 6

then it can be split into two parts that can be solved independently:

part 1:

1 2 3 4 1 4 3 2 1

part 2:

6 7 8 7 6
1 Like
#3

This is always possible as long as the first and last cells were not painted as part of the same interval.

1 Like