You are not logged in. Please login at to post your questions!


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.

asked 12 Jan, 15:14

mmmreddy's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 12 Jan, 15:14

question was seen: 99 times

last updated: 12 Jan, 15:14