Editorial for An Animal Contest 2 P3 - Koala Balloons

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.

Authors: sjay05, samliu12

Subtask 1

We iterate through each size i and check if Sanjay can reach Sam with i balloons. To do so, we use BFS and a 2 dimensional prefix sum array. To move to cell (r, c), we query the PSA to check that there are no obstacles in the square defined by (r-i+1, c-i+1, r, c). The maximum size is outputted.

Time Complexity: \mathcal{O}(N M \cdot \min(N, M))

Subtask 2

To optimize, we binary search the size i.

Time Complexity: \mathcal{O}(N M \cdot \log(\min(N, M)))

Comments

There are no comments at the moment.