Minimum Euler Cycle (Codeforces 1334D)
Tags: Greedy, graphs

You are given a complete directed graph $$$K_n$$$ with $$$n$$$ vertices: each pair of vertices $$$u \neq v$$$ in $$$K_n$$$ have both directed edges $$$(u, v)$$$ and $$$(v, u)$$$; there are no self-loops.You should find such a cycle in $$$K_n$$$ that visits every directed edge exactly once (allowing for revisiting vertices).We can write such cycle as a list of $$$n(n - 1) + 1$$$ vertices $$$v_1, v_2, v_3, \dots, v_{n(n - 1) - 1}, v_{n(n - 1)}, v_{n(n - 1) + 1} = v_1$$$ — a visiting order, where each $$$(v_i, v_{i + 1})$$$ occurs exactly once.Find the lexicographically smallest such cycle. It's not hard to prove that the cycle always exists.Since the answer can be too large print its $$$[l, r]$$$ segment, in other words, $$$v_l, v_{l + 1}, \dots, v_r$$$.

Input: The first line contains the single integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of test cases.Next $$$T$$$ lines contain test cases — one per line. The first and only line of each test case contains three integers $$$n$$$, $$$l$$$ and $$$r$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le l \le r \le n(n - 1) + 1$$$, $$$r - l + 1 \le 10^5$$$) — the number of vertices in $$$K_n$$$, and segment of the cycle to print.It's guaranteed that the total sum of $$$n$$$ doesn't exceed $$$10^5$$$ and the total sum of $$$r - l + 1$$$ doesn't exceed $$$10^5$$$.

Output: For each test case print the segment $$$v_l, v_{l + 1}, \dots, v_r$$$ of the lexicographically smallest cycle that visits every edge exactly once.

Note: In the second test case, the lexicographically minimum cycle looks like: $$$1, 2, 1, 3, 2, 3, 1$$$.In the third test case, it's quite obvious that the cycle should start and end in vertex $$$1$$$.

Sample Inputs:
3
2 1 3
3 3 6
99995 9998900031 9998900031

Sample Outputs:
1 2 1 
1 3 2 3 
1

Solution (Python):
import sys
input = sys.stdin.readline

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

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, l, r) = readInts()
    cnt = r - l + 1
    x = []
    if r == n * (n - 1) + 1:
        x.append(1)
        cnt -= 1
    ans = []
    (lo, hi) = (0, n)
    while lo < hi:
        mid = (lo + hi) // 2
        if 2 * n * mid - mid * (mid + 1) >= l:
            hi = mid
        else:
            lo = mid + 1
    lo -= 1
    j = l - (2 * n * lo - lo * (lo + 1))
    i = lo + 1
    if j % 2 == 0:
        ans.append(i + j // 2)
        j = ans[-1] + 1
        cnt -= 1
    else:
        j = i + (j + 1) // 2
    while cnt > 0:
        while cnt > 0 and j <= n:
            ans.append(i)
            ans.append(j)
            j += 1
            cnt -= 2
        if cnt == -1:
            ans.pop()
            cnt = 0
        i += 1
        j = i + 1
    ans += x
    print(*ans)
for _ in range(int(input())):
    solve()

Solution (Python):
import itertools as it
import os

def items(k, n):
    return 2 * k * n - k * (k + 1)

def b(l, n):
    if l > n * (n - 1):
        return n
    low = 1
    high = n - 1
    while low < high:
        mid = (high + low) // 2
        if items(mid, n) < l:
            low = mid + 1
        else:
            high = mid
    return low

def row_gen(r, n):
    while r <= n:
        if r == n:
            yield 1
        else:
            x = r
            a = False
            while x < n:
                a = not a
                if a:
                    yield r
                else:
                    x += 1
                    yield x
        r += 1
''

def get_seg(l, r, n):
    start_row = b(l, n)
    count_r = l - items(start_row - 1, n)
    g = row_gen(start_row, n)
    return it.islice(g, count_r - 1, count_r + r - l)

def pp(input):
    T = int(input())
    for i in range(T):
        (n, l, r) = map(int, input().split())
        print(' '.join(map(str, get_seg(l, r, n))))
if 'paalto' in os.getcwd():
    from string_source import string_source
    pp(string_source('3\n2 1 3\n3 3 6\n99995 9998900031 9998900031\n'))
else:
    pp(input)

Solution (Python):
import sys

def minp():
    return sys.stdin.readline().strip()

def mint():
    return int(minp())

def mints():
    return map(int, minp().split())

def stupid(x, n):
    k = (n - 1) * 2
    r = 0
    while x >= k:
        x -= k
        r += 1
        k -= 2
    return r

def findl(x, n):
    (l, r) = (0, n)
    while r - l > 1:
        c = (l + r) // 2
        if (2 * n - 1 - c) * c <= x:
            l = c
        else:
            r = c
    return l

def solve():
    (n, l, r) = mints()
    res = []
    f = r == n * (n - 1) + 1
    r -= l + f - 1
    l -= 1
    x = findl(l, n)
    l -= (2 * n - 1 - x) * x
    k = (n - 1 - x) * 2
    x += 1
    while False:
        print(l, k)
        l -= k
        x += 1
        k -= 2
    y = x + 1 + l // 2
    if l % 2:
        while r >= 2:
            res.append(y)
            if y == n:
                x += 1
                y = x + 1
            else:
                y += 1
            res.append(x)
            r -= 2
        if r != 0:
            res.append(y)
    else:
        while r >= 2:
            res.append(x)
            res.append(y)
            if y == n:
                x += 1
                y = x + 1
            else:
                y += 1
            r -= 2
        if r != 0:
            res.append(x)
    if f:
        res.append(1)
    print(' '.join(map(str, res)))
for i in range(mint()):
    solve()