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)

Subtask 2:

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

Note: A dynamic programming approach will also work.

Time Complexity: \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)


There are no comments at the moment.