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$ ~i~ and check if Sanjay can reach Sam with $i$ ~i~ balloons. To do so, we use BFS and a 2 dimensional prefix sum array. To move to cell $(r, c)$ ~(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)$ ~(r-i+1, c-i+1, r, c)~. The maximum size is outputted.

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

Subtask 2

To optimize, we binary search the size $i$ ~i~.

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

Comments

There are no comments at the moment.