K. Counting Good Teams

Codeforces

IDCF10148K

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

When building teams for programming competitions, it is a good idea to team up people that are good at different topics. For instance, it would be a good idea to team up someone who is good at graph problems and bad at geometry problems with someone who is good at geometry problems but bad at graph problems. GEMA is a programming competition study group with N members. GEMA coaches are interested in counting the number of different good teams that can be created. A good team is composed of 2 members and each member is good at at least one topic that his teammate isn't good at. Two teams are considered different if at least one member is present in one team but not in the other. GEMA coaches are only considering the M most important topics, and they know, for each member, which topics they are good at, and which topics they are bad at. The first line of the input contains two integers N (2 ≤ N ≤ 105) and M (2 ≤ M ≤ 21), indicating respectively the number of members in the study group and the number of topics that are being considered. The second line contains N integers. The i-th integer corresponds to xi (0 ≤ xi < 2M). The j-th least significant digit of the binary representation of xi is 1 if the i-th member is good at the j-th topic and 0 otherwise. For instance, if M = 5 and the i-th member has xi = 11 = (01011)2, it means that he is good at the first, second and fourth topic and bad at the third and fifth topic. Output a single integer: the number of different good teams that can be created. ## Input The first line of the input contains two integers N (2 ≤ N ≤ 105) and M (2 ≤ M ≤ 21), indicating respectively the number of members in the study group and the number of topics that are being considered. The second line contains N integers. The i-th integer corresponds to xi (0 ≤ xi < 2M). The j-th least significant digit of the binary representation of xi is 1 if the i-th member is good at the j-th topic and 0 otherwise. For instance, if M = 5 and the i-th member has xi = 11 = (01011)2, it means that he is good at the first, second and fourth topic and bad at the third and fifth topic. ## Output Output a single integer: the number of different good teams that can be created. [samples]

**Definitions** Let $ N, M \in \mathbb{Z} $ with $ 2 \leq N \leq 10^5 $, $ 2 \leq M \leq 21 $. Let $ A = (x_1, x_2, \dots, x_N) $ be a sequence of integers, where each $ x_i \in \{0, 1, \dots, 2^M - 1\} $ represents the set of topics member $ i $ is good at, encoded as a bitmask: bit $ j $ (0-indexed from LSB) is 1 iff member $ i $ is good at topic $ j+1 $. **Constraints** For all $ i \in \{1, \dots, N\} $: $ 0 \leq x_i < 2^M $. **Objective** Count the number of unordered pairs $ \{i, j\} $ with $ i \neq j $ such that: $$ (x_i \setminus x_j) \neq \emptyset \quad \text{and} \quad (x_j \setminus x_i) \neq \emptyset $$ Equivalently: $$ x_i \not\subseteq x_j \quad \text{and} \quad x_j \not\subseteq x_i $$

API Response (JSON)

{
  "problem": {
    "name": "K. Counting Good Teams",
    "description": {
      "content": "When building teams for programming competitions, it is a good idea to team up people that are good at different topics. For instance, it would be a good idea to team up someone who is good at graph p",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10148K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "When building teams for programming competitions, it is a good idea to team up people that are good at different topics. For instance, it would be a good idea to team up someone who is good at graph p...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, M \\in \\mathbb{Z} $ with $ 2 \\leq N \\leq 10^5 $, $ 2 \\leq M \\leq 21 $.  \nLet $ A = (x_1, x_2, \\dots, x_N) $ be a sequence of integers, where each $ x_i \\in \\{0, 1, \\dots, 2^M...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments