Reverse Game HackerRank Ruby Solution

Question

Problem Statement

Akash and Akhil are playing a game. They have N balls numbered from 0 to N−1. 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 N 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 0th position, then from 1st position, then from 2nd position and so on.

At the end of the game, Akhil will ask Akash the final position of any ball numbered K. Akash will win the game, if he can answer. Help Akash.

Input

The first line contains an integer \$T\$, i.e., the number of the test cases.

The next \$T\$ lines will contain two integers \$N\$ and \$K\$.

Output

Print the final index in array.

Constraints

• \$1 ≤ T ≤ 50\$
• \$1 ≤ N ≤ 10^5\$
• \$0≤K<N\$

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

test = gets.chomp.to_i
test.times do
   num, numbered = gets.split.map(&:to_i)
   a = []
   elem = 0 
   a << elem

  (num-1).times do
   elem += 1
   a << elem
  end


  len = a.length
  final = []
  w = []

 len.times do 
  if w.length == 0
   q = a.reverse
  else
   q = w.reverse
  end
  elem = q.shift
  final << elem
  w = q - [elem]
 end

 puts final.index(numbered)
end

My Problem

I could only pass 4 test cases out of 11 since it always timed out for the rest. This is happening because my solution isn't efficient enough. How can we do it efficiently so that it passes all 11 test cases?

Answer 1

Let's analyze what the problem is saying.

Let's say we start out with the array:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

We then reverse the elements of the array starting at element 0:

9, 8, 7, 6, 5, 4, 3, 2, 1, 0

Then, we reverse all elements except the 0th element:

9, 0, 1, 2, 3, 4, 5, 6, 7, 8

Then we reverse all elements except 0th and 1st element:

9, 0, 8, 7, 6, 5, 4, 3, 2, 1

And so on like so:

9, 0, 8, 1, 2, 3, 4, 5, 6, 7
9, 0, 8, 1, 7, 6, 5, 4, 3, 2
9, 0, 8, 1, 7, 2, 3, 4, 5, 6
9, 0, 8, 1, 7, 2, 6, 5, 4, 3
9, 0, 8, 1, 7, 2, 6, 3, 4, 5

To get the final result:

9, 0, 8, 1, 7, 2, 6, 3, 5, 4

The key thing to note here is that if take every odd-indexed element we get:

9, 8, 7, 6, 5

While every even-indexed element is:

0, 1, 2, 3, 4

So it looks like the final sequence is constructed like this:

• Split elements into lower half and upper half
• Reverse the order of the upper half
• Merge them by taking 1 element from upper half and 1 element from lower half and so on

This is an \$O(n)\$ process with the right implementation

All that remains is to then search the list for the given element (which is \$O(n)\$ in the worst case with a standard implementation), yielding a final computational time complexity of \$O(n)\$. That's it, right? Well it would be, if not for some interesting math.

---

If we apply some mathematical logic we can get an even faster solution:

• Decide if element is in lower half (which will have even indices) or the upper half (which will have odd indices) with a simple comparison to half the length of the array
• If element is in lower half: final index will be 1 + 2 * K (as 0 will be in 1st index, 1 will be in 3rd, 2 will be in 5th and so on)
• If element is in upper half: final index will be 2 * (N - 1 - K) (as N - 1 will be at 0, N - 2 will be at 2, N - 3 will be at 4 and so on)

This yields an \$O(1)\$ solution! Hurray for Math!

---

You can also simplify the logic a bit by noticing an interesting fact:

If you wrongly put an element from the upper half into the formula for the lower half and vice versa, an interesting thing happens: the final index will be out of the bounds of the array, and most importantly is greater than the index calculated from the other formula. The proof is left as an exercise, but this allows your entire program to boil down to:

min(1 + 2 * K, 2 * (N - 1 - K)) for every N, K pair

Note: this code ran in .05 sec for each trial under Python3.

---

Implementations are left as an exercise to the reader.

Answer 2

This is one way to do it.

Code

def final_pos(n)
  n.times.map {|j| [j, (j <= n/2-1) ? 2*j+1 : 2*(n-1-j)] }.to_h.invert
end

This returns a hash that gives the ball (value) at each offset position (key) after all rearrangements have been made.

Examples

final_pos(8).sort_by(&:first).to_h
  #=> {0=>7, 1=>0, 2=>6, 3=>1, 4=>5, 5=>2, 6=>4, 7=>3}
final_pos(10).sort_by(&:first).to_h
  #=> {0=>9, 1=>0, 2=>8, 3=>1, 4=>7, 5=>2, 6=>6, 7=>3, 8=>5, 9=>4}

I tacked .sort_by(&:first).to_h onto the end of final_pos merely to display the hash in order of increasing keys (positions).

Explanation

Let

n: number of balls
a = [0,1,2,..,n-1].reverse => [n-1,n2,...,0]
m: number of rearrangements of a
f(j,m): offset of ball j in a after m rearragements

Ball j will change positions in a until m rearrangements have been performed, at which time it will be at offset m, and will remain at that position (i.e., it will be at its final position). m therefore satisfies the following identity:

f(j,m) = m

Initially, ball j is at offset n-1-j in a. If j == n-1, it is offset zero, and therefore will remain at that location. For any other ball j < n-1, after one rearrangement if will be at offset:

n-1-(n-1-j)+1 => j+1

It can be inferred (and easily proved by induction) that after p rearrangements, if ball j has not yet been fixed in its final position, it will be at offset:

n-1-j+(p/2)

if n is even, and at offset

j+1+(p-1)/2

if n is odd. If ball j is fixed in is final position after p reaarrangements, at offset p of a, it follows that either p is odd and

n-1-j+(p/2) = p

or p is even and

j+1+(p-1)/2 = p

These identities reduce to:

p = 2*(n-1-j) # `p` even
p = 2*j+1     # `p` odd

Suppose j <= n/2-1. Then:

p = 2*(n-1-j) >= 2*(n-1-((n/2)-1)) = n    # `p` even
p = 2*j+1     =< 2*(((n/2)-1)+1)-1 = n-1  # `p` odd**

whereas if j > n/2-1:

p = 2*(n-1-j) < 2*(n-1-((n/2)-1)) = n   # `p` even**
p = 2*j+1     > 2*(((n/2)-1)+1)-1 = n-1 # `p` odd

It follows that for j <= n/2-1, the odd expression of p applies and for larger values of j the even expression applies.

We form a hash that maps j into p and then invert the hash to map p into j.