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.