Editorial for LCC '21 Contest 1 J4 - Explosive Candygrams


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: Trent

Subtask 1

For a candygram l and r, we know that the number of candygrams in between is |r-l|-1. Therefore, for each candygram, we can loop through all other candygrams. If the number of candygrams between the two is more than or equal to R_i, then we know that the current candygram can be hit. We then take the maximum R_i of all candygrams we can hit. If we cannot hit any candygrams, then we instead take -1

Subtask 2

Image

Consider the above image, where we are calculating the answer for the sixth candygram, the one with the second "2" in its cell. Orange cells denote candygrams which the candygram cannot hit (they are all either the current candygram, have 0 candygrams in between, or 1 candygram in between). The important thing to note is that we "split" the current array into 3 sections, where we must consider all candygrams in the yellow section.

For the current candygram i, all candygrams with index j, such that j\le i-R_i-1 can be hit, as they have at least R_i candygrams in between. Similarly, all candygrams with index j, such that j\ge i+R_i+1 can be hit, as they have at least R_i candygrams in between.

We can use a prefix maximum array to quickly calculate the maximum explosiveness on the left side, and a suffix maximum array to quickly calculate the maximum explosiveness on the right side. Let us call the prefix maximum array maxTo and the suffix maximum array maxFrom

Then, the annoyance of the current candygram is \max(maxTo[i - R_i-1], maxFrom[i+R_i+1]), making sure to account for when we go out of bounds (i.e, i-R_i-1 is before the first element, or i+R_i+1 is past the final element). Furthermore, if we cannot hit any candygram, then the annoyance is -1


Comments

There are no comments at the moment.