Split and Square

AtCoder

IDarc155_e

Time2000ms

Memory256MB

Difficulty—

For a set $X$ of non-negative integers, let $f(X)$ denote the set of non-negative integers that can be represented as the bitwise $\mathrm{XOR}$ of two integers (possibly the same) in $X$. As an example, for $X=\lbrace 1, 2, 4\rbrace$, we have $f(X)=\lbrace 0, 3, 5, 6\rbrace$. You are given a set of $N$ non-negative integers less than $2^M$: $S=\lbrace A_1, A_2, \dots, A_N\rbrace$. You may perform the following operation any number of times. * Divide $S$ into two sets $T_1$ and $T_2$ (one of them may be empty). Then, replace $S$ with the union of $f(T_1)$ and $f(T_2)$. Find the minimum number of operations needed to make $S=\lbrace 0\rbrace$. What is bitwise $\mathrm{XOR}$?The bitwise $\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows. * When $A \oplus B$ is written in binary, the $k$\-th lowest bit ($k \geq 0$) is $1$ if exactly one of the $k$\-th lowest bits of $A$ and $B$ is $1$, and $0$ otherwise. For instance, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$). Generally, the bitwise $\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \dots, p_k$ is defined as $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$, which can be proved to be independent of the order of $p_1, p_2, p_3, \dots, p_k$. ## Constraints * $1 \leq N \leq 300$ * $1 \leq M \leq 300$ * $0 \leq A_i < 2^{M}$ * $A_i\ (1\leq i \leq N)$ are pairwise distinct. * Each $A_i$ is given with exactly $M$ digits in binary (possibly with leading zeros). * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $A_1$ $A_2$ $\vdots$ $A_N$ [samples]

Samples

Input #1

Output #1

2

In the first operation, you can divide $S$ into $T_1=\lbrace 0, 1\rbrace, T_2=\lbrace 2, 3\rbrace$, for which $f(T_1) =\lbrace 0, 1\rbrace, f(T_2) =\lbrace 0, 1\rbrace$, replacing $S$ with $\lbrace 0, 1\rbrace$.
In the second operation, you can divide $S$ into $T_1=\lbrace 0\rbrace, T_2=\lbrace 1\rbrace$, making $S=\lbrace 0\rbrace$.
There is no way to make $S=\lbrace 0\rbrace$ in fewer than two operations, so the answer is $2$.

Input #2

1 8
10011011

Output #2

1

In the first operation, you can divide $S$ into $T_1=\lbrace 155\rbrace, T_2=\lbrace \rbrace$, making $S=\lbrace 0\rbrace$. Note that $T_1$ or $T_2$ may be empty.

Input #3

1 2
00

Output #3

0

We have $S=\lbrace 0\rbrace$ from the beginning; no operation is needed.

Input #4

20 20
10011011111101101111
10100111100001111100
10100111100110001111
10011011100011011111
11001000001110011010
10100111111011000101
11110100001001110010
10011011100010111001
11110100001000011010
01010011101011010011
11110100010000111100
01010011101101101111
10011011100010110111
01101111101110001110
00111100000101111010
01010011101111010100
10011011100010110100
01010011110010010011
10100111111111000001
10100111111000010101

Output #4

API Response (JSON)

{
  "problem": {
    "name": "Split and Square",
    "description": {
      "content": "For a set $X$ of non-negative integers, let $f(X)$ denote the set of non-negative integers that can be represented as the bitwise $\\mathrm{XOR}$ of two integers (possibly the same) in $X$. As an examp",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc155_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For a set $X$ of non-negative integers, let $f(X)$ denote the set of non-negative integers that can be represented as the bitwise $\\mathrm{XOR}$ of two integers (possibly the same) in $X$. As an examp...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments