Editorial for MWC '15 #1 P2: Postcard

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.

When solving this problem, take note that the shape we're striving for is a rectangle. This means all we care about is to find the minimum $x$ $x$ value and the maximum $x$ $x$ value, along with the upper and lower $y$ $y$ value. We process the array once, taking note of $\min_X$ $min_{X}$ , $\max_X$ $max_{X}$ , and $\min_Y$ $min_{Y}$ , $\max_Y$ $max_{Y}$ . Now process the array again, and output the solution directly to the output stream.

Time complexity: $\mathcal{O}(N \times M)$ $O (N \times M)$

Comments

There are no comments at the moment.