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 (ri+1,ci+1,r,c). The maximum size is outputted.

Time Complexity: O(NMmin(N,M))

Subtask 2

To optimize, we binary search the size i.

Time Complexity: O(NMlog(min(N,M)))


Comments

There are no comments at the moment.