RTTE - Editorial

Race To The End (RTTE)

Tags: Complete Search, Shortest path in DAG.


Author: Naman.
Tester: Shami.

There are two possible approaches for this problem.

Brute force
Since the limit on N is very small, we can try all possible combinations and find the result. We can store the minimum steps to reach each index in an array (arr).


  1. Start from index 0. a[0] = 0
  2. For each index ‘i’, we update value of a[i] = min(a[i], a[i+1]+1)
    we don’t need to check a[i-1] as it would already have been processed because we started from left.
  3. Find all indices j to the right such that a[j] == a[i]
    a. For each j, update all left indices similar to step #2.
  4. Answer is stored in a[N-1].


Let’s consider each index ‘i’ as a node and all possible moves as directed edges. So the edges from A[i] will be

  1. A[i-1]
  2. A[i+1]
  3. All A[j] such that A[j] == A[i]

Complexity to generate graph: O(N^2)

Notice that the directed graph may have back edges, but it does not matter in our case. Now we can apply BFS starting from index 0 and count the minimum number of levels to reach N. The number of levels is the answer.