Ducks in a Row

This problem gives us series of ducks and geese, gives us the operation of "flipping" a range, where ducks become geese and vice versa, and asks the minimum number of operations until we have at least k runs of n ducks.

The limit is 2000 everything.

We can see at first that any solution will be less than 2000 operations, which would allow us to flip every animal. We can also check whether it is impossible by checking the length, which must be at least k*n + k-1. We can also make the assertion that any given duck will only be flipped once. If it were flipped twice, there is an equivalent set of operations that does not flip it.

If it is possible, it becomes challenging when we have "play" in the length of the string, as then we don't necessarily know where the runs should go. The first thought in such a case is DP.

The "standard" way of doing such a DP would be for the dp array to store the "optimal" value, and then the dimensions of the state would be all the things we need to guarantee an independent sub problem.

In this case, the value we're trying to optimize is number of wand uses. Figuring out the "state" is a bit trickier.

1. We can take an educated guess that position in the string is one of the dimensions. It almost always is. (2000)
2. Given that the contiguous lengths which need to be flipped is what we're optimizing, we need to know whether we flipped the last animal or not (2)
3. We need to know how many runs of correct length we've seen already (2000)
4. we need to know how long the current run we've seen is (2000)

This yields the recurrence relation: Our choice is to either flip this or not flip the element at the selected position (knapsack!). This yields eight cases, indicating our current animal, whether we flipped the previous animal, and whether we choose to flip this one

1. on a duck, didn't flip previous, don't flip this one: add 1 to the current run and indicate we didn't flip when we recurse
2. on a duck, didn't flip previous, flip: end current run (incrementing correct length runs if long enough), indicate we flip when we recurse. add one to total wand uses
3. on a duck, did flip previous, don't flip: same as (1)
4. on a duck, did flip previous, flip: same as (2), but don't add to total wand uses
5. on a goose, didn't flip previous, don't flip: end current run, recurse
6. on a goose, didn't flip previous, flip: add 1 to current run, indicate flip when we recurse and add 1 to wand uses
7. on a goose, flip previous, don't flip: end current run
8. on a goose, flip previous, flip: add 1 to current run

Obviously we need slight special case handling at beginning and end. We then check for all elements for the full length string that have at least the correct number of runs to see what the minimum wand usages is (be sure to account for ongoing runs that are long enough!).

The runtime looks big (2000^3*8), but we can do a constant time reduction....noting that the total sum of runs we've seen and current length of the ongoing run is severely limited. First, the number of runs we've seen is limited to current index/2. The values that the length of the current run is limited by the current index in the string and the number of runs we've seen. Namely, length < current index - num runs * 2. This is BORDERLINE fast enough (650 million), not including the 8 cases. Actually, it's fast enough that it's what one of the judge's solutions uses. If that doesn't satisfy you, we can do better.

We noticed earlier that this solution is a knapsack, because we're including/not including at each step. We can use the typical knapsack trick of dimension swapping. In this case, we attempt to MAXIMIZE the runs we see, and include the number of wand uses it takes to get that maximum in the dimension. This gives us:

1. We can take an educated guess that position in the string is one of the dimensions. It almost always is. (2000)
2. Given that the contiguous lengths which need to be flipped is what we're optimizing, we need to know whether we flipped the last animal or not (2)
3. how many want uses we've done (2000)

Then our state includes BOTH the number of runs we've seen AND the length of the current run. So at each element, we make the same decisions we did before, but we recurse on wand uses and store the run data. This brings up a problem. Since what we're storing in the array encompasses BOTH the number of runs and the length of them, how do we decide whether one is better than another? We can do this greedily.

1. if one has more complete runs of the right length than the other, it's better
2. if either is longer than the requisite length to make a run (next time we make a goose), then pick the other one
   • if they both are long enough, it doesn't matter
3. if they are BOTH too short, take the longer one, since we're closer to completion

This gets our runtime down to 2000^2 * 8, which is easily fast enough.