You are not logged in. Please login at to post your questions!


GO5 Editorial


Problem Link:


Author: Shivam Jindal




Dynamic Programming, Convex Hull


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.


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 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 code for complete understanding of the solution.

This question is marked "community wiki".

asked 13 Sep '18, 21:51

s_jindal00's gravatar image

accept rate: 0%

edited 13 Sep '18, 21:52

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 13 Sep '18, 21:51

question was seen: 57 times

last updated: 13 Sep '18, 21:52