Editorial for Baltic OI '09 P6 - Monument - DMOJ: Modern Online Judge

Editorial for Baltic OI '09 P6 - Monument

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.

To simplify, consider $p, q, r \approx n$ ~p, q, r \approx n~.

Naive solution: test all $\mathcal O(n^2)$ ~\mathcal O(n^2)~ possibilities for choosing $a$ ~a~ and $b$ ~b~, in all possible $\mathcal O(n^3)$ ~\mathcal O(n^3)~ locations. At least $\mathcal O(n^5)$ ~\mathcal O(n^5)~ time.

Basic dynamic programming: fill values $d[x, y, z, k] =$ ~d[x, y, z, k] =~ maximum height $b$ ~b~ for a rectangle with base length $a = k$ ~a = k~ and a corner at $(x, y, z)$ ~(x, y, z)~. Results in $\mathcal O(n^4)$ ~\mathcal O(n^4)~ time.

Proposed solution: precompute in $\mathcal O(n^3)$ ~\mathcal O(n^3)~ time and space for each $(x, y, z)$ ~(x, y, z)~ what is the side-length of maximal full square with e.g. lower-right corner at $(x, y, z)$ ~(x, y, z)~ (this is computed along one of the three orientations: xy-plane, xz-plane and yz-plane). Then the solutions for the current orientation can be computed with an $\mathcal O(n^3)$ ~\mathcal O(n^3)~ time traversal over all $(x, y, z)$ ~(x, y, z)~. The final solution is taken as the best found among three traversals (and precomputations): one for each orientation.

Comments

There are no comments at the moment.