A. Two Subsequences

Codeforces

IDCF10286A

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given a permutation $p$ of integers $1$ to $n$. You need to partition $p$ into two disjoint increasing subsequences such that the difference between the sizes of these subsequences is the maximum possible. Note that each element must belong to exactly one of the subsequences. The empty subsequence is also allowed. The first line contains a single integer $n$ ($1 <= n <= 5 dot.op 10^5$), the number of elements in the permutation. The second line contains $n$ integers $p_i$ ($1 <= p_i <= n$), where the $i$-th of them equals the $i$-th element of the permutation. It is guaranteed that each integer from ${1, \\dots, n}$ appears exactly once among $p_i$. Output a single integer, the maximum difference of sizes of subsequences. If it is not possible to partition the permutation into two disjoint increasing subsequences, output $-1$. ## Input The first line contains a single integer $n$ ($1 <= n <= 5 dot.op 10^5$), the number of elements in the permutation. The second line contains $n$ integers $p_i$ ($1 <= p_i <= n$), where the $i$-th of them equals the $i$-th element of the permutation. It is guaranteed that each integer from ${1, \\dots, n}$ appears exactly once among $p_i$. ## Output Output a single integer, the maximum difference of sizes of subsequences. If it is not possible to partition the permutation into two disjoint increasing subsequences, output $-1$. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of target patterns. For each target pattern $ k \in \{1, \dots, T\} $: - Let $ N_k \in \mathbb{Z} $ be the length of the target pattern ($1 \leq N_k \leq 9$). - Let $ R_k \in \mathbb{Z} $ be the number of observed repeats ($1 \leq R_k \leq 100$). - For each repeat $ j \in \{1, \dots, R_k\} $, let $ r_{k,j} \in \mathbb{Z} $ be the number of observed flashes, and let $ F_{k,j} = (f_{k,j}^1, f_{k,j}^2, \dots, f_{k,j}^{r_{k,j}}) $ be the sequence of observed button locations (distinct letters from $\{A, B, \dots, I\}$), representing a subsequence of the target pattern. **Constraints** 1. $1 \leq T \leq 1000$ 2. For each $k$: - $1 \leq N_k \leq 9$ - $1 \leq R_k \leq 100$ - $1 \leq r_{k,j} \leq N_k$ for all $j$ - All elements in each $F_{k,j}$ are distinct and from $\{A, B, \dots, I\}$ - Each $F_{k,j}$ is a subsequence (not necessarily contiguous) of the target pattern $P_k = (p_k^1, p_k^2, \dots, p_k^{N_k})$, which contains no repeated elements. **Objective** For each target pattern $k$, determine if there exists a **unique** permutation $P_k$ of $N_k$ distinct letters from $\{A, \dots, I\}$ such that every observed sequence $F_{k,j}$ is a subsequence of $P_k$. - If exactly one such $P_k$ exists, output $P_k$. - Otherwise, output "NOT ENOUGH INFO".

API Response (JSON)

{
  "problem": {
    "name": "A. Two Subsequences",
    "description": {
      "content": "You are given a permutation $p$ of integers $1$ to $n$. You need to partition $p$ into two disjoint increasing subsequences such that the difference between the sizes of these subsequences is the maxi",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10286A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a permutation $p$ of integers $1$ to $n$. You need to partition $p$ into two disjoint increasing subsequences such that the difference between the sizes of these subsequences is the maxi...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of target patterns.  \nFor each target pattern $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ N_k \\in \\mathbb{Z} $ be the length of the target pattern ($1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments