Connection Status:
Competition Arena > ShuffleSort

ShuffleSort

SRM 568 · 2012-12-13 · by ltaravilse

SRM 568 · 2012-12-13 · by ltaravilse · Dynamic Programming
Class Name: ShuffleSort
Return Type: double
Method Name: shuffle
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Fox Ciel has a deck of N cards numbered from 0 to N-1, inclusive. For each i, the i-th card has an integer cards[i] written on it. It is possible that the integers written on some cards are the same. Such cards are indistinguishable.

Ciel wants to sort the cards. More exactly, she wants to place them in a line on the table so that the integers on the cards form a non-decreasing sequence. To achieve this goal, she takes the entire deck into her hand and applies the following process (starting from step 1).
  1. She shuffles all cards in her hand. This is equivalent to permuting the order of cards uniformly at random.
  2. Let X be the smallest of all integers written on cards she still holds in her hand. Ciel checks the topmost card of the deck she just shuffled. If the card contains an integer greater than X, she proceeds to step 1. Otherwise, she places the card onto the table. (If there are already some cards on the table, the new card is placed on their right to extend the line of sorted cards.) After she does that, if she has no more cards in her hand, she is done. Otherwise, she repeats step 2 (without shuffling the deck!).
Given the int[] cards, return the expected number of times that step 1 (a shuffle of the deck) will be executed during the sorting process described above.

Notes

  • The return value must have a relative or an absolute error of less than 1e-9.
  • Informally, the return value can be seen as the average number of card shuffles required to sort a given deck of cards (where the average is taken over very many rounds of the experiment). For a formal definition, you can check http://en.wikipedia.org/wiki/Expected_value.

Constraints

  • cards will contain between 1 and 50 elements, inclusive.
  • Each element of cards will be between 1 and 50, inclusive.
Examples
0)
{1}
Returns: 1.0

There is just 1 card, but Ciel will still shuffle the cards once anyway.

1)
{1,2}
Returns: 2.0

After a single shuffle of the cards, their order from top to bottom can be (1, 2) or (2, 1). If it is (1, 2), then both cards will be placed on the table and the process will stop. Otherwise, no cards will be placed on the table and shuffle will have to be repeated. In average, the process will end after 2 card shuffles.

2)
{2,3,1}
Returns: 4.0

The elements of cards are not necessarily given in a sorted order.

3)
{15,16,4,8,42,23}
Returns: 16.0
4)
{1,1,1,1,1,1,1,1}
Returns: 1.0

All cards are the same, so just one shuffle is always enough.

Submissions are judged against all 59 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ShuffleSort with a public method double shuffle(vector<int> cards) · 59 test cases · 2 s / 256 MB per case

Submitting as anonymous