Problem Link:
[Practice][1]
Author: [Shivam Jindal][2]
Difficulty:
Hard
Prerequisites:
Dynamic Programming, Convex Hull
Problem:
Given a grid, you have to count no. of ways to reach from one corner to another corner where some of the cells are blocked and with the constraint that you can take a maximum of k1, k2 number of steps in up and right direction respectively.
Approach:
First find all the blocked cells. Then, the question is simply dynamic programming based where for each cell you have to maintain the count of number of ways to reach that cell when the last x < k1 steps were taken in up direction and y < k2 steps taken in right direction. Hence the state of dp is (i,j,steps,direc) where i,j is the cell coordinate and direc is boolean - up or right.
How to find blocked cells?
Notice that all the jammers will form a polygon which is the convex hull of all the given points and any (x,y) point that lies inside or on the convex hull is unreachable. So for each cell, you need to find whether any of it’s four corners is lying inside or on the convex hull polygon. If none of them is, the cell is not blocked.
For any cell on the gird with coordinates (x, y) the corresponding corners on the Cartesian plane are: (x,y), (x,y+1), (x+1,y), (x+1,y+1).
To check whether a point lies in the polygon we can use the [horizontal line algorithm][3] in O(p) where p is the number of vertices of the polygon. Now, notice that in a grid of N*N, no matter how many jammer points you are given, the convex hull will be having O(N) number of vertices. Hence to find all blocked cells, the cost is 4*N*N*N and time complexity is O(N^3).
The time complexity of dynamic programming is O(N^3) as well which becomes the overall complexity of the solution.
Author’s solution:
Refer to this
[4] for complete understanding of the solution.
[1]: https://www.codechef.com/problems/GO5
[2]: https://www.codechef.com/users/s_jindal00
[3]: https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/
[4]: https://www.codechef.com/viewsolution/20143188