[Here](https://mirror.codeforces.com/contestInvitation/bd2ec5f38eb60d210302662eaf22551ca641423d) is the link to the contest (4 of the problems are from Codeforces problemset).↵
↵
#### [A. Balanced Alphabet](https://mirror.codeforces.com/gym/520390/problem/A)↵
↵
↵
<spoiler summary = "Solution">↵
To maximize the minimum frequency of a character, it's best to equalize the frequencies of each character as much as possible. So, each set of $k$ characters should have a frequency of at least $n$ // $k$. Then, we can distribute the remaining $n$ % $k$ characters however we want among those $k$ characters.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
``` python3↵
t = int(input())↵
for _ in range(t):↵
n,k = input()↵
↵
numbers = n // k↵
↵
remaining = n % k↵
↵
ans = ""↵
↵
for i in range(k):↵
ans += chr(i + ord("a")) * numbers↵
ans += "a" * remaining↵
print(ans)↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [B. Chat](https://mirror.codeforces.com/gym/520390/problem/B)↵
↵
<spoiler summary="Solution">↵
We can easily add a friend to the display system when that friend goes online. When there is a query to check if a friend can be displayed by the system, we need to remove friends with the lowest goodness values until the size of the online friends list is less than or equal to $k$. The answer will be $YES$ if the friend exists in the displayed system. If the friend is not currently in the display system, either because they were never added or because they were removed from the list, the answer will be $NO$.↵
↵
↵
Time Complexity: $(O(q * log(n)))$ where $q$ is number of queries and $n$ is number of friends↵
Space Complexity: $O(n)$↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
↵
from heapq import heappop, heappush↵
from collections import defaultdict↵
↵
def main():↵
n, k, q = map(int, input().split())↵
friendship = list(map(int, input().split()))↵
hashMap = defaultdict(int)↵
heap = []↵
↵
for _ in range(q):↵
type, friend = map(int, input().split())↵
if type == 1:↵
hashMap[friend] = 2↵
heappush(heap, (friendship[friend - 1], friend))↵
else:↵
if hashMap[friend]:↵
while len(heap) > k:↵
weight, f = heappop(heap)↵
hashMap[f] = 1 ↵
if hashMap[friend] == 2:↵
print('YES') ↵
else:↵
print('NO')↵
↵
if __name__ == '__main__':↵
main()↵
↵
↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [C. Poker](https://mirror.codeforces.com/gym/520390/problem/C)↵
↵
<spoiler summary = "Hint">↵
The order in which they will be applied is not important.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
To solve it, it should be noted that despite the way the deck with bonuses works, the order in which they will be applied is not important. Then, when we meet the hero card, we just need to add to the answer the maximum of the available bonuses.↵
↵
Constraints make you use data structures such as $heap$ to quickly find and extract the maximum.↵
↵
Total complexity: $O(nlogn)$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
from heapq import heappush, heappop↵
↵
t = int(sys.stdin.readline().strip())↵
↵
for _ in range(t):↵
↵
n = int(sys.stdin.readline().strip())↵
nums = list(map(int, sys.stdin.readline().strip().split()))↵
my_heap = []↵
ans = 0↵
for num in nums:↵
if num:↵
heappush(my_heap, -1 * num)↵
else:↵
if my_heap:↵
ans +=( heappop(my_heap) * -1)↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [D. Restricted Permutation](https://mirror.codeforces.com/gym/520390/problem/D)↵
↵
<spoiler summary="Solution">↵
Consider an $N$-vertex directed graph where for each $i$ $(1 \leq i \leq M)$, there is an edge from vertex $a_i$ to vertex $b_i$.↵
The goal is to find the lexicographically smallest sequence of topologically sorted vertices.↵
↵
Topological sorting can be applied to the directed graph we have built.↵
By choosing the vertex with the smallest index and indegree 0 at each step, we obtain the lexicographically smallest sequence $S$.↵
↵
To choose the vertex with the smallest index and indegree, we can use a heap data structure.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
↵
import heapq↵
↵
N, M = map(int, input().split())↵
indeg = [0] * N↵
out = [[] for _ in range(N)]↵
for _ in range(M):↵
a, b = map(int, input().split())↵
a -= 1↵
b -= 1↵
indeg[b] += 1↵
out[a].append(b)↵
↵
heap = []↵
for i in range(N):↵
if indeg[i] == 0:↵
heapq.heappush(heap, i)↵
↵
ans = []↵
while heap:↵
i = heapq.heappop(heap)↵
ans.append(i)↵
for j in out[i]:↵
indeg[j] -= 1↵
if indeg[j] == 0:↵
heapq.heappush(heap, j)↵
↵
if len(ans) != N:↵
print(-1)↵
else:↵
print(*[x + 1 for x in ans])↵
```↵
</spoiler>↵
↵
↵
#### [E. Seamless Flow](https://mirror.codeforces.com/gym/520390/problem/E)↵
↵
<spoiler summary="Hint 1">↵
<p>When do we print $NO$?</p>↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
<p>If we can't form a valid topological order of the vertices by using only the directed edges, the answer is $NO$.</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
<p>↵
If the graph consisting of the vertices and only directed edges contains at least one cycle then the answer is $NO$. In other words, If we can’t form a valid topological order of the vertices with just the directed edges, we print $NO$.↵
</p>↵
<p> ↵
Let’s now have the topological sort of the graph without undirected edges. For each pair of vertices $X, Y$ in the undirected edges, if $X$ comes before $Y$ in the topological order, we direct the edge from $X$ to $Y$, otherwise we direct it from $Y$ to $X$.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
from collections import deque, defaultdict↵
↵
↵
def topSort(graph, indegree):↵
queue = deque()↵
↵
for node in range(n):↵
if not indegree[node]:↵
queue.append(node)↵
↵
top_order = []↵
↵
while queue:↵
cur = queue.popleft()↵
top_order.append(cur)↵
↵
for neigh in graph[cur]:↵
indegree[neigh] -= 1↵
↵
if not indegree[neigh]:↵
queue.append(neigh)↵
↵
return top_order↵
↵
↵
t = int(input())↵
↵
for _ in range(t):↵
n, m = map(int, input().split())↵
↵
directed = []↵
undirected = []↵
↵
for i in range(m):↵
direction, x, y = map(int, input().split())↵
↵
x -= 1 # let's make it zero indexed↵
y -= 1↵
↵
if direction:↵
directed.append((x, y))↵
↵
else:↵
undirected.append((x, y))↵
↵
↵
graph = [[] for node in range(n)]↵
indegree = defaultdict(int)↵
↵
for x, y in directed:↵
graph[x].append(y)↵
indegree[y] += 1↵
↵
↵
order= topSort(graph, indegree)↵
↵
if len(order) < n:↵
print("NO")↵
↵
else:↵
# compute the index of each node in the topological order↵
temp = {node: idx for idx, node in enumerate(order)}↵
↵
↵
print('YES')↵
for x, y in undirected:↵
if temp[x] < temp[y]:↵
print(x + 1, y + 1)↵
↵
else:↵
print(y + 1, x + 1)↵
↵
for x, y in directed:↵
print(x + 1, y + 1)↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [A. Balanced Alphabet](https://mirror.codeforces.com/gym/520390/problem/A)↵
↵
↵
<spoiler summary = "Solution">↵
To maximize the minimum frequency of a character, it's best to equalize the frequencies of each character as much as possible. So, each set of $k$ characters should have a frequency of at least $n$ // $k$. Then, we can distribute the remaining $n$ % $k$ characters however we want among those $k$ characters.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
``` python3↵
t = int(input())↵
for _ in range(t):↵
n,k = input()↵
↵
numbers = n // k↵
↵
remaining = n % k↵
↵
ans = ""↵
↵
for i in range(k):↵
ans += chr(i + ord("a")) * numbers↵
ans += "a" * remaining↵
print(ans)↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [B. Chat](https://mirror.codeforces.com/gym/520390/problem/B)↵
↵
<spoiler summary="Solution">↵
We can easily add a friend to the display system when that friend goes online. When there is a query to check if a friend can be displayed by the system, we need to remove friends with the lowest goodness values until the size of the online friends list is less than or equal to $k$. The answer will be $YES$ if the friend exists in the displayed system. If the friend is not currently in the display system, either because they were never added or because they were removed from the list, the answer will be $NO$.↵
↵
↵
Time Complexity: $(O(q * log(n)))$ where $q$ is number of queries and $n$ is number of friends↵
Space Complexity: $O(n)$↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
↵
from heapq import heappop, heappush↵
from collections import defaultdict↵
↵
def main():↵
n, k, q = map(int, input().split())↵
friendship = list(map(int, input().split()))↵
hashMap = defaultdict(int)↵
heap = []↵
↵
for _ in range(q):↵
type, friend = map(int, input().split())↵
if type == 1:↵
hashMap[friend] = 2↵
heappush(heap, (friendship[friend - 1], friend))↵
else:↵
if hashMap[friend]:↵
while len(heap) > k:↵
weight, f = heappop(heap)↵
hashMap[f] = 1 ↵
if hashMap[friend] == 2:↵
print('YES') ↵
else:↵
print('NO')↵
↵
if __name__ == '__main__':↵
main()↵
↵
↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [C. Poker](https://mirror.codeforces.com/gym/520390/problem/C)↵
↵
<spoiler summary = "Hint">↵
The order in which they will be applied is not important.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
To solve it, it should be noted that despite the way the deck with bonuses works, the order in which they will be applied is not important. Then, when we meet the hero card, we just need to add to the answer the maximum of the available bonuses.↵
↵
Constraints make you use data structures such as $heap$ to quickly find and extract the maximum.↵
↵
Total complexity: $O(nlogn)$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
from heapq import heappush, heappop↵
↵
t = int(sys.stdin.readline().strip())↵
↵
for _ in range(t):↵
↵
n = int(sys.stdin.readline().strip())↵
nums = list(map(int, sys.stdin.readline().strip().split()))↵
my_heap = []↵
ans = 0↵
for num in nums:↵
if num:↵
heappush(my_heap, -1 * num)↵
else:↵
if my_heap:↵
ans +=( heappop(my_heap) * -1)↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [D. Restricted Permutation](https://mirror.codeforces.com/gym/520390/problem/D)↵
↵
<spoiler summary="Solution">↵
Consider an $N$-vertex directed graph where for each $i$ $(1 \leq i \leq M)$, there is an edge from vertex $a_i$ to vertex $b_i$.↵
The goal is to find the lexicographically smallest sequence of topologically sorted vertices.↵
↵
Topological sorting can be applied to the directed graph we have built.↵
By choosing the vertex with the smallest index and indegree 0 at each step, we obtain the lexicographically smallest sequence $S$.↵
↵
To choose the vertex with the smallest index and indegree, we can use a heap data structure.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
↵
import heapq↵
↵
N, M = map(int, input().split())↵
indeg = [0] * N↵
out = [[] for _ in range(N)]↵
for _ in range(M):↵
a, b = map(int, input().split())↵
a -= 1↵
b -= 1↵
indeg[b] += 1↵
out[a].append(b)↵
↵
heap = []↵
for i in range(N):↵
if indeg[i] == 0:↵
heapq.heappush(heap, i)↵
↵
ans = []↵
while heap:↵
i = heapq.heappop(heap)↵
ans.append(i)↵
for j in out[i]:↵
indeg[j] -= 1↵
if indeg[j] == 0:↵
heapq.heappush(heap, j)↵
↵
if len(ans) != N:↵
print(-1)↵
else:↵
print(*[x + 1 for x in ans])↵
```↵
</spoiler>↵
↵
↵
#### [E. Seamless Flow](https://mirror.codeforces.com/gym/520390/problem/E)↵
↵
<spoiler summary="Hint 1">↵
<p>When do we print $NO$?</p>↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
<p>If we can't form a valid topological order of the vertices by using only the directed edges, the answer is $NO$.</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
<p>↵
If the graph consisting of the vertices and only directed edges contains at least one cycle then the answer is $NO$. In other words, If we can’t form a valid topological order of the vertices with just the directed edges, we print $NO$.↵
</p>↵
<p> ↵
Let’s now have the topological sort of the graph without undirected edges. For each pair of vertices $X, Y$ in the undirected edges, if $X$ comes before $Y$ in the topological order, we direct the edge from $X$ to $Y$, otherwise we direct it from $Y$ to $X$.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
from collections import deque, defaultdict↵
↵
↵
def topSort(graph, indegree):↵
queue = deque()↵
↵
for node in range(n):↵
if not indegree[node]:↵
queue.append(node)↵
↵
top_order = []↵
↵
while queue:↵
cur = queue.popleft()↵
top_order.append(cur)↵
↵
for neigh in graph[cur]:↵
indegree[neigh] -= 1↵
↵
if not indegree[neigh]:↵
queue.append(neigh)↵
↵
return top_order↵
↵
↵
t = int(input())↵
↵
for _ in range(t):↵
n, m = map(int, input().split())↵
↵
directed = []↵
undirected = []↵
↵
for i in range(m):↵
direction, x, y = map(int, input().split())↵
↵
x -= 1 # let's make it zero indexed↵
y -= 1↵
↵
if direction:↵
directed.append((x, y))↵
↵
else:↵
undirected.append((x, y))↵
↵
↵
graph = [[] for node in range(n)]↵
indegree = defaultdict(int)↵
↵
for x, y in directed:↵
graph[x].append(y)↵
indegree[y] += 1↵
↵
↵
order= topSort(graph, indegree)↵
↵
if len(order) < n:↵
print("NO")↵
↵
else:↵
# compute the index of each node in the topological order↵
temp = {node: idx for idx, node in enumerate(order)}↵
↵
↵
print('YES')↵
for x, y in undirected:↵
if temp[x] < temp[y]:↵
print(x + 1, y + 1)↵
↵
else:↵
print(y + 1, x + 1)↵
↵
for x, y in directed:↵
print(x + 1, y + 1)↵
↵
↵
```↵
</spoiler>↵
↵
↵
