A9 Interview Question for abcs
- 0of 0 votes
AnswerToday Jin has given a task to Shino, Shino has to travel from cell
- pooja.senger86 October 29, 2017 in United States
(
1
,
1
)
(1,1) to cell
(
N
,
M
)
(N,M) in a grid of size
N
∗
M
N∗M. But in order make this task interesting for Shino, Jin has decided to keep some special candies in some
K
K special cells of the grid, where each candy has an amount of happiness associated with it.
Shino can travel only in right & down direction in the grid, as he is too careful & does not want to fall out of grid. Now, we call the value of a path the happiness of all cells lying on the path. All non-special cells have happiness equal to
0
0.
Now, you need to find and print the sum of the values of all paths from
(
1
,
1
)
(1,1) to
(
N
,
M
)
(N,M), traveling only right and down to an adjacent cell.
As Shino is not good at counting help him find the answer.
Input Format
The first Line contains a single integer
T
T denoting number of test cases
The next line contains
3
3 space separated integers,
N
N,
M
M and
K
K where N * M is the size of grid & K denoting number of special cells
The next
K
K lines contains three integers
X
i
,
Y
i
,
H
i
Xi,Yi,Hi where
(
X
i
,
Y
i
)
(Xi,Yi) is cell coordinate &
H
i
Hi is the amount of happiness Shino will get from a candy at cell
(
X
i
,
Y
i
)
(Xi,Yi)
Constraints
1
≤
T
≤
3
1≤T≤3
1
≤
N
,
M
,
K
≤
10
5
1≤N,M,K≤105
1
≤
X
i
≤
N
,
1
≤
Y
i
≤
M
1≤Xi≤N,1≤Yi≤M
1
≤
H
i
≤
10
5
1≤Hi≤105
Output Format
For each test case you will output a single integer denoting the total amount of happiness Shino will get. As the answer can be quiet large you can output answer modulo
10
9
+
7
109+7
Sample Input
1
2 2 2
1 2 4
2 1 7
Sample Output
11| Report Duplicate | Flag | PURGE
A9 abc .Net/C Algorithm Java
Interview Type: Written Test
DP soln. - O(n^2)
- sudip.innovates October 31, 2017