CEOI 2010 - A Huge Tower
Problem Link
Tags: 2P, Sorting
Time Complexity: O(nlogn)
In this problem, we are given a list of N block widths, and we are asked to compute the number of towers that can be built, with each block allowing blocks of D tolerance to be placed above or below it.
To begin with, block i can be placed below or above block j only if their widths have a difference of at most D.
First, sort the blocks in ascending order of widths. This will help in determining the blocks that can be placed below and above the different blocks.
Next, for block i, we need to figure out the number of blocks that have a maximum difference of width D. A naive approach would be to use two pointers: keep the left and right pointer at block i initially, but advance the right pointer until we hit a block whose width is more that block i width + D. However, this approach would exceed time limit (time complexity: O(n²))
Instead of initializing the right pointer's position to i at every iteration, we can simply pick up where the right pointer stopped at the previous iteration, and continue advancing it as described in the naive approach. This works because all blocks that block i can tolerate will be tolerable by block i+1 since block i+1 will be greater than or equal to block i.
For each block i, the number of blocks that have a maximum difference of D is the number of blocks that fall within the range of the right and left pointer (i.e position of right - position of left). Let's call this number X. Since the problem asks for number of solutions, the answer will be the product of all the values of X for each block i as this computes the number of permutations of X.
Comments