Problem Link:[problem:1397E]↵
↵
Submission Code: [submission: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 or 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.↵
↵
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.↵
↵
↵
Submission Code: [submission: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 or 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.↵
↵
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.↵
↵
