2016 Canadian Computing Olympiad Qualifying Round
Problem Q3: Data Structure
It's a well-known fact that, inside computers, all data is stored in 2D pyramids of data blocks.
A certain pyramid has N (1 ≤ N ≤ 109) rows, numbered 1..N from top to bottom. Each row r has r block spaces, which are labelled (r, 1)..(r, r) from left to right. Each block space (r, c) in rows 1..(N − 1) rests on top of two supporting block spaces in the row below it – block spaces (r + 1, c) and (r + 1, c + 1). For example, a pyramid with 6 rows is illustrated below, with block spaces (3, 1), (4, 4), and (6, 2) indicated in red:
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), 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 (1 ≤ M ≤ 105) different block spaces which must contain data – the i-th of these is block space (ri, ci) (1 ≤ ci ≤ ri ≤ N). All of the other block spaces in the pyramid may either be filled with abitrary 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 required block spaces contain data, and the entire data structure is stable.
For 3 of the 15 marks available, N ≤ 100 and M ≤ 200.
For another 3 of the 15 marks available, N ≤ 2000 and M ≤ 105.
For another 3 of the 15 marks available, N ≤ 109 and M ≤ 2.
The first line of the input contains two integers, N and M. The remaining M lines each contain two integers, ri and ci for i = 1..M.
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 /
int64 variable in C++ / Java / Pascal, respectively.
6 3 3 1 4 4 6 2
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.
Point Value: 17 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Mar 09, 2016
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Edit: I've rejudged at least one submission for each user to whom this would make a difference.