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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, 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

?