Clique Partition (Codeforces 1948E)
Tags: Greedy, graphs

You are given two integers, $$$n$$$ and $$$k$$$. There is a graph on $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$, which initially has no edges.You have to assign each vertex an integer; let $$$a_i$$$ be the integer on the vertex $$$i$$$. All $$$a_i$$$ should be distinct integers from $$$1$$$ to $$$n$$$.After assigning integers, for every pair of vertices $$$(i, j)$$$, you add an edge between them if $$$|i - j| + |a_i - a_j| \le k$$$.Your goal is to create a graph which can be partitioned into the minimum possible (for the given values of $$$n$$$ and $$$k$$$) number of cliques. Each vertex of the graph should belong to exactly one clique. Recall that a clique is a set of vertices such that every pair of vertices in it are connected with an edge.Since BledDest hasn't really brushed his programming skills up, he can't solve the problem "given a graph, partition it into the minimum number of cliques". So we also ask you to print the partition itself.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 1600$$$) — the number of test cases.Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 40$$$; $$$1 \le k \le 2n$$$).

Output: For each test case, print three lines:  the first line should contain $$$n$$$ distinct integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the values you assign to the vertices;  the second line should contain one integer $$$q$$$ ($$$1 \le q \le n$$$) — the number of cliques you partition the graph into;  the third line should contain $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le q$$$) — the partition of the graph into cliques. Where two vertices $$$u$$$ and $$$v$$$ are in the same clique if $$$c_u = c_v$$$. If there are multiple answers, print any of them.


Sample Inputs:
3
2 3
5 4
8 16

Sample Outputs:
2 1
1
1 1
3 1 5 2 4
2
1 1 2 1 2
1 2 3 4 5 6 7 8
1
1 1 1 1 1 1 1 1

Solution (Python):
import sys

def main():
    t = int(input())
    for _ in range(t):
        (n, k) = map(int, input().split())
        a = [-1] * n
        c = [-1] * n
        cnt = 0
        beg = 0
        while beg < n:
            k = min(k, n - beg)
            half = (k - 1) // 2
            for i in range(k):
                a[beg + i] = beg + (half - 1 - i)
                if a[beg + i] < beg:
                    a[beg + i] += k
                c[beg + i] = cnt
            cnt += 1
            beg += k
        print(' '.join((str(x + 1) for x in a)))
        print(cnt)
        print(' '.join((str(x + 1) for x in c)))
if __name__ == '__main__':
    main()

Solution (Python):
def solve(segment_length, start):
    if segment_length == 1:
        segment_values[start] = start
        return
    middle = (segment_length + 1) // 2
    segment_values[start] = middle + start - 1
    segment_values[start + segment_length - 1] = middle + start
    (left, right) = (start + 1, start + segment_length - 2)
    while left <= right:
        segment_values[left] = segment_values[left - 1] - 1
        left += 1
        if left > right:
            break
        segment_values[right] = segment_values[right + 1] + 1
        right -= 1

def main_routine():
    (num_elements, max_segment_size) = map(int, input().split())
    max_segment_size = min(num_elements, max_segment_size)
    answer = (num_elements - 1) // max_segment_size + 1
    for i in range(1, num_elements + 1, max_segment_size):
        solve(min(max_segment_size, num_elements - i + 1), i)
    print(' '.join(map(str, segment_values[1:num_elements + 1])))
    print(answer)
    print(' '.join((str((i - 1) // max_segment_size + 1) for i in range(1, num_elements + 1))))
    print()
if __name__ == '__main__':
    test_cases = int(input())
    for _ in range(test_cases):
        segment_values = [0] * 5005
        main_routine()

Solution (Python):
t = int(input())
for i in range(0, t):
    (n, k) = list(map(int, input().split()))
    if k <= 1:
        c = []
        for g in range(0, n):
            c.append(g + 1)
        print(*c)
        print(n)
        print(*c)
        continue
    if k > n:
        k = n
    f = n // k
    c = []
    ans = []
    for g in range(0, f):
        for j in range(k // 2 - 1, -1, -1):
            c.append(g * k + j + 1)
            ans.append(g + 1)
        for j in range(k - 1, k // 2 - 1, -1):
            c.append(g * k + j + 1)
            ans.append(g + 1)
    k = n % k
    if k > 0:
        d = ans[-1]
        w = len(c)
        if k == 1:
            c.append(n)
            ans.append(d + 1)
        else:
            for j in range(k // 2 - 1, -1, -1):
                c.append(w + j + 1)
                ans.append(d + 1)
            for j in range(k - 1, k // 2 - 1, -1):
                c.append(w + j + 1)
                ans.append(d + 1)
    print(*c)
    print(ans[-1])
    print(*ans)