#### [A. Optimal Number Partition](https://codeforces.me/gym/686937/problem/A)↵
↵
Idea and preparation:↵
↵
<spoiler summary = "Hint">↵
What kind of grouping makes the sum of squares smallest: one big group or many small balanced groups?↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
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))↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```↵
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))↵
```↵
</spoiler>↵
↵
#### [B. Optimal Picks](https://codeforces.me/gym/686937/problem/B)↵
↵
Idea and preparation:↵
↵
<spoiler summary = "Hint">↵
After sorting, which player gets the 1st, 2nd, 3rd, ... largest items in optimal play?↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
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)\)↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```↵
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)↵
```↵
↵
</spoiler>↵
↵
↵
#### [C. Sequence K-Labeling](https://codeforces.me/gym/686937/problem/C)↵
↵
Idea and preparation:↵
↵
<spoiler summary = "Hint">↵
When is the labeling impossible?↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
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))↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```↵
↵
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")↵
```↵
</spoiler>↵
↵
↵
#### [D. Sorting with Minimum Excluded Value](https://codeforces.me/gym/686937/problem/D)↵
↵
Idea and preparation:↵
↵
<spoiler summary = "Hint">↵
What should we do when the MEX is already inside the array, and what should we do when it is not?↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
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)\)↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```↵
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)↵
````↵
↵
</spoiler>↵
↵
---↵
↵
#### [E. Optimal Boat Selection](https://codeforces.me/gym/686937/problem/E)↵
↵
Idea and preparation:↵
↵
<spoiler summary = "Hint">↵
If we fix how many catamarans we take, how do we choose the best kayaks?↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
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))↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```↵
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()↵
```↵
↵
</spoiler>↵
↵
↵
↵
Idea and preparation:↵
↵
<spoiler summary = "Hint">↵
What kind of grouping makes the sum of squares smallest: one big group or many small balanced groups?↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
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))↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```↵
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))↵
```↵
</spoiler>↵
↵
#### [B. Optimal Picks](https://codeforces.me/gym/686937/problem/B)↵
↵
Idea and preparation:↵
↵
<spoiler summary = "Hint">↵
After sorting, which player gets the 1st, 2nd, 3rd, ... largest items in optimal play?↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
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)\)↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```↵
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)↵
```↵
↵
</spoiler>↵
↵
↵
#### [C. Sequence K-Labeling](https://codeforces.me/gym/686937/problem/C)↵
↵
Idea and preparation:↵
↵
<spoiler summary = "Hint">↵
When is the labeling impossible?↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
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))↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```↵
↵
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")↵
```↵
</spoiler>↵
↵
↵
#### [D. Sorting with Minimum Excluded Value](https://codeforces.me/gym/686937/problem/D)↵
↵
Idea and preparation:↵
↵
<spoiler summary = "Hint">↵
What should we do when the MEX is already inside the array, and what should we do when it is not?↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
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)\)↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```↵
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)↵
````↵
↵
</spoiler>↵
↵
---↵
↵
#### [E. Optimal Boat Selection](https://codeforces.me/gym/686937/problem/E)↵
↵
Idea and preparation:↵
↵
<spoiler summary = "Hint">↵
If we fix how many catamarans we take, how do we choose the best kayaks?↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
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))↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```↵
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()↵
```↵
↵
</spoiler>↵
↵
↵
