1743E - FTL

1743E - FTL

At any time, we have three possible choices: wait and shoot the first laser, the second laser and both lasers. Sometimes it makes sense to wait to both because you can deal s more damage than you would do by shooting both lasers separately.

The first claim: greedy won't work. Maybe there is a sufficiently smart greedy, we weren't able to come up with it. The second claim: brute force won't work. The funny thing is that it actually worked on the constraints up to 2000, but again, we couldn't code any sufficiently fast one for 5000.

Thus, let's try some dynamic programming. Since all the times are huge, we'd want to avoid having them as the states. What is small, however, is the durability of the enemy ship and the number of shots we have to make to destroy it.

Ideally, we'd like to have some \(dp[i]\)— the smallest time to deal ii damage to the enemy ship. This way, \(dp[n]\) would be the answer. Sadly, it's not immediately clear how to get rid of reload times completely. There might be states with different times until the charge with the same damage dealt, and we don't know which of those we want to keep.

Thus, let's make the \(dp\) state more complicated. Let \(dp[i]\) be the smallest time it takes to deal ii damage if the last shot was from both lasers at the same time. This way we know the reload times of both lasers — they are full \(t1\) and \(t2\).

\(dp[0]=0\), as moment 00 has both lasers zero charged as if after a shot.

What are the transitions? Well, now we have to shoot each laser multiple times, then wait until both are charged and shoot both. Both lasers can now be considered independent of each other.

Let the time between the previous double shot and the next one be some value \(t\). During this time, it never made sense to wait until shooting each laser. So we waited \(t1\), shot the first laser, waited another \(t1\), shot again, until we couldn't shoot anymore, since the laser wouldn't recharge in time before the double shot. Same for the second laser. Notice that if both \(t%t1≠0\) and \(t\%t2≠0\), then you could just decrease \(t\) by 11 and shoot each laser the same number of times. Thus, only tt that are multiples of either \(t1\) or \(t2\) are optimal.

Thus, we can iterate over all possible waiting times tt. Just iterate over \(i⋅t1\) and \(i⋅t2\) for all ii from \(1\) to \(h\). Having a fixed \(t\), calculate the number of shots of each laser, calculate the damage, go into the corresponding \(dp\) state.

It could also happen that the last shot before destroying the ship wasn't a double one. However, it still follows the same ideas. It means that each laser was shooting non-stop until the ship was destroyed. Thus, the destruction time is still a multiple of either of the reload times.