What kind of grouping makes the sum of squares smallest: one big group or many small balanced groups?

Since every group must contain at least 2 numbers, the best choice is to make every group contain exactly 2 numbers.

If a group has more than 2 numbers, splitting it into smaller groups decreases the total cost because the square function is convex. So the problem becomes pairing the numbers.

To minimize

[ \sum (s_j)^2 ]

we should pair the smallest number with the largest number, the second smallest with the second largest, and so on.

So the steps are:

• sort the array

• use two pointers

• pair nums[l] with nums[r]

• add ((nums[l] + nums[r])^2) to the answer

• Time Complexity: (O(n \log n))

• Space Complexity: (O(1))

m = int(input().strip())
arr = list(map(int, input().split()))

def solve(m, arr):
    arr.sort()
    total = 0

    left, right = 0, m - 1

    while left <= right:
        total += (arr[left] + arr[right]) ** 2
        left += 1
        right -= 1

    return total

print(solve(m, arr))

After sorting, which player gets the 1st, 2nd, 3rd, ... largest items in optimal play?

If the array is sorted in descending order, then optimal play is simple: - Eve takes the 1st, 3rd, 5th, ... largest elements - Noah takes the 2nd, 4th, 6th, ... largest elements

So the initial score is the difference between consecutive pairs in the sorted order.

Noah can increase some values with total budget at most k.
The best way is to use this budget on Noah’s picked elements so that they become as large as possible, but only up to the previous Eve element in the pair. Any extra increase beyond that does not help the score.

So: - sort descending - compute Eve’s sum and Noah’s sum - for every Noah element, use as much remaining k as possible to close the gap with the previous element - print the final score

• Time Complexity: (O(n \log n))
• Space Complexity: (O(1))

test_cases = int(input().strip())

for _ in range(test_cases):
    size, budget = map(int, input().split())
    values = list(map(int, input().split()))

    eve_sum = 0
    noah_sum = 0

    values.sort()
    previous = None

    for idx, value in enumerate(values[::-1]):
        if idx % 2 == 0:
            eve_sum += value
        else:
            gain = min(budget, previous - value)
            budget -= gain
            noah_sum += value + gain
        previous = value

    print(eve_sum - noah_sum)

When is the labeling impossible?

First, count how many times each value appears.

If some value appears more than k times, then it is impossible, because equal values cannot share the same label and there are only k labels.

Otherwise, the construction is easy:

• sort the values together with their indices
• assign labels cyclically from 1 to k

This works because:

• equal values appear at most k times, so they get different labels

• every label is used at least once

• Time Complexity: (O(n \log n))

• Space Complexity: (O(n))

from collections import defaultdict

n, k = map(int, input().split())
sequence = list(map(int, input().split()))

def solve(n, k, sequence):
    freq = defaultdict(int)

    for x in sequence:
        freq[x] += 1

    for cnt in freq.values():
        if cnt > k:
            return []

    indexed = []
    for pos, val in enumerate(sequence):
        indexed.append([val, pos])

    indexed.sort()

    label = 1
    for val, pos in indexed:
        sequence[pos] = label
        label += 1
        if label > k:
            label = 1

    return sequence

answer = solve(n, k, sequence)

if answer:
    print("YES")
    print(*answer)
else:
    print("NO")

What should we do when the MEX is already inside the array, and what should we do when it is not?

We repeatedly use the MEX operation to make the array non-decreasing.

The greedy idea is: - If mex < n, then set a[mex] = mex. This fixes one position directly. - If mex == n, then there is no missing value among 0..n-1, so the array still has some wrong position. In that case, choose the first index where a[i] != i and set it to n.

This guarantees progress every time.

We stop once the array becomes non-decreasing, and the number of operations is always at most 2n.

• Time Complexity: (O(n^2)) in the straightforward implementation
• Space Complexity: (O(n))

test_cases = int(input().strip())

for _ in range(test_cases):
    n = int(input().strip())
    array = list(map(int, input().split()))

    def is_sorted(arr):
        for i in range(1, len(arr)):
            if arr[i] < arr[i - 1]:
                return False
        return True

    def mex_value(arr, n):
        present = set(arr)
        for x in range(n + 1):
            if x not in present:
                return x

    def first_wrong(arr):
        for i in range(n):
            if arr[i] != i:
                return i

    ops = []
    for _ in range(2 * n):
        if is_sorted(array):
            break

        mex = mex_value(array, n)

        if mex < n:
            array[mex] = mex
            ops.append(mex + 1)
        else:
            pos = first_wrong(array)
            array[pos] = mex
            ops.append(pos + 1)

    print(len(ops))
    print(*ops)

If we fix how many catamarans we take, how do we choose the best kayaks?

We have two types of vehicles: - kayaks with volume 1 - catamarans with volume 2

We want the maximum total carrying capacity without exceeding the truck volume v.

The greedy idea is:

• separate kayaks and catamarans
• sort each list by capacity in descending order
• build prefix sums for both lists

Then try every possible number of catamarans:

• if we take c catamarans, they use 2c volume

• the remaining volume can be filled with the best kayaks

• compute the total capacity and keep the maximum

• Time Complexity: (O(n \log n))

• Space Complexity: (O(n))

import sys

def solve():
    input = sys.stdin.readline
    n, capacity = map(int, input().split())

    small_boats = []
    big_boats = []

    for idx in range(1, n + 1):
        boat_type, boat_power = map(int, input().split())
        if boat_type == 1:
            small_boats.append((boat_power, idx))
        else:
            big_boats.append((boat_power, idx))

    small_boats.sort(reverse=True)
    big_boats.sort(reverse=True)

    pref_small = [0]
    for power, _ in small_boats:
        pref_small.append(pref_small[-1] + power)

    pref_big = [0]
    for power, _ in big_boats:
        pref_big.append(pref_big[-1] + power)

    best_score = 0
    best_big = 0
    best_small = 0

    max_big = min(len(big_boats), capacity // 2)

    for cnt_big in range(max_big + 1):
        used_space = 2 * cnt_big
        remaining = capacity - used_space
        cnt_small = min(len(small_boats), remaining)
        current_score = pref_big[cnt_big] + pref_small[cnt_small]

        if current_score > best_score:
            best_score = current_score
            best_big = cnt_big
            best_small = cnt_small

    chosen = []
    for i in range(best_big):
        chosen.append(big_boats[i][1])
    for i in range(best_small):
        chosen.append(small_boats[i][1])

    print(best_score)
    print(*chosen)

if __name__ == "__main__":
    solve()