Bessie's Birthday Cake (Hard Version) (Codeforces 1942C2)
Tags: Greedy, geometry

Proof Geometric Construction Can Solve All Love Affairs - manbo-p⠀This is the hard version of the problem. The only difference between the two versions is the constraint on $$$y$$$. In this version $$$0 \leq y \leq n - x$$$. You can make hacks only if both versions are solved.Bessie has received a birthday cake from her best friend Elsie, and it came in the form of a regular polygon with $$$n$$$ sides. The vertices of the cake are numbered from $$$1$$$ to $$$n$$$ clockwise. You and Bessie are going to choose some of those vertices to cut non-intersecting diagonals into the cake. In other words, the endpoints of the diagonals must be part of the chosen vertices.Bessie would only like to give out pieces of cake which result in a triangle to keep consistency. The size of the pieces doesn't matter, and the whole cake does not have to be separated into all triangles (other shapes are allowed in the cake, but those will not be counted). Bessie has already chosen $$$x$$$ of those vertices that can be used to form diagonals. She wants you to choose no more than $$$y$$$ other vertices such that the number of triangular pieces of cake she can give out is maximized.What is the maximum number of triangular pieces of cake Bessie can give out?

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.The first line of each test case consists of three integers, $$$n$$$, $$$x$$$, and $$$y$$$ ($$$4 \leq n \leq 10^9$$$, $$$2 \leq x \leq \min(n, 2 \cdot 10^5)$$$, $$$0 \leq y \leq n - x$$$) — the number of sides of the polygon, number of vertices Bessie has chosen, and the maximum number of other vertices you can choose.The second line consists of $$$x$$$ distinct integers from $$$1$$$ to $$$n$$$, representing the vertices Bessie has chosen.It is guaranteed the sum of $$$x$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. 

Output: For each test case, output a single integer: the maximum number of non-intersecting triangular pieces of cake she can give out.

Note: In test cases $$$1$$$, $$$2$$$ and $$$3$$$, you can get $$$6$$$, $$$5$$$ and $$$2$$$ non-intersecting triangular pieces of cake, respectively. A possible construction is shown in the following pictures:The green dots represent vertices that Bessie chose, the yellow dots represent vertices that you chose, the blue lines represent diagonals that are drawn, and the red numbers represent triangles that are counted.  

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

Sample Outputs:
6
5
2

Solution (Python):
def solve():
    (n, x, y) = map(int, input().split())
    initial_y = y
    chosen = list(map(int, input().split()))
    chosen.sort()
    ans = x - 2
    triangles_from_even_g = 0
    odd_g = []

    def process_gap(gap):
        nonlocal ans, triangles_from_even_g, odd_g
        if gap <= 1:
            ans += gap
        elif gap % 2 == 1:
            odd_g.append(gap // 2)
        else:
            triangles_from_even_g += gap // 2
    for i in range(x - 1):
        process_gap(chosen[i + 1] - chosen[i] - 1)
    process_gap(chosen[0] + n - chosen[x - 1] - 1)
    odd_g.sort()
    for gap in odd_g:
        if y >= gap:
            ans += gap + 1
            y -= gap
        else:
            ans += y
            y = 0
            break
    even_triangles = min(triangles_from_even_g, y)
    y -= even_triangles
    ans += even_triangles
    used_vertices = initial_y - y
    ans += used_vertices
    print(ans)

def main():
    T = int(input())
    for _ in range(T):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
t = int(input())

def testcase():
    (n, x, y) = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    diffs = []
    even_diffs = 0
    nodes = x
    for i in range(x - 1):
        diff = a[i + 1] - a[i]
        if diff >= 3:
            if diff % 2 == 1:
                even_diffs += diff - 1
            else:
                diffs.append(diff - 1)
        elif diff == 2:
            nodes += 1
    diff = a[0] + n - a[-1]
    if diff >= 3:
        if diff % 2 == 1:
            even_diffs += diff - 1
        else:
            diffs.append(diff - 1)
    elif diff == 2:
        nodes += 1
    diffs.sort()
    for item in diffs:
        needed = item // 2
        if needed > y:
            nodes += y * 2
            y = 0
            break
        else:
            nodes += needed * 2 + 1
            y -= needed
    nodes += min(y * 2, even_diffs)
    nodes = min(nodes, n)
    print(nodes - 2)
for i in range(t):
    testcase()

Solution (Python):
import heapq
t_num = int(input())
r = []
mod = 10 ** 9 + 7

def solve():
    (n, x, y) = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    arr.sort()
    arr.append(arr[0] + n)
    size = []
    re = x - 2
    for i in range(x):
        k = arr[i + 1] - arr[i] - 1
        if k:
            size.append(k)
    size.sort()
    item = []
    mmm = 0
    for i in size:
        mmm += i // 2
        if i % 2 == 0:
            continue
        if i == 1:
            re += 1
            continue
        cost = i // 2
        item.append(cost)
    tot_re = 0
    tot_cost = 0
    for c in item:
        if tot_cost + c > y:
            break
        if tot_cost + c <= y:
            tot_cost += c
            tot_re += 1
    return re + tot_re + 2 * min(mmm, y)
for _ in range(t_num):
    r.append(solve())
for i in r:
    print(i)