BA-String (Codeforces 1620C)
Tags: Greedy, dp

You are given an integer $$$k$$$ and a string $$$s$$$ that consists only of characters 'a' (a lowercase Latin letter) and '*' (an asterisk).Each asterisk should be replaced with several (from $$$0$$$ to $$$k$$$ inclusive) lowercase Latin letters 'b'. Different asterisk can be replaced with different counts of letter 'b'.The result of the replacement is called a BA-string.Two strings $$$a$$$ and $$$b$$$ are different if they either have different lengths or there exists such a position $$$i$$$ that $$$a_i \neq b_i$$$.A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:   $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;  in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$. Now consider all different BA-strings and find the $$$x$$$-th lexicographically smallest of them.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of testcases.The first line of each testcase contains three integers $$$n$$$, $$$k$$$ and $$$x$$$ ($$$1 \le n \le 2000$$$; $$$0 \le k \le 2000$$$; $$$1 \le x \le 10^{18}$$$). $$$n$$$ is the length of string $$$s$$$.The second line of each testcase is a string $$$s$$$. It consists of $$$n$$$ characters, each of them is either 'a' (a lowercase Latin letter) or '*' (an asterisk).The sum of $$$n$$$ over all testcases doesn't exceed $$$2000$$$. For each testcase $$$x$$$ doesn't exceed the total number of different BA-strings. String $$$s$$$ contains at least one character 'a'.

Output: For each testcase, print a single string, consisting only of characters 'b' and 'a' (lowercase Latin letters) — the $$$x$$$-th lexicographically smallest BA-string.

Note: In the first testcase of the example, BA-strings ordered lexicographically are:   a  ab  abb  abbb  abbbb In the second testcase of the example, BA-strings ordered lexicographically are:   aa  aba  abba Note that string "aba" is only counted once, even though there are two ways to replace asterisks with characters 'b' to get it.

Sample Inputs:
3
2 4 3
a*
4 1 3
a**a
6 3 20
**a***

Sample Outputs:
abb
abba
babbbbbbbbb

Solution (Python):
for _ in range(int(input())):
    (n, k, x) = map(int, input().split())
    x -= 1
    s = input()[::-1]
    res = []
    i = 0
    while i < n:
        if s[i] == 'a':
            res.append(s[i])
        else:
            j = i
            while j + 1 < n and s[j + 1] == s[i]:
                j += 1
            cur = (j - i + 1) * k + 1
            res.append('b' * (x % cur))
            x //= cur
            i = j
        i += 1
    print(''.join(res[::-1]))

Solution (Python):
l = input
for o in [0] * int(l()):
    (n, k, x) = map(int, l().split())
    x -= 1
    p = 'a'
    a = [[0, 0]]
    i = 0
    r = ''
    for y in l()[::-1]:
        if y != p:
            p = y
            a += [[0, 0]] * i
            i ^= 1
        a[-1][i] += 1
    for (u, v) in a:
        m = k * v + 1
        r = x % m * 'b' + u * 'a' + r
        x //= m
    print(r)

Solution (Python):
t = int(input())
for i in range(t):
    (n, k, x) = map(int, input().split())
    s = input()
    lsta = []
    if n == 1:
        if s == 'a':
            print('a')
        else:
            print('b')
    elif 'a' not in s:
        print('b' * x)
    else:
        for j in range(n):
            if s[j] == 'a':
                lsta.append(j)
        lstp = []
        if lsta[0] > 0:
            lstp.append(lsta[0])
        l = len(lsta)
        for j in range(1, l):
            if lsta[j] - lsta[j - 1] - 1 > 0:
                lstp.append(lsta[j] - lsta[j - 1] - 1)
        if n - lsta[-1] - 1 > 0:
            lstp.append(n - lsta[-1] - 1)
        for r in range(len(lstp)):
            lstp[r] = lstp[r] * k + 1
        for r in range(len(lstp) - 2, -1, -1):
            lstp[r] = lstp[r + 1] * lstp[r]
        if lstp == []:
            print(s)
        else:
            lst1 = []
            for r in range(len(lstp) - 1):
                rem = x % lstp[r]
                if rem == 0:
                    rem = lstp[r]
                q = rem // lstp[r + 1]
                if rem % lstp[r + 1] == 0:
                    q -= 1
                if q == -1:
                    q = lstp[-1] - 1
                lst1.append(q)
            q = x % lstp[-1] - 1
            if q == -1:
                q = lstp[-1] - 1
            lst1.append(q)
            ans = ''
            l = len(lst1)
            ind = 0
            if lsta[0] > 0:
                ans += 'b' * lst1[0]
                ans += 'a'
                ind += 1
            else:
                ans += 'a'
            for g in range(1, len(lsta)):
                if lsta[g] - lsta[g - 1] - 1 > 0:
                    ans += lst1[ind] * 'b'
                    ind += 1
                    ans += 'a'
                else:
                    ans += 'a'
            if n - lsta[-1] - 1 > 0:
                ans += 'b' * lst1[ind]
            print(ans)