All Tracks Algorithms Searching Ternary Search Problem

Puzzled Grid
Tag(s):

Algorithms, Binary Search, Medium-Hard

Problem
Editorial
Analytics

Today, you need to solve a problem on a Puzzled Grid game. "In a grid of $$n \times n$$ size, where each cell has a positive integer, two players compete in several rounds.

Each round starts by both players putting a rock in a random location of the grid. Then, the two players must connect the two rocks with a line that passes through the grid cells (e.g: from a grid cell the line can can expand either horizontally or vertically and never out the grid). Since there may be a lot of ways to connect the two stones, we are only interested in those lines that minimizes the highest cell in their path (e.g: the cell with the highest number should be as small as possible).

You need to find and print this minimized maximum. Can you do it?

Input:

First line contains two integers $$n$$ and $$Q$$, where $$n$$ is the grid size and $$Q$$ is the number of rounds of the game. Next $$n$$ lines contain each $$n$$ integer denoting the grid cell numbers. Then, next $$Q$$ lines contain each $$4$$ integers $$x1, y1, x2, y2$$ denoting the first and second stone locations -- the indexes are 0 based and the origin is the top leftmost cell.

Output:

Print $$Q$$ lines, each denoting the answer for each round.

Constraints:

  • $$2 \le n \le 500$$.
  • Grid cell numbers are less than or equal $$10^6$$.
  • At the start of each round the stones are in different locations.
  • $$1 \le Q \le 10^5$$.
SAMPLE INPUT
3 2
1 1 2 
5 6 10
1 2 1
0 0 2 2
1 1 0 2
SAMPLE OUTPUT
5
6
Explanation

Left grid show he optimal solution for the first round, and the right one for the second round

Left grid shows the optimal solution for the first round, and the right one is for the second round.

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

HackerEarth

Challenge Name

HackerEarth Collegiate Cup - Mirror Round

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications