Editorial for Back From Summer '17 P6: Crowded Cities

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.

Author: kobortor

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.

Subtask 1

Since $N \le 9$ ~N \le 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: $\mathcal O(N! \times N)$ ~\mathcal O(N! \times N)~

Subtask 2

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: $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~

Subtask 3

Since $N \le 500$ ~N \le 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: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

Subtask 4

Since $H_i=1$ ~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: $\mathcal O(N \log 3000)$ ~\mathcal O(N \log 3000)~

Subtask 5

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) \le (x,y)$ ~(l,w) \le (x,y)~.

Runtime complexity: $\mathcal O(N \log^2 1000)$ ~\mathcal O(N \log^2 1000)~

Subtask 6

A 2D segment tree takes many times more $(\approx \times 10)$ ~(\approx \times 10)~ integers to store the value than a standard 2D array. This will easily MLE as the $5000 \times 5000$ ~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)$ ~(0,0)~. It is also much simpler to code than a 2D segment tree.

This uses no more memory than a $5000 \times 5000$ ~5000 \times 5000~ grid, which will allow it to pass.

Runtime complexity: $\mathcal O(N \log^2 5000)$ ~\mathcal O(N \log^2 5000)~

Comments

0

discoverMe commented on Jan. 7, 2019, 10:51 p.m.

why is the longest increasing subsequence the one that holds the most people?

2

account_disabled commented on March 1, 2018, 2:51 p.m.

How to construct the LIS after getting most PPL?

0

maxhflow commented on Sept. 11, 2017, 12:26 a.m.

I had a similar idea during the contest, but I can't see how to deal with the case of equal heights after sorting by height. Can somebody explain this?

1

20748588 commented on Sept. 11, 2017, 12:59 a.m. ← edited →

Tie break on max(length, width), then on min(length, width).

1

kobortor commented on Sept. 11, 2017, 4:18 a.m.

This is the intended solution. This can be made simpler if you simply swap the length and width to make sure the longer side is always the length or always the width, then sort by that.

0

maxhflow commented on Sept. 11, 2017, 4:22 a.m.

Thanks, that was a silly mistake by me!