BigJump
2020 TCO Round 4 · 2020-04-13 · by misof
Problem Statement
N points labeled 0 to N-1 are arranged around a circle in clockwise order. The number N is even.
The first point counter-clockwise from point x is called the predecessor of x. Note that the predecessor of 0 is N-1.
Whenever you stand on some point x, you have two options how to move:
- The big jump will take you to the point (2*x) modulo N.
- The almost big jump will take you to the predecessor of the point you would reach by the big jump: the point (2*x-1) modulo N.
Determine whether it is possible to start on some point, step on each other point exactly once and return to the point where you started.
If yes, find any one such solution and return it as a
Notes
- Remember that in a valid solution it must also be possible to move from the last element of your return value back to its first element.
Constraints
- N will be between 2 and 3000, inclusive.
- N will be even.
2
Returns: {0, 1 }
4
Returns: {0, 3, 1, 2 }
6
Returns: {0, 5, 4, 1, 2, 3 }
Using A to denote an almost big jump and B to denote a big jump, the return value corresponds to starting at point 0 and performing the sequence of jumps A, B, A, B, A, B.
8
Returns: {0, 7, 6, 3, 5, 1, 2, 4 }
10
Returns: {0, 9, 8, 6, 1, 2, 4, 7, 3, 5 }
12
Returns: {0, 11, 10, 8, 4, 7, 1, 2, 3, 5, 9, 6 }
There are other valid solutions. For example, {10, 7, 1, 2, 4, 8, 3, 6, 0, 11, 9, 5} is also a valid solution.
Submissions are judged against all 102 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BigJump with a public method vector<int> construct(int N) · 102 test cases · 2 s / 256 MB per case