gerrymandering_ex
sheep
Subtask 1: N < 5000
do dp
Motivation for full solution
Observe that when K is very big, the optimal solution exists to simply extract out all the ‘1’s
When there is a continuous chunk of ‘0’s, we can just use 1 segment to extract them, discarding them entirely
When there is a continuous chunk of ‘1’s, we spend as many segments as there are ‘1’s to break them up into as many pieces as possible
Idea
Let us call a dead chunk segments of ‘0’>=no. of ’1’ e.g. [0,001,01010]
Let us call an alive chunk anything else. So [1,101,11001] are all alive chunks.
For any given binary string, we spend some segments removing dead chunks and the remaining segments to extract the ‘1’s.
Suppose we spend x segments to remove dead chunks. Then the answer will be
MIN(k-x, sum of alive chunks)
We want to balance this value to maximise the answer
How to reduce the number of dead chunks?
When we reduce the number of dead chunks, it costs us some ‘1’s to do it.
2 possibilities: 111000111 or 000111000, both are same, decreases number of ‘1’s by 3 but also reduces dead segments by 1.
We want to greedily pick the shortest segment to merge
Similar to feast, the decrease in ‘1’s in convex. The more dead chunks we reduce, the higher the costs of each removal. Hence, k-x is a increasing linear function, no. of alive segments is an decreasing convex function. Their intersection point will be the optimal answer. Since the intersection point might not be an integer, just take the point directly before and after the intersection point.
How to reduce the number of dead chunks?
Please be careful: At the ends, something like 100001, even though the segment of 1 is the smallest, merging it with the 0 makes no difference on the number of dead segments.
Contrastingly, with 011110, merging the 0 does make a difference
Implementation
We can use a similar method as feast.
First, turn the ‘0’s to ‘-1’.
Our answer is min(k-dead, sum of length of array).
Implementation
Say we have A dead segments at the beginning, where A is the number of runs of ‘0’s
Initially, consider the case where we remove all A dead segments. That leaves us with few segments left to extract alive segments, unfortunately.
Now, we want to only remove A-1 dead segments. We will have to merge some segments to reduce the number of dead segments. Refer to previous slides for how. Our number of alive segments will decrease, but we will have more segments to extract them.
Repeat for A-2,A-3,A-4….until the intersection point is reached.
Implementation
Refer to feast/joi_candies on how to implement such a greedy solution
Something something use sets
Note that you must use greedy, cannot use monge.
This is because you need all cases from [1..A] and check if they intersect
Well technically can monge + bsta for 2e5 but not 1e7 lol
Monge will be Nlog^2N
Subtask 3: N<10^7
Linearise the greedy solution.
Instead of using set/pq, use linked lists in the form of an array, use array+pointer to keep track of absolute min element