CCOQR '16 - Data Structure - Olympiads Online Judge

CCOQR '16 - Data Structure

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 0.4s

Memory limit: 64M

Author:

SourSpinach

Problem types

It's a well-known fact that, inside computers, all data is stored in 2D pyramids of data blocks.

A certain pyramid has $N$ $N$ ( $1 \le N \le 10^9$ $1 \leq N \leq 10^{9}$ ) rows, numbered $1 \dots N$ $1 \dots N$ from top to bottom. Each row $r$ $r$ has $r$ $r$ block spaces, which are labelled $(r, 1) \dots (r, r)$ $(r, 1) \dots (r, r)$ from left to right. Each block space $(r, c)$ $(r, c)$ in rows $1 \dots (N-1)$ $1 \dots (N - 1)$ rests on top of two supporting block spaces in the row below it — block spaces $(r+1, c)$ $(r + 1, c)$ and $(r+1, c+1)$ $(r + 1, c + 1)$ . For example, a pyramid with 6 rows is illustrated below, with block spaces $(3, 1)$ $(3, 1)$ , $(4, 4)$ $(4, 4)$ , and $(6, 2)$ $(6, 2)$ indicated in red:

$\text{[math]}$

Now, each block space may either contain data, or be empty. A block space containing data is only stable if it's in the bottom row (row $N$ $N$ ), or if both of its two supporting block spaces also contain data. The entire pyramid is only stable if all of its non-empty block spaces are stable.

You know that there are $M$ $M$ ( $1 \le M \le 10^5$ $1 \leq M \leq 10^{5}$ ) different block spaces which must contain data - the $i^{th}$ $i^{t h}$ of these is block space $(r_i, c_i)$ $(r_{i}, c_{i})$ ( $1 \le c_i \le r_i \le N$ $1 \leq c_{i} \leq r_{i} \leq N$ ). All of the other block spaces in the pyramid may either be filled with arbitrary data or be left empty. However, everyone knows that data is expensive. As such, you're interested in the smallest amount of data that the pyramid's block spaces can contain such that at least the $M$ $M$ required block spaces contain data, and the entire data structure is stable.

Subtasks

For 3 of the 15 marks available, $N \le 100$ $N \leq 100$ and $M \le 200$ $M \leq 200$ .
For another 3 of the 15 marks available, $N \le 2\,000$ $N \leq 2 000$ and $M \le 10^5$ $M \leq 10^{5}$ .
For another 3 of the 15 marks available, $N \le 10^9$ $N \leq 10^{9}$ and $M \le 2$ $M \leq 2$ .

Note that the original data were weak, so an additional test case was added to the first two subtasks. Data were provided by dxke02.

Input Specification

The first line of the input contains two integers, $N$ $N$ and $M$ $M$ . The remaining $M$ $M$ lines each contain two integers, $r_i$ $r_{i}$ and $c_i$ $c_{i}$ for $i = 1 \dots M$ $i = 1 \dots M$ .

Output Specification

Output a single integer, the minimum number of block spaces which can contain data such that the entire pyramid is stable. Note that this value may not fit in a 32-bit signed integer, and may need to be stored in a long long / long / int64 variable in C++ / Java / Pascal, respectively.

Sample Input

Copy

Output for Sample Input

Copy

Explanation for Output for Sample Input

The diagram below illustrates the pyramid described by the sample case, where the 3 red block spaces must contain data, while the 12 orange block spaces represent the optimal set of blocks to additionally fill with data to make the entire pyramid stable.

$\text{[math]}$

Comments

0

maxcruickshanks commented 99 days ago

Since the original data were weak, an additional test case was added to the first two batches, and all submissions were rejudged. Data were provided by dxke02.

2

Evan_Yu123 commented on Nov. 2, 2017, 1:59 p.m.

Is it guaranteed that the answer can be stored in a 64 bit integer? What if the test case is 10e9 1 1 1 ?

2

Kirito commented on Nov. 2, 2017, 4:59 p.m.

The answer to that case is on the order of $5 \times 10^{17}$ $5 \times 10^{17}$ , which fits in a 64-bit integer.

2

Evan_Yu123 commented on Nov. 2, 2017, 7:32 p.m.

Sorry im dumb, i think i typed 2^54 into my calculator earlier

3

Kirito commented on Nov. 3, 2017, 1:33 a.m.

10e9 is actually $10^{10}$ $10^{10}$ , 1e9 is $10^9$ $10^{9}$ . That might be why.

5

Evan_Yu123 commented on Nov. 3, 2017, 12:32 p.m.

UGHH whats wrong with me, thx for all ur help

31

ImbaCalvin commented on Dec. 13, 2016, 6:16 p.m.

How is this a data structure problem?

4

Lost commented on March 20, 2021, 11:50 p.m.

The problem is about a structure that contains data, not a data structure problem

162

bruce commented on Jan. 19, 2017, 11:29 p.m.

You're right Data structure is not a data structure problem, Convex hull is not a convex hull problem, Gaussian elimination is not a Gaussian elimination problem, Heavy-light decomposition is not a heavy-light decomposition problem. This is the real world~

10

harry7557558 commented on April 8, 2020, 2:31 a.m. ← edit 3 →

Raytracing is not a ray tracing problem, Gradient Descent is not a gradient descent problem.

9

moladan123 commented on March 25, 2016, 1:55 p.m.

Is anyone interested in making editorials for these ccoqr problems?