Little Elephant and Bubble Sort

Problem code: LEBOBBLE

All submissions for this problem are available.

Little Elephant loves bubble sorting.

Bubble sorting for any array A of n integers works in the following way:

var int i, j;
for i from n downto 1
{
for j from 1 to i-1
{
if (A[j] > A[j+1])
swap(A[j], A[j+1])
}
}

You are given an array B of n integers. Then the array A is created using array B as following : for each i (1 <= i <= n), we set Ai = Bi + d with the probability Pi, otherwise Ai = Bi.

Help Little Elephant to find the expect number of swaps that bubble sorting will make when the array A is sorted with the above bubble sorting algorithm.

Input

First line of the input contains single integer T - the number of test cases. T test cases follows. First line of each test case contains pair of integers n and d. Next line of each test case contains n integers - array B. Next line contains n integers - array P.

Output

In T lines print T real numbers - the answers for the corresponding test case. Please round all numbers to exactly 4 digits after decimal point.

Constraint

1 <= T <= 5

1 <= n <= 50000

1 <= Bi, d <= 10^9

0 <= Pi, <= 100

Example

Input:
2
2 7
4 7
50 50
4 7
5 6 1 7
25 74 47 99

Output:
0.2500
1.6049
Author: witua
Tester: laycurse
Editorial http://discuss.codechef.com/problems/LEBOBBLE
Date Added: 10-05-2012
Time Limit: 6 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

can somebody explain how do

nitish712 @ 1 Jul 2012 07:02 PM
can somebody explain how do we get the answer for the 2nd case???

@admin plz reply

nitish712 @ 1 Jul 2012 07:25 PM
@admin plz reply

Please clarify A[i] = B[i] +

a1_b21991 @ 1 Jul 2012 07:29 PM
Please clarify A[i] = B[i] + d with the probability Pi, otherwise A[i] = B[i]

This means that before

witaliy_adm @ 1 Jul 2012 09:51 PM
This means that before sorting (using bubble sort) array A is created. To each element of A must be assigned some number. With the probability Pi it is Bi + d, and with the probability (100-Pi) it is Bi.

does that mean that if Pi is

sharod @ 1 Jul 2012 10:20 PM
does that mean that if Pi is greater than (100-Pi) then Ai=Bi+d,otherwise Ai=Bi?

admin plz reply soon

sharod @ 1 Jul 2012 10:21 PM
admin plz reply soon

@sharod No, the array A isn't

hiroto_adm @ 1 Jul 2012 10:32 PM
@sharod No, the array A isn't created by deterministic. Anyway "with probability P[i]" should be "with probability P[i]%".

plz explain the test cases.

abhinav321000 @ 2 Jul 2012 04:06 AM
plz explain the test cases.

please explain test case and

johncena10 @ 2 Jul 2012 12:17 PM
please explain test case and their answer?

@ admin please explain the

selfcompiler @ 2 Jul 2012 12:45 PM
@ admin please explain the test cases :)

Can anyone explain a single

abhinav1 @ 2 Jul 2012 02:58 PM
Can anyone explain a single test case.?? The problem statement is not clear. Please explain " Ai = Bi + d with the probability Pi, otherwise Ai = Bi." How do we create the array A??

Please tell me if I'm

abhinav1 @ 2 Jul 2012 03:03 PM
Please tell me if I'm wrong.....There are Pi% chances that Ai=Bi+d and (100-Pi)% chances that Ai=Bi....We need to find expected number of swaps to sort array A using bubble sort. Am I right??

In the first sample there are

witaliy_adm @ 2 Jul 2012 03:11 PM
In the first sample there are 4 possibilities, each with probability 25%: (4, 7), (11, 7), (4, 14), (11, 14). The second case requires a single swap, when the rest are already sorted. Hence, he answer is 0.25.

@all : I cannot understand

phantom11 @ 2 Jul 2012 08:31 PM
@all : I cannot understand why the problem us not clear to u ... The problem states that each of the elements of array A can take 2 values.. i.e.A[i]=B[i] or B[i]+d .. It is B[i] with prob P[i] and B[i]+d with prob 100-P[i]..

@phantom11: Your last

imgpsingh @ 3 Jul 2012 12:08 AM
@phantom11: Your last statement has a mistake. The correct thing is : "It is B[i] with prob 100-P[i] and B[i]+d with prob P[i]".

@phantom11: I get it but what

programme @ 3 Jul 2012 12:54 AM
@phantom11: I get it but what next? The probabilities thing is fine, but then what are the output "fractions" (Is the no. swap multiplied by fraction of the particular array or what)? I surely hope one should not be so evasive about it. If so, one must specify : "No more questions".

@imgpsingh: I admit...My

phantom11 @ 3 Jul 2012 04:18 AM
@imgpsingh: I admit...My mistake... @programme: You have to find the expected value.. It is calculated as: p1*x1+p2*x2+p3*x3.... and so on...where pi's are the probabilty and xi's are the values (number of swaps) ... I hope now it is crystal clear

@phantom11 : It is indeed

programme @ 4 Jul 2012 04:30 AM
@phantom11 : It is indeed very clear now. Thanks a lot.

@admin what does round number

sarthak @ 7 Jul 2012 10:53 PM
@admin what does round number to 4 digits after decimal point mean? What exactly are u expecting from this? plz give example(s)

@sarthak: by "round to

witaliy_adm @ 8 Jul 2012 07:09 PM
@sarthak: by "round to exactly 4 digits after the decimal point" we mean that you should output answer in form "xx..xx.xxxx", i. e. there must be exactly 4 digits after '.'. For example, number 47.4520, 0.0000, 2.0100 are all rounded to exactly 4 digits, when 47.5 and 101.000 are not.

finally giving up !!!

shashwat001 @ 11 Jul 2012 02:58 PM
finally giving up !!!

SUCCESSFUL SUBMISSIONS


Fetching successful submissions