[Here](https://codeforces.me/gym/544854) is the mashup link for Div1. Round #41 contest.↵
↵
[Here](https://codeforces.me/gym/544853) is the mashup link for Div2. Round #41 contest.↵
↵
[Here](https://codeforces.me/gym/545013) is the mashup link for Div3. Round #41 contest.↵
↵
All problems are from Codeforces' problem set.↵
↵
↵
#### [A. Lucky Numbers](https://codeforces.me/gym/545013/problem/A)↵
↵
<spoiler summary="Solution">↵
↵
This problem just needs to simulate everything that was given in the statement.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
n, k = map(int, input().split())↵
nums = input().split()↵
count = 0 ↵
for num in nums:↵
num_count = num.count('4') + num.count('7')↵
if num_count <= k:↵
count += 1↵
↵
print(count)↵
↵
```↵
</spoiler>↵
↵
↵
#### [B. Chore Partitioning](https://codeforces.me/gym/545013/problem/B)↵
↵
<spoiler summary = "Solution">↵
The problem requires finding how many values of`x`can divide the chores into exactly`a`chores for Petya (with complexity greater than`x`) and`b`chores for Vasya (with complexity less than or equal to`x`).↵
↵
**Approach:**↵
↵
1. **Sort the Chore Complexities:** Begin by sorting the array of chore complexities in ascending order. This allows us to easily separate the chores for Petya and Vasya based on their desired counts.↵
2. **Identifying the Chore Split:**↵
Since Vasya will take the`b`least complex chores, these will be the first`b`elements in the sorted array.↵
Petya will then take the remaining a chores, which are the last`a`elements in the sorted array.↵
3. **Determine`x`:**↵
The threshold`x`that divides the chores must be greater than the largest complexity of the chores Vasya takes and less than or equal to the smallest complexity of the chores Petya takes.↵
Therefore,`x`must satisfy: `arr[b - 1] < x ≤ arr[b]`.↵
4. **Calculate the Number of Valid Values for`x`:**↵
The number of valid`x`values is given by `arr[b] - arr[b - 1]`. This represents the range of values that`x`can take to properly divide the chores between Petya and Vasya.↵
If the values of `arr[b]` and `arr[b - 1]` are the same, no such`x`exists, and the answer is $0$.↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
↵
import sys↵
↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
n, a, b = map(int, input().split())↵
arr = list(map(int, input().split()))↵
arr.sort()↵
↵
print(arr[b] - arr[b - 1])↵
↵
```↵
</spoiler>↵
↵
↵
#### [C. Lab Renovation Sum Check](https://codeforces.me/gym/544853/problem/A)↵
↵
<spoiler summary = "Solution">↵
We can simulate exactly what's described in the statement: loop over all cells not equal to $1$ and check if it doesn't break the city property. To check if a cell breaks the property, just loop over an element in the same row, and an element in the same column, and see if they can add to give the cell's number. The complexity is $O(n^4)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input())↵
↵
lab = [] ↵
for _ in range(n):↵
lab.append(list(map(int, input().split())))↵
↵
for i in range(n):↵
for j in range(n):↵
if lab[i][j] != 1:↵
for k in range(n):↵
if i != k and lab[i][j] - lab[k][j] in lab[i]:↵
break↵
else:↵
print('No')↵
exit(0)↵
↵
print('Yes')↵
↵
```↵
</spoiler>↵
↵
↵
#### [D. Card Dealing](https://codeforces.me/gym/544853/problem/B)↵
↵
<spoiler summary = "Hint 1">↵
<p>Look for patterns in how cards are distributed based on the step number..</p>↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2">↵
<p>Group steps using modulo 4 to see who gets which cards.</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
To determine how many cards Alice and Bob receive from a deck of `n` cards dealt in increasing steps, we can use two approaches: a direct simulation and an optimized mathematical method.↵
↵
**Initial Approach (Simulation):**↵
↵
1. **Calculate Maximum Complete Steps `x`:** Simulate dealing cards step-by-step until the total dealt cards exceed `n`.↵
↵
2. **Compute Total Cards Dealt and Remainder:** Sum the cards dealt up to the largest complete step `x` and find the remaining cards.↵
3. **Distribute Cards:**↵
- **Alice** receives cards on steps where `current_step % 4` is $1$ or $0$.↵
- **Bob** receives cards on steps where `current_step % 4` is $2$ or $3$.↵
4. **Add Remaining Cards:** Distribute any leftover cards based on the current step index after the last complete step.↵
↵
**Time complexity:** $O(n)$ ↵
**Space complexity:** $O(1)$↵
</spoiler>↵
↵
<spoiler summary="Code (Approach 1)">↵
```python↵
import sys↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
total_cards = 0↵
step = 1↵
↵
# Find the maximum number of complete steps↵
while total_cards + step <= n:↵
total_cards += step↵
step += 1↵
↵
x = step - 1↵
remainder = n - total_cards↵
↵
alice_sum = bob_sum = 0↵
current_step = 1↵
↵
# Distribute cards up to step x↵
for i in range(1, x + 1):↵
if current_step % 4 == 1 or current_step % 4 == 0:↵
alice_sum += i↵
else:↵
bob_sum += i↵
current_step += 1↵
↵
# Add the remainder to the correct person↵
if remainder > 0:↵
if current_step % 4 == 1 or current_step % 4 == 0:↵
alice_sum += remainder↵
↵
else:↵
bob_sum += remainder↵
↵
print(alice_sum, bob_sum)↵
```↵
</spoiler>↵
↵
<spoiler summary="Optimized Approach">↵
↵
The initial approach, while straightforward, may be inefficient for large `n`. We can optimize it using mathematical formulas.↵
↵
**Solution Approach:**↵
↵
1. **Find Maximum Number of Complete Steps`x`:** Calculate`x` where the sum of the first `x` numbers does not exceed `n`: ↵
↵
- Solving for x from this equation ($n = \frac{x \cdot (x + 1)}{2}$↵
) which is the sum of the first natural numbers up to $x$ gives the bound as $x = \left\lfloor \frac{-1 + \sqrt{1 + 8 \cdot n}}{2} \right\rfloor$.↵
↵
2. **Calculate Total Cards Dealt and Remaining Cards:**↵
- **Total cards dealt** `total`: $\frac{x \cdot (x + 1)}{2}$ ↵
- **Remainder**: `n - total`↵
↵
3. **Distribute Cards Using Arithmetic Series:**↵
- **Alice’s Cards:** Sum of series for steps where `i % 4 = 1` and `i % 4 = 0`.↵
- **Bob’s Cards:** Sum of series for steps where `i % 4 = 2` and `i % 4 = 3`.↵
- Use the formula for the sum of an arithmetic series:↵
- $S_m = \frac{m}{2} \left(2a_1 + (m - 1) \cdot d \right)$↵
where $a_1$ is the first term, $d$ is the common difference, and $m$ is the number of terms.↵
4. **Add Remaining Cards:**↵
Distribute the remainder based on the step index after `x` steps.↵
↵
**Time complexity:** $O(\log n)$ ↵
**Space complexity:** $O(1)$↵
</spoiler>↵
↵
<spoiler summary="Code (Approach 2)">↵
```python↵
import sys, math↵
↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
def arithmetic_series_sum(start, diff, last_term):↵
"""↵
Calculate the sum of an arithmetic series where the first term is `start`,↵
the common difference is `diff`, and the last term is `last_term`.↵
"""↵
count = (last_term - start) // diff + 1↵
return count * (2 * start + (count - 1) * diff) // 2↵
↵
def find_max_x(n):↵
"""↵
Find the maximum `x` such that the sum of the first `x` natural numbers is <= `n`.↵
"""↵
return math.floor((-1 + math.sqrt(1 + 8 * n)) / 2)↵
↵
t = int(input())↵
↵
for _ in range(t):↵
n = int(input())↵
↵
# Determine the maximum `x` for which the sum of the first `x` natural numbers is <= `n`↵
x = find_max_x(n)↵
↵
# Total sum of the first `x` natural numbers↵
total_sum_x = x * (x + 1) // 2↵
↵
# Calculate the remaining cards↵
remainder = n - total_sum_x↵
↵
# Calculate sums for Alice and Bob up to the largest valid `x`↵
alice_sum = 1 + arithmetic_series_sum(4, 4, x) + arithmetic_series_sum(5, 4, x)↵
bob_sum = arithmetic_series_sum(2, 4, x) + arithmetic_series_sum(3, 4, x)↵
↵
# Distribute the remaining cards↵
if remainder > 0:↵
if (x + 1) % 4 in (1, 0):↵
alice_sum += remainder↵
else:↵
bob_sum += remainder↵
↵
print(alice_sum, bob_sum)↵
```↵
</spoiler>↵
↵
↵
#### [E. Min Divisible Outside Segment](https://codeforces.me/gym/544854/problem/A)↵
↵
<spoiler summary="Solution">↵
↵
If $d_i$ is less than $l_i$, then $d_i$ itself is the smallest integer that satisfies the condition because it is divisible by $d_i$ and does not belong to $[l_i, r_i]$.↵
↵
Otherwise, if $d_i$ is within the segment $[l_i, r_i]$, the smallest integer divisible by $d_i$ that is not in the segment is $(\lfloor r_i / d_i \rfloor + 1) \cdot d_i$.↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code">↵
```python↵
for _ in range(int(input())):↵
l, r, d = map(int,input().split())↵
if d < l:↵
print(d)↵
else:↵
print((r//d + 1)*d)↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [F. Swapping](https://codeforces.me/gym/544854/problem/B)↵
↵
<spoiler summary = "Solution">↵
↵
In this problem, our goal is to determine the number of indices that can be set to $1$ after performing m swaps. Each swap operation allows us to swap elements within a given range $[l, r]$.↵
↵
Initially, without any swaps, the only index that can be $1$ is $x$. However, if we have a range that includes the current index $x$, we can swap any of the indices within that range with the current index. This means that the possible indices that can be $1$ expand based on the ranges provided.↵
↵
To solve this, we need to combine all the ranges. If the final combined range includes the index $x$, then all indices within that range can be set to $1$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
``` python3↵
t = int(input())↵
for _ in range(t):↵
n,k,m = list(map(int,input().split()))↵
start = k↵
end = k↵
↵
for i in range(m):↵
l,r = gns()↵
if l <= start <= r or l <= end <= r:↵
start = min(start,l)↵
end = max(end,r)↵
print(end - start + 1)↵
```↵
</spoiler>↵
↵
↵
#### [G. MEX Tree Labeling](https://codeforces.me/gym/544854/problem/C)↵
↵
<spoiler summary = "Solution">↵
Notice that there will be a path that passes through the edge labeled $0$ and the edge labeled $1$ no matter how you label the edges, so there's always a path with MEX $2$ or more. If any node has degree $3$ or more, you can distribute the labels $0$, $1$, and $2$ to edges incident to this node and distribute the rest of the labels arbitrarily. Otherwise, the tree is a bamboo, and it doesn't actually matter how you label the edges, since there will be a path with MEX $n−1$ anyway.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
from collections import defaultdict↵
↵
graph = defaultdict(list)↵
ans = {}↵
↵
n = int(sys.stdin.readline().strip())↵
↵
for i in range(1, n):↵
a, b = map(int, sys.stdin.readline().strip().split())↵
graph[a].append(i)↵
graph[b].append(i)↵
ans[i] = -1↵
↵
# Find the node with the maximum degree↵
mx = (0, 0)↵
for i in range(1, n + 1):↵
if len(graph[i]) > mx[0]:↵
mx = (len(graph[i]), i)↵
↵
cur = 0↵
for i in graph[mx[1]]:↵
ans[i] = cur↵
cur += 1↵
↵
for i in range(1, n):↵
if ans[i] == -1:↵
ans[i] = cur↵
cur += 1↵
print(ans[i])↵
```↵
</spoiler>↵
↵
↵
#### [H. Martian Maximum XOR](https://codeforces.me/gym/544854/problem/D)↵
↵
<spoiler summary="Solution">↵
<ul>↵
<li>↵
<b>Solution 1:</b> Let's use the data structure called a bitwise trie. Fix some $a_{i}$, where all $a_{j}$ for $j<i$ have already been added to the trie. We will iterate over the bits in $a_{i}$ from the $(k−1)^{th}$ bit to the $0^{th}$ bit. Since $2^{t}>2^{t−1}+2^{t−2}+…+2+1$, if there exists $a_{j}$ with the same bit at the corresponding position in $a_{i}$, we will go into that branch of the trie and append $1−b$ to the corresponding bit $x$. Otherwise, our path is uniquely determined. When we reach a leaf, the bits on the path will correspond to the optimal number $a_{j}$ for $a_{i}$. The time complexity of this solution is $O(nk)$.↵
</li>↵
<li>↵
<b>Solution 2:</b> Sort $a_{1},a_{2},…,a_{n}$ in non-decreasing order. We will prove that the answer is some pair of adjacent numbers. Let the answer be numbers $a_{i},a_{j} (j−i>1)$. If $a_{i}=a_{j}$, then $a_{i}=a_{i+1}$. Otherwise, they have a common prefix of bits, after which there is a differing bit. That is, at some position $t$, $a_{i}$ has a $0$ and $a_{j}$ has a $1$. Since $j−i>1$, $a{i+1}$ can have either $0$ or $1$ at this position, but in the first case it is more advantageous to choose $a_{i},a_{i+1}$ as the answer, and in the second case it is more advantageous to choose $a_{i+1},a_{j}$ as the answer. The complexity of this solution is $O(nlogn)$.↵
</li>↵
</ul>↵
</p>↵
↵
<p>↵
For the first approach, make sure to use $PyPy 3-64$.↵
</p>↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
class TrieNode:↵
def __init__(self):↵
self.children = [None, None]↵
self.position = -1 # index of the corresponding number in the given array↵
↵
t = int(input())↵
for _ in range(t):↵
n, k = map(int, input().split())↵
a = list(map(int, input().split()))↵
↵
ans_i = ans_j = ans_x = 1, 1, 0↵
max_val = 0 # maximum value of (a[i] ^ x) & (a[j] ^ x)↵
↵
root_node = TrieNode()↵
for i, num in enumerate(a):↵
cur_node = root_node↵
# find a pair a[j] for this number↵
# first check if there's at least one number in the trie↵
if cur_node.children[0] or cur_node.children[1]:↵
x = 0↵
for bit_i in range(k - 1, -1, -1):↵
if num & (1 << bit_i):↵
# match 1 bit with 1 bit↵
if cur_node.children[1]:↵
cur_node = cur_node.children[1]↵
else: # if not possible, match 1 bit with 0 bit↵
cur_node = cur_node.children[0]↵
↵
else:↵
# match 0 bit with 0 bit↵
if cur_node.children[0]:↵
cur_node = cur_node.children[0]↵
x = x ^ (1 << bit_i)↵
else: # if not possible, match 0 bit with 1 bit↵
cur_node = cur_node.children[1]↵
↵
j = cur_node.position↵
new_val = (num ^ x)&(a[j] ^ x)↵
if new_val >= max_val:↵
max_val = new_val↵
ans_i, ans_j, ans_x = i + 1, j + 1, x↵
↵
# insert the current number into the trie↵
cur_node = root_node↵
for bit_i in range(k - 1, -1, -1):↵
if num & (1 << bit_i):↵
if not cur_node.children[1]:↵
cur_node.children[1] = TrieNode()↵
cur_node = cur_node.children[1]↵
↵
else:↵
if not cur_node.children[0]:↵
cur_node.children[0] = TrieNode()↵
cur_node = cur_node.children[0]↵
↵
cur_node.position = i↵
↵
print(ans_i, ans_j, ans_x)↵
↵
↵
```↵
</spoiler>↵
↵
↵
#### [I. MST for Promptness](https://codeforces.me/gym/544854/problem/E)↵
↵
<spoiler summary="solution">↵
If we connect the graph using $0$-weighted edges only and we are left with $k$ components, we need $k - 1$ $1$-weighted edges.↵
↵
Let's keep track of the unconnected nodes in a set and every time we do a BFS starting from an unconnected node to a node that has no edge with it. We have to check if there is a node in unconnected nodes that is not a neighbor (considering $1$-weighted edge) of it. Every time we check if the node is the neighbor we pass it and if not we add it in the BFS queue. Worst case, the first case will only happen $m$ (the number of $1$-weighted edges) times and the second case will only happen $n$ times. The overall time complexity will be $O(n + m)$.↵
↵
</spoiler>↵
↵
<spoiler summary="code">↵
```python↵
from collections import defaultdict, deque↵
from sys import stdin↵
↵
↵
def input(): return stdin.readline().strip()↵
↵
N, M = map(int, input().split())↵
↵
adj = defaultdict(set)↵
for _ in range(M):↵
u, v = map(int, input().split())↵
u, v = u - 1, v - 1↵
adj[u].add(v)↵
adj[v].add(u)↵
↵
unconnected = set(range(N))↵
edges = 0↵
↵
for i in range(N):↵
if i in unconnected:↵
q = deque([i])↵
unconnected.remove(i)↵
while q:↵
v = q.popleft()↵
remove = []↵
for u in unconnected:↵
if v not in adj[u]:↵
edges += 1↵
remove.append(u)↵
q.append(u)↵
for u in remove:↵
unconnected.remove(u)↵
print(N - 1 - edges)↵
```↵
</spoiler>↵
↵
↵
↵
[Here](https://codeforces.me/gym/544853) is the mashup link for Div2. Round #41 contest.↵
↵
[Here](https://codeforces.me/gym/545013) is the mashup link for Div3. Round #41 contest.↵
↵
All problems are from Codeforces' problem set.↵
↵
↵
#### [A. Lucky Numbers](https://codeforces.me/gym/545013/problem/A)↵
↵
<spoiler summary="Solution">↵
↵
This problem just needs to simulate everything that was given in the statement.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
n, k = map(int, input().split())↵
nums = input().split()↵
count = 0 ↵
for num in nums:↵
num_count = num.count('4') + num.count('7')↵
if num_count <= k:↵
count += 1↵
↵
print(count)↵
↵
```↵
</spoiler>↵
↵
↵
#### [B. Chore Partitioning](https://codeforces.me/gym/545013/problem/B)↵
↵
<spoiler summary = "Solution">↵
The problem requires finding how many values of`x`can divide the chores into exactly`a`chores for Petya (with complexity greater than`x`) and`b`chores for Vasya (with complexity less than or equal to`x`).↵
↵
**Approach:**↵
↵
1. **Sort the Chore Complexities:** Begin by sorting the array of chore complexities in ascending order. This allows us to easily separate the chores for Petya and Vasya based on their desired counts.↵
2. **Identifying the Chore Split:**↵
Since Vasya will take the`b`least complex chores, these will be the first`b`elements in the sorted array.↵
Petya will then take the remaining a chores, which are the last`a`elements in the sorted array.↵
3. **Determine`x`:**↵
The threshold`x`that divides the chores must be greater than the largest complexity of the chores Vasya takes and less than or equal to the smallest complexity of the chores Petya takes.↵
Therefore,`x`must satisfy: `arr[b - 1] < x ≤ arr[b]`.↵
4. **Calculate the Number of Valid Values for`x`:**↵
The number of valid`x`values is given by `arr[b] - arr[b - 1]`. This represents the range of values that`x`can take to properly divide the chores between Petya and Vasya.↵
If the values of `arr[b]` and `arr[b - 1]` are the same, no such`x`exists, and the answer is $0$.↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
↵
import sys↵
↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
n, a, b = map(int, input().split())↵
arr = list(map(int, input().split()))↵
arr.sort()↵
↵
print(arr[b] - arr[b - 1])↵
↵
```↵
</spoiler>↵
↵
↵
#### [C. Lab Renovation Sum Check](https://codeforces.me/gym/544853/problem/A)↵
↵
<spoiler summary = "Solution">↵
We can simulate exactly what's described in the statement: loop over all cells not equal to $1$ and check if it doesn't break the city property. To check if a cell breaks the property, just loop over an element in the same row, and an element in the same column, and see if they can add to give the cell's number. The complexity is $O(n^4)$.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input())↵
↵
lab = [] ↵
for _ in range(n):↵
lab.append(list(map(int, input().split())))↵
↵
for i in range(n):↵
for j in range(n):↵
if lab[i][j] != 1:↵
for k in range(n):↵
if i != k and lab[i][j] - lab[k][j] in lab[i]:↵
break↵
else:↵
print('No')↵
exit(0)↵
↵
print('Yes')↵
↵
```↵
</spoiler>↵
↵
↵
#### [D. Card Dealing](https://codeforces.me/gym/544853/problem/B)↵
↵
<spoiler summary = "Hint 1">↵
<p>Look for patterns in how cards are distributed based on the step number..</p>↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2">↵
<p>Group steps using modulo 4 to see who gets which cards.</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
To determine how many cards Alice and Bob receive from a deck of `n` cards dealt in increasing steps, we can use two approaches: a direct simulation and an optimized mathematical method.↵
↵
**Initial Approach (Simulation):**↵
↵
1. **Calculate Maximum Complete Steps `x`:** Simulate dealing cards step-by-step until the total dealt cards exceed `n`.↵
↵
2. **Compute Total Cards Dealt and Remainder:** Sum the cards dealt up to the largest complete step `x` and find the remaining cards.↵
3. **Distribute Cards:**↵
- **Alice** receives cards on steps where `current_step % 4` is $1$ or $0$.↵
- **Bob** receives cards on steps where `current_step % 4` is $2$ or $3$.↵
4. **Add Remaining Cards:** Distribute any leftover cards based on the current step index after the last complete step.↵
↵
**Time complexity:** $O(n)$ ↵
**Space complexity:** $O(1)$↵
</spoiler>↵
↵
<spoiler summary="Code (Approach 1)">↵
```python↵
import sys↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
total_cards = 0↵
step = 1↵
↵
# Find the maximum number of complete steps↵
while total_cards + step <= n:↵
total_cards += step↵
step += 1↵
↵
x = step - 1↵
remainder = n - total_cards↵
↵
alice_sum = bob_sum = 0↵
current_step = 1↵
↵
# Distribute cards up to step x↵
for i in range(1, x + 1):↵
if current_step % 4 == 1 or current_step % 4 == 0:↵
alice_sum += i↵
else:↵
bob_sum += i↵
current_step += 1↵
↵
# Add the remainder to the correct person↵
if remainder > 0:↵
if current_step % 4 == 1 or current_step % 4 == 0:↵
alice_sum += remainder↵
↵
else:↵
bob_sum += remainder↵
↵
print(alice_sum, bob_sum)↵
```↵
</spoiler>↵
↵
<spoiler summary="Optimized Approach">↵
↵
The initial approach, while straightforward, may be inefficient for large `n`. We can optimize it using mathematical formulas.↵
↵
**Solution Approach:**↵
↵
1. **Find Maximum Number of Complete Steps`x`:** Calculate`x` where the sum of the first `x` numbers does not exceed `n`: ↵
↵
- Solving for x from this equation ($n = \frac{x \cdot (x + 1)}{2}$↵
) which is the sum of the first natural numbers up to $x$ gives the bound as $x = \left\lfloor \frac{-1 + \sqrt{1 + 8 \cdot n}}{2} \right\rfloor$.↵
↵
2. **Calculate Total Cards Dealt and Remaining Cards:**↵
- **Total cards dealt** `total`: $\frac{x \cdot (x + 1)}{2}$ ↵
- **Remainder**: `n - total`↵
↵
3. **Distribute Cards Using Arithmetic Series:**↵
- **Alice’s Cards:** Sum of series for steps where `i % 4 = 1` and `i % 4 = 0`.↵
- **Bob’s Cards:** Sum of series for steps where `i % 4 = 2` and `i % 4 = 3`.↵
- Use the formula for the sum of an arithmetic series:↵
- $S_m = \frac{m}{2} \left(2a_1 + (m - 1) \cdot d \right)$↵
where $a_1$ is the first term, $d$ is the common difference, and $m$ is the number of terms.↵
4. **Add Remaining Cards:**↵
Distribute the remainder based on the step index after `x` steps.↵
↵
**Time complexity:** $O(\log n)$ ↵
**Space complexity:** $O(1)$↵
</spoiler>↵
↵
<spoiler summary="Code (Approach 2)">↵
```python↵
import sys, math↵
↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
def arithmetic_series_sum(start, diff, last_term):↵
"""↵
Calculate the sum of an arithmetic series where the first term is `start`,↵
the common difference is `diff`, and the last term is `last_term`.↵
"""↵
count = (last_term - start) // diff + 1↵
return count * (2 * start + (count - 1) * diff) // 2↵
↵
def find_max_x(n):↵
"""↵
Find the maximum `x` such that the sum of the first `x` natural numbers is <= `n`.↵
"""↵
return math.floor((-1 + math.sqrt(1 + 8 * n)) / 2)↵
↵
t = int(input())↵
↵
for _ in range(t):↵
n = int(input())↵
↵
# Determine the maximum `x` for which the sum of the first `x` natural numbers is <= `n`↵
x = find_max_x(n)↵
↵
# Total sum of the first `x` natural numbers↵
total_sum_x = x * (x + 1) // 2↵
↵
# Calculate the remaining cards↵
remainder = n - total_sum_x↵
↵
# Calculate sums for Alice and Bob up to the largest valid `x`↵
alice_sum = 1 + arithmetic_series_sum(4, 4, x) + arithmetic_series_sum(5, 4, x)↵
bob_sum = arithmetic_series_sum(2, 4, x) + arithmetic_series_sum(3, 4, x)↵
↵
# Distribute the remaining cards↵
if remainder > 0:↵
if (x + 1) % 4 in (1, 0):↵
alice_sum += remainder↵
else:↵
bob_sum += remainder↵
↵
print(alice_sum, bob_sum)↵
```↵
</spoiler>↵
↵
↵
#### [E. Min Divisible Outside Segment](https://codeforces.me/gym/544854/problem/A)↵
↵
<spoiler summary="Solution">↵
↵
If $d_i$ is less than $l_i$, then $d_i$ itself is the smallest integer that satisfies the condition because it is divisible by $d_i$ and does not belong to $[l_i, r_i]$.↵
↵
Otherwise, if $d_i$ is within the segment $[l_i, r_i]$, the smallest integer divisible by $d_i$ that is not in the segment is $(\lfloor r_i / d_i \rfloor + 1) \cdot d_i$.↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code">↵
```python↵
for _ in range(int(input())):↵
l, r, d = map(int,input().split())↵
if d < l:↵
print(d)↵
else:↵
print((r//d + 1)*d)↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [F. Swapping](https://codeforces.me/gym/544854/problem/B)↵
↵
<spoiler summary = "Solution">↵
↵
In this problem, our goal is to determine the number of indices that can be set to $1$ after performing m swaps. Each swap operation allows us to swap elements within a given range $[l, r]$.↵
↵
Initially, without any swaps, the only index that can be $1$ is $x$. However, if we have a range that includes the current index $x$, we can swap any of the indices within that range with the current index. This means that the possible indices that can be $1$ expand based on the ranges provided.↵
↵
To solve this, we need to combine all the ranges. If the final combined range includes the index $x$, then all indices within that range can be set to $1$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
``` python3↵
t = int(input())↵
for _ in range(t):↵
n,k,m = list(map(int,input().split()))↵
start = k↵
end = k↵
↵
for i in range(m):↵
l,r = gns()↵
if l <= start <= r or l <= end <= r:↵
start = min(start,l)↵
end = max(end,r)↵
print(end - start + 1)↵
```↵
</spoiler>↵
↵
↵
#### [G. MEX Tree Labeling](https://codeforces.me/gym/544854/problem/C)↵
↵
<spoiler summary = "Solution">↵
Notice that there will be a path that passes through the edge labeled $0$ and the edge labeled $1$ no matter how you label the edges, so there's always a path with MEX $2$ or more. If any node has degree $3$ or more, you can distribute the labels $0$, $1$, and $2$ to edges incident to this node and distribute the rest of the labels arbitrarily. Otherwise, the tree is a bamboo, and it doesn't actually matter how you label the edges, since there will be a path with MEX $n−1$ anyway.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
from collections import defaultdict↵
↵
graph = defaultdict(list)↵
ans = {}↵
↵
n = int(sys.stdin.readline().strip())↵
↵
for i in range(1, n):↵
a, b = map(int, sys.stdin.readline().strip().split())↵
graph[a].append(i)↵
graph[b].append(i)↵
ans[i] = -1↵
↵
# Find the node with the maximum degree↵
mx = (0, 0)↵
for i in range(1, n + 1):↵
if len(graph[i]) > mx[0]:↵
mx = (len(graph[i]), i)↵
↵
cur = 0↵
for i in graph[mx[1]]:↵
ans[i] = cur↵
cur += 1↵
↵
for i in range(1, n):↵
if ans[i] == -1:↵
ans[i] = cur↵
cur += 1↵
print(ans[i])↵
```↵
</spoiler>↵
↵
↵
#### [H. Martian Maximum XOR](https://codeforces.me/gym/544854/problem/D)↵
↵
<spoiler summary="Solution">↵
<ul>↵
<li>↵
<b>Solution 1:</b> Let's use the data structure called a bitwise trie. Fix some $a_{i}$, where all $a_{j}$ for $j<i$ have already been added to the trie. We will iterate over the bits in $a_{i}$ from the $(k−1)^{th}$ bit to the $0^{th}$ bit. Since $2^{t}>2^{t−1}+2^{t−2}+…+2+1$, if there exists $a_{j}$ with the same bit at the corresponding position in $a_{i}$, we will go into that branch of the trie and append $1−b$ to the corresponding bit $x$. Otherwise, our path is uniquely determined. When we reach a leaf, the bits on the path will correspond to the optimal number $a_{j}$ for $a_{i}$. The time complexity of this solution is $O(nk)$.↵
</li>↵
<li>↵
<b>Solution 2:</b> Sort $a_{1},a_{2},…,a_{n}$ in non-decreasing order. We will prove that the answer is some pair of adjacent numbers. Let the answer be numbers $a_{i},a_{j} (j−i>1)$. If $a_{i}=a_{j}$, then $a_{i}=a_{i+1}$. Otherwise, they have a common prefix of bits, after which there is a differing bit. That is, at some position $t$, $a_{i}$ has a $0$ and $a_{j}$ has a $1$. Since $j−i>1$, $a{i+1}$ can have either $0$ or $1$ at this position, but in the first case it is more advantageous to choose $a_{i},a_{i+1}$ as the answer, and in the second case it is more advantageous to choose $a_{i+1},a_{j}$ as the answer. The complexity of this solution is $O(nlogn)$.↵
</li>↵
</ul>↵
</p>↵
↵
<p>↵
For the first approach, make sure to use $PyPy 3-64$.↵
</p>↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
class TrieNode:↵
def __init__(self):↵
self.children = [None, None]↵
self.position = -1 # index of the corresponding number in the given array↵
↵
t = int(input())↵
for _ in range(t):↵
n, k = map(int, input().split())↵
a = list(map(int, input().split()))↵
↵
ans_i = ans_j = ans_x = 1, 1, 0↵
max_val = 0 # maximum value of (a[i] ^ x) & (a[j] ^ x)↵
↵
root_node = TrieNode()↵
for i, num in enumerate(a):↵
cur_node = root_node↵
# find a pair a[j] for this number↵
# first check if there's at least one number in the trie↵
if cur_node.children[0] or cur_node.children[1]:↵
x = 0↵
for bit_i in range(k - 1, -1, -1):↵
if num & (1 << bit_i):↵
# match 1 bit with 1 bit↵
if cur_node.children[1]:↵
cur_node = cur_node.children[1]↵
else: # if not possible, match 1 bit with 0 bit↵
cur_node = cur_node.children[0]↵
↵
else:↵
# match 0 bit with 0 bit↵
if cur_node.children[0]:↵
cur_node = cur_node.children[0]↵
x = x ^ (1 << bit_i)↵
else: # if not possible, match 0 bit with 1 bit↵
cur_node = cur_node.children[1]↵
↵
j = cur_node.position↵
new_val = (num ^ x)&(a[j] ^ x)↵
if new_val >= max_val:↵
max_val = new_val↵
ans_i, ans_j, ans_x = i + 1, j + 1, x↵
↵
# insert the current number into the trie↵
cur_node = root_node↵
for bit_i in range(k - 1, -1, -1):↵
if num & (1 << bit_i):↵
if not cur_node.children[1]:↵
cur_node.children[1] = TrieNode()↵
cur_node = cur_node.children[1]↵
↵
else:↵
if not cur_node.children[0]:↵
cur_node.children[0] = TrieNode()↵
cur_node = cur_node.children[0]↵
↵
cur_node.position = i↵
↵
print(ans_i, ans_j, ans_x)↵
↵
↵
```↵
</spoiler>↵
↵
↵
#### [I. MST for Promptness](https://codeforces.me/gym/544854/problem/E)↵
↵
<spoiler summary="solution">↵
If we connect the graph using $0$-weighted edges only and we are left with $k$ components, we need $k - 1$ $1$-weighted edges.↵
↵
Let's keep track of the unconnected nodes in a set and every time we do a BFS starting from an unconnected node to a node that has no edge with it. We have to check if there is a node in unconnected nodes that is not a neighbor (considering $1$-weighted edge) of it. Every time we check if the node is the neighbor we pass it and if not we add it in the BFS queue. Worst case, the first case will only happen $m$ (the number of $1$-weighted edges) times and the second case will only happen $n$ times. The overall time complexity will be $O(n + m)$.↵
↵
</spoiler>↵
↵
<spoiler summary="code">↵
```python↵
from collections import defaultdict, deque↵
from sys import stdin↵
↵
↵
def input(): return stdin.readline().strip()↵
↵
N, M = map(int, input().split())↵
↵
adj = defaultdict(set)↵
for _ in range(M):↵
u, v = map(int, input().split())↵
u, v = u - 1, v - 1↵
adj[u].add(v)↵
adj[v].add(u)↵
↵
unconnected = set(range(N))↵
edges = 0↵
↵
for i in range(N):↵
if i in unconnected:↵
q = deque([i])↵
unconnected.remove(i)↵
while q:↵
v = q.popleft()↵
remove = []↵
for u in unconnected:↵
if v not in adj[u]:↵
edges += 1↵
remove.append(u)↵
q.append(u)↵
for u in remove:↵
unconnected.remove(u)↵
print(N - 1 - edges)↵
```↵
</spoiler>↵
↵
↵
