Challenge Overview
Important Links
- Submission-Review You can find your submissions artifacts here. Artifacts will contain output.txt's for both example test cases and provisional test cases with stdout/stderr and individual test case scores.
- Other Details: For other details like Processing Server Specifications, Submission Queue, Example Test Cases Execution.
Overview
You are given a sequence S containing N numbers in the range [0, K). Your task is to sort this sequence into monotonically increasing order, in a way that incurs the smallest penalty. You are allowed to select any contiguous sub-sequence of numbers and reverse their order. Formally, if the sub-sequence is (S[i], S[i+1], ..., S[k-1], S[k]), where 0 <= i < k < N, then its reversal is (S[k], S[k-1], ..., S[i+1], S[i]). The penalty incurred by this reversal is floor[(k-i+1)^X], where X is a given penalty parameter. Your task is to minimize the total penalty incurred by all the reversals.Here is a solution for seed=1 with N=10, K=5 and X=1.0. The sub-sequences being reversed are shown inside brackets:
Input sequence:
1 1 1 0 3 0 1 1 2 4
Move 1, move score 2, total score 2
1 1 1 0 (3 0) 1 1 2 4
Move 2, move score 3, total score 5
1 1 1 0 0 (3 1 1) 2 4
Move 3, move score 5, total score 10
(1 1 1 0 0) 1 1 3 2 4
Move 4, move score 2, total score 12
0 0 1 1 1 1 1 (3 2) 4
Sorted sequence:
0 0 1 1 1 1 1 2 3 4
Input
Your code will receive as input the following values, each on a separate line:- N, the length of the sequence.
- K, the maximum number of distinct values in the sequence.
- X, the penalty parameter.
Output
Your code should write to output the following:- On the first line, R, the number of reversal to perform.
- R lines, each representing a single reversal. The format should be "i k" (without the quotes), where i is the starting index and k is the ending index of the reversal (i < k, both 0-based).
Scoring
The scorer will compute the total penalty incurred by the reversals.If your return was invalid, then your raw score on this test case will be -1. Possible reasons include:
- Using more than floor[(N*N)/2] reversals.
- Using invalid characters or incorrectly formatted reversals.
- Using indices that are out of bounds.
Test Case Generation
Please look at the generate() method in visualizer's source code for the exact details about test case generation. Each test case is generated as follows:- The length of the sequence N is chosen between 10 and 1000, inclusive.
- The maximum number of distinct values K is chosen between 2 and N, inclusive.
- The penalty parameter X is chosen between 0.0 and 3.0, inclusive.
- Generate N sequence values, each in the range [0, K).
- All values are chosen uniformly at random.
Notes
- The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
- The compilation time limit is 30 seconds.
- There are 10 example test cases and 100 full submission (provisional) test cases. There will be 2000 test cases in the final testing.
- The match is rated.
Languages Supported
C#, Java, C++ and Python
Submission Format
Your submission must be a single ZIP file not larger than 500 MB, with your source code only.
Please Note: Please zip only the file. Do not put it inside a folder before zipping, you should directly zip the file.
SAMPLE SUBMISSIONS
Here are example solutions for different languages, modified to be executed with the visualizer. You may modify and submit these example solutions.- Java Source Code - ReversalSort.java
- C++ Source Code - ReversalSort.cpp
- Python3.6 Source Code - ReversalSort.py
- C# Source Code - ReversalSort.cs
Tools
An offline tester is available below. You can use it to test/debug your solution locally. You can also check its source code for an exact implementation of test case generation and score calculation. You can also find links to useful information and sample solutions in several languages.DOWNLOADS
OFFLINE TESTER / VISUALIZER
In order to use the offline tester/visualizer tool for testing your solution locally, you'll have to include in your solution the main method that interacts with the tester/visualizer via reading data from standard input and writing data to standard output.To run the tester with your solution, you should run:
java -jar ReversalSort.jar -exec "<command>" -seed <seed>
Here, <command> is the command to execute your program, and <seed> is seed for test case generation.
If your compiled solution is an executable file, the command will be the full path to it, for example, "C:\TopCoder\ReversalSort.exe" or "~/topcoder/ReversalSort".
In case your compiled solution is to be run with the help of an interpreter, for example, if you program in Java, the command will be something like "java -cp C:\TopCoder ReversalSort".
Additionally you can use the following options:
- -seed <seed> Sets the seed used for test case generation, default is seed 1.
- -debug Print debug information.
- -N <N> Sets a custom sequence length.
- -K <K> Sets a custom maximum number of distinct values.
- -X <X> Sets a custom penalty parameter.
Marathon local testers also have other options, including running a range of seeds with a single command, running more than one seed at time (multiple threads), controlling time limit, saving input/output/error and loading solution from a file. The usage of these other options are described here.