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)$ ~\mathcal{O}(N \times M)~

Comments

There are no comments at the moment.