VM7WC '16 #5 Silver - Jayden Plays Video Games

View as PDF

Submit solution

All submissions

Best submissions

Points: 15

Time limit: 1.0s

Memory limit: 64M

Author:

JeffreyZ

Problem types

I made a mistake while writing this problem, causing it to be much harder than originally intended. My flawed solution used simple recursion, but the actual solution requires segment trees. To fix this problem, I've made a new silver problem for this contest. Please solve that one instead.

Jayden is a little kid that likes to play video games. One of the games that he likes to play is Lumberjack, where the player, a lumberjack, must make a living by cutting down trees in a forest and selling them to a carpenter.

While playing the game, Jayden finds $N$ $N$ trees in the forest, all in a line. The $i^\text{th}$ $i^{th}$ tree will be at position $x_i$ $x_{i}$ on the line, with no tree sharing the same point. Since Jayden is a smart kid, he realizes that the trees will act like dominoes. When cutting a tree, it will fall to either the left or the right of the tree. If the tree has a height of $h_i$ $h_{i}$ and falls to the right, it will cause all trees located at positions $x_i+1$ $x_{i} + 1$ to $x_i+h_i$ $x_{i} + h_{i}$ , inclusive, to fall to the right as well. Similarly, if that tree falls to the left, all trees located at positions $x_i-h_i$ $x_{i} - h_{i}$ to $x_i-1$ $x_{i} - 1$ , inclusive, will also fall to the left.

For example, say that there are four trees of height $2$ $2$ at positions $1$ $1$ , $2$ $2$ , $3$ $3$ , and $5$ $5$ . If Jayden cuts down the tree at position $1$ $1$ and causes it to fall to the right, the second and third trees will also fall as a result. When the tree at position $3$ $3$ falls, it causes the tree at position $5$ $5$ to fall as well. By cutting down just one tree, the tree at position $1$ $1$ , Jayden can cause all of the trees in the line to fall.

Jayden can control the direction a tree falls when he cuts it. Given the line of trees he has found, what is the least amount of trees that Jayden has to cut in order to cause the entire line of trees to fall?

Input Specification

On the first line will be the integer $N$ $N$ $(1 \le N \le 10^3)$ $(1 \leq N \leq 10^{3})$ . The next $N$ $N$ lines will contain $x_i$ $x_{i}$ and $h_i$ $h_{i}$ $(1 \le x_i, h_i \le 10^8)$ $(1 \leq x_{i}, h_{i} \leq 10^{8})$ , two integers that describe the position and height of the $i^\text{th}$ $i^{th}$ tree.

Output Specification

On a single line, print out the least amount of trees that Jayden has to cut down.

Sample Input

Copy

Sample Output

Copy

Comments

7

jeffreyxiao commented on Feb. 7, 2016, 7:58 p.m. ← edited →

https://wcipeg.com/problem/domino

0

XIAOAGE commented on Feb. 5, 2016, 11:52 p.m. ← edit 5 →

Do the test cases include cases such as:

input: 4 1 1 3 1 5 1 7 6

output: 1

My code cannot pass the case above and i get AC.

5
d commented on Feb. 6, 2016, 4:31 a.m.
Not the same case, but two of my AC solutions give a different answer for

Copy
6 10 1 20 1 30 1 40 100 50 1 60 1

-1

JeffreyZ commented on Feb. 6, 2016, 2:28 a.m.

It should -- I remember having something similar as a case.