CodeChef October Challenge 2013 Editorial [Yet Another Nice Girl] _____By: Raihat Zaman Neloy

Problem: Yet Another Nice Girl
Nice problem to solve! Given two array ‘a’ & ‘b’ of N numbers. You can choose any number X from a and any number Y. Now you have to say what is the expected value that X^Y > Y^X will happen?

What kind of idea came to your mind first? I think it’s: Implement a O(n2) algorithm, take all possible pair of numbers from array a & b. Check if X^Y > Y^X, if yes, then take a counter and increase it, then multiply the probability of each pair. But, can we implement it when the limit of N is 10^5 and each of the numbers of the two arrays can be from 1 to 10^9? We can’t, because we can’t easily find the X^Y or Y^X for big numbers. So, what can we do? Let’s observe something.

Try to simulate some powers for small numbers:

1^1 = 1, 1^2 = 1, 1^3 = 1 ….
2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16, 2^5 = 32 … …
3^1 = 3, 3^2 = 9, 3^3 = 27, 3^4 = 81, 3^5 = 243  …..
4^1 = 4, 4^2 = 16, 4^3 = 64, 4^5 = 1024 …
5^1 = 5, 5^2 = 25, 5^3 = 125,5^4 = 625, 5^5 = 3125 …

Now, let’s see… We have to find whether X^Y > Y^X or not. So, here we can easily observe that, if X < Y then we can tell that X^Y > Y^X. Example:

X = 3, Y = 4, now, 3^4 = 81, 4^3 = 64
X = 4, Y = 5, now, 4^5 = 1024, 5^4 = 625
X = 2, Y = 5, now, 2^5 = 32, 5^2 = 25

So, we can easily observe that, we have to find the all the numbers greater than X in the array b. So, one solution we get, take a number from array a as X, find all the numbers greater than X in array b. Now, how will you search those numbers? Will you do a linear array search from the left to right?? If you want to then see, can you implement it where the limit in 10^5? You can’t, so we will apply binary search algorithm.

So, the solution is finished!!! Yahoooo….

Wait!!! Wait!!! Wait!!! What I am seeing??? 2^4 = 16 again 4^2 = 16?:O 1^2 = 1, 2^1 = 2??? 2^3 = 8, 3^2 = 9??? O M G!!! Now what to do???

Relax!!! These are some constraints for 1,2& 3. For 1, we don’t need to search any greater number than it, because, always 1^P = 1, and P^1 = P.

For 2, we have to search numbers in array b greater than 4, because, some variation are there from 2 to 4, that is: 2^2 = 2^2, 2^3 < 3^3 & 2^4 = 4^2, but all other are 2^P > P^2 , where P > 4

For 3, we have to searc the numbers greater than 3, and again, we have to count how many 2’s are there in array b, as 3^2 > 2^3.

That’s it. It’s all the solution. Now, count the number of pairs, multiply with the probability, and you will get your answer! 

Happy Coding!

Code: 

1. #include <bits/stdc++.h> //all pre-compiled header files
2.  
3. #define INF 1000000007
4. #define LL long long
5.  
6. using namespace std;
7.  
8. int a[100050];
9. int b[100050];
10. int n;
11.  
12. int main ()
13. {
14. int t,c,i,j,k;
15.  
16. cin >> t;
17. while (t--)
18. {
19. cin >> n;
20.  
21. i=0;j=0;
22. while (i<n) cin >> a[i++];
23. while (j<n) cin >> b[j++];
24.  
25. sort (a,a+n);
26. sort (b,b+n);
27.  
28. b[n] = INF;
29.  
30. LL ans = 0;
31. int one,two;
32.  
33. i=0;
34. while (b[i]<=1)
35. {
36. b[i] = INF;
37. i++;
38. }
39.  
40. one = i;
41.  
42. while (b[i]<=2)
43. {
44. b[i] = INF;
45. i++;
46. }
47.  
48. two = i;
49.  
50. sort(b,b+n);
51.  
52. int m = n-two;
53.  
54. for (int i=0;i<n;i++)
55. {
56. if (a[i] == 2)
57. {
58. int pos = upper_bound(b,b+n,4)-b;
59.  
60. pos = m - pos;
61. ans += (pos+one);
62. }
63.  
64. else if (a[i] == 3)
65. {
66. int pos = upper_bound(b,b+n,3)-b;
67.  
68. pos = m - pos;
69.  
70. pos += two;
71. ans += (pos);
72. }
73.  
74. else if (a[i] > 3)
75. {
76. int pos = upper_bound(b,b+n,a[i])-b;
77.  
78. pos = m - pos;
79.  
80. pos += one;
81. ans += pos;
82. }
83. }
84.  
85. printf ("%.10lf\n",ans*1.0/n);
86. }
87.  
88. return 0;
89. }