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