Editorial for Baltic OI '09 P6 - Monument - Olympiads 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)$ $O (n^{2})$ possibilities for choosing $a$ $a$ and $b$ $b$ , in all possible $\mathcal O(n^3)$ $O (n^{3})$ locations. At least $\mathcal O(n^5)$ $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)$ $O (n^{4})$ time.

Proposed solution: precompute in $\mathcal O(n^3)$ $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)$ $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.