SlideCardsLeft | Topcoder Archive

Problem Statement

Basha is playing with cards. She has N cards, numbered 0 through N-1. All cards are arranged into a single row. The positions in the row are also numbered 0 through N-1, from left to right. Initially, each card number matches its position.

Basha's game is played in turns. Each turn looks as follows:

Basha chooses a positive integer x (i.e., not 0) such that card x is currently at position x.
Basha chooses a positive integer y <= x.
Basha takes the card x and moves it y positions to the left. (When she does so, some other cards get moved one position to the right to make room for card x.)

For example, if Basha chooses x = 5 and y = 2 in the initial position {0, 1, 2, 3, 4, 5, 6, 7}, she will get the position {0, 1, 2, 5, 3, 4, 6, 7}. Note that in the next step she cannot choose x = 5 again, as now card 5 isn't at position 5 any more.

The game ends when there are no more moves left. Sooner or later this will always happen.

Basha's goal is to make as many moves as possible. She always plays the game optimally.

You are given the int N and the long steps: the number of steps of the game Basha already performed. Find and return one possible sequence of cards at this point of the game. Any valid solution will be accepted.

If steps exceeds the maximum number of steps in the game for the given N, return an empty int[] instead.

Definition

Class:: SlideCardsLeft
Method:: getPosition
Parameters:: int, long
Returns:: int[]
Method signature:: int[] getPosition(int N, long steps)
(be sure your method is public)

Constraints

N will be between 1 and 500, inclusive.
steps will be between 0 and 10^12, inclusive.

Examples

```
2
```
```
0
```
```
Returns: {0, 1 }
```
With two cards and no steps we are still in the initial position.
```
2
```
```
1
```
```
Returns: {1, 0 }
```
In the initial position we have to choose x = 1 and y = 1. After we slide card 1 one step left, we get the position shown in the example output.
```
2
```
```
2
```
```
Returns: { }
```
In the position shown in output of Example 1 there are no more moves left, so the game was already over after one step.
```
7
```
```
5
```
```
Returns: {1, 3, 2, 0, 4, 5, 6 }
```
For N = 7 there is an optimal solution such that after five steps the numbers on Basha's cards, read from left to right, are 1, 3, 2, 0, 4, 5, 6. (That is, card 1 is at position 0, card 3 is at position 1, and so on.)

Returns: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46 }

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.