BLOCKS - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

CHALLENGE

EXPLANATION

It is currently unknown whether this problem is NP-hard, but due to the high number of testcases it is highly unlikely that the problem is solvable exactly within the time limit. The variation in which the blocks cannot be rotated is solvable in O(N^2) time. This gives rise to a simple algorithm that chooses fixed rotations for each block, finds the tallest tower, then rotates blocks not belonging to the tallest tower and tries again. For small cases, the solution can be computed exactly using dynamic programming in at most O(N^2*2^N) time, though typically much faster on random data. Because of how the scoring mechanism works, small cases are generally worth more, and should given higher priority.