Round 1
Questions:
Problem 1:
Count number of unique ways to get a total of N using numbers m, any number of times, also mod needs to be taken. Classic DP problem.
Constraints: N*m < 10^6;
Mock solution:
dp[0] = 1; for(int i = 0; i <= Total; ++i) { for(int j = 1; j <= m; ++j) { (dp[i] += dp[i - j]) %= mod; // i >= j } }
Problem 2:
A tree is given, with every node containing a non-negative value and a value m. We need to count the number of paths in the vertical direction such that the sum of nodes in the vertical direction modulo m is zero.
Constraints: nodes < 10^6; nodes_val < 10^9; m < 10^5;
Mock approach:
Maintain a hashmap of prefix sum during the DFS. Any vertical path's sum can be deduced as (pre[i] - pre[j]) % m = 0 which is equivalent to pre[i] == pre[j].
Problem 3:
A grid is given with a start and end node, we have to find the minimum number of jumps from start to end. There are blocks, we can jump in all 4 directions. Also, there is a constraint on the jump:
- If jump length is 1, no conditions.
- If jump length is K, we have to take the next jump in the same direction of this jump. (Blocks can be bypassed in JUMP; we must not land on a blocked position)
Constraints: row <= 100 and col <= 100.
Approach:
BFS put the starting node, iterate over all cells with the same row and same column.