GATE CS 2014 Set 3 Q.47 (CS Q.37): Dynamic Programming

Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers $i, j$ with $i < j$ . Given a shortcut $i, j$ if you are at position $i$ on the number line, you may directly move to $j$ . Suppose $T(k)$ denotes the smallest number of steps needed to move from $k$ to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let $y$ and $z$ be such that $T(9) = 1 + \min(T(y), T(z))$ . Then the value of the product $yz$ is _____.

Your answer

Official answer and solution

Official answer: 150
From: Official GATE 2014 answer key

Solution

Write the Bellman-Ford / shortest-path dynamic programming recurrence for moving on the number line from 9.

Let $T(k)$ denote the minimum number of steps to reach 100 starting from position $k$ .
From position $9$ , only two valid moves exist in one step:
- Option 1 (regular unit step): Move right by distance 1, reaching position $9 + 1 = 10$ . The remaining steps from this choice will be $T(10)$ , giving a total of $1 + T(10)$ steps.
- Option 2 (shortcut): The problem states that from 9 there is a shortcut to 15. Taking this shortcut reaches position 15 in 1 step. The remaining steps will be $T(15)$ , giving a total of $1 + T(15)$ steps.
By the principle of optimality (dynamic programming):
$T(9) = 1 + \min(T(10), T(15)).$
Comparing this with the given equation $T(9) = 1 + \min(T(y), T(z))$ :
$\{y, z\} = \{10, 15\}.$
The product of $y$ and $z$ is:
$yz = 10 \times 15 = 150.$

Final answer

150

Common trap

Confusing the shortcut destination with the difference (15 - 9 = 6).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 3
Question: 47 of 65, printed as CS Q.37
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source