Editorial for OTHS Coding Competition 1 (Mock CCC) J4 - Railgun

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: htoshiro

Subtask 1:

It is always optimal to choose to eliminate as many robots on the right side of the array as possible.

Time Complexity: $\mathcal{O}(ST)$ ~\mathcal{O}(ST)~

Subtask 2:

It is possible to find the damage of all combinations utilising her railgun ability $T$ ~T~ times from destroying the $S$ ~S~ leftmost robots $T$ ~T~ times and the $S$ ~S~ rightmost robots 0 times, to destroying the $S$ ~S~ leftmost robots 0 times and destroying the $S$ ~S~ rightmost $T$ ~T~ times. We then choose the maximum out of all combinations.

Note: A dynamic programming approach will also work.

Time Complexity: $\mathcal{O}(ST)$ ~\mathcal{O}(ST)~

Subtask 3:

We can further optimise our idea from Subtask 2 by using a prefix-sum array or sliding window.

Time Complexity: $\mathcal{O}(T)$ ~\mathcal{O}(T)~

Comments

There are no comments at the moment.