I thought of this problem while discussing 343C - Время чтения with my friend. It's basically the same idea as 343C - Время чтения but over two dimensions instead of one, so I suggest you read the original problem and its solution first.

Spoiler Alert: I briefly talk about the solution to the original problem so don't continue reading if you want to try to solve it for yourself.

Also, it is very possible that the new version of the problem I came up with has already appeared in some form in a competition before. If you are aware of a such problem, Please Link It! Or if you can think of a good solution feel free to share as well! One of the main reasons I'm posting here is because I myself am having trouble coming up with a good solution to this "new" problem.

Brief description of the original problem So in the original problem, you essentially have n hard drive heads that can move left and right and m hard drive tracks that must be read located along a 1-dimensional number line. Each head can move left/right by 1 track in 1 second of time, and you are trying to find the minimum time it takes to read all the tracks that you want to read.

The solution is to first sort all n heads and tracks that you want to read, and then you can simply do a binary search for the minimum time because we can check if it is possible to read all the tracks in time t by greedily reading as many tracks as possible starting from the leftmost head.

New version of the problem So the problem I thought of is basically just the same problem but in two dimensions.

Suppose there are n helicopters located throughout an x*y rectangular grid. There are also m bomb sites in the grid where we want to drop a bomb. Assume that each helicopter carries infinite bombs, and it requires no time for a helicopter to drop a bomb. However, the helicopter requires 1 second to move 1 unit length in the grid. Also, the helicopters can move freely, they don't have to move along the gridlines (eg. they can fly diagonally). Find the minimum time it takes for all the helicopters to destroy all the bomb sites. For sake of simplicity, lets assume that all the helicopters and bomb sites are located in integer coordinates.

My thoughts/attempts of a solution So clearly this problem is a lot more complicated than the original problem since now we have to deal with 2 dimensions. My first thought was to use binary search again, but this causes some problems. Suppose that we want to check if the bombsites can be destroyed in less than t seconds. Then we can draw circles of radius t around each helicopter, and then see if the bomb sites lie within the circles. But what if multiple bomb sites occur within one circle? Or what if there are areas where 2 or more circles overlap and the overlapping space has multiple bomb sites in it? So I'm not sure what to do from there.

Please let me know if you have seen this problem somewhere before, or if you have any ideas on how to solve it!

Problem Link:1397E - Monster Invaders

Submission Code: 91449336

A few of my friends have asked me for a solution to this problem, so I thought I might as well post it here since the editorial is not out yet.

Disclaimer: I was not able to solve this question during the contest period, I was able to come up with it and clean up the code a little after the contest was over. Also I am still fairly new to competetive programming and this is my first public solution, so feel free to leave any feedback!

Methodology (you can skip this if you just want to see the solution):

So first of all, there are a few things to notice:

Switching between stages is costly, so we should take out as many enemies as we can before switching.

• The only times we should switch are therefore:

1. We have cleared all the enemies in a stage
2. We have damaged the boss and we are forced to switch.

• Since we cannot focus on the boss until all the other enemies are dead, and we should not switch unless required to, there are essentially three options upon entering a new stage before switching:

1. Kill all the non-boss enemies one by one with pistol until they are all dead, then kill the boss with the AWP.
2. Kill all the non-boss enemies one by one with pistol until they are all dead, then damage the boss once with the pistol.
3. Kill all the enemies and damage the boss with one shot from the laser gun.

• Notice that options (2) and (3) leave us with the same outcome (eg. all the non-boss enemies are dead and the boss has 1 health left). We can therefore group these two options together and find their minimum. So the options become:

1. Kill all non-boss enemies one by one with pistol until they are all dead, then kill the boss with AWP.
2. Clear smaller enemies with pistol and then damage boss with pistol, or shoot all enemies with laser gun. Whichever costs less.

• So now we have discussed everything we can do upon first entering the stage. Now notice that these 2 options lead to 2 different outcomes, respectively

1. All the enemies in the stage is dead, so the stage is cleared.
2. There is only the boss left in the stage, and he only has one health. One shot with the pistol will take him out

• Given this, we can assign three possible states S_i to each stage i
• The states are as follows:
  (2): The state has not been touched yet. All the enemies in the stage are still alive.
  (1): All the enemies in the stage have been killed except for the boss, who only has 1 health left.
  (0): All the enemies in the stage have been killed.

We never need to consider more than 2 consecutive stages at a time.

• Let's think about all the possible cases we can have starting from the first stage. When we first enter the game, S_i = 2 for all stages i. We start at the first stage. We have 2 options:

1. Kill everything in the stage (using pistol and AWP) and move on to the next stage.
2. Clear the non-boss enemies at the stage (using either pistol or laser, whatever costs less), and the move on to the next stage.

• Notice that if we choose option (1), then we no longer have to care about the first stage anymore, and we are left with essentially the same case that we started with. That is, the current state we are on (which is now the 2nd stage) is at state (2), and so is everything after it. So we are left with the same 2 choices above. So we can say that those two options are relevant whenever S_i = 2 or S_i = 0 for all stages i.
• However, if we choose option (2), things are more complicated as we are now in the 2nd stage, but we still have to worry about the boss at stage 1. So s_2 = 2 and s_1 = 1. At this point we should do what we can at stage 2, and then switch back to stage 1 right after.
• Why do we have to go back to stage 1 and not go to stage 3? Well, because we would still have to come back to stage 1 eventually anyways, so it is better to do it while we are only 1 stage away from it, rather than several stages away.
• So our options are:

1. Kill everything in stage 2 using pistol and AWP, and then go back to stage 1. Then, after killing the boss at stage 1 using pistol, we move to stage 2 and then to stage 3. And we are left with our original case again where all the stages are at state 2 or state 0 (s_i = 2 or 0 for all stages i).
2. Clear the non-boss enemies in stage 2. Then go back to stage 1 and kill the boss. Then go back to stage 2 and kill the boss. Then go to stage 3 and we are at our original case again where everything is state 2 or 0.

Now that we have established this, we can move on to the actual solution. Let's define some variables and data structures. They will correspond to the variables/data structures with the same name as in my submission code. As mentioned before, we only really care about two consecutive stages at a time. So we need to keep track of the orientation of these two consecutive states, and we also need to keep track of what stage we are in.

Solution:

So in our recursive DP function we have an int "stage", which corresponds to the current stage that we are in. We also have an int "state". This state corresponds to one of six possible orientations of two consecutive stages. Notice that the use of the term "state" here is different from my explanation above, but we are still using 0, 1, and 2 to describe the status of each stage. So for clarification, I will now refer to the status of a single stage (which can be either 0, 1, or 2) as the "case" of that stage, and "state" now refers to the orientations for two consecutive stages, which can be {0, 1, 2, 3, 4, or 5}, so 6 possible.

More formally:

There are three possible cases for each stage:
(0): Everything is dead.
(1): Only the boss is alive and it has 1 health.
(2): Everything is still alive

And there are six possible states for a pair of consecutive stages:
(0): The current stage is in case 2, and the stage after it is 2.
(1): The current stage is in case 2, and the stage before it has a boss remaining.
(2): The current stage is in case 1 and the stage after it is in case 1.
(3): The current stage is in case 1 and the stage after it is in case 0.
(4): The current stage is in case 1, and the stage after it is in case 2.
(5): The current stage is in stage 0, and the stage after it is in case 2.

We also have two options in action, but only when the current stage is in case 2. The 2 possible actions (corresponding to their variable names in the code) are:
(inst): Kill all the non-boss enemies with pistol and then kill the boss with the AWP.
(clear): Kill all the non-boss enemies and damage the boss once. (Either with pistol or laser gun, whichever costs less).

You might be thinking that there are other states we have not considered, such as if the current stage is 2 and the stage after it is 1. This is impossible and the following state diagram shows us why:

Notice that movement between states is implied in the state transitions. The rule for movement is that we always move to the left if the stage before is non-zero. Otherwise, we move to the right. Also note that it is possible for some of these states to be combined, and we really only need 4 states total. But I used 6 because I felt it was more intuitive.

Finally, we keep track of how many stages we have cleared with an integer "cleared", and our base case is to return when cleared is equal to the number of stages.

There are also a few special cases we have to consider when we are at the first stage, or the last stage, which you can see in the code.

Since we have at most 6 cases for each stage, the runtime complexity would be O(6n) = O(n). where n is the number of stages.