Sereja and Bubble Sort
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja has an array A that contains n integers, namely A1, A2, ..., An. A single action consists of performing one of two following operations:
- To swap two consecutive elements;
- To make a random and uniform shuffle of all the elements of the array A.
Now Sereja's goal is to make the expected value of the function f(A) as minimal as possible, by doing no more than k actions.
The function f(A) is the minimal number of consecutive elements' swaps you need in order to sort the array A in the increasing order.
What is the expected value of f(A) in case Sereja uses no more than k actions in the optimal way?
The first line contains an integer T, denoting the number of testcases. Then, T testcase descriptions follow.
The first line of each desription contains the integers n and k from the statement, respectively. The following line contains n space separated integers - A1, A2, ..., An. All the values of Ai will form a permutation of the first N natural numbers.
For each test case output the minimal possible expected value of f(A). Your answer will be considered correct in case it differs by no more than 10-6 from the official one.
- 1 ≤ T ≤ 100
- 1 ≤ n ≤ 100
- 0 ≤ k ≤ 1018
- 1 ≤ Ai ≤ n
Input: 2 2 1 2 1 3 1 3 2 1 Output: 0.0000 1.5000
|Tags||dynamic-programming, expectation, medium, sept14, sereja|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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.