ARRGAME2 - Editorial

PROBLEM LINK:

Practice
Contest

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:

  1. If the set R is chosen randomly, then what is the probability that a given pair (p, q) belongs to R
  2. 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§ = 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.

10 Likes

This was another interesting Question of this Contest…!!

This has a very interesting solution just like the last month’s problem(INTEG), which also had an interesting solution…!!

One can easily come to the conclusion that Answer to this would be = (Total number of kisses CHEF gets from SASHA)/N;

Use Pen , Paper , little bit of logic & Calculator to come to the following CASES…!

CONSIDER THE 2 COLUMNS :

INTEGER’S IN CHEF ARRAY ------------------ CHEF WON’T GET KISSES FOR THE FOLLOWING INTEGER’S IN SASHA’S ARRAY

{1} ----------------------------------------------> {1 to N} ie; (For All the Cases)

{2} ----------------------------------------------> {2,3,4}

{3} ----------------------------------------------> {3}

{4} ----------------------------------------------> {2,3,4}

{5} ----------------------------------------------> {2,3,4,5}

{6} ----------------------------------------------> {2,3,4,5,6}

{7} ----------------------------------------------> {2,3,4,5,6,7}

{8} ----------------------------------------------> {2,3,4,5,6,7,8}

{9} ----------------------------------------------> {2,3,4,5,6,7,8,9}
.

.

.

{n} ----------------------------------------------> {2,3,…,n}

From Above We notice that ONLY {1} {2} & {3} from CHEF’s ARRAY SEEMS TO DISOBEY THE TREND THAT THE REST OF THE NUMBERS ARE FOLLOWING … :stuck_out_tongue: … So , Do a Pre-Calculation for these numbers…!!

LET’s HANDLE THEM SEPERATELY…!!!

CASE 1 : CHEF won’t get any kiss if he has the number {1} … So Ignore it while taking the Input…!

CASE 2 : If CHEF has the number {2} , this will behave just like the number {4} , (SEE IT IN THE TABLE ABOVE) … So replace 2 with 4 while taking the i/p to CHEF’s array…!!

NOW We Sort both the Array for CASE 3 & Further Calculation…!!

CASE 3 : If CHEF has the number {3} , He will win for all the cases (EXCEPT FOR THE CASES WHERE SASHA HAS {3}), So do a pre-calculation for this by counting the Number of 3’s for both CHEF & SASHA…!!

Now , we are done with all the cases…

We Need to Handle One more case to simplify our calculation :

CASE when SASHA Has {1} : CHEF will win for all the cases where SASHA has {1} (EXCEPT FOR THE CASE WHERE CHEF HAS {1} , WHICH WE HAVE ALREADY IGNORED) … So Keep a counter for SASHA’s {1} and Ignore it while taking the Input… Later add it to your answer!

That’s it.!

Now We Can Run a Loop for the CHEF’s Array & also keep track of SASHA’s Array & Easily Get the Number Of Kisses CHEF gets in best Possible Complexity…!! Note : BOTH THE ARRAY SHOULD BE SORTED FOR THIS STEP…!

Link to this Approach : http://www.codechef.com/viewsolution/2804603

NOTE : This Approach with fast i/o got passed with best TIME & SPACE … 0.14 sec , 2.8 M

5 Likes

I came at the exact same conclusions. I had trouble in translating that in terms of expected value. :frowning:

Hi,I tried this in practice section but getting WA…can someone please check and let me know what mistakes I am making?

http://www.codechef.com/viewsolution/2832836

@plcpunk >> Here is your corrected code http://www.codechef.com/viewsolution/2832905

1 Like

Thanks!!!

You could have given more time for thinking in terms of expected value here… That was the only major challenge for this problem i guess…!! :stuck_out_tongue:

1 Like

i dont understand why http://www.codechef.com/viewsolution/2833274 is giving WA. As soon as make every variable of the type long long it gets accepted. But according to me long long should only be required by the counter variable. Please see to this.

i am not able to see this editorial completely till the end :frowning:

i can only read it till expected score of the game.
kindly fix this.
thank you.

i am trying to implement the editorial approach.

please point out where is the mistake i am getting a lot of WAs.

my solution:http://www.codechef.com/viewsolution/2835502

again the same problem occured :frowning:

at least there is one problem that you are not handling the case of a[i] = 1, in which case there should be no valid pairs.

1 Like

I keep getting TLE please help

http://www.codechef.com/viewsolution/2830729

I permute to all the sequence of one array and keep checking weather (Y log X > X log Y ) and kept a count++. After that cout << count/N. what is wrong in my logic ?
http://www.codechef.com/viewsolution/2802112

@djdolls Thank you for answering.

If i am right, we are counting all the valid pairs and the result by n, and that is the answer.

Now, as given in editorial, when x=1, then there exists no valid pair, so i didn’t count it.

isn’t that right ?

In your code the values of a[i],b[i] can be till 10^9. Those will not fit in integer type.See the below link for clarity.

http://www.cplusplus.com/reference/climits/

Your approach is O(n^2) which will time out with the given constraints.You can improve it to O(nlogn)by sorting the array and using binary search.

Nice problem :slight_smile:
My solution was based on binary search.

Please Please tell me What is wrong with my code. I had gone nuts over it. I have seen many solutions just like it which have got accepted… Plz check… :frowning:

http://www.codechef.com/viewsolution/2802046

Thanx in advance…

no need to count ones & twos

instead of storing numbers, store log(x)/x in arrays.
then sort the second array
then

for(i=0;i<n;i++)
ans+=(lower_bound(b.begin(),b.end(),a[i])-b.begin());