C. Qualification Rounds

Codeforces

IDCF868C

Time2000ms

Memory256MB

Difficulty—

bitmasksbrute forceconstructive algorithmsdp

English · Original

Chinese · Translation

Formal · Original

Snark and Philip are preparing the problemset for the upcoming pre-qualification round for semi-quarter-finals. They have a bank of _n_ problems, and they want to select any non-empty subset of it as a problemset. _k_ experienced teams are participating in the contest. Some of these teams already know some of the problems. To make the contest interesting for them, each of the teams should know at most half of the selected problems. Determine if Snark and Philip can make an interesting problemset! ## Input The first line contains two integers _n_, _k_ (1 ≤ _n_ ≤ 105, 1 ≤ _k_ ≤ 4) — the number of problems and the number of experienced teams. Each of the next _n_ lines contains _k_ integers, each equal to 0 or 1. The _j_\-th number in the _i_\-th line is 1 if _j_\-th team knows _i_\-th problem and 0 otherwise. ## Output Print "_YES_" (quotes for clarity), if it is possible to make an interesting problemset, and "_NO_" otherwise. You can print each character either upper- or lowercase ("_YeS_" and "_yes_" are valid when the answer is "_YES_"). [samples] ## Note In the first example you can't make any interesting problemset, because the first team knows all problems. In the second example you can choose the first and the third problems.

Snark 和 Philip 正在为即将举行的半四分之一决赛预选赛准备题库。他们有一个包含 #cf_span[n] 道题的题库，并希望从中选出任意非空子集作为题库。 #cf_span[k] 支有经验的队伍将参加比赛。其中一些队伍已经知道部分题目。为了使比赛对这些队伍具有挑战性，每支队伍知道的选中题目数量不得超过选中题目总数的一半。请判断 Snark 和 Philip 是否能组成一个有趣的题库！第一行包含两个整数 #cf_span[n], #cf_span[k] (#cf_span[1 ≤ n ≤ 105], #cf_span[1 ≤ k ≤ 4]) —— 题目数量和有经验队伍的数量。接下来的 #cf_span[n] 行，每行包含 #cf_span[k] 个整数，每个整数为 #cf_span[0] 或 #cf_span[1]。第 #cf_span[i] 行的第 #cf_span[j] 个数为 #cf_span[1] 表示第 #cf_span[j] 支队伍知道第 #cf_span[i] 道题，为 #cf_span[0] 则表示不知道。如果可以组成一个有趣的题库，请输出 "_YES_"（不含引号），否则输出 "_NO_"。你可以以任意大小写形式输出（例如 "_YeS_" 和 "_yes_" 在答案为 "_YES_" 时均有效）。在第一个示例中，你无法组成任何有趣的题库，因为第一支队伍知道所有题目。在第二个示例中，你可以选择第一道和第三道题目。 ## Input 第一行包含两个整数 #cf_span[n], #cf_span[k] (#cf_span[1 ≤ n ≤ 105], #cf_span[1 ≤ k ≤ 4]) —— 题目数量和有经验队伍的数量。接下来的 #cf_span[n] 行，每行包含 #cf_span[k] 个整数，每个整数为 #cf_span[0] 或 #cf_span[1]。第 #cf_span[i] 行的第 #cf_span[j] 个数为 #cf_span[1] 表示第 #cf_span[j] 支队伍知道第 #cf_span[i] 道题，为 #cf_span[0] 则表示不知道。 ## Output 如果可以组成一个有趣的题库，请输出 "_YES_"（不含引号），否则输出 "_NO_"。你可以以任意大小写形式输出（例如 "_YeS_" 和 "_yes_" 在答案为 "_YES_" 时均有效）。 [samples] ## Note 在第一个示例中，你无法组成任何有趣的题库，因为第一支队伍知道所有题目。在第二个示例中，你可以选择第一道和第三道题目。

**Definitions** Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 10^5 $, $ 1 \leq k \leq 4 $. Let $ P = \{p_1, p_2, \dots, p_n\} $ be the set of problems. For each problem $ p_i $, define a binary vector $ v_i \in \{0,1\}^k $, where $ v_i[j] = 1 $ if team $ j $ knows problem $ p_i $, and $ 0 $ otherwise. Let $ S \subseteq P $, $ S \neq \emptyset $, be a selected non-empty subset of problems. For each team $ j \in \{1, \dots, k\} $, define: $$ c_j(S) = \sum_{p_i \in S} v_i[j] $$ as the number of problems in $ S $ known to team $ j $. **Constraints** For all $ j \in \{1, \dots, k\} $: $$ c_j(S) \leq \left\lfloor \frac{|S|}{2} \right\rfloor $$ **Objective** Determine whether there exists a non-empty subset $ S \subseteq P $ satisfying the above constraints.

Samples

Input #1

Output #1

NO

Input #2

Output #2

YES

API Response (JSON)

{
  "problem": {
    "name": "C. Qualification Rounds",
    "description": {
      "content": "Snark and Philip are preparing the problemset for the upcoming pre-qualification round for semi-quarter-finals. They have a bank of _n_ problems, and they want to select any non-empty subset of it as ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF868C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Snark and Philip are preparing the problemset for the upcoming pre-qualification round for semi-quarter-finals. They have a bank of _n_ problems, and they want to select any non-empty subset of it as ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Snark 和 Philip 正在为即将举行的半四分之一决赛预选赛准备题库。他们有一个包含 #cf_span[n] 道题的题库，并希望从中选出任意非空子集作为题库。\n\n#cf_span[k] 支有经验的队伍将参加比赛。其中一些队伍已经知道部分题目。为了使比赛对这些队伍具有挑战性，每支队伍知道的选中题目数量不得超过选中题目总数的一半。\n\n请判断 Snark 和 Philip 是否能组成一个有趣的题库...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 10^5 $, $ 1 \\leq k \\leq 4 $.  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} $ be the set of problems.  \nFor each problem $ p_i $, define a bi...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments