All Tracks Algorithms Searching Binary Search Problem

Matrix sum
Tag(s):

Algorithms, Binary Search, Easy-Medium, approved

Problem
Editorial
Analytics

Assume that you are given an $$N∗N$$ matrix $$A$$ and an integer $$K$$. You are required to find the top left and bottom right co-ordinates of the smallest square sub-matrix of $$A$$ such that the sum of all the elements in the square sub-matrix is $$ \ge K $$

A sub-matrix of the original matrix having co-ordinates $$(x1,y1)$$, $$(x2,y2)$$ is considered to be a square sub-matrix if $$ |x1-x2|>=0$$ and $$ x2-x1 $$ = $$ y2-y1 $$.

All elements $$(i,j)$$, where $$ x1 \le i \le x2$$, and $$ y1 \le j \le y2$$ are considered to be a part of the square $$(x1,y1)$$, $$(x2,y2)$$

Input

  • First line comprises two space-separated integers $$N$$ and $$K$$

  • Each of the next $$N$$ lines contains $$N$$ space separated integers. where the $$j^{th}$$ integer on the $$i^{th}$$ line denotes $$A[i][j]$$.

Output :

If there exists a matrix satisfying the above conditions, then on the first line print "YES" (without quotes). On the next line, Print four space-separated integers $$x1$$, $$y1$$, $$x2$$, and $$y2$$, which denote the top left and bottom right positions of the smallest square sub-matrix of $$A$$ such that the sum of all the elements in the square sub-matrix is $$ \ge $$ to $$K$$. If there are multiple answers, print any one answer.

If there is no such square sub-matrix, then print "NO" without quotes.

Constraints

  • $$1 \le N \le 250 $$

  • $$ 0 \le A[i][j] \le 10^9 $$

  • $$1 \le K \le 10^{15}$$

SAMPLE INPUT
3 12
11 1 0
1 11 0
0 0 0
SAMPLE OUTPUT
YES
1 1 2 2
Explanation

The square matrix having top right co-ordinates $$ (1,1) $$ and bottom right co-ordinates $$ (2,2) $$ has sum equal to $$ 11 + 1 + 1 + 11 \ge 12 $$. The side length of this square is $$2$$, and no smaller square sub-matrix has sum $$ \ge K $$

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Zauba Technologies & Data Services Private Limited

Challenge Name

Zauba Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications