The Gateway to Computer Science Excellence

+37 votes

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 \:\text{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 _____.

+40 votes

Best answer

$T(k)$ is the smallest number of steps needed to move from $k$ to $100$.

Now, it is given that $y$ and $z$ are two numbers such that,

$T(9) = 1 + \min (T(y), T(z))$ , i.e.,

$T(9) = 1 + \min ($Steps from $y$ to $100$, Steps from $z$ to $100)$, where $y$ and $z$ are two possible values that can be reached from $9$.

One number that can be reached from $9$ is $10$, which is the number obtained if we simply move one position right on the number line. Another number is $15$, the shortcut path from $9$, as given in the question. So, we have two paths from $9$, one is $10$ and the other is $15$.

Therefore, the value of $y$ and $z$ is $10$ and $15$ (either variable may take either of the values).

Thus, $yz = 150$.

Now, it is given that $y$ and $z$ are two numbers such that,

$T(9) = 1 + \min (T(y), T(z))$ , i.e.,

$T(9) = 1 + \min ($Steps from $y$ to $100$, Steps from $z$ to $100)$, where $y$ and $z$ are two possible values that can be reached from $9$.

One number that can be reached from $9$ is $10$, which is the number obtained if we simply move one position right on the number line. Another number is $15$, the shortcut path from $9$, as given in the question. So, we have two paths from $9$, one is $10$ and the other is $15$.

Therefore, the value of $y$ and $z$ is $10$ and $15$ (either variable may take either of the values).

Thus, $yz = 150$.

0

""T(9)=1+min(T(9)=1+min(Steps from yy to 100100, Steps from zz to 100)100),__ where y and z are two possible values that can be reached from 9__." Where it is mentioned???

0

I am unable to find out how it,"__ where y and z are two possible values that can be reached from 9__", is linked. Can you please explain where it is ?

+4

T(9)=

1+min(T(y),T(z))

@rahulgargnov4 here the 1 in the equation is telling that. Equation says calculate minimum of T(y) and T(z) and then simply add 1 to it. What does that mean? 9 is at a distance of 1 from both y and z.

Analogy : height of the tree is : 1 + height(left) + height (right). Why one is here? because root is at distance one from both right and left.

+36 votes

$T(9) =$ Distance from $9$ to $100$

$T(9)=1+ \min(T(y),T(z))=1+$min(Distance from $y$ to $100$ , Distance from $z$ to $100$)

There are only two such values where we can reach from $9$ , one is simple step to right on number line , i.e $10$ and another is $15$ (given shortcut)

Hence , $y=10$ , $z=15$

$yz=10 \times 15 = 150$

$T(9)=1+ \min(T(y),T(z))=1+$min(Distance from $y$ to $100$ , Distance from $z$ to $100$)

There are only two such values where we can reach from $9$ , one is simple step to right on number line , i.e $10$ and another is $15$ (given shortcut)

Hence , $y=10$ , $z=15$

$yz=10 \times 15 = 150$

+2

it is solved like this

T(1)=1+min(T(y),T(z))=1+1=2

T(2)=1+min(T(y),T(z))=1+2=3

T(3)=1+min(T(y),T(z))=1+3=4

.

.

.

T(9)=10

Now, shortcut for T(9)=15

So, yz=10*15=150

but how could it be say , it goes from 0 to 100?

@ Srinath

+2 votes

From $k$, we have two paths-

*Path 1*- This is the path where we go from $k$ to $k_1$ where $k_1 = k+1$. Here, $k_1$ is the next number to the right of $k$.*Path 2*- This is the path where we go from $k$ to $k_2$ where $k_2 = k+i$. Here, $k_2$ is the the number to which $k$ has a shortcut.

Therefore, we have the following recurrence relation-

$T(k) = 1 + min(T(k_1), T(k_2))$

This basically means that the smallest no. of steps from $k$ to $100$ includes at least one step (either from $k$ to $k_1$ or from $k$ to $k_2$) and then subsequent smallest no. of steps from either $k_1$ to $100$ or from $k_2$ to $100$, whichever is minimum.

$\therefore T(9) = 1 + min(T(10), T(15))$

Here,

$k_1 = 9+1 = 10 \Rightarrow y = 10$,

$k_2 = 15$ ,($\because$ there is at most a single shortcut involving any number and it is given that the shortcut from $9$ is $15$) $\Rightarrow z = 15$

$\therefore y.z = 10.(15) = 150$

0

- Suppose, if another shortcut is from (11,100), then also, we would take T(10) and T(15).

As 11 can go only from 10, not from 9.

right??

- And Ans couldnot be T(9) and T(15), because, T(9) has only one shortcut. No, more shortcut possible from T(9)

right??

+1

- And Ans couldn't be T(9) and T(15), because, T(9) has only one shortcut. No, more shortcut possible from T(9), right?

It is mentioned that there can be **at most** 1 shortcut involving any number.

- Suppose, if another shortcut is from (11,100), then also, we would take T(10) and T(15).
As 11 can go only from 10, not from 9.

right??

Not necessarily. It is mentioned that a shortcut is present at 9 which takes us to the number 15. Therefore, we can decide to go from 9 to 10 or from 9 to 15.

Suppose we chose the first path, i.e. we went from 9 to 10. Now, from 10, there is no shortcut, i.e. we can go to 11 only. This is possible because not every number needs to have a shortcut. From 11, we have two paths-

-11 to 12 (usual path)**Path 1**-11 to 100 (shortcut path)]**Path 2**

Therefore, we have-

*T(9) = 1 + min[T(10), T(15)]*

*T(10) = 1 + T(11)*

*T(11) = 1 + min[T(12), T(100)] *

0

See, from number $9$, we can go to either number $10$ (immediate successor) or number $15$ (shortcut successor).

Now, irrespective of the successor we finally choose, we already have one path- either $9 \rightarrow 10$ or $9 \rightarrow 15$. Hence the $1 \ +$.

0

So, from 1 to 9 , there is no path??

Question is

want to move from 0 to 100 on the number line

right?

0

Another question

Suppose, we want to find the function $T(9) = 1 + \min(T(y),T(z))$

then what will be ur answer?

0

No. Even if there might not be any shortcut paths for the numbers ${0, 1, 2, \dots 8}$, yet there is at least one path which is guaranteed to exist. That path is-

$0 \rightarrow 1 \rightarrow 2 \rightarrow \dots \rightarrow 8 \rightarrow 9$

The given question is simply asking us to determine what will be the value of the variables $y$ and $z$ when we consider the paths from $9$. We don't need to consider the preceding paths that we might have followed to reach $9$.

0

Suppose, we want to find the function T(9)=1+min(T(y),T(z))T(9)=1+min(T(y),T(z))

then what will be ur answer?

We will calculate $T(y)$ and $T(z)$, which, in this case, is $T(10)$ and $T(15)$.

Now, depending on which one (out of $T(10)$ and $T(15)$) has the minimum vale, we will substitute $T(9) = 1 + min(T(10), T(15))$ by either $T(9) = 1 + T(10)$ if $T(10)$ has minimum value; or by $T(9) = 1 + T(15)$ if $T(15)$ has minimum value

.

In order to find $T(10)$ and $T(15)$, we can use the same formula that is used to find $T(9)$ by using the appropriate values. In other words,

$T(10) = 1 + min(T(11), T(a))$, (*assuming there is a shortcut from 10 to some number a)*

Similarly, $T(15) = 1 + min(T(16), T(b))$, (*assuming there is a shortcut from 15 to some number b)*

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,317 answers

198,367 comments

105,099 users