BigJump | Topcoder Archive

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 int[] with N elements: the order in which you first step on the points. If there is no solution, return an empty int[].

Definition

Class:: BigJump
Method:: construct
Parameters:: int
Returns:: int[]
Method signature:: int[] construct(int N)
(be sure your method is public)

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.

Examples

```
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.
```
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.

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)2024, Topcoder, Inc. All rights reserved.