K-th Beautiful String (Codeforces 1328B)
Tags: Math, combinatorics

For the given integer $$$n$$$ ($$$n > 2$$$) let's write down all the strings of length $$$n$$$ which contain $$$n-2$$$ letters 'a' and two letters 'b' in lexicographical (alphabetical) order.Recall that the string $$$s$$$ of length $$$n$$$ is lexicographically less than string $$$t$$$ of length $$$n$$$, if there exists such $$$i$$$ ($$$1 \le i \le n$$$), that $$$s_i < t_i$$$, and for any $$$j$$$ ($$$1 \le j < i$$$) $$$s_j = t_j$$$. The lexicographic comparison of strings is implemented by the operator < in modern programming languages.For example, if $$$n=5$$$ the strings are (the order does matter):  aaabb  aabab  aabba  abaab  ababa  abbaa  baaab  baaba  babaa  bbaaa It is easy to show that such a list of strings will contain exactly $$$\frac{n \cdot (n-1)}{2}$$$ strings.You are given $$$n$$$ ($$$n > 2$$$) and $$$k$$$ ($$$1 \le k \le \frac{n \cdot (n-1)}{2}$$$). Print the $$$k$$$-th string from the list.

Input: The input contains one or more test cases.The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test. Then $$$t$$$ test cases follow.Each test case is written on the the separate line containing two integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 10^5, 1 \le k \le \min(2\cdot10^9, \frac{n \cdot (n-1)}{2})$$$.The sum of values $$$n$$$ over all test cases in the test doesn't exceed $$$10^5$$$.

Output: For each test case print the $$$k$$$-th string from the list of all described above strings of length $$$n$$$. Strings in the list are sorted lexicographically (alphabetically).


Sample Inputs:
7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

Sample Outputs:
aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa

Solution (Python):
from sys import stdin
input = stdin.readline

def ri():
    return int(input())

def rl(v_type=int, output=list):
    return output(map(v_type, input().split()))

def rs():
    return input()[:-1]

def out(x, sep='\n'):
    print(sep.join(x))

def solve():
    (n, k) = rl(output=tuple)
    no = int((2 * k) ** 0.5)
    if no * (no + 1) / 2 < k:
        no += 1
    excess = k - no * (no - 1) / 2
    ans = 'a' * int(n - no - 1) + 'b' + 'a' * int(no - excess) + 'b' + 'a' * int(excess - 1)
    return ans
output = []
for _ in range(ri()):
    output.append(str(solve()))
out(output)

Solution (Python):
import sys
input = sys.stdin.readline
t = 1
mod = 998244353
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    if k == 1:
        print('a' * (n - 2) + 'b' * 2)
        continue
    for i in range(1, 100000):
        if i * (i + 1) // 2 >= k:
            break
    k -= i * (i - 1) // 2
    i += 1
    print('a' * (n - i) + 'b' + 'a' * (i - k - 1) + 'b' + 'a' * (k - 1))

Solution (Python):
def s():
    (n, m) = map(int, input().split())
    delta = 1 + 8 * m
    f = int((-1 + delta ** 0.5) // 2)
    while f * (f + 1) // 2 < m:
        f += 1
    s = max(m - f * (f - 1) // 2, 0)
    f += 1
    res = (n - f) * 'a' + 'b' + (f - s - 1) * 'a' + 'b' + 'a' * (s - 1)
    return res + '\n'
t = int(input())
res = ''
for x in range(t):
    res += s()
print(res)