K. The Dragon and the Kingdom of Trees

Codeforces

IDCF10241K

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Ayoub hates King Mahmoud, who is the king of a very large kingdom that is famous for planting very tall trees. King Mahmoud started a new plan to plant $n$ trees, so he planted $n$ seeds in $n$ consecutive places. Initially, the height of every tree is $0$ units. Every year the height of every tree increases by one unit, but in some years Ayoub comes and chooses exactly $k$ non-intersecting sub-arrays of trees and attack them with his dragon. When a tree is attacked the seed won't be affected, so it can grow again, but its height becomes "0". King Mahmoud came after $m$ years and found that the height of the $i_{t h}$ tree is $h_i$ units. King Mahmoud noticed that in some years Ayoub's dragon came and attacked the plants. King Mahmoud became very angry and decided to attack Ayoub with his army. Ayoub is very powerful with his dragon but King Mahmoud has a strategy to take down Ayoub, but he needs to know the minimum possible $k$ so that the heights of the trees are correct. King Mahmoud knows that Ayoub attacked at least once, it can also happen that Ayoub attacked immediately after they planted the seeds in the first year. It can happen that there is no possible $k$, in that case, Ayoub has cheated and used a different way to attack King Mahmoud's plants, in this case, King's Mahmoud strategy will fail so he won't attack Ayoub. The first line contains two integers $n$ and $m$ $(1 <= n <= 10^6)$ $(1 <= m <= 10^9)$. The second line contains $n$ integers, the $i_{t h}$ one is $h_i$ which is the height of the $i_{t h}$ $(0 <= h_i <= m)$ plant after $m$ years. If there is no possible $k$ print _-1_, otherwise print the minimum possible $k$ on a line. ## Input The first line contains two integers $n$ and $m$ $(1 <= n <= 10^6)$ $(1 <= m <= 10^9)$.The second line contains $n$ integers, the $i_{t h}$ one is $h_i$ which is the height of the $i_{t h}$ $(0 <= h_i <= m)$ plant after $m$ years. ## Output If there is no possible $k$ print _-1_, otherwise print the minimum possible $k$ on a line. [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $, with $ 1 \leq n \leq 10^6 $, $ 1 \leq m \leq 10^9 $. Let $ H = (h_1, h_2, \dots, h_n) $ be a sequence of integers with $ 0 \leq h_i \leq m $ for all $ i \in \{1, \dots, n\} $. **Constraints** Each $ h_i $ represents the final height of tree $ i $ after $ m $ years, where: - Initially, all trees have height 0. - Each year, all trees grow by 1 unit unless attacked. - In some years, Ayoub selects exactly $ k $ non-intersecting contiguous subarrays and resets the height of all trees in those subarrays to 0. - Ayoub attacks at least once. **Objective** Find the minimum integer $ k \geq 1 $ such that $ H $ can be produced by exactly $ k $ attacks (each resetting a set of non-overlapping contiguous subarrays) over $ m $ years. If no such $ k $ exists, output $ -1 $.

API Response (JSON)

{
  "problem": {
    "name": "K. The Dragon and the Kingdom of Trees",
    "description": {
      "content": "Ayoub hates King Mahmoud, who is the king of a very large kingdom that is famous for planting very tall trees. King Mahmoud started a new plan to plant $n$ trees, so he planted $n$ seeds in $n$ conse",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10241K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ayoub hates King Mahmoud, who is the king of a very large kingdom that is famous for planting very tall trees.\n\nKing Mahmoud started a new plan to plant $n$ trees, so he planted $n$ seeds in $n$ conse...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $, with $ 1 \\leq n \\leq 10^6 $, $ 1 \\leq m \\leq 10^9 $.  \nLet $ H = (h_1, h_2, \\dots, h_n) $ be a sequence of integers with $ 0 \\leq h_i \\leq m $ for all ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments