G. Almost Increasing Array

Codeforces

IDCF946G

Time3000ms

Memory512MB

Difficulty—

data structuresdp

English · Original

Chinese · Translation

Formal · Original

We call an array _almost increasing_ if we can erase not more than one element from it so that the array becomes strictly increasing (that is, every element is striclty greater than every element before it). You are given an array _a_ consisting of _n_ elements. You are allowed to replace any element with any integer number (and you may do so any number of times you need). What is the minimum number of replacements you have to perform in order to make the array _almost increasing_? ## Input The first line contains one integer _n_ (2 ≤ _n_ ≤ 200000) — the number of elements in _a_. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the array _a_. ## Output Print the minimum number of replaces you have to perform so that _a_ is _almost increasing_. [samples]

我们称一个数组为“几乎递增”的，如果我们可以从中删除不超过一个元素，使得该数组变为严格递增（即，每个元素都严格大于它之前的所有元素）。给你一个包含 #cf_span[n] 个元素的数组 #cf_span[a]。你可以将任意元素替换为任意整数（你可以根据需要进行任意次替换）。为了使数组成为“几乎递增”的，你至少需要进行多少次替换？第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 200000]) —— 数组 #cf_span[a] 中的元素个数。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[1 ≤ ai ≤ 109]) —— 数组 #cf_span[a]。请输出使 #cf_span[a] 成为“几乎递增”的最少替换次数。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 200000]) —— 数组 #cf_span[a] 中的元素个数。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[1 ≤ ai ≤ 109]) —— 数组 #cf_span[a]。 ## Output 请输出使 #cf_span[a] 成为“几乎递增”的最少替换次数。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the array. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers with $ a_i \in [1, 10^9] $. **Constraints** $ 2 \leq n \leq 200000 $ **Objective** Find the minimum number of elements to replace in $ A $ such that the resulting array is *almost increasing*, i.e., there exists an index $ j \in \{1, \dots, n\} $ such that the sequence $ A $ with the $ j $-th element removed is strictly increasing. Equivalently, find the minimum number of replacements so that there exists a subsequence of length $ n-1 $ or $ n $ that is strictly increasing, and the removed or replaced elements account for the minimal number of changes. Let $ \ell $ be the length of the longest strictly increasing subsequence (LIS) of $ A $ that can be formed with at most one "gap" allowed (i.e., skipping at most one element). Then the answer is: $$ \min_{\substack{S \subseteq \{1,\dots,n\} \\ |S| \geq n-1 \\ \text{and } A|_S \text{ is strictly increasing}}} (n - |S|) $$ Equivalently, let $ L $ be the maximum length of a strictly increasing subsequence of $ A $ that omits at most one element (i.e., $ L = \max\{ \text{LIS}(A \setminus \{a_j\}) \mid j \in \{1,\dots,n\} \} \cup \{\text{LIS}(A)\} $). Then the minimum number of replacements is: $$ n - L $$

Samples

Input #1

5
5 4 3 2 1

Output #1

Input #2

5
1 2 8 9 5

Output #2

API Response (JSON)

{
  "problem": {
    "name": "G. Almost Increasing Array",
    "description": {
      "content": "We call an array _almost increasing_ if we can erase not more than one element from it so that the array becomes strictly increasing (that is, every element is striclty greater than every element befo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF946G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We call an array _almost increasing_ if we can erase not more than one element from it so that the array becomes strictly increasing (that is, every element is striclty greater than every element befo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "我们称一个数组为“几乎递增”的，如果我们可以从中删除不超过一个元素，使得该数组变为严格递增（即，每个元素都严格大于它之前的所有元素）。\n\n给你一个包含 #cf_span[n] 个元素的数组 #cf_span[a]。你可以将任意元素替换为任意整数（你可以根据需要进行任意次替换）。为了使数组成为“几乎递增”的，你至少需要进行多少次替换？\n\n第一行包含一个整数 #cf_span[n] (#cf_span...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ a_i \\in [1, 10^9] $.\n\n**Constraints**  \n$ 2 \\leq n \\leq 200...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments