Sereja and Two Arrays
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja and Arrays
Sereja have an array that consist of n integers a, a, ..., a[n]. Also Sereja have an array that consist of m integers b, b, ..., b[m]. Sereja make next operations:
- random_shuffle(b) — shuffle elements of b
- random_merge(a, b) — merge array a and b to array a. From all possible merges Sereja chooses a random one. For better understanding you can imagine, that merged array is sequence q of n+m elements, each element if either zero or one. It contains exactly n zeroes and m ones. Then zeroes are replaced with elements of a, and ones are replaced with elements of b (without changing their relative order inside initial sequences).
Now Sereja want to know expected number of inversions in array a after described operations. Inversion is a pair (i, j) (1 ≤ i < j ≤ n + m) such that a[i] > a[j].
First line contain number T — number of testcases. T tests follow. First line of each testcase contain two integers n and m. Next line contain n integers a, a, ..., a[n]. Next line contain m integers b, b, ..., b[m].
For each testcase print expected number of inversions.
- 1 ≤ T ≤ 7
- 1 ≤ n,m ≤ 10^5
- 1 ≤ a[i], b[i] ≤ 10^5
Input: 2 5 3 1 5 4 3 2 2 6 3 10 9 10 3 6 4 8 4 1 9 7 2 9 8 3 3 10 8 2 9 2 Output: 13.833333333 87.818181818
Test #0-1 (25 points): n,m ≤ 10
Test #2 (25 points): n,m ≤ 1000
Test #3-4 (50 points): n,m ≤ 100000
|Tags||fenwick, inversions, ltime09, maths, medium, sereja|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.