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.

2 Likes
#5

I understand the reason why we can spilt when endpoints are not the same, because it can be proved that in the optimal solution, two intervals are either disjoint or one completely contains another, and since there can’t exist an interval that contains the whole array, we can split it into two disjoint subproblems.

But in the case that two endpoints are the same, I’m confused that why can we spilt it into two disjoint subarrays and compute them independently?

#6

I guess that when a[l] == a[r], dp[l][r] = dp[l + 1][r], and I got ac. But I don’t know how to formally prove it.