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 (t ime comp...