PROBLEM LINK:
Author: Pratik Dayama
Tester: Pratik Dayama
Editorialist: Aakash Jain
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Greedy algorithms, Math
PROBLEM:
Given a triangle of the form
3
7 4
2 3 6
8 5 9 3
Find the first top-to-bottom path with the maximum weight. Find the number of paths, starting with the leftmost path, that will be encountered until the maximum weight path is traversed and report this number modulo 1000000007.
QUICK EXPLANATION:
Start from the bottom row of the triangle and make a greedy choice of the greater value between each pair of adjacent numbers. Add that value to the value immediately above the pair. Also in a separate array, store 0 if first no was greater or 1 if second no was greater. Bubble upwards in this manner through each row until the top is reached.
To calculate the number of paths, start from the top and follow the left most edge as long as 0 is present. If 1 is present, go to the right and add 2^i to the number of paths, where i is the number of levels left till the bottom. Continue this until the bottom row is reached. This can be sped up by precomputing the value of 2^i for all 0 <= i <= 1000.
EXPLANATION:
The first step involves a greedy strategy to find out the maximum sum path in the triangle. We store the triangle in a 2D matrix tri[][], so tri[0][0] is the starting point and tri[n][…] is the last row.
We start from the bottom and go upto the second row of the triangle. For each row, we consider each pair of adjecent elements and add the greater of the two to the value just above them.
Also we form another matrix compute[][]. compute[i][j] is 0 if the left element below tri[i][j] is greater, or 1 if the right element below tri[i][j] is greater.
Pseudo-code:
if tri[i][j] < tri[i][j+1]
tri[i-1][j] = tri[i-1][j] + tri[i][j+1]
compute[i-1][j] = 1
else
tri[i-1][j] = tri[i-1][j] + tri[i][j+1]
compute[i-1][j] = 0
Once we have computed the compute[][] matrix, we must find the number of paths before the maximum one. We start at the top of the triangle. If compute[i][j] is 0, we simply move downwards to the left. If it is 1, we move downwards to the right, and add 2^(n-i-1) to our answer. n-i-1 is the number of rows left till the bottom of the triangle. This works since the number of distinct paths in such a triangle of height x is 2^(x-1),
Notice that we repeatedly need to find 2^x. We can speed up our solution considerably by precomputing 2^i % 1000000007 for all 0 <= i <= 1000 (since our constraint for number of rows in the triangle is 1000) and storing it in pow2[].
Pseudo-code:
i = j = 0
sum = 1
while 1
while compute[i,j] == 0 and i < n
i++
if i > n
break
i++
j++
sum = (sum + pow2[n-i-1]) % MOD
The final solution is in sum.
AUTHOR’S SOLUTION:
Author’s solution can be found here.