Editorial for Back From Summer '17 P6: Crowded Cities
Submitting an official solution before solving the problem yourself is a bannable offence.
Note that the order of length vs width does not matter since we can rotate the blocks by 90 degrees. We can prove that it is optimal to have the longer side always be either the length or width. We can then rotate to make sure the length is always the longer (or equal) side, and ignore the option to rotate later when we are trying to get the solution.
Since ~N \leq 9~, it is possible to go through permutations of blocks. For each permutation, greedily combine the front blocks 1 by 1 until you either reach the end of the sequence, or find a block that cannot stack on top of the previous block.
After you go through all the permutations, output the sequence with the greatest population.
Runtime complexity: ~O(N!*N)~
Since all the block heights, lengths and widths are the same, you can simply sort by one of the dimensions and greedily combine all the blocks in greatest to least order.
Runtime complexity: ~O(N \log N)~
Since ~N \leq 500~, we can go through each pair of points and see which one can stack on top of each other. Once we create a directed acyclic graph (DAG), we can find the longest path using topological sort. Runtime complexity: ~O(N^2)~
Since ~H_i=1~, we can always ignore the height factor, leaving us with only 2 dimensions. We can then sort to eliminate the length and do the classical Longest Increasing Subsequence problem to solve it.
Runtime complexity: ~O(N \log 3000)~
After solving subtask 4, we realize that we can also sort by the height factor, and solve a 2D version of the Longest Increasing Subsequence problem. To do this, we can use a 2D segment tree, which will let us query the largest value with ~(l,w) \leq (x,y)~.
Runtime complexity: ~O(N \log^2 1000)~
A 2D segment tree takes many times more ~(\approx \times 10)~ integers to store the value than a standard 2D array. This will easily MLE as the ~5000 \times 5000~ grid is quite large. To get around this we can use a 2D Binary Index Tree, but instead of storing sums, we can use it to store the largest value and query from ~(0,0)~. It is also much simpler to code than a 2D segment tree.
This uses no more memory than a ~5000 \times 5000~ grid, which will allow it to pass.
Runtime complexity: ~O(N \log^2 5000)~