Editorialist: Anubhav Dhar
Problem Statement: ZIO 2007 Problem 5
Quick Explanation:
- The question basically tells us to find the path with the minimum sum of potholes. We can come up with an algorithm similar to Dijkstra’s Algorithm to solve this.
- We can rephrase the question: We are given a grid of petrol tanks, where each petrol tank can be set to fire. Each petrol tank takes some amount of time to be burnt completely and then the fire spreads to the neighbouring tanks which are not burnt yet. So we need to find out at what point of time the rightmost bottommost petrol tank is burnt completely if we were to ignite the topmost leftmost petrol tank.
- Notice that due to the nature of fire, it will choose the path which takes the shortest time possible.
- So now we can set the time associated with each of the petrol tanks in the intersection i-th row and j-th column to be equal to the number of potholes in the i-th row and j-th column in the question.
- Now we can just simulate the process and find out when the rightmost bottommost petrol tank burns completely.
Explanation:
Notice that the question simply tells us to report the minimum sum of potholes possible in a path going from the top most leftmost square to the bottommost rightmost square. We can recreate the Dijkstra’s Algorithm to solve this question, although being familiar with it is not essential.
Imagine instead of squares having potholes, consider a petrol tank in each of the squares. These petrol tanks can catch fire and once they start burning, they take a specific amount of time required to burn completely (time required for different petrol tanks may be different), and once they are completely burnt, the fire spreads to the neighbouring petrol tanks, which are not yet burnt. Now, we can place a petrol tank in each of these squares, and then set the time required for the petrol tank corresponding to a particular square to be the number of potholes there was initially. Why do we do this? Well now we can set the petrol tank in the topmost leftmost square to fire. The fire will gradually propagate and reach the square in the rightmost bottommost square. We just record the time when the petrol tank at the one in the rightmost bottommost square is completely burnt. Now, notice that due to the nature of fire, it will take the route with the shortest possible time to reach the last petrol tank from the first petrol tank. So the recorded time should correspond to the shortest time possible. Now if we backtrack what happened: just before the last petrol tank was set to fire, some petrol tank (say tank a) had finished burning and then passed its fire to the last tank, after which the tank took the time associated with it to burn completely. Now before tank a was set to fire, the fire must have come from some other tank (say tank b), which had just finished burning; after which tank a burnt for some time (precisely the time associated with it), and then passed the fire to the last tank, which again burnt for some more time(precisely the time associated with the last tank). So we can backtrack further, but the point is, the fire had travelled through a path from the first tank to the last tank and then the time required is the sum of all the times associated with the tanks in that path and it is the minimum among all other paths (if there was a path which had a faster route, the fire would have chosen that path instead). Notice the analogy? That is exactly what we need to find out, the minimum sum of some value in a path from the first square to the last square. So instead of reporting the minimum sum of potholes, we can just report the time when the last tank burns. It should be intuitively clear now that these two questions are essentially the same and are bound to have the same answer.
Now this might seem to be an unnecessary rephrasing. But now, we just need to simulate the fire. But it is not obvious how we would do that, and that is where we need to reconstruct the Dijkstra’s Algorithm.
At any point of time we can classify petrol tanks into three categories: completely burnt, burning, and not burnt. Now, once a not yet burning tank starts burning, it will be burnt completely after time associated with the square, and after that it will start burning neighbouring petrol tanks which are not burnt yet. So if we consider all the tanks which are presently burning, then we can choose the burning tank which becomes completely burnt the earliest among the all burning tanks, and once it burns completely, we can propagate the fire to the neighbouring unburnt tanks.
So what we can do systematically is keep track of which vertices are burning, which are burnt and which have not started burning yet. Along with that we can keep track of the time when a particular tank is being burnt. So if a tank has been burnt at time t and an unburnt neighbouring tank takes time h to be burnt completely, then the time when that neighboring not yet burnt tank will have been completely burnt will be at h + t. That is all that is to be done, but we must be careful that only the burning tanks can spread fire, neither the completely burnt tanks nor the unburnt tanks can spread fire.
So, our algorithm is:
- Consider all burning tanks. Take the one which will be completely burnt the earliest (in case of ties, we can choose arbitrarily). Mark it completely burnt and mark all the unburnt neighbouring tanks as burning (We want to simulate the part where one tank becomes completely burnt and the fire spreads to neighbouring unburnt tanks). Now, then we can calculate for each of these tanks, the times when these tanks will be burnt completely.
- Finally we just need to report the time when the last tank, the bottommost, rightmost tank is burnt completely.
Let us try to solve the subtasks.
Subtask (a):
We are given the table
| 8 | 11 | 4 | 6 | 14 | 14 |
| 27 | 26 | 21 | 5 | 19 | 11 |
| 9 | 2 | 4 | 5 | 18 | 23 |
| 12 | 10 | 15 | 28 | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
Let us denote the time at which a tank is burnt completely inside parentheses. Also let us denote completely burnt tanks by bold numbers and the burning tanks by placing a symbol ‘*’ in before those.
Let us set fire to the first tank. We know that it will be burnt at time = 8.
| *8 (8) | 11 | 4 | 6 | 14 | 14 |
| 27 | 26 | 21 | 5 | 19 | 11 |
| 9 | 2 | 4 | 5 | 18 | 23 |
| 12 | 10 | 15 | 28 | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
Now we just follow our algorithm. Notice that only one tank is burning. We mark it completely burnt and mark all the unburnt neighbouring tanks as burning, i.e. the tank having time 11 and the tank having time 27. So the tank with time 11 is set to fire at time = 8, and then burns for 11 more units of time. So the time when it is burnt is 11 + 8 = 19. Similarly the tank with 27 will be completely burnt at time 27 + 8 = 35
| 8 (8) | *11 (19) | 4 | 6 | 14 | 14 |
| *27 (35) | 26 | 21 | 5 | 19 | 11 |
| 9 | 2 | 4 | 5 | 18 | 23 |
| 12 | 10 | 15 | 28 | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
Now, among the two burning tanks, the tank *11 (19) burns completely the earliest. So we mark it as completely burnt and then mark its unburnt neighbours as burning, and calculate when they become completely burnt. So, the tank to the right of it, takes 4 units of time to be burnt completely and it is set to fire at time = 19, so the time when it burns completely is 19 + 4 = 23. Similarly the one under that will burn completely at time 19 + 26 = 45.
| 8 (8) | 11 (19) | *4 (23) | 6 | 14 | 14 |
| *27 (35) | *26 (45) | 21 | 5 | 19 | 11 |
| 9 | 2 | 4 | 5 | 18 | 23 |
| 12 | 10 | 15 | 28 | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
Let us see what happens once more. So, among the three burning tanks, the tank *4 (23) burns completely the earliest. So we mark it as completely burnt and then mark its unburnt neighbours as burning, and calculate when they become completely burnt. So, the tank to the right of it, takes 6 units of time to be burnt completely and it is set to fire at time = 23, so the time when it burns completely is 23 + 6 = 29. Similarly the one under that will burn completely at time 23 + 21 = 44.
| 8 (8) | 11 (19) | 4 (23)** | *6 (29) | 14 | 14 |
| *27 (35) | *26 (45) | *21 (44) | 5 | 19 | 11 |
| 9 | 2 | 4 | 5 | 18 | 23 |
| 12 | 10 | 15 | 28 | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
Let us see what happens next. So, among all the burning tanks, the tank *6 (29) burns completely the earliest. So we mark it as completely burnt and then mark its unburnt neighbours as burning, and calculate when they become completely burnt. So, the tank to the right of it, takes 14 units of time to be burnt completely and it is set to fire at time = 29, so the time when it burns completely is 29 + 14 = 43. Similarly the one under that will burn completely at time 29 + 5 = 34.
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | *14 (43) | 14 |
| *27 (35) | *26 (45) | *21 (44) | *5 (34) | 19 | 11 |
| 9 | 2 | 4 | 5 | 18 | 23 |
| 12 | 10 | 15 | 28 | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
Let us see what happens next. So, among all the burning tanks, the tank *5 (34) burns completely the earliest. So we mark it as completely burnt and then mark its unburnt neighbours as burning, and calculate when they become completely burnt. So, the tank to the right of it, takes 19 units of time to be burnt completely and it is set to fire at time = 34, so the time when it burns completely is 34 + 19 = 53. Similarly the one under that will burn completely at time 34 + 5 = 39.
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | *14 (43) | 14 |
| *27 (35) | *26 (45) | *21 (44) | 5 (34) | *19 (53) | 11 |
| 9 | 2 | 4 | *5 (39) | 18 | 23 |
| 12 | 10 | 15 | 28 | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
Let us simulate the rest of the process
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | *14 (43) | 14 |
| 27 (35) | *26 (45) | *21 (44) | 5 (34) | *19 (53) | 11 |
| *9 (44) | 2 | 4 | *5 (39) | 18 | 23 |
| 12 | 10 | 15 | 28 | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | *14 (43) | 14 |
| 27 (35) | *26 (45) | *21 (44) | 5 (34) | *19 (53) | 11 |
| *9 (44) | 2 | *4 (43) | 5 (39) | *18 (57) | 23 |
| 12 | 10 | 15 | *28 (67) | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | *14 (57) |
| 27 (35) | *26 (45) | *21 (44) | 5 (34) | *19 (53) | 11 |
| *9 (44) | 2 | *4 (43) | 5 (39) | *18 (57) | 23 |
| 12 | 10 | 15 | *28 (67) | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | *14 (57) |
| 27 (35) | *26 (45) | *21 (44) | 5 (34) | *19 (53) | 11 |
| *9 (44) | *2 (45) | 4 (43) | 5 (39) | *18 (57) | 23 |
| 12 | 10 | *15 (58) | *28 (67) | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | *14 (57) |
| 27 (35) | *26 (45) | 21 (44) | 5 (34) | *19 (53) | 11 |
| *9 (44) | *2 (45) | 4 (43) | 5 (39) | *18 (57) | 23 |
| 12 | 10 | *15 (58) | *28 (67) | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | *14 (57) |
| 27 (35) | *26 (45) | 21 (44) | 5 (34) | *19 (53) | 11 |
| 9 (44) | *2 (45) | 4 (43) | 5 (39) | *18 (57) | 23 |
| *12 (56) | 10 | *15 (58) | *28 (67) | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | *14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | *19 (53) | 11 |
| 9 (44) | *2 (45) | 4 (43) | 5 (39) | *18 (57) | 23 |
| *12 (56) | 10 | *15 (58) | *28 (67) | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | *14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | *19 (53) | 11 |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | *18 (57) | 23 |
| *12 (56) | *10 (55) | *15 (58) | *28 (67) | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | *14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | *11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | *18 (57) | 23 |
| *12 (56) | *10 (55) | *15 (58) | *28 (67) | 29 | 7 |
| 20 | 2 | 8 | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | *14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | *11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | *18 (57) | 23 |
| *12 (56) | 10 (55) | *15 (58) | *28 (67) | 29 | 7 |
| 20 | *2 (57) | 8 | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | *14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | *11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | *18 (57) | 23 |
| 12 (56) | 10 (55) | *15 (58) | *28 (67) | 29 | 7 |
| *20 (76) | *2 (57) | 8 | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | *14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | *11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | *18 (57) | 23 |
| 12 (56) | 10 (55) | *15 (58) | *28 (67) | 29 | 7 |
| *20 (76) | 2 (57) | *8 (65) | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | 14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | *11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | *18 (57) | 23 |
| 12 (56) | 10 (55) | *15 (58) | *28 (67) | 29 | 7 |
| *20 (76) | 2 (57) | *8 (65) | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | 14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | *11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | 18 (57) | *23 (80) |
| 12 (56) | 10 (55) | *15 (58) | *28 (67) | *29 (86) | 7 |
| *20 (76) | 2 (57) | *8 (65) | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | 14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | *11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | 18 (57) | *23 (80) |
| 12 (56) | 10 (55) | 15 (58) | *28 (67) | *29 (86) | 7 |
| *20 (76) | 2 (57) | *8 (65) | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | 14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | 11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | 18 (57) | *23 (80) |
| 12 (56) | 10 (55) | 15 (58) | *28 (67) | *29 (86) | 7 |
| *20 (76) | 2 (57) | *8 (65) | 16 | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | 14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | 11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | 18 (57) | *23 (80) |
| 12 (56) | 10 (55) | 15 (58) | *28 (67) | *29 (86) | 7 |
| *20 (76) | 2 (57) | 8 (65) | *16 (81) | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | 14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | 11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | 18 (57) | *23 (80) |
| 12 (56) | 10 (55) | 15 (58) | 28 (67) | *29 (86) | 7 |
| *20 (76) | 2 (57) | 8 (65) | *16 (81) | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | 14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | 11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | 18 (57) | *23 (80) |
| 12 (56) | 10 (55) | 15 (58) | 28 (67) | *29 (86) | 7 |
| 20 (76) | 2 (57) | 8 (65) | *16 (81) | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | 14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | 11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | 18 (57) | 23 (80) |
| 12 (56) | 10 (55) | 15 (58) | 28 (67) | *29 (86) | *7 (87) |
| 20 (76) | 2 (57) | 8 (65) | *16 (81) | 3 | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | 14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | 11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | 18 (57) | 23 (80) |
| 12 (56) | 10 (55) | 15 (58) | 28 (67) | *29 (86) | *7 (87) |
| 20 (76) | 2 (57) | 8 (65) | 16 (81) | *3 (84) | 17 |
| 8 (8) | 11 (19) | 4 (23) | 6 (29) | 14 (43) | 14 (57) |
| 27 (35) | 26 (45) | 21 (44) | 5 (34) | 19 (53) | 11 (64) |
| 9 (44) | 2 (45) | 4 (43) | 5 (39) | 18 (57) | 23 (80) |
| 12 (56) | 10 (55) | 15 (58) | 28 (67) | *29 (86) | *7 (87) |
| 20 (76) | 2 (57) | 8 (65) | 16 (81) | 3 (84) | *17 (101) |
We need not go any further since we have already calculated the time when the last tank is being burnt, which is 101.
So the answer to the question must be 101.
Note that multiple tables were created for the purpose of illustration only; we can compute all the values keeping only one table for a single subtask.
We can solve other subtasks similarly.
Table for Subtask (b):
| 4 (4) | 2 (6) | 3 (9) | 3 (12) | 2 (14) | 5 (19) | 4 (23) | 5 (28) |
| 1 (5) | 3 (8) | 5 (13) | 5 (17) | 5 (19) | 5 (24) | 5 (28) | 5 (33) |
| 5 (10) | 4 (12) | 4 (16) | 1 (17) | 4 (21) | 5 (26) | 3 (29) | 3 (32) |
| 1 (11) | 3 (14) | 2 (16) | 3 (19) | 5 (24) | 4 (28) | 5 (33) | 5 (37) |
Answer = 37.
Table for Subtask (c):
| 15 (15) | 21 (36) | 29 (65) | 15 (80) | 28 (108) | 39 (147) |
| 27 (42) | 37 (73) | 34 (99) | 21 (101) | 17 (118) | 30 (147) |
| 28 (70) | 14 (84) | 30 (114) | 13 (114) | 38 (152) | 34 (182) |
| 25 (95) | 13 (97) | 31 (128) | 38 (152) | 23 (175) | 40 (215) |
| 16 (111) | 21 (118) | 20 (138) | 28 (166) | 14 (180) | 4 (184) |
Answer = 184.
