F. Cell Borders

Codeforces

IDCF10286F

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given a strip of paper that consists of $n$ consecutive square cells. The cells are numbered $1$ to $n$ from left to right. Each cell has an integer written in it, which is either $0$, $1$, or $2$. Denote the integer in the $i$-th cell by $a_i$. You can color black any number of the left or right borders of these cells (there are $n + 1$ such borders in total). Is it possible to color the borders in such a way that for each cell $i$, the number of its borders that is colored is equal to $a_i$? For example, if you are given the numbers $1 med 2 med 1 med 0 med 1 med 2$, then it is possible to color the borders as follows: The first line of input contains a single integer $n$, the number of cells ($1 <= n <= 10^5$). The next line contains $n$ integers $a_1$, $\\dots$, $a_n$ ($0 <= a_i <= 2$), the numbers of colored borders the cells $1$, $\\dots$, $n$ should have. If it is possible, output "_Yes_" in a single line, otherwise output "_No_". ## Input The first line of input contains a single integer $n$, the number of cells ($1 <= n <= 10^5$). The next line contains $n$ integers $a_1$, $\\dots$, $a_n$ ($0 <= a_i <= 2$), the numbers of colored borders the cells $1$, $\\dots$, $n$ should have. ## Output If it is possible, output "_Yes_" in a single line, otherwise output "_No_". [samples]

**Definitions** Let $ n, q \in \mathbb{Z}^+ $ be the number of crewmate intervals and admin observations, respectively. Let $ I = \{ [l_i, r_i] \mid i \in \{1, \dots, n\} \} $ be the set of time intervals claimed by crewmates. Let $ O = \{ (t_j, v_j) \mid j \in \{1, \dots, q\} \} $ be the set of admin observations, where $ t_j $ is a time and $ v_j $ is the observed count. For any time $ x \in \mathbb{Z}^+ $, define the **true count** function: $$ f(x) = \left| \left\{ i \in \{1, \dots, n\} \mid x \in [l_i, r_i] \right\} \right| $$ **Constraints** 1. $ 1 \le n, q \le 10^4 $ 2. $ 1 \le l_i \le r_i \le 10^{18} $ for all $ i $ 3. $ 1 \le t_j \le 10^{18} $, $ 0 \le v_j \le 10^{18} $ for all $ j $ **Objective** Find the smallest $ t_j $ such that $ f(t_j) \ne v_j $. If no such $ t_j $ exists, output $ -1 $.

API Response (JSON)

{
  "problem": {
    "name": "F. Cell Borders",
    "description": {
      "content": "You are given a strip of paper that consists of $n$ consecutive square cells. The cells are numbered $1$ to $n$ from left to right. Each cell has an integer written in it, which is either $0$, $1$, or",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10286F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a strip of paper that consists of $n$ consecutive square cells. The cells are numbered $1$ to $n$ from left to right. Each cell has an integer written in it, which is either $0$, $1$, or...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ be the number of crewmate intervals and admin observations, respectively.  \nLet $ I = \\{ [l_i, r_i] \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of time i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments