E. New Year and Old Subsequence

Codeforces

IDCF750E

Time3000ms

Memory256MB

Difficulty—

data structuresdivide and conquerdpmatrices

English · Original

Chinese · Translation

Formal · Original

A string _t_ is called _nice_ if a string "_2017_" occurs in _t_ as a **subsequence** but a string "_2016_" doesn't occur in _t_ as a **subsequence**. For example, strings "_203434107_" and "_9220617_" are nice, while strings "_20016_", "_1234_" and "_20167_" aren't nice. The _ugliness_ of a string is the minimum possible number of characters to remove, in order to obtain a nice string. If it's impossible to make a string nice by removing characters, its ugliness is - 1. Limak has a string _s_ of length _n_, with characters indexed 1 through _n_. He asks you _q_ queries. In the _i_\-th query you should compute and print the ugliness of a **substring** (continuous subsequence) of _s_ starting at the index _a__i_ and ending at the index _b__i_ (inclusive). ## Input The first line of the input contains two integers _n_ and _q_ (4 ≤ _n_ ≤ 200 000, 1 ≤ _q_ ≤ 200 000) — the length of the string _s_ and the number of queries respectively. The second line contains a string _s_ of length _n_. Every character is one of digits '_0_'–'_9_'. The _i_\-th of next _q_ lines contains two integers _a__i_ and _b__i_ (1 ≤ _a__i_ ≤ _b__i_ ≤ _n_), describing a substring in the _i_\-th query. ## Output For each query print the ugliness of the given substring. [samples] ## Note In the first sample: * In the first query, _ugliness_("_20166766_") = 4 because all four sixes must be removed. * In the second query, _ugliness_("_2016676_") = 3 because all three sixes must be removed. * In the third query, _ugliness_("_0166766_") = - 1 because it's impossible to remove some digits to get a nice string. In the second sample: * In the second query, _ugliness_("_01201666209167_") = 2. It's optimal to remove the first digit '_2_' and the last digit '_6_', what gives a string "_010166620917_", which is nice. * In the third query, _ugliness_("_016662091670_") = 1. It's optimal to remove the last digit '_6_', what gives a nice string "_01666209170_".

一个字符串 #cf_span[t] 被称为 _nice_，当且仅当字符串 "_2017_" 作为 *子序列* 出现在 #cf_span[t] 中，但字符串 "_2016_" 不作为 *子序列* 出现在 #cf_span[t] 中。例如，字符串 "_203434107_" 和 "_9220617_" 是 nice 的，而字符串 "_20016_"、"_1234_" 和 "_20167_" 不是 nice 的。一个字符串的 _ugliness_ 是为了获得一个 nice 字符串所需移除的最少字符数。如果无法通过移除字符使字符串变成 nice，则其 ugliness 为 #cf_span[ - 1]。 Limak 有一个长度为 #cf_span[n] 的字符串 #cf_span[s]，字符索引从 #cf_span[1] 到 #cf_span[n]。他向你提出 #cf_span[q] 个查询。在第 #cf_span[i] 个查询中，你需要计算并输出字符串 #cf_span[s] 中从索引 #cf_span[ai] 开始、到索引 #cf_span[bi] 结束（包含两端）的 *子串* 的 ugliness。输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[4 ≤ n ≤ 200 000], #cf_span[1 ≤ q ≤ 200 000]) —— 分别表示字符串 #cf_span[s] 的长度和查询次数。第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]。每个字符都是数字 '_0_' 到 '_9_' 之一。接下来的 #cf_span[q] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai ≤ bi ≤ n])，描述第 #cf_span[i] 个查询中的子串。对于每个查询，请输出对应子串的 ugliness。在第一个样例中：在第二个样例中： ## Input 输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[4 ≤ n ≤ 200 000], #cf_span[1 ≤ q ≤ 200 000]) —— 分别表示字符串 #cf_span[s] 的长度和查询次数。第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]。每个字符都是数字 '_0_' 到 '_9_' 之一。第 #cf_span[i] 行是接下来的 #cf_span[q] 行之一，包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai ≤ bi ≤ n])，描述第 #cf_span[i] 个查询中的子串。 ## Output 对于每个查询，请输出对应子串的 ugliness。 [samples] ## Note 在第一个样例中：在第一个查询中，#cf_span[ugliness(]"_20166766_"#cf_span[) = 4]，因为必须移除全部四个 '6'。在第二个查询中，#cf_span[ugliness(]"_2016676_"#cf_span[) = 3]，因为必须移除全部三个 '6'。在第三个查询中，#cf_span[ugliness(]"_0166766_"#cf_span[) = - 1]，因为无法通过移除某些数字得到一个 nice 字符串。在第二个样例中：在第二个查询中，#cf_span[ugliness(]"_01201666209167_"#cf_span[) = 2]。最优策略是移除第一个 '2' 和最后一个 '6'，得到字符串 "_010166620917_"，这是一个 nice 字符串。在第三个查询中，#cf_span[ugliness(]"_016662091670_"#cf_span[) = 1]。最优策略是移除最后一个 '6'，得到 nice 字符串 "_01666209170_"。

**Definitions** Let $ s \in \{0,1,\dots,9\}^n $ be a string of length $ n $. Let $ T = \text{"2017"} $, $ F = \text{"2016"} $. A substring $ s[a:b] $ is *nice* if $ T $ is a subsequence of $ s[a:b] $ and $ F $ is **not** a subsequence of $ s[a:b] $. The *ugliness* of a substring $ s[a:b] $ is the minimum number of characters to remove so that the result is nice. If no such removal exists, ugliness is $ -1 $. **Constraints** 1. $ 4 \le n \le 200{,}000 $ 2. $ 1 \le q \le 200{,}000 $ 3. For each query $ i $, $ 1 \le a_i \le b_i \le n $ **Objective** For each query $ i $, compute: $$ u_i = \min \left\{ k \in \mathbb{N}_0 \,\middle|\, \exists S \subseteq s[a_i:b_i],\, |S| = b_i - a_i + 1 - k,\, T \sqsubseteq S,\, F \not\sqsubseteq S \right\} $$ If no such $ S $ exists, then $ u_i = -1 $.

Samples

Input #1

Output #1

4
3
-1

Input #2

15 5
012016662091670
3 4
1 14
4 15
1 13
10 15

Output #2

\-1
2
1
-1
-1

Input #3

Output #3

\-1
-1

API Response (JSON)

{
  "problem": {
    "name": "E. New Year and Old Subsequence",
    "description": {
      "content": "A string _t_ is called _nice_ if a string \"_2017_\" occurs in _t_ as a **subsequence** but a string \"_2016_\" doesn't occur in _t_ as a **subsequence**. For example, strings \"_203434107_\" and \"_9220617_",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF750E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A string _t_ is called _nice_ if a string \"_2017_\" occurs in _t_ as a **subsequence** but a string \"_2016_\" doesn't occur in _t_ as a **subsequence**. For example, strings \"_203434107_\" and \"_9220617_...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一个字符串 #cf_span[t] 被称为 _nice_，当且仅当字符串 \"_2017_\" 作为 *子序列* 出现在 #cf_span[t] 中，但字符串 \"_2016_\" 不作为 *子序列* 出现在 #cf_span[t] 中。例如，字符串 \"_203434107_\" 和 \"_9220617_\" 是 nice 的，而字符串 \"_20016_\"、\"_1234_\" 和 \"_20167_\" 不是 ni...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{0,1,\\dots,9\\}^n $ be a string of length $ n $.  \nLet $ T = \\text{\"2017\"} $, $ F = \\text{\"2016\"} $.  \nA substring $ s[a:b] $ is *nice* if $ T $ is a subsequence of $ s[a...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments