Here is the link to the contest. All problems are from Codeforces problemset.
A. Memory and Crow
B. Diversity
C. Avoid Trygub
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))
#### [D. Decide Your Division](https://codeforces.net/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">
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://codeforces.net/gym/543431/problem/E)
#### [F. OR Encryption](https://codeforces.net/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">
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() ```
G. Small Town
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.
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://codeforces.net/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">
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://codeforces.net/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 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">
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 countdef 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)```
