Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

Chef has failed miserably in several cooking competitions, which makes him think that he's been out of luck recently. Therefore, he decided to build a magic circle using his N chopsticks (numbered 1 through N), hoping that it would somehow improve his luck.

The magic circle consists of N chopsticks placed on an infinite straight line (so it's not actually a circle). The line is drawn on the ground and chopsticks should be stuck vertically into the ground.

The chopsticks have lengths x_{1},x_{2},\cdots,x_{N}. For each valid i, the i-th chopstick can be placed on the line at any integer position y_{i}; then it casts a shadow on the range [y_{i},y_{i}+x_{i}] on the line. No two chopsticks may be placed at the same position.

The positions of the chopsticks should satisfy an additional condition: for each pair of neighbouring chopsticks i and j (such that there are no other chopsticks between them), the distances between these neighbouring chopsticks | y_{i} - y_{j} \right| must fall in a given range [L,U].

The magic power of the circle depends on the total shadowed length S=| \bigcup_{i} [y_{i},y_{i}+x_{i}] \right|. While Chef expects the circle to have the maximum effect, he must prepare for the worst-case scenario — due to his recent bad luck. Please help Chef find both the minimum and the maximum value of S.

------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains three space-separated integers N, L and U.
- The second line contains N space-separated integers x_{1},x_{2},\cdots,x_{N}.

------ Output Format ------ 

For each test case, print a single line containing two space-separated integers S_{\min} and S_{\max}.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ L ≤ U ≤ 10^{9}$
$1 ≤ x_{i} ≤ 10^{9}$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^{5}$

------ subtasks ------ 

Subtask #1 (5 points):
$T ≤ 5$
$N ≤ 3$

Subtask #2 (15 points):
$T ≤ 5$
$N ≤ 11$, and additionally $N > 5$ in at most one test case

Subtask #3 (30 points): $N ≤ 200$

Subtask #4 (50 points): original constraints

----- Sample Input 1 ------ 
3
2 2 4
8 5
3 1 2
1 2 3
5 3 5
1 9 2 6 6
----- Sample Output 1 ------ 
8 12
3 6
13 22
----- explanation 1 ------ 
Example case 1:
- To minimize $S$, we may set $y_{1}=0$ and $y_{2}=2$.
- To maximize $S$, we may set $y_{1}=4$ and $y_{2}=0$.

Example case 2:
- To minimize $S$, we may set $y_{1}=2$, $y_{2}=1$ and $y_{3}=0$.
- To maximize $S$, we may set $y_{1}=0$, $y_{2}=1$ and $y_{3}=3$.

Example case 3:
- To minimize $S$, we may set $y_{1}=0$, $y_{2}=3$, $y_{3}=12$, $y_{4}=6$ and $y_{5}=9$.
- To maximize $S$, we may set $y_{1}=0$, $y_{2}=20$, $y_{3}=5$, $y_{4}=10$ and $y_{5}=15$.

Source: codechef | Difficulty: VERY_HARD
Tags: Constructive algorithms

Sorting

Complete search

Data structures

Ad-hoc


Solutions:
import math
from collections import Counter, defaultdict
import sys
import heapq

def overlap(res):
	res.sort()
	res2 = [res[0]]
	for i in res:
		if i[0] <= res2[-1][1] and i[1] <= res2[-1][1]:
			continue
		elif i[0] <= res2[-1][1] and i[1] >= res2[-1][1]:
			res2[-1][1] = i[1]
		else:
			res2.append(i)
	min_res = 0
	for i in res2:
		min_res += i[1] - i[0]
	return min_res

def solve():
	arr.sort()
	max_res = arr[-1]
	heap = []
	for i in range(n - 2, -1, -1):
		heapq.heappush(heap, -arr[i])
	for i in range(n - 1):
		val = -heapq.heappop(heap)
		if val > u:
			max_res += u
			heapq.heappush(heap, -(val - u))
		else:
			max_res += val
	arr.sort(reverse=True)
	pos = 0
	res = []
	for i in arr:
		pos += l
		res.append([pos, pos + i])
	min_res = overlap(res)
	return (min_res, max_res)
for _ in range(int(input())):
	(n, l, u) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(*solve())


T = int(input())
for t in range(T):
	(N, L, U) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	mini = maxi = arr[-1]
	pref = min(L, arr[-1])
	(cnt, mod) = (0, [])
	for i in range(N - 2, -1, -1):
		mini = max(mini, pref + arr[i])
		pref = min(pref + L, mini)
		if arr[i] >= U:
			cnt += (arr[i] - U) // U
			mod.append(arr[i] % U)
			maxi += U
	mod.sort(reverse=True)
	ln = len(mod)
	right = min(cnt + ln, N - 1 - ln)
	maxi += min(cnt, N - 1 - ln) * U
	for i in range(cnt, right):
		maxi += max(mod[i - cnt], arr[i])
	for i in range(right, N - 1 - ln):
		maxi += arr[i]
	print(mini, maxi)


import heapq

def min_power(n, l, xs):
	total = 0
	y = 0
	s = 0
	for i in range(len(xs)):
		x = xs[i]
		total += min(x, max(0, y + x - s))
		s = max(s, y + x)
		y += l
	return total

def max_power(n, u, xs):
	xs = list(map(lambda x: -x, xs))
	total = heapq.heappop(xs)
	for _ in range(n - 1):
		x = xs[0]
		if x < -u:
			total += -u
			x += u
			heapq.heapreplace(xs, x)
		else:
			total += heapq.heappop(xs)
	return -total
t = int(input())
for _ in range(t):
	(n, l, u) = map(int, input().split())
	xs = list(map(int, input().split()))
	xs.sort(reverse=True)
	print(min_power(n, l, xs), max_power(n, u, xs))


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07

def dfs(a, b, p, c):
	if a == b:
		return c
	for (i, j) in adj[a]:
		if i == p:
			continue
		temp = dfs(i, b, a, c + j)
		if dfs(i, b, a):
			mx = max(i, mx)
			return 1
adj = []
ans = []

def dfs(root, par, v):
	global adj, ans, abe
	tot = v
	for (child, val) in adj[root]:
		if par == child:
			continue
		tot |= dfs(child, root, val)
	ans[root] = tot
	return tot
abe = 0

def traverse(root, par):
	global adj, ans, abe
	for (child, val) in adj[root]:
		if par == child:
			continue
		if ans[child] == 0:
			abe += 1
		else:
			traverse(child, root)

def hnbhai(tc):
	(n, l, u) = sd()
	x = sd()
	x.sort(reverse=True)
	tot = 0
	bacha = 0
	pos = 0
	for i in x:
		tmp = i + pos
		if bacha < pos:
			bacha = pos
		if tmp > bacha:
			tot += tmp - bacha
			bacha = tmp
		pos += l
	abe = 0
	tot1 = x[0]
	temp = []
	for i in range(1, n):
		abe += x[i] // u
		temp.append(x[i] % u)
	temp.sort(reverse=True)
	are = min(n - 1, abe)
	tot1 += are * u + sum(temp[:min(n - 1 - are, len(temp))])
	print(tot, tot1)
for _ in range(sb()):
	hnbhai(_ + 1)