Jolly Jumpers..~

Problem Statement
     
You are given a vector <int> permutation containing a permutation of the first n positive integers (1 through n), and you want to sort them in ascending order. To do this, you will perform a series of swaps. For each swap, you consider all pairs (i, j) such that i < j and permutation[i] > permutation[j]. Among all those pairs, you choose one randomly and swap permutation[i] and permutation[j]. Each pair has the same probability of being chosen. Return the expected number of swaps needed to sort permutation in ascending order.
Definition
   
Class:
RandomSort
Method:
getExpected
Parameters:
vector <int>
Returns:
double
Method signature:
double getExpected(vector <int> permutation)
(be sure your method is public)
   
 
Notes
-
The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
-
permutation will contain between 1 and 8 elements, inclusive.
-
permutation will contain each integer between 1 and n, inclusive, exactly once, where n is the number of elements in permutation.
Examples
0)
 
   
{1,3,2}
Returns: 1.0
Exactly one swap is needed.
1)
 
   
{4,3,2,1}
Returns: 4.066666666666666
In the first step, any two elements can be swapped.
2)
 
   
{1}
Returns: 0.0
This permutation is already sorted, so there's no need to perform any swaps.
3)
 
   
{2,5,1,6,3,4}
Returns: 5.666666666666666
 
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)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
Given a vector <string> board, concatenate all its elements, in order, to get a single string representing a circular board consisting of uppercase 'X' and '.' characters. "Circular" means that the first and the last characters on the board are consecutive. Maximal consecutive groups of 'X' characters form blocks and maximal consecutive groups of '.' characters form gaps. The size of the gap is the number of '.' characters in it.
You want to remove exactly one block from the board, getting a circular board of smaller size. For each possible block to be removed consider the board after its removal, construct an array of all gaps' sizes on the board and sort this array in non-ascending order. Choose the block for which the described array is lexicographically maximal (see notes for the description of lexicographical array comparison). Return the smallest 0-based index among all characters in this block (indices are taken in the concatenated string). In case of a tie choose the block which results in the smallest return value.
Definition
   
Class:
LargestGap
Method:
getLargest
Parameters:
vector <string>
Returns:
int
Method signature:
int getLargest(vector <string> board)
(be sure your method is public)
   
 
Notes
-
Let vector <int>s A and B contain the same number of elements. Then A is lexicographically larger than B if A contains a larger value at the first position where A and B differ.
Constraints
-
board will contain between 1 and 50 elements, inclusive.
-
Each element of board will contain between 1 and 50 characters, inclusive.
-
board will contain only uppercase 'X' and '.' characters.
-
board will contain at least two blocks.
Examples
0)
 
   
{".....X.X......."}
Returns: 5
Remove the first block.
1)
 
   
{"XXXX","....","XXXX","....","XXXX","...."}
Returns: 0
There are three blocks whose smallest indices are 0, 8, 16, respectively.
The board after removing each of the blocks look as follows:
The 1st block: "....XXXX....XXXX....".
The 2nd block: "XXXX........XXXX....".
The 3rd block: "XXXX....XXXX........".
All three results produce the same gaps array {8,4}. So we return the smallest index among {0,8,16}.
2)
 
   
{"XXX.........XX...........XX..X"}
Returns: 12
There are three gaps and three blocks (recall that the board is circular).
3)
 
   
{"XXX","X.....","....XX..XXXXXX","X........X..",".XXX."}
Returns: 32
There are 5 blocks and 5 gaps. There are two ways to maximize the largest gap, but only one of them also maxmizes the second largest one.
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)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
You are given a vector <string> digits. Concatenate the elements of digits to get one large string. Then, insert spaces to divide it into a list of strictly increasing integers (leading zeros are allowed). If there are multiple ways to do this, minimize the last integer. If there are still multiple solutions, maximize the first integer. If multiple solutions still remain, maximize the second integer, then the third one, etc. Return the product of all the integers in the list, modulo 1,000,000,003.
Definition
   
Class:
IncreasingSequence
Method:
getProduct
Parameters:
vector <string>
Returns:
int
Method signature:
int getProduct(vector <string> digits)
(be sure your method is public)
   
 
Notes
-
Two integers that differ only by the number of leading zeros they contain (for example, 0123 and 00123, or 95 and 00095) are considered equal (i.e., neither of them is less than the other).
Constraints
-
digits will contain between 1 and 50 elements, inclusive.
-
Each element of digits will contain between 1 and 50 characters, inclusive.
-
Each element of digits will contain digits ('0'-'9') only.
-
The first character of the first element of digits will not be '0'.
Examples
0)
 
   
{"12345"}
Returns: 120
Each single character can be an integer. The sequence 1, 2, 3, 4, 5 is strictly increasing.
1)
 
   
{"543210"}
Returns: 45150
The best thing we can get is 5, 43, 210.
2)
 
   
{"20210222"}
Returns: 932400
There are multiple ways to divide this string. The minimal last integer among all solutions is 222. There are four solutions where the last integer is 222:
2 021 0222
2 0210 222
20 21 0222
20 210 222
The last two solutions are better than the first two, because 20 > 2. And the last solution is the best one, because 210 > 21. So we need to return 20 * 210 * 222 = 932,400.
3)
 
   
{"1111111111"}
Returns: 1356531
Adjacent integers should never be equal to each other, so the optimal solution here is 1, 11, 111, 1111.
4)
 
   
{"171829294246"}
Returns: 385769340
Though we can try to start the sequence by 1, 7, 18, 29, we'll soon find that the only way to finish it is with 294246, which is unsatisfactory. The optimal sequence is 1, 71, 82, 92, 94, 246. The product is 12,385,769,376, which gives 385,769,340 as a remainder, when divided by 1,000,000,003.
5)
 
   
{"3","235","236"}
Returns: 264320
The last integer must be 236. But the sequence 3, 235, 236 is not optimal. We can maximize the first integer in 32, 35, 236, the product is 32 * 35 * 236 = 264,320.
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)2003, TopCoder, Inc. All rights reserved.