대회 개최

• 주어진 난이도 커브 공식 $ |x_0-x_1| + |x_1-x_2| + ... + |x_{N-1} - x_{N}| $ 을 바꿔쓰면 max(x) - min(x) 이 된다. 그러므로 문제들의 난이도들이 결정되면, 난이도커브값은 가장 어려운 난이도와 가장 쉬운 난이도의 차이가 된다.
• 가장 어려운 난이도와 가장 쉬운 난이도의 차이가 최소화 되는 난이도들을 구하면 된다. 모든 문제의 난이도들을 정렬해서 하나의 배열에 저장해두자. 이렇게 하면 모든 문제 종류를 포함하면서 최댓값과 최솟값의 차이가 가장 작은 부분구간을 찾는 문제로 바꿀수 있다. 이것은 투포인터를 이용해서 푸는 전형적인 형태의 문제가 된다. 시간복잡도는 정렬에 O(NKlog(NK)), 투포인터 서치에 O(NK), 총 O(NKlog(NK))가 된다.

"""Solution code for "BOJ 31411. 대회 개최".

- Problem link: https://www.acmicpc.net/problem/31411
- Solution link: http://www.teferi.net/ps/problems/boj/31411

Tags: [two pointer]
"""

import sys
from teflib import twopointer


def main():
    # pylint: disable=unused-variable
    N, K = [int(x) for x in sys.stdin.readline().split()]
    problems = []
    for i in range(N):
        d_i = [int(x) for x in sys.stdin.readline().split()]
        problems.extend((d_ij, i) for d_ij in d_i)

    difficulties, algos = zip(*sorted(problems))
    answer = min(
        difficulties[end - 1] - difficulties[beg]
        for beg, end in twopointer.minimal_ranges_with_k_unique_elems(algos, N)
    )

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.twopointer.minimal_ranges_with_k_unique_elems