Simple Subsequence Problem

AtCoder

IDagc024_f

Time2000ms

Memory256MB

Difficulty—

You are given a set $S$ of strings consisting of `0` and `1`, and an integer $K$. Find the longest string that is a subsequence of $K$ or more different strings in $S$. If there are multiple strings that satisfy this condition, find the lexicographically smallest such string. Here, $S$ is given in the format below: * The data directly given to you is an integer $N$, and $N+1$ strings $X_0,X_1,...,X_N$. For every $i$ $(0\leq i\leq N)$, the length of $X_i$ is $2^i$. * For every pair of two integers $(i,j)$ $(0\leq i\leq N,0\leq j\leq 2^i-1)$, the $j$\-th character of $X_i$ is `1` if and only if the binary representation of $j$ with $i$ digits (possibly with leading zeros) belongs to $S$. Here, the first and last characters in $X_i$ are called the $0$\-th and $(2^i-1)$\-th characters, respectively. * $S$ does not contain a string with length $N+1$ or more. Here, a string $A$ is a subsequence of another string $B$ when there exists a sequence of integers $t_1 < ... < t_{|A|}$ such that, for every $i$ $(1\leq i\leq |A|)$, the $i$\-th character of $A$ and the $t_i$\-th character of $B$ is equal. ## Constraints * $0 \leq N \leq 20$ * $X_i(0\leq i\leq N)$ is a string of length $2^i$ consisting of `0` and `1`. * $1 \leq K \leq |S|$ * $K$ is an integer. ## Input Input is given from Standard Input in the following format: $N$ $K$ $X_0$ $:$ $X_N$ [samples]

Samples

Input #1

Output #1

10

The following strings belong to $S$: the empty string, `1`, `00`, `10`, `11`, `001`, `100`, `101` and `110`. The lexicographically smallest string among the longest strings that are subsequences of four or more of them is `10`.

Input #2

4 6
1
01
1011
10111010
1101110011111101

Output #2

Input #3

Output #3

The answer is the empty string.

API Response (JSON)

{
  "problem": {
    "name": "Simple Subsequence Problem",
    "description": {
      "content": "You are given a set $S$ of strings consisting of `0` and `1`, and an integer $K$. Find the longest string that is a subsequence of $K$ or more different strings in $S$. If there are multiple strings t",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc024_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a set $S$ of strings consisting of `0` and `1`, and an integer $K$.\nFind the longest string that is a subsequence of $K$ or more different strings in $S$. If there are multiple strings t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments