Hints : Yet Another Monster Fight

It is not an easy task to figure out the best candidate for the first lightning strike.

The maxima is not necessarily the best candidate.

No, choosing one maxima over another might yield completely different results. If you ended up somehow proving otherwise, you should revisit your proof to investigate how innocent sounding proofs might be misleading.

Here’s a testcase to prove that the maxima is not necessarily the best candidate.

8
1 11 1 1 12 1 1 1

Credits: This comment from NathanB. He also explains the reasoning behind it.

Here, if we choose the monster with 12 health we need x = 17, but if we choose to start from the monster with health 11 we only need x = 16.

We can’t choose the monster with 12 and have x = 16 because we kill that monster and all monster to the right and our power decreases to 12, we kill the monster to the left of it with 12 and we get to 11, we kill the left monster again and we are down to 10, this is less than what we need to kill the monster with 11 health.

Consider this testcase that demonstrates that the maximas are not equivalent.

4
2 4 2 1 

Credits: This comment from variety-jones

Here are the answers when the first strike hits the i-th element.

x = [5 5 6 6]

Hence, if you somehow end up taking the second maxima, the answer won’t be optimal.

So far, we’ve just done guesswork on what the optimal index for the first lightning strike would be. However, during contests, sometimes this approach would land, while other times it would lead you down a rabbit hole of complex implementation, only to receive a WA at pretest 2.

What’s equally important is to let go of a certain approach and start thinking in a completely new direction.

We’ve already seen that finding the optimal index for the first lightning strike is not an easy task. BUT what if we were to magically infer that the i-th index will COMPULSORILY be the receiver of the first strike? Can you figure out the minimum possible x needed in this scenario?

Formally, let x[i] be the minimum initial damage needed to clear all monsters when the first strike COMPULSORILY hits the i-th monster. Can you print out the array x in, say, O(n^2) time?

The above hint for choosing the smaller neighbor looks convincing, but is actually incorrect. It doesn’t incorporate all the scenarios in a which a monster can be hit. Can you construct a (theoretical) testcase to disprove the smaller neighbor theory?

Consider this testcase

n
98 100 99 1 1 1 .... (70 times)

If you start the hit at monster 100, with a power of 101, you can then kill the smaller monster (98), followed by next smallest (99), followed by next smallest neighbor (1) and so on …

However, if you don’t be greedy in the first step, and actually kill the bigger monster, i.e, 99, then you’ll only come to monster with health 98 after clearing the stream of 1s. Hence, in this case, even 101 is not sufficient.

So what exactly did we miss? Notice that we are doing the same mistakes as we did in the first part while figuring out the optimal index for first strike, i.e, we are applying too much logic and guesswork instead of just considering all possibilities.

Consider

7
a b c src p q r

If you start the strike at monster src with intensity x, what is the minimum possible damage that each monster would receive?

Consider

7
a b c src p q r

• By the time strike reaches monster c, all elements to the right could have been cleared. Hence, x - element_count_to_the_right_of_c.
• By the time strike reaches monster b, all elements to the right could have been cleared. Hence, x - element_count_to_the_right_of_b.
• By the time strike reaches monster a, all elements to the right could have been cleared. Hence, x - element_count_to_the_right_of_a.
• By the time strike reaches monster p, all elements to the left could have been cleared. Hence, x - element_count_to_the_left_of_p.
• By the time strike reaches monster q, all elements to the left could have been cleared. Hence, x - element_count_to_the_left_of_q.
• By the time strike reaches monster r, all elements to the left could have been cleared. Hence, x - element_count_to_the_left_of_r.

So, if you look at the element c, x - element_count_to_the_right_of_c >= health[c] ==> x >= health[c] + element_count_to_right_of_c.

If you combine all of them, the minimum x would then be.

left_half = max(health[i] + element_count_to_the_right_of_i such that i < source_index)
right_half = max(health[i] + element_count_to_the_left_of_i such that i > source_index)
x = max(left_half, source_health, right_half)

You can easily compute the left_half and right_half array for a given source. Hence, each source takes O(n) time, and we can solve the original problem in O(n^2).

How to compute the maximum of the left half and right half for any given source quickly?

Notice that left_half and right_half arrays remain same regardless of the source considered. Also, notice that you are only interested in the prefix maxima of left_half array and suffix maxima of right_half array.

Look at the code for more details.