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

×

RTTE - Editorial

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:

  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].

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

mmmreddy's gravatar image

0★mmmreddy
121
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×141
×99
×57
×22
×12
×1
×1

question asked: 12 Jan, 15:14

question was seen: 29 times

last updated: 12 Jan, 15:14