Paired Up USACO Gold

I’m looking at the official solution for the 2021 december gold problem 1, paired up.

I’m not understanding what they mean by ‘chains’. As in, for the first sample input, when i connect all the cows that can be paired up(with a semicircle because it’s in geogebra):


Doesn’t this mean all cows are in the same chain, even though they can’t all be paired up? Or am i misunderstanding?

Thanks in advance

1 Like

Yes.

1 Like

as a follow up, when we compute “ub[i]” (from the official solution), can’t we just use a pointer for this, since ub[] will always move leftwards?
and when they state 𝚍𝚙[i][j]=𝚍𝚙[i+1][j], how do we ensure cow i is paired up? (For example, say we want to leave i + 1 unpaired but i + 2 is too far away? Or, there are an even number of cows that are already paired?)

yes

adjacent cows in a chain can always be paired up