ZIO15004 - Editorial

Editorialist: Anubhav Dhar

Problem link: ZIO 2015 Problem 4

Quick Explanation:

  • We can use a dynamic programming approach to solve this problem.

  • We define dp[i][j] to be the maximum number of flights taken among the first j flights of the sequence, starting from airport 0 and ending at the i-th airport.

  • For calculating dp[i][j], for all i, j ; we consider two cases and take the maximum of the two:

    • We didn’t take the j-th flight, so we must be staying at the i-th airport. So the maximum number of flights taken till now is dp[i][j-1].

    • We took the j-th flight and landed in airport i. So for example if the j-th flight is of the type β€˜c’, then we will consider all airports k, such that there is a type β€˜c’ flight from airport k to airport i . So the answer should be \max\limits_{k}{(dp[k][j-1]+1)}, where there is a flight from airport k to airport i of the type β€˜c’.

  • The final answer will be dp[2][Number\_of\_Flights]
    (Note that Number\_of\_Flights = 15 for all subtasks), since we must end our journey at airport 2.

Explanation:

This question is based on dynamic programming, but it is not essential to be familiar with dynamic programming beforehand to solve this problem.

Let dp[i][j], denote the maximum number of flights taken among the first j flights starting from airport 0 and ending at the i-th airport; 0 ≀ i ≀ 4 and 0 ≀ j ≀ Number\_of\_Flights = 15.

So, to initialize, we set dp[i][0] = 0 if i = 0, dp[i][0] = βˆ’βˆž otherwise (since we cannot possibly reach other airports taking zero flights from airport 0, so we would like to ignore these cases. Later we will see that we are interested in only the maximum of some values, so setting these to βˆ’βˆž will implicitly ignore these).

Now we are presently in airport 0, and we have to take some of the flights to possibly go to other locations and finally end the journey at 2.

Then we have two cases:-

  1. We didn’t take the j-th flight, so we must be staying in the i-th airport either from the beginning or we came by some flight among the first j-1 flights. So the maximum number of flights taken is dp[i][j-1].

\text OR

  1. We took the j-th flight and landed at airport i. So for example if the j-th flight is of the type β€˜c’, then we will consider all airports k, such that there is a flight from airport k to airport i of the type β€˜c’. Therefore if we fix the airport k, from where we took a flight of type β€˜c’ to airport i, we can say that our answer is dp[k][j-1]+1, (dp[k][j-1] flights taken as we somehow ended up in the k-th airport and then we took one flight, the j-th flight from airport k to airport i, hence total number of flights is dp[k][j-1]+1). Now, there might be multiple possible such airports k, but we are only interested in the maximum value derived from all of those. So the answer should be,
    \max\limits_{k}(dp[k][j-1]+1) ,
    where there is a flight from airport k to airport i of the type β€˜c’.

Now we simply need to take the maximum of these two cases.

So, we have:

For every airport k, such that there is a flight from airport k to airport i of the type described by the j-th letter of the flight sequence -

dp[i][j] = \max (dp[i][j-1],\max\limits_{k}(dp[k][j-1]+1)) ) .

Subtask (a):

Flight sequence: β€œcacbcbbbbaaacba”

We set up the column zero of the table as discussed above, 0 for row zero and βˆ’βˆž for others.

i \ j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0
1 -∞
2 -∞
3 -∞
4 -∞

Now for dp[i][1], since the only β€˜c’ type flight (first flight of the sequence) departing from airport 0 comes back to airport 0, we can only stay at airport 0. It is not possible to reach any other airport, so we assign βˆ’βˆž to these.

We consider the first flight now, type β€˜c’. So we have:

i \ j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 1
1 -∞ -∞
2 -∞ -∞
3 -∞ -∞
4 -∞ -∞

Now for dp[i][2], we can either stay at airport i or we can take the flight of type β€˜a’(second flight of the sequence) and come from all the airports having a flight of type β€˜a’ to the airport i (which is also not possible in this case).

So we have:

i \ j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 1 1
1 -∞ -∞ -∞
2 -∞ -∞ -∞
3 -∞ -∞ -∞
4 -∞ -∞ -∞

Similarly in the next step we have (flight type β€˜c’):

i \ j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 1 1 2
1 -∞ -∞ -∞ -∞
2 -∞ -∞ -∞ -∞
3 -∞ -∞ -∞ -∞
4 -∞ -∞ -∞ -∞

Now in the next step we have a flight of type β€˜b’. we β€œcan” only go to airport 4 from 0, so we have (flight type β€˜b’) :

i \ j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 1 1 2 2
1 -∞ -∞ -∞ -∞ -∞
2 -∞ -∞ -∞ -∞ -∞
3 -∞ -∞ -∞ -∞ -∞
4 -∞ -∞ -∞ -∞ 3

Now we can fill the rest of the table similarly:

i \ j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 1 1 2 2 3 3 3
1 -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞
2 -∞ -∞ -∞ -∞ -∞ -∞ 4 5
3 -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞
4 -∞ -∞ -∞ -∞ 3 3 4 4

The entire table can be written as

i \ j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 1 1 2 2 3 3 3 3 3 3 6 8 9 10 10
1 -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ 5 7 7 9 9 11
2 -∞ -∞ -∞ -∞ -∞ -∞ 4 5 5 5 5 6 8 8 10 10
3 -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ 6 6 8 9 10 11
4 -∞ -∞ -∞ -∞ 3 3 4 4 4 4 6 6 7 9 10 11

Now we want dp[2][15] which is the cell corresponding to the intersection of column 15 and row 2, which has 10,

Therefore, the answer is 10

Note that multiple tables were created for the purpose of illustration only; we only need to compute one such table for a single subtask.

Similarly we can do subtasks (b) and (c);

Table for subtask (b):

Sequence: β€œaaacaabcccbabac”

i \ j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 0 0 0 1 1 1 1 2 3 4 4 4 7 7 8
1 -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ 6 6 8 8
2 -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ 3 3 6 7 9
3 -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ -∞ 4 5 7 8
4 -∞ -∞ -∞ -∞ -∞ -∞ -∞ 2 2 2 2 5 5 7 7 8

Answer: 9

Table for subtask (c) :

Sequence: β€œaababccbcacaaca”

i \ j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 0 0 0 0 3 4 5 5 6 7 8 9 10 11 12
1 -∞ -∞ -∞ -∞ 2 2 2 4 4 6 7 8 9 10 11 12
2 -∞ -∞ -∞ -∞ -∞ 2 3 3 5 5 7 8 9 10 11 12
3 -∞ -∞ -∞ -∞ -∞ -∞ 3 4 5 6 7 8 9 10 11 12
4 -∞ -∞ -∞ 1 1 3 3 4 6 6 6 8 9 10 11 12

Answer: 12

1 Like

Actually we dont need to do dynamic programming :

( NOTE : here i am considering that we should only visit the 2nd city only once and once we visit it we have to end our trip and the answers i have got is given in the 4 (ii) in the answer sheet )

( a ). cacbcbbbbaaacba

  1. c -> we are at 0 and taking c is no harm coz we end up at 0 :white_check_mark:
  2. a -> we cant use a from 0 :x:
  3. c -> again take as we will end up in 0 only :white_check_mark:
  4. b -> If we use this , then we have a c next ( which we cant use ) and then we have 4 b’s which again we can’t use so we have to skip this :x:
  5. c -> again take as we will end up in 0 only :white_check_mark:
  6. b -> If we use this , then we have to skip the next 3 b’s , at this point it is best to skip :x:
  7. b -> If we use this , then we have to skip the next 2 b’s , at this point it is best to skip :x:
  8. b -> If we use this , then we have to skip the next 1 b’s , at this point it is best to skip :x:
  9. b -> We have to use this because to get out from 0th city , we have to use b ONLY and we find that till 14th we dont have a b , so we will be stuck in this city forever , and even if we use the 14th b then also in 15th step we cant reach the city 2 so we have to use this :white_check_mark:
  10. a -> We have got 3 consecutive a’s and we find that if we use 2 consecutive a’s then we will end up at 3 and then we can use c and b to get to the destination , so we can use 2 a’s here out of 3 , so we will use the first 2 a’s :white_check_mark:
  11. a -> As said , we will be using this a to get to the 3rd city :white_check_mark:
  12. a -> from the third city we cant use a , so we have to skip this :x:
  13. c -> we will use this to get to the fourth city an then use the next b to get to 2nd city which is our destination :white_check_mark:
  14. b -> we will use this flight to get to our destination :white_check_mark:
  15. a -> we have already reached our destination :x:

We are visiting 8 cities so our answer is 8

( b ). aaacaabcccbabac

  1. a -> we cant use a from 0 :x:
  2. a -> we cant use a from 0 :x:
  3. a -> we cant use a from 0 :x:
  4. c - > we will end up in 0 only so take :white_check_mark:
  5. a -> we cant use a from 0 :x:
  6. a -> we cant use a from 0 :x:
  7. b -> If we use this we have to skip 3 c’s and 1’b so it is the best to skip this :x:
  8. c -> we will end up in 0 only so take :white_check_mark:
  9. c -> we will end up in 0 only so take :white_check_mark:
  10. c -> we will end up in 0 only so take :white_check_mark:
  11. b -> we have to get out of 0th city , so we will use this :white_check_mark: ( If we dont use this , then we have to use the 13th b and then a and c where we will be using 3 flights but if we use this flight we will be using more flights )
  12. a -> we can use this flight to go the first city :white_check_mark:
  13. b -> we can use this flight to go back to fourth city :white_check_mark:
  14. a -> again go to the 1st city :white_check_mark:
  15. c -> reach our destination :white_check_mark:

We are visiting 9 cities so our answer is 9

( c ). aababccbcacaaca

  1. a -> we cant use a from 0 :x:
  2. a -> we cant use a from 0 :x:
  3. b -> we see that we have got 2 c’s in 6,7 so if we use bab ( next two ) and end up in 0th city again then we can use those 2’s and maximize our answer , and we also see that we can come back to the 0th city using bab , so we will be using this flight :white_check_mark:
  4. a -> use this flight and go to the 1st city :white_check_mark:
  5. b -> use this flight and go back to the 0th city and use the next 2 c’s :white_check_mark:
  6. c -> use this flight to maximize our answer :white_check_mark:
  7. c -> use this flight and stay at 0th city and maximize our answer :white_check_mark:
  8. b -> Now we are in 0th city and we have to reach the destination and to do so we have to exit the 0th city and we can only use b to exit the 0th city and till 15th , we have no b , so we cant reach our destination if we dont use this , so we will be using this flight :white_check_mark:
  9. c -> we cant use c in 4th city :x:
  10. a -> we have to use this because to reach our destination from the 4th city we have to use b and we dont even have b afterwards so we have to use this and go to the first city :white_check_mark:
  11. c -> if we use this , we will reach our destination and can’t use any of the below ones so we will actually decrease our answer so we are not going to use this :x:
  12. a -> using this a , we can go to 3rd city and we see that we can use c again to come back to the first city , so we will use this and go to the third city :white_check_mark:
  13. a -> we can’t use a in the third city :x:
  14. c -> as said earlier , we will use this and go back to the first city :white_check_mark:
  15. a -> now using this ( last flight ) we will reach our destination :white_check_mark:

We are visiting 10 cities so our answer is 10

Your approach is also good , this is my approach
Thanks :slight_smile:

4 Likes

+1
Made things up clear @sudheerays123. :slight_smile:

3 Likes

I don’t quite understand your approach (correct me if I am wrong).

You are basically observing how to find the maximum number of flights to reach the destination at the end. But won’t that lead to 2^{LengthOfString} routes, which is impossible to calculate using pen and paper.

Or a second thing which I think you are trying to say is to observe and brute force the approach to minimize the number of strings, which leads to dynamic programming, or an approach using the principle of dynamic programming?

1 Like

No , i am NOT considering all the 2^n cases
I will explain the (a) subtask

  1. We can use c as it doesnt matter because we will be back in the starting position only
  2. There is no outgoing ’ a ’ flight from 0 , so thats why we can’t use that
  3. Again as said in 1 , we can use c
  4. If we use this flight , we have to skip the next c and the next 4 consecutive b’s , so it is better to skip this flight
  5. Again as said in 1 , we can use c
    .
    .
    .
    The next is all the same

Hope this is better :slight_smile:

1 Like

For Subtask a) , can someone please show the β€œpath” as well , how are u getting 10 as the answer ?

1 Like

@jinishatejura The path --> c c c b a a c b
The correct answer is 8

There are two cases
Case 1. We can only visit the destination once and the path ends
Case 2. We can visit destination any number of times but we have to end there

For the two cases there are different answers :

Case 1 :

a. 8
b. 9
c. 10

Case 2 :

a. 10
b. 9
c. 12

:slight_smile:

2 Likes

The path I got was

CaCbCBBbbAAACBa (Capital letters represent the selected path)
or cccbbaaacb

c : from 0 to 0
c : from 0 to 0
c : from 0 to 0
b : from 0 to 4
b : from 4 to 2
a : from 2 to 4
a : from 4 to 1
a : from 1 to 3
c : from 3 to 4
b : from 4 to 2

2 Likes