E. Liner vectors

Codeforces

IDCF10280E

Time1000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Given you two integers $N$,$K$,you need to construct a set of $N$-dimensional vectors of size $N$.Each dimension of each vector can only be $0$ or $1$. And for a vector, its sum of all dimensions is $K$. Meanwhile, any vector can't be represented by other vectors using $X O R$ operation. If such a vector group exists, find the minimum vector group, otherwise output $-1$. (Define the minimum set of vectors as the minimum lexicographic order after each vector is converted to binary) There are $T (1 <= T <= 1000)$ test cases in this problem. For every test case,the first line has two integer $N (1 <= N <= 62)$,$K (1 <= K <= N)$. If the vector group does not exist, output $-1$. Otherwise output the minimum vector group, expressed in decimal notation. ## Input There are $T (1 <= T <= 1000)$ test cases in this problem.For every test case,the first line has two integer $N (1 <= N <= 62)$,$K (1 <= K <= N)$. ## Output If the vector group does not exist, output $-1$.Otherwise output the minimum vector group, expressed in decimal notation. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the string $ S $. Let $ SA = (sa_1, sa_2, \dots, sa_n) $ be the suffix array, where $ sa_i \in \{1, \dots, n\} $ are distinct and represent the starting positions of the $ i $-th lexicographically smallest suffix. Let $ \text{height} = (h_2, h_3, \dots, h_n) $ be the height array, where $ h_i \in \mathbb{Z}_{\geq 0} \cup \{-1\} $, and $ h_i = -1 $ denotes an erased value; otherwise, $ h_i $ is the length of the longest common prefix (LCP) between the suffixes starting at $ sa_{i-1} $ and $ sa_i $. **Constraints** 1. $ 1 \leq n \leq 5000 $ 2. $ SA $ is a permutation of $ \{1, 2, \dots, n\} $ 3. For each $ i \in \{2, \dots, n\} $: - If $ h_i \neq -1 $, then $ \text{LCP}(S[sa_{i-1}:], S[sa_i:]) = h_i $ - If $ h_i = -1 $, then $ \text{LCP}(S[sa_{i-1}:], S[sa_i:]) $ is unconstrained (to be determined) **Objective** Find the lexicographically smallest string $ S \in \{a, b, \dots, z\}^n $ satisfying the above constraints.

API Response (JSON)

{
  "problem": {
    "name": "E. Liner vectors",
    "description": {
      "content": "Given you two integers $N$,$K$,you need to construct a set of $N$-dimensional vectors of size $N$.Each dimension of each vector can only be $0$ or $1$. And for a vector, its sum of all dimensions is $",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10280E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given you two integers $N$,$K$,you need to construct a set of $N$-dimensional vectors of size $N$.Each dimension of each vector can only be $0$ or $1$. And for a vector, its sum of all dimensions is $...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the string $ S $.  \nLet $ SA = (sa_1, sa_2, \\dots, sa_n) $ be the suffix array, where $ sa_i \\in \\{1, \\dots, n\\} $ are distinct and repres...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments