Google Kickstart

general
,
1

https://code.google.com/codejam/contest/12254486/dashboard#s=p1

Problem

Codejamon trainers are actively looking for monsters, but if you are not a trainer, these monsters could be really dangerous for you. You might want to find safe places that do not have any monsters!

Consider our world as a grid, and some of the cells have been occupied by monsters. We define a safe square as a grid-aligned D × D square of grid cells (with D ≥ 1) that does not contain any monsters. Your task is to find out how many safe squares (of any size) we have in the entire world.
Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line with three integers, R, C, and K. The grid has R rows and C columns, and contains K monsters. K more lines follow; each contains two integers Ri and Ci, indicating the row and column that the i-th monster is in. (Rows are numbered from top to bottom, starting from 0; columns are numbered from left to right, starting from 0.)
Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the the total number of safe zones for this test case.
Limits

1 ≤ T ≤ 20.

(Ri, Ci) ≠ (Rj, Cj) for i ≠ j. (No two monsters are in the same grid cell.)

0 ≤ Ri < R, i from 1 to K

0 ≤ Ci < C, i from 1 to K

Small dataset

1 ≤ R ≤ 10.

1 ≤ C ≤ 10.

0 ≤ K ≤ 10.

Large dataset

1 ≤ R ≤ 3000.

1 ≤ C ≤ 3000.

0 ≤ K ≤ 3000.

Sample

2

3 3 1

2 1

Case #1: 10

4 11 12

0 1

0 3

0 4

0 10

1 0

1 9

2 0

2 4

2 9

2 10

3 4

3 10

Case #2: 51

The grid of sample case #1 is:

0 0 0

0 0 0

0 1 0

Here, 0 represents a cell with no monster, and 1 represents a cell with a monster. It has 10 safe squares: 8 1x1 and 2 2x2.

The grid of sample case #2 is:

0 1 0 1 1 0 0 0 0 0 1

1 0 0 0 0 0 0 0 0 1 0

1 0 0 0 1 0 0 0 0 1 1

0 0 0 0 1 0 0 0 0 0 1

Note that sample case #2 will only appear in the Large dataset. It has 51 safe squares: 32 1x1, 13 2x2, 5 3x3, and 1 4x4.

Please Explain me how to solve this.

2

Consider this situation.


0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 1

We consider top leftmost point as point(i,j) and its adjacent point as (i,j+1), (i+1,j), (i+1,j+1)
First of all we try to find out what is the max possible length of the square starting from adjacent points of point (i,j).

For point (i,j+1) max possible size of square is 2 unit, for point (i+1,j) is 2 unit and for point (i+1,j+1) is 1 unit (distance between two zero’s is considered as one unit length). Now we have to look upon that what is the maximum possible length of the square formed by extending anyone of these squares into a square starting from point (i,j).

Can we extend maximum possible square starting from (i+1,j) into a square starting from point (i,j)?? NO, We can’t. Because when we’ll try to extend this square, we’ll find that the next element is 1 at the righmost corner.

Can we extend maximum possible square starting from (i,j+1) into a square starting from point (i,j)??
NO, We can’t. Because when we’ll try to extend this square, we’ll find that the one of element at the rightmost corner is is 1.So, we can’t extend this square.

Can we extend maximum possible square starting from (i+1,j+1) into a square starting from point (i,j)??
YES, We can.

So, After little thinking, we can realize that out of three point adjacent to (i,j) we are able to extend only those square from these points, which is smallest among them.

So,Size of max possible square for point (i,j) is the minimum size of maximum square possible from these adjacent points plus 1.

Let assume that dp[i,j+1] represents maximum possible size of square from point (i,j+1) and dp[i+1,j] for point (i+1,j) and dp[i+1,j+1] for point (i,j).

so, dp[i,j]=min(dp[i,j+1],dp[i+1,j],dp[i+1,j+1])+1;

Now, we know the value of max possible size of square from point (i,j). How can we find the no. of different size squares possible from that point?? It’s equal to dp[i,j]+1. Extra one for zero size square.

So, overall answer will be equal to sum of (dp[i,j]+1) for every points which are represented by zero.
It is a 2D dynamic programming question where you have to scan the elements from the right bottom of the grid.