I. Idiotic Suffix Array

Codeforces

IDCF10260I

Time1000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

Cuber QQ did not know about the _Suffix Array_ before, now he knows. So he eagerly wants to teach you. Now he takes a string containing only lowercase letters as an example and builds a _Suffix Array_ with the following C++ code on a supercomputer. For example, the _Suffix Array_ of "_ecnu_" is ${1, 0, 2, 3}$ and the _Suffix Array_ of "_cubercsl_" is ${2, 5, 0, 3, 7, 4, 6, 1}$. It's definitely not satisfying enough for Cuber QQ to show off his algorithm skills, so he wants to test you with a problem. He will give you two integers $n$ and $k$ ($1 <= k <= n$), you are required to answer him a string of length $n$ containing only lowercase letters and satisfying _sa[k - 1] == 0_, where _sa_ is the _Suffix Array_ of the string built by the code above. TL;DR, you are required to answer a string of length $n$ containing only lowercase letters and it ranks $k$-th smallest among all its suffixes in lexicographical order. We can show that an answer always exists. A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds: Two integers $n$, $k$ ($1 <= k <= n <= 10^5$) — the length of the string and the rank of the string itself among all its suffixes. Output the answer, which is a string of length $n$ only containing lowercase letters. If there are multiple answers, print any of them. ## Input Two integers $n$, $k$ ($1 <= k <= n <= 10^5$) — the length of the string and the rank of the string itself among all its suffixes. ## Output Output the answer, which is a string of length $n$ only containing lowercase letters.If there are multiple answers, print any of them. [samples]

Let $n, k \in \mathbb{Z}$ with $1 \leq k \leq n \leq 10^5$. Construct a string $s \in \{a, b, \dots, z\}^n$ such that the suffix starting at index $0$ (i.e., $s[0:n]$) is the $k$-th lexicographically smallest suffix among all suffixes $s[i:n]$ for $i \in \{0, 1, \dots, n-1\}$. **Objective:** Find any string $s$ of length $n$ such that $\text{sa}[k-1] = 0$, where $\text{sa}$ is the suffix array of $s$.

API Response (JSON)

{
  "problem": {
    "name": "I. Idiotic Suffix Array",
    "description": {
      "content": "Cuber QQ did not know about the _Suffix Array_ before, now he knows. So he eagerly wants to teach you. Now he takes a string containing only lowercase letters as an example and builds a _Suffix Array",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10260I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Cuber QQ did not know about the _Suffix Array_ before, now he knows. So he eagerly wants to teach you.\n\nNow he takes a string containing only lowercase letters as an example and builds a _Suffix Array...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $n, k \\in \\mathbb{Z}$ with $1 \\leq k \\leq n \\leq 10^5$.  \nConstruct a string $s \\in \\{a, b, \\dots, z\\}^n$ such that the suffix starting at index $0$ (i.e., $s[0:n]$) is the $k$-th lexicographicall...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments