IITKESO207SPA3D - Largest bunch of zeros

no tags 

Problem description



You are given a mxn binary matrix (contains only 1s and 0s). You have to use dynamic programming to find the largest contiguous square containing only zeros in the matrix. 



Input format

The input will contain two lines. The first line will contain three integers m n x which denote the row size, column size, and number of 1s in the matrix. The second line will consist of x pairs of integers, each denoting the location of a 1 in the matrix.


Output format

 You are required to print out two pairs of coordinates, that denote the top left and the bottom right of the square formed by the contiguos set of zeros. If there are multiple solutions, print the rectangle sorted by the coordinates of the top left vertex, first along row number, then along column.

In case the solution is not present, print just one integer 0. In case the solution is just one square, print starting and ending as the same point (so you would print x y x y if the square is located at x y )


Sample input

3 4 4

0 3 1 1 1 2 2 0

Sample output

0 0 0 0


Notice that here there are two rectangles with the largest size, but the one printed is the one with top left vertex sorted according to row index, and then along column index.

Scoring method


Please note that apart from the sample test case posted here, there will be other hidden test cases that your code will checked on. The final score you see is a percentage of the test cases you have passed. If you pass only the sample test case, you will get 0/100 (even though your score will be shown as 10/100).


Each of these questions are finally worth the points mentioned in the assignment pdf file. So your credit for this problem shall be your score/100 * points for this question. Your final credit for programming assignment 3 shall be final score / 55 * 100.


Plagiarism and copying


Strict action will be taken against students who are found to be indulging in plagiarism.  Please note that changing variable names, removing indentation or moving code around will not help with regards to plagiarism checking.

hide comments
daud_spoj2015: 2017-07-03 21:31:56

Last edit: 2017-07-05 13:50:10
wisfaq: 2017-07-02 15:13:20

Please note that this assignment is visible and solvable for the general public.
I hate to be adressed as a student at my age. I could be your father if not your grandfather I think.
I hate the fact that there seems to be a pdf I haven't seen.
I don't see how in the case of plagiarism you can take strict actions against. me as I live thousands of miles away from you.

If you want to make assignments for students use one of the other options that SPOJ has to offer.

Have a nice day.

Last edit: 2017-07-02 15:13:48
Programming Club, IITK: 2017-06-30 05:11:38

Description has been updated, thank you for pointing out the error.

alpha_codeboy: 2017-06-29 21:28:55

sample test case is invalid but test cases are valid

pawanrocks: 2017-06-29 16:14:34

The given sample test case is:
3 4 4
0 3 1 1 1 2 3 0
is wrong (according to my understanding of question)
Coordinate 3, 0 cannot exist...will give segmentation fault.
I think it must be 0, 3... which also produces the same result: 0 0 0 0.

Last edit: 2017-06-29 16:15:11
vipiitk: 2017-06-29 10:56:46

If row = 3 and Column =4
but matrix(3,0)=1, How can this possible ? (In the sample Input)

Programming Club, IITK: 2017-06-29 07:19:53

Sort the top left vertex of each answer by their row, and then by column. Print the first answer from this ordering.

alpha_codeboy: 2017-06-27 21:52:50

There can be multiple answers, whose co-ordinates we need to print then?

Last edit: 2017-06-28 08:40:56

Added by:Programming Club, IITK
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:ESO207, IIT Kanpur Summer Semester 2017