GUESSMID - Editorial

PROBLEM LINK:

Practice

Author: Istvan Nagy

Tester: tncks0121

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Brute Force, Math

PROBLEM:

An integer x is chosen randomly from the set of integers between A and B with maximum number of digits C. Similarly y is chosen randomly from the set of integers between A and B having maximum number of digits D. Choose an integer z which has the maximum probability of lying between the numbers x and y.

Explanation:

Let X be the set of integers between A and B with maximum number of digits equal to C.

Let Y be the set of integers between A and B with maximum number of digits equal to D.

The crucial observation is that the sizes of both X and Y are O(\log(B - A)).

Proof:

Let A = a_n a_{n-1} \ldots a_0, B = b_n b_{n-1} \ldots b_0 be the decimal representations of A and B respectively. WLOG, assume a_n < b_n, else we can find the first digit at which A and B differ and consider the remaining digits only.

Case 1: b_n > a_n + 1.

In this case, the integer (a_n+1) \underbrace{CC \ldots C}_{n} lies between A and B, and has n C's. So, clearly, any integer in X can have at max 1 digit not equal to C. So |X| = O(n) = O(\log(B - A))

Case 2: b_n = a_n + 1

Let H = (a_n+1) 10^n . Break the range [A, B] into [A, H - 1] \cup [H, B].

Consider the range [A, H - 1]. Let k be the greatest index < n with a_k < 9. If there is no such k, there is only one integer in the range [A, H - 1], and we can consider it separately.

If we increase a_k and replace the following digits by C, we get a_n \underbrace{9 \ldots 9}_{n-k-1} (a_k+1) \underbrace{C \ldots C}_k. Any integer in this range has only the last k + 1 digits variable and atleast k out of them must be C. So, the number of possible integers in X in this range is O(k) = O(\log(H - A)) = O(\log(B - A)).

Similarly, consider range [H, B]. Let k be the greatest index < n with a_k > 0. Then, one can decrease a_k by 1 and replace the following digits by C. By a similar analysis, the number of possible integers in X from this range is also O(\log(B - A))

Note that the above proof can be used to find the sets X and Y.

For an integer z, the chances of it lying between x and y, f(z) are proportional to (# of integers in X \leq z) (# of integers in Y \geq z) + (# of integers in Y \leq z) (# of integers in X \geq z) with a few small adjustments (when two numbers from \{x, y, z\} are equal).

On iterating on z from A to B, f(z) only changes O(|X| + |Y|) times, and we can easily maintain f(z) in O(1) per change.

The overall complexity would be O(\log(B - A) \log( \log(B - A))) per test case. The \log\log factor comes because we have to sort X and Y.

TESTER’s SOLUTION:

Tester’s solution can be found here