×

# RTTE - Editorial

 0 Race To The End (RTTE) Tags: Complete Search, Shortest path in DAG. Problem: practice 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). Steps: Start from index 0. a[0] = 0 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. 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. Answer is stored in a[N-1]. Graph 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 0★mmmreddy 12●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×145
×116
×62
×24
×18
×1
×1