Problem:


Score : 600 points

Problem Statement

You are given an integer sequence A of length N and an integer K.
You will perform the following operation on this sequence Q times:

Choose a contiguous subsequence of length K, then remove the smallest element among the K elements contained in the chosen subsequence (if there are multiple such elements, choose one of them as you like).

Let X and Y be the values of the largest and smallest element removed in the Q operations. You would like X-Y to be as small as possible.
Find the smallest possible value of X-Y when the Q operations are performed optimally.

Constraints

1 \leq N \leq 2000

1 \leq K \leq N

1 \leq Q \leq N-K+1

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K Q
A_1 A_2 ... A_N

Output

Print the smallest possible value of X-Y.

Sample Input 1

5 3 2
4 3 1 5 2

Sample Output 1

1

In the first operation, whichever contiguous subsequence of length 3 we choose, the minimum element in it is 1.
Thus, the first operation removes A_3=1 and now we have A=(4,3,5,2).
In the second operation, it is optimal to choose (A_2,A_3,A_4)=(3,5,2) as the contiguous subsequence of length 3 and remove A_4=2.
In this case, the largest element removed is 2, and the smallest is 1, so their difference is 2-1=1.

Sample Input 2

10 1 6
1 1 2 3 5 8 13 21 34 55

Sample Output 2

7

Sample Input 3

11 7 5
24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784

Sample Output 3

451211184



Sample input:
5 3 2
4 3 1 5 2


Sample output:
1

Submission status: Runtime Error

Solution code:
# E
from heapq import heappush, heappop
import numpypy as np

N, K, Q = map(int, input().split())
A = list(map(int, input().split()))

A_args = np.argsort(A)

nodeid = np.ones(N).astype("int32")
canput = np.ones(N)
nodeid_dict = dict()
nodeid_dict[1] = [0, N]
# initial output
res = A[A_args[Q-1]] - A[A_args[0]]

ind_del = 0

for i in range(N):
    
    nid = A_args[i]
    
    # update nodeid
    ndid = nodeid[nid]
    nodeid[nid] = 0
    left, right = nodeid_dict[ndid]
    nodeid[(nid+1):right] = i+2
    nodeid_dict[nid] = [left, nid]
    nodeid_dict[i+2] = [nid+1, right]

    # update canput
    canput[nid] = 0
    
    canput[left:nid] = 0
    h = []
    for j in range(left, nid):
        heappush(h, (-A[j], j))
    while len(h) >= K:
        _, j = heappop(h)
        canput[j] = 1
    
    canput[(nid+1):right] = 0
    h = []
    for j in range(nid+1, right):
        heappush(h, (-A[j], j))
    while len(h) >= K:
        _, j = heappop(h)
        canput[j] = 1
    
    # break
    if canput.sum() <= Q:
        break
        
    # calculate
    q = 0
    qmin = 10**9
    qmax = 1
    for i in range(N):
        if canput[A_args[i]] == 1:
            q += 1
            qmin = min(A[A_args[i]], qmin)
            qmax = max(A[A_args[i]], qmax)
            if q == Q:
                r = qmax - qmin
    res = min(res, r)
print(res)

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,k,q = LI()
    a = LI()
    sa = sorted(a)
    r = sa[-1] - sa[0]
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(n):
        if sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        def f(i):
            ma = sa[i]
            c = 0
            cc = 0
            g = 0
            ss = 1
            for t in a:
                if t < mi:
                    if c > k and c > cc:
                        g += c - max(k, cc)
                    ss = 0
                    c = 0
                    cc = 0
                    continue
                if t >= ma:
                    cc += 1
                c += 1
            if ss == 1 and c > cc:
                g += c - cc
            elif c > k and c > cc:
                g += c - max(k, cc)
            # print(mi, ma, cc, i, g, q)
            return g < q

        l = bs(f, 0, n+1)
        # print(i,l,mi)
        if l > n or l <= i:
            continue
        t = sa[l-1] - mi
        if r > t:
            r = t


    return r




print(main())

Submission status: Runtime Error

Solution code:
# E
import heapq
import numpy as np

N, K, Q = map(int, input().split())
A = list(map(int, input().split()))

A_args = np.argsort(A)

nodeid = np.ones(N).astype("int32")
canput = np.ones(N)
nodeid_dict = dict()
nodeid_dict[1] = [0, N]
# initial output
res = A[A_args[Q-1]] - A[A_args[0]]

ind_del = 0

for i in range(N):
    
    nid = A_args[i]
    
    # update nodeid
    ndid = nodeid[nid]
    nodeid[nid] = 0
    left, right = nodeid_dict[ndid]
    nodeid[(nid+1):right] = i+2
    nodeid_dict[nid] = [left, nid]
    nodeid_dict[i+2] = [nid+1, right]

    # update canput
    canput[nid] = 0
    
    canput[left:nid] = 0
    h = []
    for j in range(left, nid):
        heappush(h, (-A[j], j))
    while len(h) >= K:
        _, j = heappop(h)
        canput[j] = 1
    
    canput[(nid+1):right] = 0
    h = []
    for j in range(nid+1, right):
        heappush(h, (-A[j], j))
    while len(h) >= K:
        _, j = heappop(h)
        canput[j] = 1
    
    # break
    if canput.sum() <= Q:
        break
        
    # calculate
    q = 0
    qmin = 10**9
    qmax = 1
    for i in range(N):
        if canput[A_args[i]] == 1:
            q += 1
            qmin = min(A[A_args[i]], qmin)
            qmax = max(A[A_args[i]], qmax)
            if q == Q:
                r = qmax - qmin
    res = min(res, r)
print(res)

Submission status: Runtime Error

Solution code:
import numpy as np

def ii():
    return int(input())


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


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def n_removable(N, ix, K):
    # ix is sorted
    cnt = max(0, ix[0] - K + 1)
    for j in range(len(ix) - 1):
        cnt += max(0, ix[j+1] - ix[j] - K)
    cnt += max(0, N - ix[-1] - K)
    return cnt


def manage_luck_flag(luck_flag, j, K):
    luck_flag[j] = 1
    N = len(luck_flag)
    if j < K:
        luck_flag[:K] = 1
    elif j >= N - K:
        luck_flag[-K:] = 1
    else:
        for k in range(1, K+1):
            if luck_flag[j - k] == 1:
                for p in range(k+1):
                    luck_flag[j - p] = 1
                break
        for k in range(1, K+1):
            if luck_flag[j + k] == 1:
                for p in range(k+1):
                    luck_flag[j + p] = 1
                break  
    
    return luck_flag


def main():
    N, K, Q = lii()
    A = lii()
    Asort = sorted(A)
    ix = np.argsort(A)
    luck_ix = []

    diff = Asort[Q-1] - Asort[0]

    luck_flag = np.zeros(N)

    for i in range(N-Q+1):
        luck_ix.append(ix[i])
        luck_ix = sorted(luck_ix)
        luck_flag = manage_luck_flag(luck_flag, ix[i], K)

        cnt = n_removable(N, luck_ix, K)
        # print(i, cnt)
        j = i+Q-1
        while luck_flag[ix[j]] == 1:
            j += 1

        diff = min(diff, Asort[j] - Asort[i])
        if Q > cnt:
            break

    return diff

if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from itertools import accumulate
def inpl(): return map(int, input().split())

N, K, Q = inpl()
A = input()

S = sorted(map(int, A.split()))
ans = S[Q-1] - S[0]
S = S[::-1]
Que = [A]


while True:
    s = S.pop()
    nQ = []
    OK = 0
    for q in Que:
        for r in (" "+q).split(" {} ".format(s)):
            L = len(r.split())
            if L >= K:
                nQ.append(r)
                OK += (L - K + 1)
    if OK < Q:
        break
    tmp = []
    for q in nQ:
        tmp.extend(sorted([int(x) for x in q.split()])[::-1][K-1:])
    tmp = sorted(tmp)
    ans = min(ans, tmp[Q-1] - tmp[0])
    Que = nQ

print(ans)

Submission status: Runtime Error

Solution code:
n,k,q = map(int,input().split())
lis = list(map(int,input()))
lis.sort()
print(lis[q-1]-lis[0])