KDCT04 - Editorial

PROBLEM LINKS

Contest

DIFFICULTY

medium

PROBLEM

You have an NxN grid. Each cell can either be traversed or is blocked. There are Q obstacles in the grid, each one starts from a given point and extends till the end of the grid in a particular direction (given either left or right). You are also given a start cell (X,Y).How many cells are reachable from the start cell if you can go left, right, up, and down, and you cannot traverse obstacles?

EXPLANATION

If the grid were small, we could just do a BFS from the start square. This is O(N^2), which is much too big for N=10^9. However, we can coordinate compress the grid.

The key idea is that MOST ROWS ARE DUPLICATES. The only time row R is different than row R+1 is if an obstacle starts or ends on R or R+1. But there are only 100 obstacles, so this only happens ~100 times. Once we’ve identified these interesting rows, we know that all the other rows are duplicates of them, so we can compress the grid down into ~100 interesting rows. The same applies for columns. Once we’ve compressed the grid, we can run the BFS.

Now find all the rows where the obstacles start or end and sort them. Same way find all the columns too. Now build up a new grid such that each cell here is either a blocked part of row or column or the free space between the blocked rows or columns.

Now find the block where the start point is present in. This can be done when building up the new grid. No run a bfs and find the answer.