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

×

GO5 Editorial

0
1

Problem Link:

Practice

Author: Shivam Jindal

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 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, 21:51

s_jindal00's gravatar image

5★s_jindal00
1
accept rate: 0%

edited 13 Sep, 21:52

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,952
×142
×18
×10

question asked: 13 Sep, 21:51

question was seen: 44 times

last updated: 13 Sep, 21:52