Even Split (Codeforces 1666E)
Tags: Greedy, binary search

A revolution has recently happened in Segmentland. The new government is committed to equality, and they hired you to help with land redistribution in the country.Segmentland is a segment of length $$$l$$$ kilometers, with the capital in one of its ends. There are $$$n$$$ citizens in Segmentland, the home of $$$i$$$-th citizen is located at the point $$$a_i$$$ kilometers from the capital. No two homes are located at the same point. Each citizen should receive a segment of positive length with ends at integer distances from the capital that contains her home. The union of these segments should be the whole of Segmentland, and they should not have common points besides their ends. To ensure equality, the difference between the lengths of the longest and the shortest segments should be as small as possible.

Input: The first line of the input contains two integers $$$l$$$ and $$$n$$$ ($$$2 \leq l \leq 10^9; 1 \leq n \leq 10^5$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 < a_1 < a_2 < \dots < a_n < l$$$).

Output: Output $$$n$$$ pairs of numbers $$$s_i, f_i$$$ ($$$0 \leq s_i < f_i \leq l$$$), one pair per line. The pair on $$$i$$$-th line denotes the ends of the $$$[s_i, f_i]$$$ segment that $$$i$$$-th citizen receives.If there are many possible arrangements with the same difference between the lengths of the longest and the shortest segments, you can output any of them.

Note: In the first example, it is possible to make all segments equal. Viva la revolucion!  In the second example, citizens live close to the capital, so the length of the shortest segment is 2 and the length of the longest segment is 8.  

Sample Inputs:
6 3
1 3 5

10 2
1 2

Sample Outputs:
0 2
2 4
4 6

0 2
2 10

Solution (Python):
import io
import os
import heapq
from collections import deque, Counter
FILE_INPUT_MODE = 0
if FILE_INPUT_MODE >= 0:
    if FILE_INPUT_MODE == 1:
        CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
        FD = os.open(f'{CURRENT_DIR}\\input.txt', os.O_RDONLY)
    elif FILE_INPUT_MODE == 0:
        FD = 0
    DATA = io.BytesIO(os.read(FD, os.fstat(FD).st_size))
    if FD != 0:
        os.close(FD)

    def input():
        return DATA.readline().decode().rstrip('\r\n')

def solve():

    def check_max(x):
        nonlocal n, a, l
        cur = a[1]
        for i in range(1, n):
            if cur > x:
                return False
            cur = max(a[i + 1] - a[i] + cur - x, 0)
        return cur + l - a[n] <= x

    def check_min(x):
        nonlocal n, a, l
        cur = a[1]
        for i in range(1, n):
            if cur + a[i + 1] - a[i] < x:
                return False
            cur = min(cur + a[i + 1] - a[i] - x, a[i + 1] - a[i])
        return True
    (l, n) = [int(word) for word in input().split()]
    a = [int(word) for word in input().split()]
    a = [0] + a + [l]
    left = 0
    right = l
    while left + 1 < right:
        mid = (left + right) // 2
        if check_max(mid):
            right = mid
        else:
            left = mid
    hi = right
    left = 0
    right = l + 1
    while left + 1 < right:
        mid = (left + right) // 2
        if check_min(mid):
            left = mid
        else:
            right = mid
    lo = left
    graph = [[] for i in range(n + 1)]
    d = [float('inf') for i in range(n + 1)]
    for i in range(0, n):
        graph[i].append((i + 1, hi))
        graph[i + 1].append((i, -lo))
    for i in range(1, n):
        graph[0].append((i, a[i + 1]))
        graph[i].append((n, l - a[i]))
    graph[0].append((n, l))
    d[0] = 0
    q = deque([0])
    while len(q) != 0:
        u = q.popleft()
        for (v, cost) in graph[u]:
            if d[u] + cost < d[v]:
                d[v] = d[u] + cost
                q.append(v)
    ans = []
    for i in range(1, len(d)):
        ans.append(f'{d[i - 1]} {d[i]}')
    return '\n'.join(ans)

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

Solution (Python):
import io
import os
import heapq
from collections import deque, Counter
FILE_INPUT_MODE = 0
if FILE_INPUT_MODE >= 0:
    if FILE_INPUT_MODE == 1:
        CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
        FD = os.open(f'{CURRENT_DIR}\\input.txt', os.O_RDONLY)
    elif FILE_INPUT_MODE == 0:
        FD = 0
    DATA = io.BytesIO(os.read(FD, os.fstat(FD).st_size))
    if FD != 0:
        os.close(FD)

    def input():
        return DATA.readline().decode().rstrip('\r\n')

def solve():

    def check_max(x):
        nonlocal n, a, l
        cur = a[1]
        for i in range(1, n):
            if cur > x:
                return False
            cur = max(a[i + 1] - a[i] + cur - x, 0)
        return cur + l - a[n] <= x

    def check_min(x):
        nonlocal n, a, l
        cur = a[1]
        for i in range(1, n):
            if cur + a[i + 1] - a[i] < x:
                return False
            cur = min(cur + a[i + 1] - a[i] - x, a[i + 1] - a[i])
        return True
    (l, n) = [int(word) for word in input().split()]
    a = [int(word) for word in input().split()]
    a = [0] + a + [l]
    left = 0
    right = l
    while left + 1 < right:
        mid = (left + right) // 2
        if check_max(mid):
            right = mid
        else:
            left = mid
    hi = right
    left = 0
    right = l + 1
    while left + 1 < right:
        mid = (left + right) // 2
        if check_min(mid):
            left = mid
        else:
            right = mid
    lo = left
    graph = [[] for i in range(n + 1)]
    d = [float('inf') for i in range(n + 1)]
    for i in range(0, n):
        graph[i].append((i + 1, hi))
        graph[i + 1].append((i, -lo))
    for i in range(1, n):
        graph[0].append((i, a[i + 1]))
        graph[i].append((n, l - a[i]))
    graph[0].append((n, l))
    d[0] = 0
    q = deque([0])
    vis = {0}
    while len(q) != 0:
        u = q.popleft()
        vis.remove(u)
        for (v, cost) in graph[u]:
            if d[u] + cost < d[v]:
                d[v] = d[u] + cost
                if v not in vis:
                    vis.add(v)
                    q.append(v)
    ans = []
    for i in range(1, len(d)):
        ans.append(f'{d[i - 1]} {d[i]}')
    return '\n'.join(ans)

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

Solution (Python):
import io
import os
import heapq
from collections import deque, Counter
FILE_INPUT_MODE = 0
if FILE_INPUT_MODE >= 0:
    if FILE_INPUT_MODE == 1:
        CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
        FD = os.open(f'{CURRENT_DIR}\\input.txt', os.O_RDONLY)
    elif FILE_INPUT_MODE == 0:
        FD = 0
    DATA = io.BytesIO(os.read(FD, os.fstat(FD).st_size))
    if FD != 0:
        os.close(FD)

    def input():
        return DATA.readline().decode().rstrip('\r\n')

def solve():

    def check_max(x):
        nonlocal n, a, l
        cur = a[1]
        for i in range(1, n):
            if cur > x:
                return False
            cur = max(a[i + 1] - a[i] + cur - x, 0)
        return cur + l - a[n] <= x

    def check_min(x):
        nonlocal n, a, l
        cur = a[1]
        for i in range(1, n):
            if cur + a[i + 1] - a[i] < x:
                return False
            cur = min(cur + a[i + 1] - a[i] - x, a[i + 1] - a[i])
        return True
    (l, n) = [int(word) for word in input().split()]
    a = [int(word) for word in input().split()]
    a = [0] + a + [l]
    left = 0
    right = l
    while left + 1 < right:
        mid = (left + right) // 2
        if check_max(mid):
            right = mid
        else:
            left = mid
    hi = right
    left = 0
    right = l + 1
    while left + 1 < right:
        mid = (left + right) // 2
        if check_min(mid):
            left = mid
        else:
            right = mid
    lo = left
    graph = [[] for i in range(n + 1)]
    d = [float('inf') for i in range(n + 1)]
    for i in range(0, n):
        graph[i].append((i + 1, hi))
        graph[i + 1].append((i, -lo))
    for i in range(1, n):
        graph[0].append((i, a[i + 1]))
        graph[i].append((n, l - a[i]))
    graph[0].append((n, l))
    d[0] = 0
    q = deque([0])
    vis = {0}
    while len(q) != 0:
        u = q.popleft()
        vis.remove(u)
        for (v, cost) in graph[u]:
            if d[u] + cost < d[v]:
                d[v] = d[u] + cost
                if v not in vis:
                    vis.add(v)
                    q.append(v)
    ans = []
    for i in range(1, len(d)):
        ans.append(f'{d[i - 1]} {d[i]}')
    return '\n'.join(ans)

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