Patriotic Painting 1#12864

Patriotic Painting 1 (Editorial)

Suppose that point is counted by some painter. What condition on must hold so that no matter what painters are chosen, at least one of them paints ? Suppose that painters would paint . Then, we can choose n-t painters such that none of them would paint , but in any set of n-t+1 painters there would be at least one which would paint . So, the condition is k\ge n-t+1.

So, we just need to find the min\_painted — the smallest of these numbers over all points which are painted by at least one painter, and output n - min\_painted + 1.

We can find this min\_painted by traversing the line from left to right and keeping the number of painters who would paint the current point. When we meet the end of the segment of some painter, we subtract one from this number, when we meet the start, we add one to it, and we just need to find the smallest nonzero value, that's all.

Note: It seems that many teams in the start misread the statement, thinking that we only paint integer points. Because of this, we had a weird monitor effect, where teams were scared to try this problem, even though it's one of the easiest in the set. Sad...