GATE CSE 2014 Set 3 | Question: 37

Question

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

Comments

who are not getting the question take it like this way,…

Suppose their is a stair in which you wanted to go up. Either you can go one step(similar to one step right move in question) at a time or you can jump to more than one steps at a time( similar to taking shortcut in question 9 to 15).

Now everybody is asking why 1 is added in question. when you at 9^th step (assuming ground level step to 1). so in order to go up you have to add 1+min(steps by y,steps by z). here y and z are any locations or steps above 9 in stairs. So obviously need less no. of steps and t(9) will take more no. of steps.

---

The only thing this question is testing is how well you read a question right?? Or is there any concept involved in this question

---

I Think we can solve this question like this also-→
--------------------------------------------------------------------------------------------------------------------------------------
first of let’s understand question itself    
       1)we want to go from 0 to 100 there are 2 choice either we can go 1 position right or we can take short cut
      2)  and T(k) denotes smallest number of move required to reach from position k to 100 
these are the information given 
________________________________________________________________________________________
what are the condition that we need to satisfy while solving this
1)we can take at most one shortcut (means either o or 1)
2) and that shortcut also given of 6 length (from 9-->15) means if you are at 9 then either you can take shortcut or you can move one position right 

_______________________________________________________________________________________________
to understand this question i am now going to related with some other DP(dynamic programming question)
assume  if this question might was asked like that –

---

minimum number of step to reach from anywhere to 100  and you have two choice everywhere either you can take shortcut or one position right.
then in such satuation you can  write DP expression ,
at every step we have two choice either take shortcut or take one position right and at each step take minimum
assume i am at k step
T(k)=1+min(T(x),T(y))
means i am at t and by taking one step i can go to at x or y --->her i can go to at x by taking shortcut and y by taking one position right.
and we will solve this recurencee relation and at last we will get answer.
-----------------------------------------------------------------------------------------------------------------------------------------

now come to question-------------→

we want to solve this question for
T(9)=1+min(T(x),t(y))
# here by taking one step i can go to x, or y  i will go to x if  i will take shortcut and i will to y if i will take one position right

now according to question if i am at 9 position then   i have two choice either i can take shortcut or we can take one right

T(9)=1+min(T(15),t(10)    #because x=15 and y=10
now were at 9 position we was having two choice and after that that we are taken now after that any where we are having only one choice
now they are asking value of x*y
so this will be 150  ans.
_____________________________________________________________________________________________
some confusion related to this question

1)they are not asking about  T(9)

2)they are just asking if you want to calculate from 9 to 100 .after taken first step what you will put at the value of x and y

3)assume that if they have ask T(10) then how we will solve we will say that
by taking only 1 step either i can go to t(x) or t(y)
so we can write T(10)=1+min(t(x),t(y)
but here at position 10 we are only having one choice to go write .because of the choice of short cut is only from position 9
so x==11,y==11

 

Answer 1

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

Comments

In the equation, T(9)=1+min(T(y),T(z))

In case the shortcut is not taken,  “1” is for 9 → 10 because of “unit distance” when we move right.

But when the shortcut is taken, i.e. 9 → 15, “1” does not make sense since it is nowhere specified in the question that the shortcut is also of unit distance. Are we supposed to assume that?

---

Either to move unit distance right or using shortcut takes a move ..that is why 1 is added (not for the unit distance mentioned)

---

Nice aptitude question. In these type of qs, if $T(x)$ is asked, just think about all the possible values that can be reached from $x$ (or the values that $x$ can take).

Answer 2

$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$

Comments

I am not getting .. Please explain anyone

---

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

---

Solution of the equation

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

Now, 9 to 15 there is a shortcut.

Now, if I take solution like that

T(9)=1+min(T(10),T(15))

    =1+T(15)

that means , T(9) to T(15) there exists 1 step, i.e. why we are adding 1.

Answer 3

From $k$, we have two paths-

1. 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$.
2. 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$

Comments

@Debargha Bhattacharj

Another question

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

then what will be ur answer?

---

@srestha

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

---

@srestha

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) 

Answer 4

$T(9)= 1 +min(T(y),T(z)),$

Here, T(9) is nothing but min steps required to move from $9\rightarrow 100$.

For T(9) we have only 2 choices, i.e either we can take a shortcut to 15 or we can just move by 1 unit to right that is to10.

Let’s assume we didn’t took shortcut and we are simply moving 1 unit by right(i.e we reached to 10) and then, started moving right by 1 unit till 100, Bcz we only know shortcut for 9, for the rest of the numbers we don't know.

i.e $9\rightarrow 10\rightarrow 100$,

(100- 10= 90 +1= 91) steps are required, +1 bcz $9\rightarrow 10 $, 1 step is required. 

okay, Now lets assume we took a shortcut from $9\rightarrow 15\rightarrow 100$,

Now min no.of steps required is (100-15 = 85 +1 =86 steps )  , +1 is for $9\rightarrow 15$.  here also same as for the above reasoing i.e we dont know shortcut for 15 so we are moving right by simply 1 unit till 100. therefore it took 85 steps min.

By, the above complete reasoning we got to know that $min(T(y), T(z)),$ should be either 85 or 90(since, +1 is already given),

As we see,

T(10) is  giving exactly 90 min steps(100-10=90), since we don't know the shortcut for 10, we move by 1 unit to right till 100,

and T(15) is giving exactly 85 min steps(100-15=85), since we don't know the shortcut for 15, we move by 1 unit to right till 100,

$T(9)= 1 +min(T(y),T(z)),$ = 1+ min(T(10), T(15)) = 1 +min (90,85) =1 + 85 = 86.

so,By Observing the above senario, y=10. z=15. 

$\therefore$ Ans is 10*15 =150.