Optimal Subsequences (Easy Version) (Codeforces 1261B1)
Tags: Greedy, data structures

This is the easier version of the problem. In this version $$$1 \le n, m \le 100$$$. You can hack this problem only if you solve and lock both problems.You are given a sequence of integers $$$a=[a_1,a_2,\dots,a_n]$$$ of length $$$n$$$. Its subsequence is obtained by removing zero or more elements from the sequence $$$a$$$ (they do not necessarily go consecutively). For example, for the sequence $$$a=[11,20,11,33,11,20,11]$$$:  $$$[11,20,11,33,11,20,11]$$$, $$$[11,20,11,33,11,20]$$$, $$$[11,11,11,11]$$$, $$$[20]$$$, $$$[33,20]$$$ are subsequences (these are just some of the long list);  $$$[40]$$$, $$$[33,33]$$$, $$$[33,20,20]$$$, $$$[20,20,11,11]$$$ are not subsequences. Suppose that an additional non-negative integer $$$k$$$ ($$$1 \le k \le n$$$) is given, then the subsequence is called optimal if:  it has a length of $$$k$$$ and the sum of its elements is the maximum possible among all subsequences of length $$$k$$$;  and among all subsequences of length $$$k$$$ that satisfy the previous item, it is lexicographically minimal. Recall that the sequence $$$b=[b_1, b_2, \dots, b_k]$$$ is lexicographically smaller than the sequence $$$c=[c_1, c_2, \dots, c_k]$$$ if the first element (from the left) in which they differ less in the sequence $$$b$$$ than in $$$c$$$. Formally: there exists $$$t$$$ ($$$1 \le t \le k$$$) such that $$$b_1=c_1$$$, $$$b_2=c_2$$$, ..., $$$b_{t-1}=c_{t-1}$$$ and at the same time $$$b_t<c_t$$$. For example:  $$$[10, 20, 20]$$$ lexicographically less than $$$[10, 21, 1]$$$,  $$$[7, 99, 99]$$$ is lexicographically less than $$$[10, 21, 1]$$$,  $$$[10, 21, 0]$$$ is lexicographically less than $$$[10, 21, 1]$$$. You are given a sequence of $$$a=[a_1,a_2,\dots,a_n]$$$ and $$$m$$$ requests, each consisting of two numbers $$$k_j$$$ and $$$pos_j$$$ ($$$1 \le k \le n$$$, $$$1 \le pos_j \le k_j$$$). For each query, print the value that is in the index $$$pos_j$$$ of the optimal subsequence of the given sequence $$$a$$$ for $$$k=k_j$$$.For example, if $$$n=4$$$, $$$a=[10,20,30,20]$$$, $$$k_j=2$$$, then the optimal subsequence is $$$[20,30]$$$ — it is the minimum lexicographically among all subsequences of length $$$2$$$ with the maximum total sum of items. Thus, the answer to the request $$$k_j=2$$$, $$$pos_j=1$$$ is the number $$$20$$$, and the answer to the request $$$k_j=2$$$, $$$pos_j=2$$$ is the number $$$30$$$.

Input: The first line contains an integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the sequence $$$a$$$.The second line contains elements of the sequence $$$a$$$: integer numbers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).The third line contains an integer $$$m$$$ ($$$1 \le m \le 100$$$) — the number of requests.The following $$$m$$$ lines contain pairs of integers $$$k_j$$$ and $$$pos_j$$$ ($$$1 \le k \le n$$$, $$$1 \le pos_j \le k_j$$$) — the requests.

Output: Print $$$m$$$ integers $$$r_1, r_2, \dots, r_m$$$ ($$$1 \le r_j \le 10^9$$$) one per line: answers to the requests in the order they appear in the input. The value of $$$r_j$$$ should be equal to the value contained in the position $$$pos_j$$$ of the optimal subsequence for $$$k=k_j$$$.

Note: In the first example, for $$$a=[10,20,10]$$$ the optimal subsequences are:   for $$$k=1$$$: $$$[20]$$$,  for $$$k=2$$$: $$$[10,20]$$$,  for $$$k=3$$$: $$$[10,20,10]$$$. 

Sample Inputs:
3
10 20 10
6
1 1
2 1
2 2
3 1
3 2
3 3

7
1 2 1 3 1 2 1
9
2 1
2 2
3 1
3 2
3 3
1 1
7 1
7 7
7 4

Sample Outputs:
20
10
20
10
20
10

2
3
2
3
2
3
1
1
3

Solution (Python):
n = int(input())
c = list(map(lambda x: (int(x[1]), -x[0]), enumerate(input().split())))
so = sorted(c)
for i in range(int(input())):
    (k, r) = map(int, input().split())
    now = so[-k:]
    now.sort(key=lambda x: -x[1])
    print(now[r - 1][0])

Solution (Python):
test_case = '7\n1 2 1 3 1 2 1\n9\n2 1\n2 2\n3 1\n3 2\n3 3\n1 1\n7 1\n7 7\n7 4'
length = int(input())
a = [int(x) for x in input().split()]
l = []
for x in range(length):
    l.append([a[x], x + 1])
ll = sorted(l, key=lambda y: (y[0], -y[1]))
t = int(input())
for _ in range(t):
    (k, p) = [int(x) for x in input().split()]
    ans = ll[length - k:]
    final = sorted(ans, key=lambda y: y[1])
    print(final[p - 1][0])

Solution (Python):
n = int(input())
a = input().split()
for i in range(n):
    a[i] = int(a[i])
a_sorted = sorted(a, reverse=True)
m = int(input())
r = []
for _ in range(m):
    b = []
    (k, pos) = input().split()
    k = int(k)
    pos = int(pos) - 1
    for i in range(n - 1, -1, -1):
        if a[i] > a_sorted[k - 1]:
            b.append([a[i], i])
    i = 0
    while len(b) < k:
        if a[i] == a_sorted[k - 1]:
            b.append([a[i], i])
        i += 1
    c = sorted(b, key=lambda x: x[1])
    r.append(c[pos][0])
for i in r:
    print(i)