Author: | Virgil Palanciuc |
Developer: | Adrian Budău |
Editorialist: | Adrian Budău |
Let's call the 2 projections the and projections.
First of all, we can notice that a shadow on row in one of the projections can only be generated from a cube that is at coordinates (X, some Y, some Z). This means that the problem can be solved independently for each from to .
First let's discuss the case of no solution: If at some row one of the projections has at least one shadow (implying there is a cube at this row), but the other one doesn't (implying that there isn't any cube at this row) then obviously we can not construct a solution. If this doesn't happen there is always a solution and it will be obvious from the construction.
For the maximum number of cubes, the solution is unique. If the projection has a shadow (X, Y) and the solution has a shadow at (X, Z) then we can put a cube at (X, Y, Z). There is no other spot we can place a cube, thus the solution is unique. Since it's unique we just have to print these cubes ordered by , then by , then by to get the minimal lexicographically solution.
For the minimum number of cubes let's look at some row . If the projection has shadows it means there are at least cubes at this row. Similarly, if the projection has shadows there are at least cubes at this row.
If P = Q and we have shadows in at (x, y_1), (x, y_2), \dots, (x, y_P) and shadows in NH at (x, z_1), (x, z_2), \dots, (x, z_Q) with y_1 < y_2 < \dots < y_P and z_1 < z_2 < \dots < z_Q. then we can place the cubes at (x, y_1, z_1), (x, y_2, z_2), \dots, (x, y_P, z_P) and there is no solution using less cubes at this row (since we need at least P = Q) and no smaller lexicographically one using only cubes.
If P < Q we obviously need to use the same multiple times (since we need at least cubes at this row). Because we require the minimum lexicographically solution we should use the smallest multiple times. We can duplicate it until we have as many as and then apply the same idea as in the P = Q case.
If P > Q we do as in P < Q except we duplicate the smallest and then apply the same idea as in the P = Q case.
Total complexity: \mathcal(N \cdot M \cdot H) time and space.