Internet Problem Solving Contest

IPSC 2015

Solution to Problem T – Town

The easy subtask can be solved by brute force: generate house numbers starting from 1, for each of them count the digits used and terminate once you don’t have enough digits to build the current number.

For the hard subtask this solution would be too slow. How can we improve it? The key is to notice that the answer is monotonous: if we have enough digits for houses 1 through x, we have enough digits for houses 1 through y, for any y < x. This makes it possible to determine the optimal answer using binary search.

In order to perform the binary search we have to implement a function that takes an n and verifies whether the box contains enough digits to produce numbers from 1 to n. This function will somehow count the digits used in the numbers from 1 to n and compare those counts to the counts of digits in our box.

We will now show how to calculate the value Cd, n: the number of times the digit d occurs in the numbers 0 through n − 1. The value Cd, n can easily be computed recursively in O(logn) time as follows:

Once we know how to compute the values Cd, n, we are all set. During the binary search we will compute the value C0, n + 1 − 1 and the values C1, n + 1 through C9, n + 1 and we will compare these to the ten values we were given as the input.