Get Time

   Problem Statement  

 Problem Statement for TheSwapsDivOne

Problem Statement

    John has a sequence of digits. He and Brus will now play with the sequence.

First, John will repeat the following operation k times: He will choose two different positions in the sequence, and swap the elements at those positions. (John makes each choice uniformly at random. That is, each time John chooses two positions, each pair of different positions has the same probability of being chosen.)

Afterwards, Brus will randomly choose a non-empty contiguous subsequence of John's sequence. He will compute the sum of all elements in the chosen subsequence and he will write it down on a piece of paper. (Brus also makes his choice uniformly at random. That is, each possible contiguous subsequence has the same probability of being chosen.)

You are given a String[] sequence. Concatenate all elements of sequence to get the string s. For each i, the i-th character of s is a digit ('0'-'9') representing the digit at index i in John's original sequence.

Return the expected value of the sum Brus writes down.


Parameters:String[], int
Method signature:double find(String[] sequence, int k)
(be sure your method is public)


-The returned value must be accurate to within a relative or absolute value of 1E-9.


-sequence will contain between 2 and 47 elements, inclusive.
-Each element of sequence will contain between 1 and 47 characters, inclusive.
-Each element of sequence will consist of only decimal digits ('0'-'9').
-k will be between 1 and 1,000,000, inclusive.


{"4", "77"}
Returns: 10.0
There are three equally likely swaps John might make. If the first two elements are swapped, John will get the sequence {7,4,7}. Then Brus chooses one of the six possible subsequences. Their sums are 7, 4, 7, 11, 11 and 18. Thus the expected value is (7 + 4 + 7 + 11 + 11 + 18)/6 = 29/3.

If the first and the last elements are swapped, the sequence becomes {7,7,4}, and the subsequence sums are 7, 7, 4, 14, 11 and 18. The expected value in this case is (7 + 7 + 4 + 14 + 11 + 18)/6 = 61/6.

When the last two elements are swapped, the sequence doesn't change and the expected value is equal to 61/6 as well. Finally, the overall expected value is equal to (29/3 + 61/6 + 61/6)/3 = 10.
{"4", "77"}
Returns: 10.0
{"1", "1", "1", "1", "1", "1", "1"}
Returns: 3.0
{"572685085149095989026478064633266980348504469", "19720257361", "9", "69"}
Returns: 98.3238536775161

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 575 Round 1 - Division I, Level Two