PROBLEM LINK:
Author: Ivan Zdomsky
Tester: Jingbo Shang
Editorialist: Ajay K. Verma
DIFFICULTY:
EASY
PREREQUISITES:
High school maths, Linearity of expectation, Sorting
PROBLEM:
Given two array of integers A and B of the same size N, a random permutation z is picked. We want to compute the expected value of the size of the set S = {i | A[i]B[j] > B[j]A[i], where j = z(i)}.
QUICK EXPLANATION:
For each valid pair (A[i], B[j]) satisfying the above inequality, create a random variable Xij which takes value 1, if the randomly chosen permutation z maps i to j, and 0 otherwise. Based on the linearity of expectation the expected score of the game is the sum of expected value of these random variables. Since the expected value of each of these random variables is 1/N, the problem reduces to find the number of valid pairs.
The function x1/x has exactly one extreme point (maxima at e), Hence for any integer a, the set of integers b satisfying the inequality (a1/a > b1/b), i.e. (ab > ba) can be written as the union of two intervals. If the array B is sorted then, for each element a in array A, we can use binary search on array B, to find out how many compatiable b it contains.
EXPLANATION:
As explained in the problem, the game consist of N turns, where in each turn we pick two unselected numbers, one from the array A (call this number x), and one from array B (call this number y). The score of the game is the number of turns in which picked numbers satisfy the inequality (xy > yx).
Now, create two new arrays P and Q, such that
P[i] = index of the element x in array A, which was selected in i-th turn, likewise
Q[i] = index of the element y in array B, which was selected in i-th turn.
Since each element is selected exactly once, both P and Q must be permutations of {1, 2, …, N}. In fact, each game can be defined uniquely by the two permutations P and Q. Hence, the total number of games is the same as number of permutation pairs (P, Q), i.e., (N!)2.
For example, a game ({2, 3, 1}, {2, 1, 3}) means that in first turn A[2] and B[2] were selected, in the second turn A[3] and B[1] were selected and in the last turn A[1] and B[3] were selected.
For a game (P, Q) consider the following set of pairs R = {(P[i], Q[i]) | 1 <= i <= N}. It can be observed that using the set R, one can compute the score of the game. For the above example
R = {(2, 2), (3, 1), (1, 3)}. Therefore, in order to compute the score of this game we need to check the inequality (xy > yx) for the three pairs (A[2], B[2]), (A[3], B[1]) and (A[1], B[3]).
If two games (P1, Q1) and (P2, Q2) have the same set R, then their score must be the same, e.g., for the game ({1, 3, 2}, {3, 1, 2}) the set R is {(1, 3), (3, 1), (2, 2)}, which is the same as the R of the previous example (order of elements in a set does not matter). Hence, the two games must have the same score.
Note that each set R corresponds to N! games, as the elements of R can be permuted in N! ways, and each such permutation correspond to a unique game. Hence, the expected value of the score over all games is the same as the average score over all set R.
Expected score of the game:
The elements of R are pairs (i, j), with 1 <= i, j <= N. We have two basic questions:
- If the set R is chosen randomly, then what is the probability that a given pair (p, q) belongs to R
- How do we find out if a given pair (p, q) will contribute to the score of the game, i.e., A[p]B[q] > B[q]A[p].
If we can answer these two questions, then we can compute the expected value of the score easily: For a randomly chosen set R, we can create N2 random variables Xij (1 <= i, j <= N), such that
Xij = 1, if pair (i, j) is in the chosen set, and (i, j) contributes to the score.
= 0, otherwise.
Clearly, the score of the game is the sum of these random variables. Hence, the expected value of the score is E[sum of Xij’s]. Using the linearity of the expectation, this can be written as aum of E[Xij]’s.
E[Xij] = Pr(Xij = 1) * 1 + Pr(Xij = 0) * 0
= Pr(Xij = 1)
Pr(Xij = 1) = 0, if pair (i, j) does not contribute to the score, i.e., A[i]B[j] > B[j]A[i].
= Pr(pair (i, j) belongs to R), otherwise.
We need to compute the sum of all N2 probabilities Pr(Xij = 1).
What is the probability that a pair (p, q) belongs to a randomly chosen set R:
Since each of the 1, 2, …, N occurs exactly once on the left side of a pair in R, and exactly once on the right side of a pair in R, we can write R as {(1, z(1)), (2, z(2))), …, (N, z(N)))}, where z is a permutation (more formally z = Q o P-1).
Hence, the number of possible sets R is the same as number of permutations of N integers, which is N!. The number of sets R which contain the pair (p, q) is the same as the number of permutation where z(p) = q, which is (N - 1)!.
Therefore, the probability that a pair (p, q) belongs to a randomly chosen R is (N - 1)! / N! = 1/N.
When does the inequality (xy > yx) hold:
We call a pair of integers (x, y) a valid pair, if the above inequality hold for this pair.
Since x, y > 0, we can rewrite the above inequality as (x1/x > y1/y).
Now consider the function f(x) = x1/x.
f’(x) = (1 - ln x) x(1/x - 2)
This means the value of f increases from 1 to e, and then decreases afterwards. Hence, if both x, y < e, then (x1/x > y1/y) <==> x > y, and if both x, y > e, then (x1/x > y1/y) <==> x < y. After taking care of the pairs (x, y), where x < e < y, or vice versa, we can come to the following criteria of deciding if (x, y) is a valid pair.
If x = 1, then (x, y) can never be a valid pair.
If x = 2, then (x, y) is a valid pair iff y ∈ {1} U [5, inf).
If x = 3, then (x, y) is a valid pair iff y ∈ {1, 2} U [4, inf).
If x > 3, then (x, y) is a valid pair iff y ∈ {1} U [x + 1, inf).
Algorithm:
Based on the above explanation, we can see that
E[Xij] = 1/N, if (A[i], B[j]) is a valid pair
= 0, otherwise.
This gives us an easy O (N2) algorithm by considering all pair (i, j), compute E[Xij], and then add them together. This can be further improved using the fact that the value of E[Xij] is the same for all valid pairs (A[i], B[j]). Hence, the value of the expected score is
E = Number of valid pairs (A[i], B[j]) / N.
Counting the number of valid pairs (A[i], B[j]):
This can be done by iterating through the elements array A and, for each A[i] compute how many j’s exist such that (A[i], B[j]) is a valid pair. Based on criteria of valid pair this is equivalent of finding how many elements of B are in an interval, which can be achieved in O (lg N) time if B is sorted.
ONE = number of 1’s in B
TWO = number of 2’s in B
Rank(x) = smallest j such that B[j] >= x, or N + 1 if no such j exists.
now for a given A[i] the number of valid pairs can be computed like this:
A[i] = 1 ⇒ valid pairs = 0
A[i] = 2 ⇒ valid pairs = ONE + N - Rank(5) + 1
A[i] = 3 ⇒ valid pairs = ONE + TWO + N - Rank(4) + 1
A[i] >= 4 ⇒ valid pairs = ONE + N - Rank(A[i] + 1) + 1
Time Complexity:
O (N lg N)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be put up soon.
Tester’s solution can be found here.
… So , Do a Pre-Calculation for these numbers…!!
