PROBLEM LINK:
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