Perform Easily (Codeforces 1413C)
Tags: DP, two pointers

After battling Shikamaru, Tayuya decided that her flute is too predictable, and replaced it with a guitar. The guitar has $$$6$$$ strings and an infinite number of frets numbered from $$$1$$$. Fretting the fret number $$$j$$$ on the $$$i$$$-th string produces the note $$$a_{i} + j$$$.Tayuya wants to play a melody of $$$n$$$ notes. Each note can be played on different string-fret combination. The easiness of performance depends on the difference between the maximal and the minimal indices of used frets. The less this difference is, the easier it is to perform the technique. Please determine the minimal possible difference.For example, if $$$a = [1, 1, 2, 2, 3, 3]$$$, and the sequence of notes is $$$4, 11, 11, 12, 12, 13, 13$$$ (corresponding to the second example), we can play the first note on the first string, and all the other notes on the sixth string. Then the maximal fret will be $$$10$$$, the minimal one will be $$$3$$$, and the answer is $$$10 - 3 = 7$$$, as shown on the picture.  

Input: The first line contains $$$6$$$ space-separated numbers $$$a_{1}$$$, $$$a_{2}$$$, ..., $$$a_{6}$$$ ($$$1 \leq a_{i} \leq 10^{9}$$$) which describe the Tayuya's strings.The second line contains the only integer $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) standing for the number of notes in the melody.The third line consists of $$$n$$$ integers $$$b_{1}$$$, $$$b_{2}$$$, ..., $$$b_{n}$$$ ($$$1 \leq b_{i} \leq 10^{9}$$$), separated by space. They describe the notes to be played. It's guaranteed that $$$b_i > a_j$$$ for all $$$1\leq i\leq n$$$ and $$$1\leq j\leq 6$$$, in other words, you can play each note on any string.

Output: Print the minimal possible difference of the maximal and the minimal indices of used frets.

Note: In the first sample test it is optimal to play the first note on the first string, the second note on the second string, the third note on the sixth string, the fourth note on the fourth string, the fifth note on the fifth string, and the sixth note on the third string. In this case the $$$100$$$-th fret is used each time, so the difference is $$$100 - 100 = 0$$$.  In the second test it's optimal, for example, to play the second note on the first string, and all the other notes on the sixth string. Then the maximal fret will be $$$10$$$, the minimal one will be $$$3$$$, and the answer is $$$10 - 3 = 7$$$.  

Sample Inputs:
1 4 100 10 30 5
6
101 104 105 110 130 200

1 1 2 2 3 3
7
13 4 11 12 11 13 12

Sample Outputs:
0

7

Solution (Python):
import math
import random
import time
import sys, threading
from collections import defaultdict
contor = 0
matricea = {}
alfabet = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8, 'i': 9, 'j': 10, 'k': 11, 'l': 12, 'm': 13, 'n': 14, 'o': 15, 'p': 16, 'q': 17, 'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23, 'x': 24, 'y': 25, 'z': 26}
alfabet_2 = {'1': 'a', '2': 'b', '3': 'c', '4': 'd', '5': 'e', '6': 'f', '7': 'g', '8': 'h', '9': 'i', '10': 'j', '11': 'k', '12': 'l', '13': 'm', '14': 'n', '15': 'o', '16': 'p', '17': 'q', '18': 'r', '19': 's', '20': 't', '21': 'u', '22': 'v', '23': 'w', '24': 'x', '25': 'y', '26': 'z'}
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound

class FenwickTree:

    def __init__(self, x):
        bit = self.bit = list(x)
        size = self.size = len(bit)
        for i in range(size):
            j = i | i + 1
            if j < size:
                bit[j] += bit[i]

    def update(self, idx, x):
        """"""
        while idx < self.size:
            self.bit[idx] += x
            idx |= idx + 1

    def __call__(self, end):
        """"""
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x

    def find_kth(self, k):
        """"""
        idx = -1
        for d in reversed(range(self.size.bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < self.size and self.bit[right_idx] <= k:
                idx = right_idx
                k -= self.bit[idx]
        return (idx + 1, k)

class SortedList:
    block_size = 700

    def __init__(self, iterable=()):
        self.macro = []
        self.micros = [[]]
        self.micro_size = [0]
        self.fenwick = FenwickTree([0])
        self.size = 0
        for item in iterable:
            self.insert(item)

    def insert(self, x):
        i = lower_bound(self.macro, x)
        j = upper_bound(self.micros[i], x)
        self.micros[i].insert(j, x)
        self.size += 1
        self.micro_size[i] += 1
        self.fenwick.update(i, 1)
        if len(self.micros[i]) >= self.block_size:
            self.micros[i:i + 1] = (self.micros[i][:self.block_size >> 1], self.micros[i][self.block_size >> 1:])
            self.micro_size[i:i + 1] = (self.block_size >> 1, self.block_size >> 1)
            self.fenwick = FenwickTree(self.micro_size)
            self.macro.insert(i, self.micros[i + 1][0])

    def pop(self, k=-1):
        (i, j) = self._find_kth(k)
        self.size -= 1
        self.micro_size[i] -= 1
        self.fenwick.update(i, -1)
        return self.micros[i].pop(j)

    def __getitem__(self, k):
        (i, j) = self._find_kth(k)
        return self.micros[i][j]

    def count(self, x):
        return self.upper_bound(x) - self.lower_bound(x)

    def __contains__(self, x):
        return self.count(x) > 0

    def lower_bound(self, x):
        i = lower_bound(self.macro, x)
        return self.fenwick(i) + lower_bound(self.micros[i], x)

    def upper_bound(self, x):
        i = upper_bound(self.macro, x)
        return self.fenwick(i) + upper_bound(self.micros[i], x)

    def _find_kth(self, k):
        return self.fenwick.find_kth(k + self.size if k < 0 else k)

    def __len__(self):
        return self.size

    def __iter__(self):
        return (x for micro in self.micros for x in micro)

    def __repr__(self):
        return str(list(self))

def prime_generator(nr_elemente_prime):
    vector_prime = [-1] * nr_elemente_prime
    vector_rasp = [0] * nr_elemente_prime
    vector_prime[1] = 1
    vector_rasp[1] = 1
    contor = 2
    for i in range(2, nr_elemente_prime):
        if vector_prime[i] == -1:
            vector_prime[i] = 1
            vector_rasp[contor] = i
            contor = contor + 1
        for j in range(i + i, nr_elemente_prime, i):
            if vector_prime[j] == -1:
                vector_prime[j] = i
    set_prime = set(vector_rasp)
    set_prime.remove(0)
    set_prime.remove(1)
    answ_prime = list(set_prime)
    answ_prime.sort()
    return answ_prime

def binary_search(vectorul, valoarea):
    left = 0
    right = len(vectorul) - 1
    while left <= right:
        centru = (left + right) // 2
        if vectorul[centru] <= valoarea:
            left = centru + 1
        else:
            right = centru - 1
    return left

def binary_search_vectorul(vectorul, valoarea):
    left = 0
    right = len(vectorul) - 1
    while left <= right:
        centru = (left + right) // 2
        if vectorul[centru] <= valoarea:
            left = centru + 1
        else:
            right = centru - 1
    return left

def functie_combinari(vectorul, pozitie, sfarsit):
    global contor
    global matricea
    if pozitie >= sfarsit:
        setul = set()
        for hh in vectorul:
            setul.add(hh)
        if len(setul) == sfarsit:
            contor += 1
            matricea[contor] = vectorul
            print('contor=', contor)
    else:
        for vectorul[pozitie] in range(sfarsit):
            functie_combinari(vectorul, pozitie + 1, sfarsit)

def functie_val(val, poz, dictionarul, prezentul, ciclul, rel):
    if val not in prezentul:
        return val
    else:
        ciclul[val, poz, rel] = 1
        poz = binary_search(dictionarul[val], poz)
        if poz == 0:
            return val
        else:
            return functie_val(dictionarul[val][len(dictionarul[val]) - poz][0], dictionarul[val][len(dictionarul[val]) - poz][1], dictionarul, prezentul, ciclul, dictionarul[val][len(dictionarul[val]) - poz][2])

def factorial_invers(a, mod):
    calcul = pow(a, mod - 2, mod)
    return calcul

def functie_factorial(numar, modul):
    vec_fac = [1] * (numar + 1)
    for i in range(1, numar + 1):
        vec_fac[i] = vec_fac[i - 1] * i % modul
    return vec_fac
factorialul = functie_factorial(150001, 10 ** 9 + 7)

def combinari(baza, exponent, modulul):
    numitor = factorialul[baza - exponent] * factorialul[exponent] % modulul
    rasp_partial = factorialul[baza] % modulul * factorial_invers(numitor, modulul) % modulul
    return rasp_partial

def main():
    modul = 10 ** 9 + 7
    pp = 10 ** 40
    vec_answ = []
    kuri = []
    answ = []
    for gg in range(1):
        v = list(map(int, input().split()))
        n = int(input())
        lista = list(map(int, input().split()))
        primul = v[0]
        vector = list(set(v))
        set_unice = set()
        vectorul = []
        dictionar = defaultdict(int)
        lungime = len(vector)
        for i in lista:
            if i not in set_unice:
                set_unice.add(i)
                for j in range(lungime):
                    vectorul.append((i - vector[j], i))
        cate = len(set_unice)
        answ = pp
        pornire = -1
        posibil = 1
        oprire = 1
        vectorul = sorted(vectorul, key=lambda x: (x[0], x[1]))
        setul = set()
        pornire = 0
        lungime = len(vectorul)
        oprire = 0
        while posibil == 1:
            adev = 0
            for i in range(oprire, lungime):
                dictionar[vectorul[i][1]] += 1
                setul.add(vectorul[i][1])
                if len(setul) >= cate:
                    adev = 1
                    answ = min(answ, vectorul[i][0] - vectorul[pornire][0])
                    oprire = i + 1
                    break
            if adev == 0:
                posibil = 0
            else:
                for j in range(pornire, min(lungime, oprire)):
                    dictionar[vectorul[j][1]] -= 1
                    if dictionar[vectorul[j][1]] == 0:
                        setul.remove(vectorul[j][1])
                        answ = min(answ, vectorul[oprire - 1][0] - vectorul[j][0])
                        pornire = j + 1
                        break
                    elif len(setul) >= cate:
                        answ = min(answ, vectorul[oprire - 1][0] - vectorul[j][0])
        print(answ)
main()

Solution (Python):
import operator
import sys
a = list(set(map(int, sys.stdin.readline().split())))
n = int(input())
c2 = list(set(map(int, sys.stdin.readline().split())))
s = 0
v = []
index = 0
n = len(c2)
c = [0] * n
qm = 1000000000.0 + 1
for q in range(len(a)):
    for i in range(len(c2)):
        v.append([c2[i] - a[q], i])
v.sort(key=operator.itemgetter(0))
for i in range(len(v)):
    c[v[i][1]] += 1
    if c[v[i][1]] == 1:
        s += 1
    if s == n:
        while c[v[index][1]] > 1:
            c[v[index][1]] -= 1
            index += 1
        if v[i][0] - v[index][0] < qm:
            qm = v[i][0] - v[index][0]
        c[v[index][1]] -= 1
        if c[v[index][1]] == 0:
            s -= 1
        index += 1
sys.stdout.write(str(qm))

Solution (Python):
import operator
import sys
a = list(set(map(int, sys.stdin.readline().split())))
n = int(input())
c2 = list(set(map(int, sys.stdin.readline().split())))
s = 0
v = []
index = 0
n = len(c2)
c = [0] * n
qm = 1000000000.0 + 1
for q in range(len(a)):
    for i in range(len(c2)):
        v.append([c2[i] - a[q], i])
v.sort(key=operator.itemgetter(0))
for i in range(len(v)):
    c[v[i][1]] += 1
    if c[v[i][1]] == 1:
        s += 1
    if s == n:
        while c[v[index][1]] > 1:
            c[v[index][1]] -= 1
            index += 1
        if v[i][0] - v[index][0] < qm:
            qm = v[i][0] - v[index][0]
        c[v[index][1]] -= 1
        if c[v[index][1]] == 0:
            s -= 1
        index += 1
sys.stdout.write(str(qm))