Read problems statements in Mandarin Chinese here 

------ Problem Statement ------ 

Little Chef doesn't love math anymore. He loves Aleksandra.

Sashen'ka is nice. They spend all the time together. Even their birthdays they are celebrating together, because they were born on the same day :)

And now, this day is coming...

Chef know that most of all Sasha loves numbers, that's why he bought N positive numbers to a girl.
From her side, Sasha as all girls, thought that if she likes something, then all people like that too. And bought to a boy N numbers too. xD
After all greeting young people decide to play a game with their gifts. The game will be continued for N turns, in each turn the following will be done:
Chef randomly choose some number x from his gift.
Sasha randomly choose some number y form her gift.
If x^{y} > y^{x} then girl will kiss fellow.
Numbers x,y will be discarded from gifts.
Now chef is wondering what is the expected number of times he will be kissed by Sasha ?

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of numbers in each gift. The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the numbers Sasha gave to Chef. Next line describe B_{1}, B_{2}, ..., B_{N} numbers boy gave to girl in the same way. 

------ Output ------ 

For each test case, output a single line containing answer for corresponding test. Your answer will be considered as correct if it will have absolute error not more then 10^{-6}.
 
------ Constraints ------ 

1 ≤ T ≤ 5
1 ≤ N ≤ 10^{5}
1 ≤ A_{i} ≤ 10^{9}
1 ≤ B_{i} ≤ 10^{9}

----- Sample Input 1 ------ 
3
1
3
4
2
2 3
1 4
2
2 4
2 2
----- Sample Output 1 ------ 
1.000000
1.500000
0.000000
----- explanation 1 ------ 
Example case 1. Game will have only 1 turn. Chef will choose 3, while Sasha will choose 4. Since 34>43 girl will kiss boy. Hence answer is 1.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Probability

Sorting

Amortized analysis

Complete search

Mathematics

Ad-hoc


Solutions:
import bisect
import itertools

class Main:

	def __init__(self):
		iterable = self.__standard()
		self.__solution(iterable)

	def __solution(self, iterable):
		(cases,) = map(int, next(iterable).split())
		for _test in range(cases):
			(total,) = map(int, next(iterable).split())
			girl = map(int, next(iterable).split())
			boy = map(int, next(iterable).split())
			kisses = self.__kisses(girl, boy)
			print('{:.6f}'.format(kisses / total))

	def __kisses(self, girl, boy):
		girl = sorted(girl)
		boy = sorted(boy)
		kisses = 0
		for (x, group) in itertools.groupby(girl):
			count = 0
			for _item in group:
				count += 1
			current = 0
			if x == 1:
				pass
			elif x == 2:
				current += bisect.bisect_right(boy, 1)
				current += len(boy) - bisect.bisect_left(boy, 5)
			elif x == 3:
				current += bisect.bisect_right(boy, 2)
				current += len(boy) - bisect.bisect_left(boy, 4)
			else:
				current += bisect.bisect_right(boy, 1)
				current += len(boy) - bisect.bisect_right(boy, x)
			kisses += count * current
		return kisses

	def __test(self):
		yield '3'
		yield '1'
		yield '3'
		yield '4'
		yield '2'
		yield '2 3'
		yield '1 4'
		yield '2'
		yield '2 4'
		yield '2 2'

	def __standard(self):
		try:
			while True:
				yield input()
		except EOFError:
			pass
Main()


t = int(input())
for z in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	(count, count3, num, p, i) = (0, 0, 0, 0, 0)
	while i < n and a[i] == 1:
		i += 1
	while p < n and b[p] == 1:
		count += n - i
		p += 1
	while p < n and b[p] < 5:
		p += 1
	while i < n and a[i] == 2:
		count += n - p
		i += 1
	p = 0
	while i < n and a[i] == 3:
		count3 += 1
		i += 1
	while p < n:
		if b[p] == 2 or b[p] > 3:
			num += 1
		p += 1
	count += count3 * num
	p = 0
	while i < n and p < n:
		if b[p] > a[i]:
			count += n - p
			i += 1
		else:
			p += 1
	print(count / n)


from math import log
T = int(input())
while T > 0:
	T -= 1
	n = int(input())
	(count, incre, value1, value3) = (0, 0, 0, 0)
	dic1 = {}
	dic2 = {}
	x = list(map(int, input().split(' ')))
	y = list(map(int, input().split(' ')))
	for i in x:
		if i == 1:
			value1 += 1
		if i == 3:
			value3 += 1
		if i in dic1:
			dic1[i] += 1
		else:
			dic1[i] = 1
	for i in y:
		if i not in dic1:
			dic1[i] = 0
	for i in sorted(dic1):
		dic2[i] = dic1[i] + incre
		incre += dic1[i]
	for i in sorted(y):
		if i == 1:
			count += n - value1
		elif i == 2 or i == 4:
			count += value3
		elif i == 3:
			continue
		else:
			if i not in dic2:
				dic2[i] = 0
			if i not in dic1:
				dic1[i] = 0
			count += dic2[i] - dic1[i] - dic1[1]
	print(count / n)