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.

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

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

Proposed solution: precompute in \mathcal O(n^3) time and space for each (x, y, z) what is the side-length of maximal full square with e.g. lower-right corner at (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) time traversal over all (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.