F. Almost Permutation

Codeforces

IDCF863F

Time3000ms

Memory512MB

Difficulty—

flows

English · Original

Chinese · Translation

Formal · Original

Recently Ivan noticed an array _a_ while debugging his code. Now Ivan can't remember this array, but the bug he was trying to fix didn't go away, so Ivan thinks that the data from this array might help him to reproduce the bug. Ivan clearly remembers that there were _n_ elements in the array, and each element was not less than 1 and not greater than _n_. Also he remembers _q_ facts about the array. There are two types of facts that Ivan remembers: * 1 _l__i_ _r__i_ _v__i_ — for each _x_ such that _l__i_ ≤ _x_ ≤ _r__i_ _a__x_ ≥ _v__i_; * 2 _l__i_ _r__i_ _v__i_ — for each _x_ such that _l__i_ ≤ _x_ ≤ _r__i_ _a__x_ ≤ _v__i_. Also Ivan thinks that this array was a permutation, but he is not so sure about it. He wants to restore some array that corresponds to the _q_ facts that he remembers and is very similar to permutation. Formally, Ivan has denoted the _cost_ of array as follows: , where _cnt_(_i_) is the number of occurences of _i_ in the array. Help Ivan to determine minimum possible _cost_ of the array that corresponds to the facts! ## Input The first line contains two integer numbers _n_ and _q_ (1 ≤ _n_ ≤ 50, 0 ≤ _q_ ≤ 100). Then _q_ lines follow, each representing a fact about the array. _i_\-th line contains the numbers _t__i_, _l__i_, _r__i_ and _v__i_ for _i_\-th fact (1 ≤ _t__i_ ≤ 2, 1 ≤ _l__i_ ≤ _r__i_ ≤ _n_, 1 ≤ _v__i_ ≤ _n_, _t__i_ denotes the type of the fact). ## Output If the facts are controversial and there is no array that corresponds to them, print _\-1_. Otherwise, print minimum possible _cost_ of the array. [samples]

最近，Ivan 在调试代码时注意到一个数组 #cf_span[a]。现在 Ivan 已经不记得这个数组了，但他试图修复的 bug 仍然存在，因此他认为这个数组中的数据可能有助于他复现该 bug。 Ivan 清楚地记得，该数组包含 #cf_span[n] 个元素，每个元素的值不小于 #cf_span[1] 且不大于 #cf_span[n]。此外，他还记得 #cf_span[q] 条关于该数组的事实。Ivan 记住的事实有两种类型：此外，Ivan 认为这个数组是一个排列，但他对此并不十分确定。他希望恢复一个符合他所记得的 #cf_span[q] 条事实、且与排列非常相似的数组。形式上，Ivan 将数组的 #cf_span[cost] 定义为：，其中 #cf_span[cnt(i)] 是数字 #cf_span[i] 在数组中出现的次数。请帮助 Ivan 确定符合所给事实的数组的最小可能 #cf_span[cost]！第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 50]，#cf_span[0 ≤ q ≤ 100]）。接下来 #cf_span[q] 行，每行表示一条关于数组的事实。第 #cf_span[i] 行包含四个数：#cf_span[ti]、#cf_span[li]、#cf_span[ri] 和 #cf_span[vi]（#cf_span[1 ≤ ti ≤ 2]，#cf_span[1 ≤ li ≤ ri ≤ n]，#cf_span[1 ≤ vi ≤ n]，其中 #cf_span[ti] 表示事实的类型）。如果这些事实相互矛盾，不存在符合它们的数组，则输出 _-1_。否则，输出符合事实的数组的最小可能 #cf_span[cost]。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 50]，#cf_span[0 ≤ q ≤ 100]）。接下来 #cf_span[q] 行，每行表示一条关于数组的事实。第 #cf_span[i] 行包含四个数：#cf_span[ti]、#cf_span[li]、#cf_span[ri] 和 #cf_span[vi]（#cf_span[1 ≤ ti ≤ 2]，#cf_span[1 ≤ li ≤ ri ≤ n]，#cf_span[1 ≤ vi ≤ n]，其中 #cf_span[ti] 表示事实的类型）。 ## Output 如果这些事实相互矛盾，不存在符合它们的数组，则输出 _-1_。否则，输出符合事实的数组的最小可能 #cf_span[cost]。 [samples]

**Definitions** Let $ n, q \in \mathbb{Z} $ with $ 1 \leq n \leq 50 $, $ 0 \leq q \leq 100 $. Let $ A = (a_1, a_2, \dots, a_n) $ be an array where each $ a_i \in \{1, 2, \dots, n\} $. Let $ \text{cnt}(i) = |\{ j \in \{1, \dots, n\} \mid a_j = i \}| $ be the frequency of value $ i $ in $ A $. Define the **cost** of $ A $ as: $$ \text{cost}(A) = \sum_{i=1}^n \text{cnt}(i)^2 $$ Let $ F = \{ (t_k, l_k, r_k, v_k) \mid k \in \{1, \dots, q\} \} $ be a set of constraints, where for each fact: - If $ t_k = 1 $: $ \forall j \in [l_k, r_k],\ a_j = v_k $ - If $ t_k = 2 $: $ \forall j \in [l_k, r_k],\ a_j \neq v_k $ **Constraints** 1. For each $ k \in \{1, \dots, q\} $: - $ 1 \leq l_k \leq r_k \leq n $ - $ 1 \leq v_k \leq n $ 2. All constraints in $ F $ must be simultaneously satisfiable. **Objective** Find the minimum possible $ \text{cost}(A) $ over all arrays $ A \in \{1, \dots, n\}^n $ satisfying $ F $. If no such $ A $ exists, output $ -1 $.

Samples

Input #1

3 0

Output #1

Input #2

3 1
1 1 3 2

Output #2

Input #3

3 2
1 1 3 2
2 1 3 2

Output #3

Input #4

3 2
1 1 3 2
2 1 3 1

Output #4

\-1

API Response (JSON)

{
  "problem": {
    "name": "F. Almost Permutation",
    "description": {
      "content": "Recently Ivan noticed an array _a_ while debugging his code. Now Ivan can't remember this array, but the bug he was trying to fix didn't go away, so Ivan thinks that the data from this array might hel",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF863F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Recently Ivan noticed an array _a_ while debugging his code. Now Ivan can't remember this array, but the bug he was trying to fix didn't go away, so Ivan thinks that the data from this array might hel...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "最近，Ivan 在调试代码时注意到一个数组 #cf_span[a]。现在 Ivan 已经不记得这个数组了，但他试图修复的 bug 仍然存在，因此他认为这个数组中的数据可能有助于他复现该 bug。\n\nIvan 清楚地记得，该数组包含 #cf_span[n] 个元素，每个元素的值不小于 #cf_span[1] 且不大于 #cf_span[n]。此外，他还记得 #cf_span[q] 条关于该数组的事实...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, q \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 50 $, $ 0 \\leq q \\leq 100 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be an array where each $ a_i \\in \\{1, 2, \\dots, n\\} $.  \nLet $ \\tex...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments