All Tracks Algorithms Dynamic Programming Problem

Game
Tag(s):

Algorithms, Dynamic Programming, Easy

Problem
Editorial
Analytics

Consider the following game. There is a field with $$n$$ rows and $$3$$ columns. Some cells contain obstacles. But the first row is always empty. Let's define cell in $$i$$-th row and $$j$$-th column as $$(i, j)$$. From cell $$(i, j)$$ you can go to cells $$(i + 1, j - 1)$$, $$(i + 1, j)$$ and $$(i + 1, j + 1)$$ if such cell exists (you can't go out of field) and doesn't contain obstacle. You can start in any column in the first row. What is the maximum $$i$$, such that $$i$$-th row is reachable?

Input format

Given several test cases.

First line of input contains integer $$T$$ ($$1 \leq T \leq 3 \cdot 10^5$$) — number of test cases.

Then follow $$T$$ blocks of input.

The first line of block contains integers $$n$$ and $$q$$ ($$2 \leq n \leq 10^9$$, $$0 \leq q \leq \min(3 \cdot 10^5, 3 \cdot (n - 1))$$) — number of rows and number of obstacles, respectively.

Then follow $$q$$ lines with obstacles description.

The $$i$$-th of them contains integers $$x$$ and $$y$$ ($$2 \leq x \leq n$$, $$1 \leq y \leq 3$$) — the coordinates of $$i$$-th obstacle, located at $$(x, y)$$.

Coordinates of all obstacles in a single test case are pairwise distinct.

Sum of all $$q$$ in input doesn't exceed $$3 \cdot 10^5$$.

Output format

For each block print single integer — the maximum row that is possible to be reached.

SAMPLE INPUT
2
4 3
2 2
2 3
4 1
2 3
2 1
2 2
2 3
SAMPLE OUTPUT
4
1
Explanation

In the first test case one of the optimal paths is $$(1, 2)$$, $$(2, 1)$$, $$(3, 2)$$, $$(4, 2)$$. So the row $$4$$ is possible to be reached.

In the second test case there are no possible moves from $$(1, 2)$$. So only the row $$1$$ is possible to be reached.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 512 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

HackerEarth

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications