Reverse Game - Hackerrank solution

Reverse Game - Hackerrank solution:
Welcome back Guys !!
Today we will be discussing the   Reverse Game  hackerrank problemof section Mathematics
It involves beautiful use of combinatorics....
Lets get started...

Problem Statement to hackerrank problem  Reverse Game is as follows:

Akash and Akhil are playing a game. They have  balls numbered from  to . Akhil asks Akash to reverse the position of the balls, i.e., to change the order from say, 0,1,2,3 to 3,2,1,0. He further asks Akash to reverse the position of the balls  times, each time starting from one position further to the right, till he reaches the last ball. So, Akash has to reverse the positions of the ball starting from  position, then from  position, then from  position and so on. At the end of the game, Akhil will ask Akash the final position of any ball numbered . Akash will win the game, if he can answer. Help Akash.

Input Format
The first line contains an integer , i.e., the number of the test cases.
The next  lines will contain two integers  and .

Output Format
Print the final index of ball  in the array.

Constraints

Sample Input

2
3 1
5 2

Sample Output

2
4

Explanation
For first test case, The rotation will be like this:
0 1 2 -> 2 1 0 -> 2 0 1 -> 2 0 1
So, Index of 1 will be 2.

Solution Code to hackerrank problem  Reverse Game is as follows:

IF you analysis properly by tracing the permutations. You start with

0 1 2 3 ... (N-3) (N-2) (N-1)

The first operation flips the whole thing:

(N-1) (N-3) (N-2) ... 3 2 1 0

The second operation fixes the first, and flips the other N-1:

(N-1) 0 1 2 3 ... (N-2) (N-3)

The third operation fixes the first two and flips the other N-2:

(N-1) 0 (N-2) (N-3) ... 3 2 1.

The fourth operation fixes the first three and flips the other N-3:

(N-1) 0 (N-2) 1 2 3 ... (N-3).

Et cetera.

If you trace this out with a small example, you'll see that this process ends with ball number (N - 2 + N%2)/2, which should basically be the 'middle' of the original list, at the end. Note that the N%2 in this formula just handles the even and odd cases together: when N is even, the last number is (N - 2)/2 and when N is odd, the last number is (N - 1)/2.

Since every other step you reduce to the same problem with one less ball, this is amenable to induction if you wanted to write a formal proof.

For n = 5, the last number in the list is (5 - 2 + 1)/2 = 4/2 = 2.

0: 0 1 2 3 4

1: 4 3 2 1 0

2: 4 0 1 2 3

3: 4 0 3 2 1

4: 4 0 3 1 2

For n = 6, the last number in the list is (6 - 2 + 0)/2 = 4/2 = 2.

0: 0 1 2 3 4 5

1: 5 4 3 2 1 0

2: 5 0 1 2 3 4

3: 5 0 4 3 2 1

4: 5 0 4 1 2 3

5: 5 0 4 1 3 2

If you think about the resulting arrangement geometrically, it becomes pretty clear where the formula comes from. Think about the original sequence of numbers as an array or something.

1. Break the list somewhere so that the two pieces are either of equal size (N is even), or there is one more element on the right (N is odd).
2. Think of the things on the left as taking the odd positions, while the things on the right take the even positions.
3. Fold (like paper) the right side over the left.
4. Now merge the lists back together in the obvious way.

Concretely, here are two small cases.

N = 5:

1. 0 1 2 3 4 breaks into 0 1 and 2 3 4.
2. Rewrite the left so it fits in the odd positions and rewrite the right so it fits in the even positions:

_ 0 _ 1 and 2 _ 3 _ 4

3. Flip the one on the right (keeping the spaces) and stack it on top of the one on the left:

4 _ 3 _ 2

_ 0 _ 1

4. Now merge them back together to get

4 0 3 1 2.

N = 6:

1. 0 1 2 3 4 5 breaks into 0 1 2 and 3 4 5.
2. Rewrite the left so it fits in the odd positions and rewrite the right so it fits in the even positions:

_ 0 _ 1 _ 2 and 3 _ 4 _ 5.

3. Flip the one on the right (keeping the spaces) and stack it on top of the one on the left:

5 _ 4 _ 3

_ 0 _ 1 _ 2

4. Now merge them back together to get

5 0 4 1 3 2.

#include <iostream>

using namespace std;

int f(int N, int K) { return K < N / 2 ? 2 * K + 1 : 2 * (N - K - 1); }

int main() {

  int T;

  cin >> T;

  for (int i = 0; i < T; i++) {

    int N, K;

    cin >> N >> K;

    cout << f(N, K) << endl;

  }

  return 0;

}
I hope this problem has added valuable knowledge to you.

Please go through the solution properly.

Feel free to share your thoughts in the comment section below.

See you next time...