TheSwapsDivOne
SRM 575 · 2012-12-13 · by Vasyl[alphacom]
Problem Statement
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
Return the expected value of the sum Brus writes down.
Notes
- The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
- 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"}
1
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"}
47
Returns: 10.0
{"1", "1", "1", "1", "1", "1", "1"}
1000000
Returns: 3.0
{"572685085149095989026478064633266980348504469", "19720257361", "9", "69"}
7
Returns: 98.3238536775161
{"1652032429911007", "547420218806349319256", "0163197091083813015782", "45886495561569867943", "71858041493356764841426836575808", "316625261873581203866991044993470248548647", "315167", "041479578798", "5813855100465408673907745961503719014103", "1339492822022683257344", "917074984523152384501095786", "9996138678622894935145757540553475217415796544", "478868905", "11873099891526193114937789648327683529116", "433347", "206504728324689215908815", "63706", "6", "8209877114319", "14853", "879031633374148493762638533329", "453659180159552453943568", "298893659564697923600054452", "54248943558227734556538762532351241553", "0897169365545393630469914685037394336558351624", "71440977", "99", "17893815059146271523024434632056482965116749", "845109", "659271053948657342659219311121775858685738483", "11114395317835840375202777013255835", "910681218357650846946", "62366447413", "690306575831679853", "71324059566096657933123793076021398685873936979", "570672685794269958", "1239437891746781633967520838878238", "8734595290108757695279433833304893784096290", "13355594072205852861049111757", "2582765453926897625323"}
249874
Returns: 1499.7912317327769
Submissions are judged against all 71 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheSwapsDivOne with a public method double find(vector<string> sequence, int k) · 71 test cases · 2 s / 256 MB per case