A. Daniel and Perpendophobia

Codeforces

IDCF10245A

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

_Daniel is a master on Codeforces, thus he is particularly fond of golden color_. Instead of maintaining his streak of master title on Codeforces, Daniel decides to take a day off and goes for real golden treasures in a remote location. Though the place that he chooses to dig gold is quite complicated, for the sake of simplicity, Daniel models it as the first quadrant of the Cartesian plane: The place contains $N$ gold mines in different coordinates. Daniel does not care how much value of gold he could take, but he wants to explore as many gold mines as possible. As he is eager to explore, he considers the following strategy: So, can you calculate the maximum number of gold mines that Daniel could explore, if he executes his strategy optimally? The first line contains integer $N (N >= 1)$. $N$ lines follow, each line contains 2 integer $x, y " "(0 <= x, y <= 10^9)$ denoting the coordinate of a gold mine. It is guaranteed that no two gold mines is located on the same spot and no goal mine is located at $O (0, 0)$. Integers on the same line are separated by spaces. A single integer denoting the maximum number of gold mines that Daniel could explore, if he executes his strategy optimally. This problem worths 60 points. Subtasks: ## Input The first line contains integer $N (N >= 1)$.$N$ lines follow, each line contains 2 integer $x, y " "(0 <= x, y <= 10^9)$ denoting the coordinate of a gold mine. It is guaranteed that no two gold mines is located on the same spot and no goal mine is located at $O (0, 0)$.Integers on the same line are separated by spaces. ## Output A single integer denoting the maximum number of gold mines that Daniel could explore, if he executes his strategy optimally. [samples] ## Scoring This problem worths 60 points.Subtasks: 5 points: $N <= 10$. 15 points: $N <= 20$. 20 points: $N <= 400$. 20 points: $N <= 80000$.

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of gold mines. Let $ P = \{ (x_i, y_i) \mid i \in \{1, \dots, N\} \} $ be the set of distinct gold mine coordinates in $ \mathbb{Z}_{\geq 0}^2 \setminus \{(0,0)\} $. **Constraints** 1. $ 1 \leq N \leq 10^5 $ 2. $ 0 \leq x_i, y_i \leq 10^9 $ for all $ i $ 3. $ (x_i, y_i) \neq (0,0) $ for all $ i $ 4. All points in $ P $ are distinct. **Objective** Find the maximum size of a subset $ S \subseteq P $ such that the points in $ S $ can be ordered as $ (x_1, y_1), (x_2, y_2), \dots, (x_k, y_k) $ with $ x_1 \leq x_2 \leq \dots \leq x_k $ and $ y_1 \leq y_2 \leq \dots \leq y_k $, i.e., $ S $ forms a non-decreasing chain under the partial order $ (x_i, y_i) \leq (x_j, y_j) \iff x_i \leq x_j \land y_i \leq y_j $. Equivalently, compute the length of the longest chain in $ P $ under component-wise $ \leq $.

API Response (JSON)

{
  "problem": {
    "name": "A. Daniel and Perpendophobia",
    "description": {
      "content": "_Daniel is a master on Codeforces, thus he is particularly fond of golden color_. Instead of maintaining his streak of master title on Codeforces, Daniel decides to take a day off and goes for real g",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10245A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_Daniel is a master on Codeforces, thus he is particularly fond of golden color_.\n\nInstead of maintaining his streak of master title on Codeforces, Daniel decides to take a day off and goes for real g...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of gold mines.  \nLet $ P = \\{ (x_i, y_i) \\mid i \\in \\{1, \\dots, N\\} \\} $ be the set of distinct gold mine coordinates in $ \\mathbb{Z}_{\\geq 0...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments