[Here](https://mirror.codeforces.com/contestInvitation/35507e5f76294d0824cd0c2b0d5d97bb434c813b) is the link to the contest. All problems are from Codeforces problemset.↵
↵
↵
#### [A. Memory and Crow](https://mirror.codeforces.com/gym/543431/problem/A)↵
↵
<spoiler summary="solution">↵
↵
We can re-write the formula as $b_i = a_i + (b_{i + 1} - b_{i + 2} + \dots)$. Then, we can reduce $(b_{i + 1} - b_{i + 2} + \dots)$ to $a_{i + 1}$. So, $b_i = a_i + a_{i + 1}$.↵
↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
```python↵
n = int(input())↵
arr = list(map(int, input().split()))↵
arr.append(0)↵
ans = [0] * (n + 1)↵
for i in range(n - 1, -1, -1):↵
ans[i] = arr[i] + arr[i + 1]↵
print(*ans[:n])↵
```↵
↵
</spoiler>↵
↵
#### [B. Diversity](https://mirror.codeforces.com/gym/543431/problem/B)↵
↵
<spoiler summary="solution">↵
↵
If $n$ is greater than 26 or the length of the word is less than $n$, it's impossible to reach $n$ distinct characters. Otherwise, we can count how many characters are left to reach $n$ distinct characters.↵
↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
```python↵
word = input()↵
n = int(input())↵
↵
if n > 26 or len(word) < n:↵
print("impossible")↵
else:↵
print(max(0, n - len(set(word))))↵
↵
```↵
↵
</spoiler>↵
↵
#### [C. Avoid Trygub](https://mirror.codeforces.com/gym/543431/problem/C)↵
↵
<spoiler summary = "Solution">↵
The solution to preventing "trygub" from being a subsequence involves disrupting the specific order of its characters. Since "trygub" requires the characters 't', 'r', 'y', 'g', 'u', and 'b' to appear in that precise sequence, the approach is to rearrange the string so that this order cannot be maintained. The simplest way to achieve this is by sorting the string, which effectively disturbs the positions and prevents the sequence from forming. However, a more efficient solution is to start the rearranged string with any character that is not 't' from "trygub." By beginning with a different character and appending the others afterward, we ensure that the required sequence is broken, thus preventing "trygub" from appearing as a subsequence. ↵
↵
Time complexity = $O(n)$.↵
Space complexity = $O(1)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
input = lambda: sys.stdin.readline().rstrip()↵
t = int(input())↵
↵
for _ in range(t):↵
N = int(input())↵
s = input()↵
ans = ["b"] * s.count("b")↵
↵
for char in s:↵
if char != "b":↵
ans.append(char)↵
↵
print("".join(ans))↵
↵
↵
```↵
</spoiler>↵
↵
#### [D. Decide Your Division](https://mirror.codeforces.com/gym/543431/problem/D)↵
↵
<spoiler summary = "Solution">↵
What if the given number $n$ cannot be represented as $2^{cnt2}⋅3^{cnt3}⋅5^{cnt5}$? It means that the answer is $-1$ because all actions we can do are: remove one power of two, remove one power of three and add one power of two, and remove one power of five and add two powers of two. So if the answer is not $-1$ then it is $cnt2+2.cnt3+3.cnt5$. If this formula isn't pretty clear for you, you can just simulate the process, performing actions from third to first.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
t = int(sys.stdin.readline().strip())↵
↵
for _ in range(t):↵
↵
n = int(sys.stdin.readline().strip())↵
cnt2, cnt3, cnt5 = 0, 0, 0↵
↵
while n % 2 == 0:↵
n //= 2↵
cnt2 += 1↵
↵
while n % 3 == 0:↵
n //= 3↵
cnt3 += 1↵
↵
while n % 5 == 0:↵
n //= 5↵
cnt5 += 1↵
↵
if n != 1:↵
print(-1)↵
else:↵
print(cnt2 + 2 * cnt3 + 3 * cnt5)↵
```↵
</spoiler>↵
↵
#### [E. Word Transformation](https://mirror.codeforces.com/gym/543431/problem/E)↵
↵
<spoiler summary = "Solution">↵
This problem can be solved in a straightforward way. The key observation is that the order in which the letters are called out does not matter in this game. We only need to know how many times each letter is called out in order to go from the initial word $s$ to the final word $t$.↵
↵
So first, let us compute the number of occurrences of each letter from 'A' to 'Z' in both words $s$ and $t$. Let’s call them $s_a$ and $t_a$ for each letter $a$. Using these numbers, we can calculate how many times each letter shall be called in order to get a chance of getting to $t$. That is $s_a − t_a$ times for each letter $a$.↵
↵
If $s_a − t_a < 0$ for any letter $a$, then the answer is 'NO'. Otherwise, there is a chance for a positive answer. However, we also need to verify that the order of the letters in $t$ is correct. The easy way to verify it is to simulate the game, dropping the first $s_a − t_a$ occurrences of each letter $a$, and then compare the result with $t$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import Counter↵
from sys import stdin↵
↵
↵
def input(): return stdin.readline().strip()↵
↵
T = int(input())↵
↵
for _ in range(T):↵
s, t = input().split()↵
s_cnt = Counter(s)↵
t_cnt = Counter(t)↵
↵
remove_cnt = {}↵
ok = True↵
for ch in s_cnt:↵
remove_cnt[ch] = s_cnt[ch] - t_cnt[ch]↵
if remove_cnt[ch] < 0:↵
ok = False↵
↵
if not ok:↵
print("NO")↵
continue↵
↵
new_s = []↵
for ch in s:↵
if remove_cnt[ch] > 0:↵
remove_cnt[ch] -= 1↵
else:↵
new_s.append(ch)↵
↵
if "".join(new_s) == t:↵
print("YES")↵
else:↵
print("NO")↵
```↵
</spoiler>↵
↵
↵
#### [F. OR Encryption](https://mirror.codeforces.com/gym/543431/problem/F)↵
↵
<spoiler summary = "Hint">↵
Think of each bit independently.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
Solution:↵
↵
Initially, we set all $a_i=2^{30}−1$ (all bits on).↵
↵
You can go through every $i$,$j$ such that $i≠j$ and do $a_i$ &= $M_{i,j}$ and $a_j$ &= $M_{i,j}$.↵
↵
Then we check if $M_{i,j}=a_i|a_j$ for all pairs. If this holds you found the array else the answer is $NO$.↵
↵
Proof:↵
↵
Initially, all elements have all their bits set on and we remove only the bits that affect our answer. If $M_{i,j}$ doesn't have a specific bit then definitely neither $a_i$ nor $a_j$ should have it. If $M_{i,j}$ has a specific bit on then we don't have to remove anything (in the end we want at least one of $a_i$ and $a_j$ to have the bit on).↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
↵
def solve():↵
n = int(sys.stdin.readline().strip())↵
matrix = []↵
↵
for _ in range(n):↵
row = list(map(int, sys.stdin.readline().strip().split()))↵
matrix.append(row)↵
↵
a = [2**30 - 1] * n↵
↵
for i in range(n):↵
for j in range(n):↵
if i != j:↵
a[i] &= matrix[i][j]↵
a[j] &= matrix[i][j]↵
↵
for i in range(n):↵
for j in range(n):↵
if i != j and a[i] | a[j] != matrix[i][j]:↵
print("NO")↵
return↵
↵
print("YES")↵
print(*a)↵
↵
t = int(sys.stdin.readline().strip())↵
↵
for _ in range(t):↵
solve()↵
```↵
</spoiler>↵
↵
#### [G. Small Town](https://mirror.codeforces.com/gym/543431/problem/G)↵
↵
<spoiler summary = "Solution">↵
↵
To solve this problem, we use binary search on the minimum possible maximum waiting time, denoted as `x`.↵
↵
**A. Binary Search on `x`**: Perform a binary search to find the smallest `x` such that all customers can be assigned to three or fewer carvers with each having a maximum waiting time of `x`.↵
↵
**B. Sorting**: First, sort the array of customers' pattern requests to facilitate efficient grouping.↵
↵
**C. Assigning Carvers**: ↵
Start assigning customers to carvers from the beginning of the sorted list.↵
For each carver, choose a range `[l, r]` of customers and set the optimal pattern as `(r + l) // 2` to minimize the maximum waiting time.↵
If the difference between this average pattern and the range limits exceeds `x`, start a new range for the next carver.↵
Continue until all customers are assigned or more than three carvers are needed.↵
↵
**D. Adjust `x`**: ↵
If three or fewer carvers suffice, reduce `x` to find a smaller maximum waiting time.↵
If more than three carvers are needed, increase `x` and retry.↵
↵
## Time Complexity↵
↵
The time complexity is `O(n * log(m))`, where `n` is the number of customers, and `m` is the difference between the maximum and minimum possible waiting times.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
``` python3↵
def solve():↵
n = int(input())↵
nums = list(map(int, input().split()))↵
nums.sort()↵
↵
def is_valid_waiting_time(waiting_time):↵
start = nums[0]↵
count = 1↵
↵
for i in range(1, n):↵
if (nums[i] - start + 1) // 2 > waiting_time:↵
count += 1↵
start = nums[i]↵
↵
return count <= 3↵
↵
l = 0↵
r = max(nums)↵
↵
while l <= r:↵
mid = (l + r) // 2↵
if is_valid_waiting_time(mid):↵
r = mid - 1↵
else:↵
l = mid + 1↵
↵
print(l)↵
↵
t = int(input())↵
for _ in range(t):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [H. Tell Directions](https://mirror.codeforces.com/gym/543431/problem/H)↵
↵
<spoiler summary="Solution">↵
First, check the parity of $k$. If $k$ is odd, there is no solution because the cycle described in the task must have an even length. Otherwise, proceed as follows:↵
Use the breadth-first search (BFS) algorithm to find the shortest distance from the starting cell to all other free cells.↵
Next, move through the grid. Before each move, determine the next cell to go to. Consider the directions in the order $( "D", "L", "R", "U")$. The current direction is $c$. If the cell $x$ corresponding to a move in direction $c$ is empty and the distance from it to the starting cell does not exceed the remaining number of steps, then move in direction $c$, add the corresponding letter to the answer, and proceed to the next step.↵
If at any step it is impossible to move the Robot, a cycle of length $k$ does not exist. Otherwise, once the Robot has completed $k$ steps, simply print the answer.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
from collections import deque↵
↵
n, m, k = map(int, input().split())↵
if k % 2:↵
print("IMPOSSIBLE")↵
exit(0)↵
↵
maze = []↵
direc = { (1, 0): 'D', (0, -1): 'L', (0, 1): 'R', (-1, 0): 'U' }↵
src = None ↵
for i in range(n):↵
maze.append(input())↵
for j in range(m):↵
if maze[i][j] == 'X':↵
src = (i, j)↵
break↵
↵
#bfs↵
track = [[float('inf') for _ in range(m)] for _ in range(n)]↵
track[src[0]][src[1]] = 0↵
queue = deque([(src, 0)])↵
visited = set([src])↵
while queue:↵
loc, step = queue.popleft()↵
for dx, dy in direc:↵
x, y = loc[0] + dx, loc[1] + dy↵
if 0 <= x < n and 0 <= y < m and maze[x][y] != '*' and (x, y) not in visited:↵
track[x][y] = min(track[x][y], step + 1)↵
queue.append(((x, y), step + 1))↵
visited.add((x, y))↵
↵
#dfs↵
stack = [src]↵
ans = []↵
while stack:↵
loc = stack.pop()↵
if len(ans) == k:↵
print("".join(ans))↵
exit(0)↵
for dx, dy in direc:↵
x, y = loc[0] + dx, loc[1] + dy↵
if 0 <= x < n and 0 <= y < m and track[x][y] <= k — len(ans):↵
ans.append(direc[(dx, dy)])↵
stack.append((x, y))↵
break↵
↵
print("IMPOSSIBLE")↵
↵
↵
```↵
</spoiler>↵
↵
↵
#### [I. Yet Another Pair Counting](https://mirror.codeforces.com/gym/543431/problem/I)↵
↵
<spoiler summary="Hint">↵
Since it is counting pairs, we can use divide and conquer approach.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
<p> ↵
Let's assume we have divided the original string in half, getting $substring1$ and $substring2$. Let's have a segment $(l, r)$↵
to be inverted where $l$ lies in $substring1$ and $r$ lies in $substring2$. We can now invert some suffix of $substring1$ and invert some prefix of $substring2$ and try to balance the brackets. ↵
</p>↵
<p>↵
There is one fact to create a balanced sequence. Because the original string is balanced:↵
</p>↵
<ul>↵
<li>↵
For $substring1$: All the closing brackets must have opening pairs. And, there could be zero or more unbalanced opening brackets.↵
</li>↵
<li>↵
For $substring2$: All the opening brackets must have closing pairs. And, there could be zero or more unbalanced closing brackets.↵
</li>↵
</ul>↵
<p>↵
For instance, after some inversion, if we have $Y$ amount opening brackets that didn't get a ↵
closing match in the fist substring, we should find $Y$ amount of excess closing brackets in the second substring. ↵
</p>↵
<p>↵
Now, with the same logic we can further divide the two substrings, and account for every $(l, r)$ pair.↵
</p>↵
<p>↵
Let's divide $substring1$ into halves, $a$ and $b$. After some $(l, r)$ inversion, where $l$ lies in $a$ and $r$ lies in $b$, let's say we have $X$ amount of excess opening brackets in $a$, the $X$ closing matches could come from not just $b$, but the whole suffix starting from and including $b$. The same applies if we have some subsegment before $a$. So, to handle that case, we do some preprocessing and count excess prefix openings and excess suffix closings. ↵
</p>↵
↵
<p>↵
Time complexity: $nlog(n)$ <br/>↵
Make sure to use $PyPy 3-64$.↵
</p>↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
↵
import sys↵
from collections import defaultdict↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
def conquer(l1, r1, l2, r2):↵
↵
excess_opening = defaultdict(int)↵
inverted_open = 0↵
unpaired_closing = 0↵
# all closing brackets must have an opening pair on the left subarray↵
# invert some suffix of substring 1↵
for indx in range(r1, l1 - 1, -1):↵
if s[indx] == ')':↵
inverted_open += 1↵
# follow kadan's algorithm to find opening matches for the closings↵
# if we have an excess opening, it is no use for a closing that comes before it↵
# so we don't make the unpaired_closing negative↵
unpaired_closing = max(unpaired_closing - 1, 0) ↵
↵
else:↵
unpaired_closing += 1↵
inverted_open -= 1↵
↵
# uninverted prefix of this index must provide opening pairs for the unpaired closings↵
if pref[indx - 1] >= unpaired_closing:↵
excess_opening[pref[indx - 1] + inverted_open] += 1↵
↵
↵
unpaired_opening = 0↵
inverted_close = 0↵
count = 0 # (l, r) matches ↵
↵
# invert some prefix of substring 2↵
for indx in range(l2, r2 + 1):↵
if s[indx] == '(':↵
inverted_close += 1↵
unpaired_opening = max(unpaired_opening - 1, 0)↵
↵
else:↵
unpaired_opening += 1↵
inverted_close -= 1↵
↵
# uninverted suffix of this index must provide closing pairs for the unpaired openings↵
if suf[indx + 1] >= unpaired_opening:↵
# match 'y' amount of excess opening in the first substring↵
# with 'y' amount of closing in the second substring↵
count += excess_opening[suf[indx + 1] + inverted_close]↵
↵
return count↵
↵
def divide(l, r):↵
if l >= r:↵
return 0↵
↵
mid = (r + l)//2↵
left_count = divide(l, mid)↵
right_count = divide(mid + 1, r)↵
cur_count = conquer(l, mid, mid + 1, r)↵
return left_count + right_count + cur_count↵
↵
t = int(input())↵
for _ in range(t):↵
s = input()↵
n = len(s)↵
↵
pref = [0]*(n + 1)↵
suf = [0]*(n + 1)↵
↵
openning_pref = 0↵
closing_suf = 0↵
for i in range(n):↵
openning_pref += 1 if s[i] == '(' else -1↵
closing_suf += 1 if s[n - i - 1] == ')' else -1↵
↵
pref[i] = openning_pref↵
suf[n - i - 1] = closing_suf↵
↵
ans = divide(0, n - 1)↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [A. Memory and Crow](https://mirror.codeforces.com/gym/543431/problem/A)↵
↵
<spoiler summary="solution">↵
↵
We can re-write the formula as $b_i = a_i + (b_{i + 1} - b_{i + 2} + \dots)$. Then, we can reduce $(b_{i + 1} - b_{i + 2} + \dots)$ to $a_{i + 1}$. So, $b_i = a_i + a_{i + 1}$.↵
↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
```python↵
n = int(input())↵
arr = list(map(int, input().split()))↵
arr.append(0)↵
ans = [0] * (n + 1)↵
for i in range(n - 1, -1, -1):↵
ans[i] = arr[i] + arr[i + 1]↵
print(*ans[:n])↵
```↵
↵
</spoiler>↵
↵
#### [B. Diversity](https://mirror.codeforces.com/gym/543431/problem/B)↵
↵
<spoiler summary="solution">↵
↵
If $n$ is greater than 26 or the length of the word is less than $n$, it's impossible to reach $n$ distinct characters. Otherwise, we can count how many characters are left to reach $n$ distinct characters.↵
↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
```python↵
word = input()↵
n = int(input())↵
↵
if n > 26 or len(word) < n:↵
print("impossible")↵
else:↵
print(max(0, n - len(set(word))))↵
↵
```↵
↵
</spoiler>↵
↵
#### [C. Avoid Trygub](https://mirror.codeforces.com/gym/543431/problem/C)↵
↵
<spoiler summary = "Solution">↵
The solution to preventing "trygub" from being a subsequence involves disrupting the specific order of its characters. Since "trygub" requires the characters 't', 'r', 'y', 'g', 'u', and 'b' to appear in that precise sequence, the approach is to rearrange the string so that this order cannot be maintained. The simplest way to achieve this is by sorting the string, which effectively disturbs the positions and prevents the sequence from forming. However, a more efficient solution is to start the rearranged string with any character that is not 't' from "trygub." By beginning with a different character and appending the others afterward, we ensure that the required sequence is broken, thus preventing "trygub" from appearing as a subsequence. ↵
↵
Time complexity = $O(n)$.↵
Space complexity = $O(1)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
input = lambda: sys.stdin.readline().rstrip()↵
t = int(input())↵
↵
for _ in range(t):↵
N = int(input())↵
s = input()↵
ans = ["b"] * s.count("b")↵
↵
for char in s:↵
if char != "b":↵
ans.append(char)↵
↵
print("".join(ans))↵
↵
↵
```↵
</spoiler>↵
↵
#### [D. Decide Your Division](https://mirror.codeforces.com/gym/543431/problem/D)↵
↵
<spoiler summary = "Solution">↵
What if the given number $n$ cannot be represented as $2^{cnt2}⋅3^{cnt3}⋅5^{cnt5}$? It means that the answer is $-1$ because all actions we can do are: remove one power of two, remove one power of three and add one power of two, and remove one power of five and add two powers of two. So if the answer is not $-1$ then it is $cnt2+2.cnt3+3.cnt5$. If this formula isn't pretty clear for you, you can just simulate the process, performing actions from third to first.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
t = int(sys.stdin.readline().strip())↵
↵
for _ in range(t):↵
↵
n = int(sys.stdin.readline().strip())↵
cnt2, cnt3, cnt5 = 0, 0, 0↵
↵
while n % 2 == 0:↵
n //= 2↵
cnt2 += 1↵
↵
while n % 3 == 0:↵
n //= 3↵
cnt3 += 1↵
↵
while n % 5 == 0:↵
n //= 5↵
cnt5 += 1↵
↵
if n != 1:↵
print(-1)↵
else:↵
print(cnt2 + 2 * cnt3 + 3 * cnt5)↵
```↵
</spoiler>↵
↵
#### [E. Word Transformation](https://mirror.codeforces.com/gym/543431/problem/E)↵
↵
<spoiler summary = "Solution">↵
This problem can be solved in a straightforward way. The key observation is that the order in which the letters are called out does not matter in this game. We only need to know how many times each letter is called out in order to go from the initial word $s$ to the final word $t$.↵
↵
So first, let us compute the number of occurrences of each letter from 'A' to 'Z' in both words $s$ and $t$. Let’s call them $s_a$ and $t_a$ for each letter $a$. Using these numbers, we can calculate how many times each letter shall be called in order to get a chance of getting to $t$. That is $s_a − t_a$ times for each letter $a$.↵
↵
If $s_a − t_a < 0$ for any letter $a$, then the answer is 'NO'. Otherwise, there is a chance for a positive answer. However, we also need to verify that the order of the letters in $t$ is correct. The easy way to verify it is to simulate the game, dropping the first $s_a − t_a$ occurrences of each letter $a$, and then compare the result with $t$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import Counter↵
from sys import stdin↵
↵
↵
def input(): return stdin.readline().strip()↵
↵
T = int(input())↵
↵
for _ in range(T):↵
s, t = input().split()↵
s_cnt = Counter(s)↵
t_cnt = Counter(t)↵
↵
remove_cnt = {}↵
ok = True↵
for ch in s_cnt:↵
remove_cnt[ch] = s_cnt[ch] - t_cnt[ch]↵
if remove_cnt[ch] < 0:↵
ok = False↵
↵
if not ok:↵
print("NO")↵
continue↵
↵
new_s = []↵
for ch in s:↵
if remove_cnt[ch] > 0:↵
remove_cnt[ch] -= 1↵
else:↵
new_s.append(ch)↵
↵
if "".join(new_s) == t:↵
print("YES")↵
else:↵
print("NO")↵
```↵
</spoiler>↵
↵
↵
#### [F. OR Encryption](https://mirror.codeforces.com/gym/543431/problem/F)↵
↵
<spoiler summary = "Hint">↵
Think of each bit independently.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
Solution:↵
↵
Initially, we set all $a_i=2^{30}−1$ (all bits on).↵
↵
You can go through every $i$,$j$ such that $i≠j$ and do $a_i$ &= $M_{i,j}$ and $a_j$ &= $M_{i,j}$.↵
↵
Then we check if $M_{i,j}=a_i|a_j$ for all pairs. If this holds you found the array else the answer is $NO$.↵
↵
Proof:↵
↵
Initially, all elements have all their bits set on and we remove only the bits that affect our answer. If $M_{i,j}$ doesn't have a specific bit then definitely neither $a_i$ nor $a_j$ should have it. If $M_{i,j}$ has a specific bit on then we don't have to remove anything (in the end we want at least one of $a_i$ and $a_j$ to have the bit on).↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
↵
def solve():↵
n = int(sys.stdin.readline().strip())↵
matrix = []↵
↵
for _ in range(n):↵
row = list(map(int, sys.stdin.readline().strip().split()))↵
matrix.append(row)↵
↵
a = [2**30 - 1] * n↵
↵
for i in range(n):↵
for j in range(n):↵
if i != j:↵
a[i] &= matrix[i][j]↵
a[j] &= matrix[i][j]↵
↵
for i in range(n):↵
for j in range(n):↵
if i != j and a[i] | a[j] != matrix[i][j]:↵
print("NO")↵
return↵
↵
print("YES")↵
print(*a)↵
↵
t = int(sys.stdin.readline().strip())↵
↵
for _ in range(t):↵
solve()↵
```↵
</spoiler>↵
↵
#### [G. Small Town](https://mirror.codeforces.com/gym/543431/problem/G)↵
↵
<spoiler summary = "Solution">↵
↵
To solve this problem, we use binary search on the minimum possible maximum waiting time, denoted as `x`.↵
↵
**A. Binary Search on `x`**: Perform a binary search to find the smallest `x` such that all customers can be assigned to three or fewer carvers with each having a maximum waiting time of `x`.↵
↵
**B. Sorting**: First, sort the array of customers' pattern requests to facilitate efficient grouping.↵
↵
**C. Assigning Carvers**: ↵
Start assigning customers to carvers from the beginning of the sorted list.↵
For each carver, choose a range `[l, r]` of customers and set the optimal pattern as `(r + l) // 2` to minimize the maximum waiting time.↵
If the difference between this average pattern and the range limits exceeds `x`, start a new range for the next carver.↵
Continue until all customers are assigned or more than three carvers are needed.↵
↵
**D. Adjust `x`**: ↵
If three or fewer carvers suffice, reduce `x` to find a smaller maximum waiting time.↵
If more than three carvers are needed, increase `x` and retry.↵
↵
## Time Complexity↵
↵
The time complexity is `O(n * log(m))`, where `n` is the number of customers, and `m` is the difference between the maximum and minimum possible waiting times.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
``` python3↵
def solve():↵
n = int(input())↵
nums = list(map(int, input().split()))↵
nums.sort()↵
↵
def is_valid_waiting_time(waiting_time):↵
start = nums[0]↵
count = 1↵
↵
for i in range(1, n):↵
if (nums[i] - start + 1) // 2 > waiting_time:↵
count += 1↵
start = nums[i]↵
↵
return count <= 3↵
↵
l = 0↵
r = max(nums)↵
↵
while l <= r:↵
mid = (l + r) // 2↵
if is_valid_waiting_time(mid):↵
r = mid - 1↵
else:↵
l = mid + 1↵
↵
print(l)↵
↵
t = int(input())↵
for _ in range(t):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [H. Tell Directions](https://mirror.codeforces.com/gym/543431/problem/H)↵
↵
<spoiler summary="Solution">↵
First, check the parity of $k$. If $k$ is odd, there is no solution because the cycle described in the task must have an even length. Otherwise, proceed as follows:↵
Use the breadth-first search (BFS) algorithm to find the shortest distance from the starting cell to all other free cells.↵
Next, move through the grid. Before each move, determine the next cell to go to. Consider the directions in the order $( "D", "L", "R", "U")$. The current direction is $c$. If the cell $x$ corresponding to a move in direction $c$ is empty and the distance from it to the starting cell does not exceed the remaining number of steps, then move in direction $c$, add the corresponding letter to the answer, and proceed to the next step.↵
If at any step it is impossible to move the Robot, a cycle of length $k$ does not exist. Otherwise, once the Robot has completed $k$ steps, simply print the answer.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
from collections import deque↵
↵
n, m, k = map(int, input().split())↵
if k % 2:↵
print("IMPOSSIBLE")↵
exit(0)↵
↵
maze = []↵
direc = { (1, 0): 'D', (0, -1): 'L', (0, 1): 'R', (-1, 0): 'U' }↵
src = None ↵
for i in range(n):↵
maze.append(input())↵
for j in range(m):↵
if maze[i][j] == 'X':↵
src = (i, j)↵
break↵
↵
#bfs↵
track = [[float('inf') for _ in range(m)] for _ in range(n)]↵
track[src[0]][src[1]] = 0↵
queue = deque([(src, 0)])↵
visited = set([src])↵
while queue:↵
loc, step = queue.popleft()↵
for dx, dy in direc:↵
x, y = loc[0] + dx, loc[1] + dy↵
if 0 <= x < n and 0 <= y < m and maze[x][y] != '*' and (x, y) not in visited:↵
track[x][y] = min(track[x][y], step + 1)↵
queue.append(((x, y), step + 1))↵
visited.add((x, y))↵
↵
#dfs↵
stack = [src]↵
ans = []↵
while stack:↵
loc = stack.pop()↵
if len(ans) == k:↵
print("".join(ans))↵
exit(0)↵
for dx, dy in direc:↵
x, y = loc[0] + dx, loc[1] + dy↵
if 0 <= x < n and 0 <= y < m and track[x][y] <= k — len(ans):↵
ans.append(direc[(dx, dy)])↵
stack.append((x, y))↵
break↵
↵
print("IMPOSSIBLE")↵
↵
↵
```↵
</spoiler>↵
↵
↵
#### [I. Yet Another Pair Counting](https://mirror.codeforces.com/gym/543431/problem/I)↵
↵
<spoiler summary="Hint">↵
Since it is counting pairs, we can use divide and conquer approach.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
<p> ↵
Let's assume we have divided the original string in half, getting $substring1$ and $substring2$. Let's have a segment $(l, r)$↵
to be inverted where $l$ lies in $substring1$ and $r$ lies in $substring2$. We can now invert some suffix of $substring1$ and invert some prefix of $substring2$ and try to balance the brackets. ↵
</p>↵
<p>↵
There is one fact to create a balanced sequence. Because the original string is balanced:↵
</p>↵
<ul>↵
<li>↵
For $substring1$: All the closing brackets must have opening pairs. And, there could be zero or more unbalanced opening brackets.↵
</li>↵
<li>↵
For $substring2$: All the opening brackets must have closing pairs. And, there could be zero or more unbalanced closing brackets.↵
</li>↵
</ul>↵
<p>↵
For instance, after some inversion, if we have $Y$ amount opening brackets that didn't get a ↵
closing match in the fist substring, we should find $Y$ amount of excess closing brackets in the second substring. ↵
</p>↵
<p>↵
Now, with the same logic we can further divide the two substrings, and account for every $(l, r)$ pair.↵
</p>↵
<p>↵
Let's divide $substring1$ into halves, $a$ and $b$. After some $(l, r)$ inversion, where $l$ lies in $a$ and $r$ lies in $b$, let's say we have $X$ amount of excess opening brackets in $a$, the $X$ closing matches could come from not just $b$, but the whole suffix starting from and including $b$. The same applies if we have some subsegment before $a$. So, to handle that case, we do some preprocessing and count excess prefix openings and excess suffix closings. ↵
</p>↵
↵
<p>↵
Time complexity: $nlog(n)$ <br/>↵
Make sure to use $PyPy 3-64$.↵
</p>↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
↵
import sys↵
from collections import defaultdict↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
def conquer(l1, r1, l2, r2):↵
↵
excess_opening = defaultdict(int)↵
inverted_open = 0↵
unpaired_closing = 0↵
# all closing brackets must have an opening pair on the left subarray↵
# invert some suffix of substring 1↵
for indx in range(r1, l1 - 1, -1):↵
if s[indx] == ')':↵
inverted_open += 1↵
# follow kadan's algorithm to find opening matches for the closings↵
# if we have an excess opening, it is no use for a closing that comes before it↵
# so we don't make the unpaired_closing negative↵
unpaired_closing = max(unpaired_closing - 1, 0) ↵
↵
else:↵
unpaired_closing += 1↵
inverted_open -= 1↵
↵
# uninverted prefix of this index must provide opening pairs for the unpaired closings↵
if pref[indx - 1] >= unpaired_closing:↵
excess_opening[pref[indx - 1] + inverted_open] += 1↵
↵
↵
unpaired_opening = 0↵
inverted_close = 0↵
count = 0 # (l, r) matches ↵
↵
# invert some prefix of substring 2↵
for indx in range(l2, r2 + 1):↵
if s[indx] == '(':↵
inverted_close += 1↵
unpaired_opening = max(unpaired_opening - 1, 0)↵
↵
else:↵
unpaired_opening += 1↵
inverted_close -= 1↵
↵
# uninverted suffix of this index must provide closing pairs for the unpaired openings↵
if suf[indx + 1] >= unpaired_opening:↵
# match 'y' amount of excess opening in the first substring↵
# with 'y' amount of closing in the second substring↵
count += excess_opening[suf[indx + 1] + inverted_close]↵
↵
return count↵
↵
def divide(l, r):↵
if l >= r:↵
return 0↵
↵
mid = (r + l)//2↵
left_count = divide(l, mid)↵
right_count = divide(mid + 1, r)↵
cur_count = conquer(l, mid, mid + 1, r)↵
return left_count + right_count + cur_count↵
↵
t = int(input())↵
for _ in range(t):↵
s = input()↵
n = len(s)↵
↵
pref = [0]*(n + 1)↵
suf = [0]*(n + 1)↵
↵
openning_pref = 0↵
closing_suf = 0↵
for i in range(n):↵
openning_pref += 1 if s[i] == '(' else -1↵
closing_suf += 1 if s[n - i - 1] == ')' else -1↵
↵
pref[i] = openning_pref↵
suf[n - i - 1] = closing_suf↵
↵
ans = divide(0, n - 1)↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
↵
↵
