Decreasing String (Codeforces 1886C)
Tags: Implement, strings

Recall that string $$$a$$$ is lexicographically smaller than string $$$b$$$ if $$$a$$$ is a prefix of $$$b$$$ (and $$$a \ne b$$$), or there exists an index $$$i$$$ ($$$1 \le i \le \min(|a|, |b|)$$$) such that $$$a_i < b_i$$$, and for any index $$$j$$$ ($$$1 \le j < i$$$) $$$a_j = b_j$$$.Consider a sequence of strings $$$s_1, s_2, \dots, s_n$$$, each consisting of lowercase Latin letters. String $$$s_1$$$ is given explicitly, and all other strings are generated according to the following rule: to obtain the string $$$s_i$$$, a character is removed from string $$$s_{i-1}$$$ in such a way that string $$$s_i$$$ is lexicographically minimal.For example, if $$$s_1 = \mathrm{dacb}$$$, then string $$$s_2 = \mathrm{acb}$$$, string $$$s_3 = \mathrm{ab}$$$, string $$$s_4 = \mathrm{a}$$$.After that, we obtain the string $$$S = s_1 + s_2 + \dots + s_n$$$ ($$$S$$$ is the concatenation of all strings $$$s_1, s_2, \dots, s_n$$$).You need to output the character in position $$$pos$$$ of the string $$$S$$$ (i. e. the character $$$S_{pos}$$$).

Input: The first line contains one integer $$$t$$$ — the number of test cases ($$$1 \le t \le 10^4$$$).Each test case consists of two lines. The first line contains the string $$$s_1$$$ ($$$1 \le |s_1| \le 10^6$$$), consisting of lowercase Latin letters. The second line contains the integer $$$pos$$$ ($$$1 \le pos \le \frac{|s_1| \cdot (|s_1| +1)}{2}$$$). You may assume that $$$n$$$ is equal to the length of the given string ($$$n = |s_1|$$$).Additional constraint on the input: the sum of $$$|s_1|$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, print the answer — the character that is at position $$$pos$$$ in string $$$S$$$. Note that the answers between different test cases are not separated by spaces or line breaks.


Sample Inputs:
3
cab
6
abcd
9
x
1

Sample Outputs:
abx

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

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (s, pos) = (readStr(), readInt())
    n = len(s)
    (lo, hi) = (1, n)
    while lo < hi:
        mid = (lo + hi) // 2
        if (2 * n - mid + 1) * mid // 2 >= pos:
            hi = mid
        else:
            lo = mid + 1
    cnt = hi - 1
    pos -= (2 * n - cnt + 1) * cnt // 2 + 1
    st = []
    for i in range(n):
        while cnt and st and (st[-1] > s[i]):
            st.pop()
            cnt -= 1
        st.append(s[i])
    return st[pos]
ans = []
for _ in range(readInt()):
    ans.append(solve())
print(''.join(ans))

Solution (Python):
import math

def mapped_read(cast):
    return map(cast, input().split(' '))

def read_list(cast):
    return list(mapped_read(cast))

def solve():
    s = input()
    n = len(s)
    (pos,) = mapped_read(int)
    pos -= 1
    if pos < n:
        print(s[pos], end='')
        return
    k = int((2 * n - 1 - math.sqrt((2 * n - 1) ** 2 - 8 * (pos - n))) / 2)
    pos -= (2 * n - k) * (k + 1) // 2
    chars = []
    cnt = k + 1
    for ind in range(n):
        while cnt > 0 and chars and (chars[-1] > s[ind]):
            chars.pop()
            cnt -= 1
        chars.append(s[ind])
    print(''.join(chars)[pos], end='')
if __name__ == '__main__':
    (t,) = mapped_read(int)
    for _ in range(t):
        solve()

Solution (Python):
from heapq import heappush, heappop, heapify

def solve(s, pos):
    n = len(s)
    (acc, rem) = (0, 0)
    while True:
        acc += n
        if acc == pos:
            p = n
            break
        elif acc > pos:
            p = n - (acc - pos)
            break
        rem += 1
        n -= 1
    p -= 1
    stack = []
    for c in s:
        while stack and stack[-1] > c and (rem > 0):
            rem -= 1
            stack.pop()
        stack.append(c)
    return stack[p]
n = int(input())
result = []
for i in range(n):
    s = input()
    pos = int(input())
    result.append(solve(s, pos))
for r in result:
    print(r, end='')