Bogo Sort
Time limit4sMemory limit1024 MB
Sort a hidden permutation using only calls that randomly shuffle a chosen contiguous segment and report the shuffled result.
- Level
Medium7 of 10
- Topics
- Sorting, Probability, Greedy, Implementation
- Solved
- No attempts yet
Problem
Bogo sort is a sorting algorithm that repeatedly shuffles randomly until the array is sorted.
In this problem, the grader holds a permutation A0, ..., A**N-1 of length N consisting of the integers from 0 to (N - 1). You must sort this permutation using only repeated operations that pick some contiguous segment and shuffle it randomly.
Fortunately, you can 'observe' how the random shuffle happened and decide your next operation.
Input
The sample grader reads the following information from standard input. You must not read any input.
The first line gives a natural number N, the length of the permutation.
The second line gives N integers A0, ..., A**N-1 separated by spaces.
Output
The sample grader writes the following information to standard output. You must not write any output.
If you sort the permutation correctly, the sample grader prints "Accepted" on the first line. It also prints on the second line the number of calls to the two functions copy_array and shuffle_array, respectively.
Constraints
Every input satisfies the following conditions.
- 1 ≤ N ≤ 200
- 0 ≤ Ai < N (0 ≤ i < N)
- Ai ≠ Aj (0 ≤ i < j < N)