** Editorialist :** Sudheera Y S

**Problem link :** Zonal Informatics Olympiad, 2005

**Prerequisites :** graphs , DP

**Problem statement :**

There are some flat areas and some slopes connecting two flat areas . A slope area has some length d and some maximum speed s in which we can go in that slope with that maximum speed. Going on the slope takes some energy as defined below :

If s <= 50 β energy e = d*(60 - s )

If s > 50 β energy e = d*(s - 40 )

Everytime you use some slope to get to the other flat area , you add the energy required to go in that slope to your total energy. You are in flat 1 and you want to reach flat area n , find the minimum total energy from which we can reach flat n

**Idea :**

First for each slope , we find the minimum energy required if we travel on this slope and then once we do this for all the slopes , as the graph is topologically sorted , we do DP to find the minimum energy required to reach each flat area and then we would find our answer

**Subtask A :**

Number of flat areas : 7

Number of slopes : 9

**Slopes :**

No. β | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|

Fro β | 1 | 1 | 1 | 2 | 3 | 3 | 4 | 5 | 6 |

To β | 2 | 3 | 4 | 5 | 5 | 6 | 6 | 7 | 7 |

s β | 60 | 40 | 20 | 40 | 60 | 30 | 20 | 30 | 30 |

d β | 15 | 10 | 5 | 20 | 30 | 10 | 5 | 10 | 10 |

e β |

**NOTE :** Here s is maximum speed , so we can go in any speed between 1 and s both inclusive

Let us denote E(x,y) as the energy required to use the slope which connects flat areas x and y

E( 1,2 ) :

Here , s > 50 , therefore energy required is (s - 40)*d = 20*15 = 300 if we go in 60 speed

Now what if we go at 51 speed ?

Here also , s > 50 , therefore energy required is (s - 40 )*d = 11*15 = 165 if we go in 51 speed

But what if we go at 50 speed ?

Here , s <= 50 , therefore energy required is (60 - s)*d = 10*15 = 150 if we go in 50 speed which is lesser than both of the above

What if we go at a speed less than 50 ?

Clearly , 60 - s would increase , hence increasing the energy required

Therefore, the formula for finding the minimum energy required is

Minimum energy = d * ( 60 - min( 50 , s ) )

Here we are doing min ( 50 , s ) because if s > 50 , then it takes as 50 making the energy minimum

Let us plot it in graph and see it graphically that taking 50 if s > 50 is better :

Here we see that , taking s = 50 ( when s > 50 ) is better than taking s > 50 or taking s < 50

So now , let us calculate the energy required for all the slopes :

E(1, 2) = d * ( 60 - min( 50 , s )) = 15*10 = 150

E(1, 3) = d * ( 60 - min( 50 , s )) = 10*20 = 200

E(1, 4) = d * ( 60 - min( 50 , s )) = 5*40 = 200

E(2, 5) = d * ( 60 - min( 50 , s )) = 20*20 = 400

E(3, 5) = d * ( 60 - min( 50 , s )) = 30*10 = 300

E(3, 6) = d * ( 60 - min( 50 , s )) = 10*30 = 300

E(4, 6) = d * ( 60 - min( 50 , s )) = 5*40 = 200

E(5, 7) = d * ( 60 - min( 50 , s )) = 10*30 = 300

E(6, 7) = d * ( 60 - min( 50 , s )) = 10*30 = 300

The table would look like this :

No. β | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|

From β | 1 | 1 | 1 | 2 | 3 | 3 | 4 | 5 | 6 |

To β | 2 | 3 | 4 | 5 | 5 | 6 | 6 | 7 | 7 |

s β | 60 | 40 | 20 | 40 | 60 | 30 | 20 | 30 | 30 |

d β | 15 | 10 | 5 | 20 | 30 | 10 | 5 | 10 | 10 |

e β | 150 | 200 | 200 | 400 | 300 | 300 | 200 | 300 | 300 |

The graph would look something like this :

Let us do DP now to find our answer :

Before doing DP , we have to know if dp works here ,

The answer is βYesβ as the graph is topologically sorted and there are no cycles ( the graph is DAG i.e Directed Acyclic Graph )

So now , after making sure that DP works , let us see how to do DP :

Dp[ i ] = minimum energy required to reach the iβth flat area

Base case : dp[ 1 ] = 0 because we start at the first flat area and reaching the first flat area requires no energy , therefore this is the base case

Relation : dp[ i ] = min ( dp[ j ] + E ( i,j ) ) for all j from which we can come to iβth flat area using some slope

**Answer :** dp[ n ] because we have to find the minimum energy required to reach the nβth flat area

So now , let us start filling the dp table :

Base case : dp[ 1 ] = 0

**Relation :**

Dp[ 2 ] = dp [ 1 ] + E(1,2) = 0 + 150 = 150 ( as we can only come from 1)

Dp[ 3 ] = dp [ 1 ] + E(1,3) = 0 + 200 = 200 ( as we can only come from 1)

Dp[ 4 ] = dp [ 1 ] + E(1,4) = 0 + 200 = 200 ( as we can only come from 1)

Dp[ 5 ] = min ( dp[ 2 ] + 400 , dp[ 3 ] + 300 ) = min ( 700 , 800 ) = 700

Dp[ 6 ] = min ( dp[ 3 ] + 300 , dp[ 4 ] + 200 ) = min ( 500 , 400 ) = 400

Dp[ 6 ] = min ( dp[ 5 ] + 300 , dp[ 6 ] + 300 ) = min ( 1000 , 700 ) = 700

**Answer : dp[ 7 ] = 700**

Dp values for all the points :

**Answer : 700**

**Subtask B :**

Number of flat areas : 9

Number of slopes : 12

**Slopes :**

Now , let us calculate the energy for all the slopes :

E(1, 2) = d * ( 60 - min( 50 , s )) = 15*10 = 150

E(1, 3) = d * ( 60 - min( 50 , s )) = 25*20 = 500

E(2, 4) = d * ( 60 - min( 50 , s )) = 30*20 = 600

E(2, 5) = d * ( 60 - min( 50 , s )) = 25*10 = 250

E(3, 5) = d * ( 60 - min( 50 , s )) = 20*10 = 200

E(3, 6) = d * ( 60 - min( 50 , s )) = 10*20 = 200

E(4, 7) = d * ( 60 - min( 50 , s )) = 10*30 = 300

E(5, 7) = d * ( 60 - min( 50 , s )) = 10*10 = 100

E(5, 8) = d * ( 60 - min( 50 , s )) = 5*20 = 100

E(6, 8) = d * ( 60 - min( 50 , s )) = 20*20 = 400

E(7, 9) = d * ( 60 - min( 50 , s )) = 10*20 = 200

E(8, 9) = d * ( 60 - min( 50 , s )) = 20*40 = 800

The table would look like :

No. β | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|

From β | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 | 5 | 6 | 7 | 8 |

To β | 2 | 3 | 4 | 5 | 5 | 6 | 7 | 7 | 8 | 8 | 9 | 9 |

s β | 50 | 40 | 40 | 50 | 50 | 40 | 30 | 60 | 40 | 40 | 40 | 20 |

d β | 15 | 25 | 30 | 25 | 20 | 10 | 10 | 10 | 5 | 20 | 10 | 20 |

E β | 150 | 500 | 600 | 250 | 200 | 200 | 300 | 100 | 100 | 400 | 200 | 800 |

The graph would look something like this :

So now , let us start filling the dp table :

Base case : dp[ 1 ] = 0

**Relation :**

Dp[ 2 ] = dp[ 1 ] + 150 = 150 ( as we can only come from 1)

DP[ 3 ] = dp[ 1 ] + 500 = 500 ( as we can only come from 1)

Dp[ 4 ] = dp[ 2 ] + 600 = 750 ( as we can only come from 2)

Dp[ 5 ] = min ( dp[ 2 ] + 250 , dp[ 3 ] + 200 ) = 400

Dp[ 6 ] = dp[ 3 ] + 200 = 700 ( as we can only come from 3)

Dp[ 7 ] = min ( dp[ 4 ] + 300 , dp[ 5 ] + 100 ) = 400

Dp[ 8 ] = min ( dp[ 5 ] + 100 , dp[ 6 ] + 400 ) = 500

Dp[ 9 ] = min ( dp[ 7 ] + 200 , dp[ 8 ] + 800 ) = 700

**Answer : dp[ 9 ] = 700**

The dp values :

**Answer : 700**

**Subtask C :**

Number of flat areas : 11

Number of slopes : 16

**Slopes :**

So now , let us calculate the energy required for each slope :

E(1, 2) = d * ( 60 - min( 50 , s )) = 10*10 = 100

E(1, 3) = d * ( 60 - min( 50 , s )) = 20*30 = 600

E(2, 4) = d * ( 60 - min( 50 , s )) = 20*10 = 200

E(2, 5) = d * ( 60 - min( 50 , s )) = 10*10 = 100

E(3, 5) = d * ( 60 - min( 50 , s )) = 10*10 = 100

E(3, 6) = d * ( 60 - min( 50 , s )) = 10*20 = 200

E(4, 7) = d * ( 60 - min( 50 , s )) = 10*30 = 300

E(4, 8) = d * ( 60 - min( 50 , s )) = 30*10 = 300

E(5, 8) = d * ( 60 - min( 50 , s )) = 30*10 = 300

E(5, 9) = d * ( 60 - min( 50 , s )) = 20*20 = 400

E(6, 9) = d * ( 60 - min( 50 , s )) = 20*20 = 400

E(6, 10) = d * ( 60 - min( 50 , s )) = 40*10 = 400

E(7, 11) = d * ( 60 - min( 50 , s )) = 20*20 = 400

E(8, 11) = d * ( 60 - min( 50 , s )) = 10*40 = 400

E(9, 11) = d * ( 60 - min( 50 , s )) = 20*20 = 400

E(10, 11) = d * ( 60 - min( 50 , s )) = 10*30 = 300

The table looks like this :

No | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

F. | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 | 6 | 7 | 8 | 9 | 10 |

To | 2 | 3 | 4 | 5 | 5 | 6 | 7 | 8 | 8 | 9 | 9 | 10 | 11 | 11 | 11 | 11 |

s | 60 | 30 | 50 | 60 | 50 | 40 | 30 | 50 | 60 | 40 | 40 | 50 | 40 | 20 | 40 | 30 |

d | 10 | 20 | 20 | 10 | 10 | 10 | 10 | 30 | 30 | 20 | 20 | 40 | 20 | 10 | 20 | 10 |

e | 100 | 600 | 200 | 100 | 100 | 200 | 300 | 300 | 300 | 400 | 400 | 400 | 400 | 400 | 400 | 300 |

The graph would look something like this :

So now , let us start filling the dp table :

Base case : dp[ 1 ] = 0

**Relation :**

Dp[ 2 ] = dp[ 1 ] + 100 = 100 ( as we can only come from 1)

DP[ 3 ] = dp[ 1 ] + 600 = 600 ( as we can only come from 1)

Dp[ 4 ] = dp[ 2 ] + 200 = 300 ( as we can only come from 2)

Dp[ 5 ] = min ( dp[ 2 ] + 100 , dp[ 3 ] + 100 ) = 200

Dp[ 6 ] = dp[ 3 ] + 200 = 600 ( as we can only come from 3)

Dp[ 7 ] = dp[ 4 ] + 300 = 600 ( as we can only come from 4)

Dp[ 8 ] = min ( dp[ 4 ] + 300 , dp[ 5 ] + 300 ) = 500

Dp[ 9 ] = min ( dp[ 5 ] + 400 , dp[ 6 ] + 400 ) = 600

Dp[ 10 ] = dp[ 6 ] + 400 = 1200 ( as we can only come from 10)

Dp[ 11 ] = min ( dp[ 7 ] + 400 , dp[ 8 ] + 400 , dp[ 9 ] + 400 , dp[ 10 ] + 300 ) = 900

**Answer : dp[ 11 ] = 900**

The dp values would look something like this :

**Answer : 900**

Hope you understood