[Here](https://codeforces.com/gym/520688) is the contest link (all problems are from Codeforces' problemset).↵
↵
↵
#### [A. Duale String](https://codeforces.com/gym/520688/problem/A)↵
↵
<spoiler summary="Solution">↵
<p>↵
If the length of the given string $s$ is odd, then the answer is $NO$, since it cannot be a concatenation of two equal strings. Otherwise, Let's slice the string into equal halves. If the two halves are equal the answer is $YES$, otherwise $NO$.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
t = int(input())↵
for _ in range(t):↵
s = input()↵
↵
if len(s)%2:↵
print('NO')↵
↵
else:↵
mid = len(s)//2↵
print('YES' if s[:mid] == s[mid:] else 'NO')↵
↵
```↵
</spoiler>↵
↵
↵
#### [B. Gelada baboon's Family Trees](https://codeforces.com/gym/520688/problem/B)↵
↵
<spoiler summary = "Hint 1">↵
<p>↵
Treat the forest as a union-find data structure.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
The key observation is that each baboon and its most distant relative on the same tree belong to the same tree (connected component). We can use this fact to identify the number of trees.↵
↵
Solution Approach:↵
↵
We can use a Union-Find data structure to efficiently group relative baboons in a single tree.↵
Initialize a union-find object with $n$ baboons (one for each baboon)↵
Iterate through the sequences $s$. For each baboon $i$, perform a union operation on $i$ and $(s[i] - 1)$. This connects baboon $i$ with its most distant relative.↵
Count the number of unique representatives in the union-find. That will be the answer. ↵
↵
↵
Time & Space Complexity ↵
↵
Time Complexity: $O(n)$, where $n$ is the number of baboons. This is due to the single loop for processing the $s$ sequence and another loop for finding representatives. ↵
Space Complexity: $O(n)$, due to the Union-Find data structure and the set used to store representatives.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
from collections import defaultdict↵
class UnionFind:↵
def __init__(self, size):↵
self.root = [i for i in range(size)]↵
self.size = [1] * size↵
↵
def find(self, x):↵
while x != self.root[x]:↵
self.root[x] = self.root[self.root[x]]↵
x = self.root[x]↵
return x↵
↵
def union(self, x, y):↵
rootX = self.find(x)↵
rootY = self.find(y)↵
if rootX != rootY:↵
if self.size[rootX] > self.size[rootY]:↵
self.root[rootY] = rootX↵
self.size[rootX] += self.size[rootY]↵
else:↵
self.root[rootX] = rootY↵
self.size[rootY] += self.size[rootX]↵
↵
↵
def main():↵
n = int(input())↵
seq = list(map(int, input().split()))↵
forest = UnionFind(n)↵
for i in range(n):↵
forest.union(i, seq[i] - 1)↵
↵
tree_numbers = set()↵
for i in range(n):↵
tree_numbers.add(forest.find(i))↵
↵
print(len(tree_numbers))↵
↵
if __name__ == '__main__':↵
main()↵
↵
```↵
</spoiler>↵
↵
↵
#### [C. Balanced Parentheses Clusters](https://codeforces.com/gym/520688/problem/C)↵
↵
<spoiler summary="Solution">↵
To track the valid parenthesis strings, we can use a stack. When encountering an opening bracket $($, we add its index to the stack. If it's a closing bracket $)$, we remove the last unpaired opening bracket. Whenever we remove the index of an opening bracket $i$, we can observe that the substring from $s_i$ to the current index forms a balanced bracket sequence. This is because when we remove an unpaired opening bracket, the substring between the removed index and the current index has matching opening and closing brackets. Thus, we unite the two indices to mark this valid substring as part of the connected components in Athanasius's graph. This process ensures that we account for all balanced bracket sequences in the graph construction.↵
Additionally, if the current bracket is a closing bracket $)$ and the next bracket (current index plus one) is an opening bracket $($, we unite them. This is because the current bracket marks the end of a balanced bracket sequence, and the next bracket marks the start of another balanced bracket sequence, and two balanced brackets together form a balanced bracket sequence.↵
</spoiler>↵
↵
↵
<spoiler summary="Code ">↵
```python↵
class UnionFind:↵
def __init__(self, size):↵
self.parent = list(range(size))↵
self.rank = [0] * size↵
↵
def find(self, element):↵
if self.parent[element] != element:↵
self.parent[element] = self.find(self.parent[element])↵
return self.parent[element]↵
↵
def union(self, element_a, element_b):↵
root_a, root_b = self.find(element_a), self.find(element_b)↵
if root_a != root_b:↵
if self.rank[root_a] > self.rank[root_b]:↵
self.parent[root_b] = root_a↵
elif self.rank[root_a] < self.rank[root_b]:↵
self.parent[root_a] = root_b↵
else:↵
self.parent[root_a] = root_b↵
self.rank[root_b] += 1↵
↵
def solve():↵
num_pairs = int(input())↵
brackets = input().strip()↵
uf = UnionFind(2 * num_pairs)↵
stack = []↵
for i, bracket in enumerate(brackets):↵
if bracket == "(":↵
stack.append(i)↵
else:↵
top = stack.pop()↵
uf.union(i, top)↵
if i + 1 < 2 * num_pairs and brackets[i + 1] == "(":↵
uf.union(i, i + 1)↵
num_connected_components = sum(1 for i, parent in enumerate(uf.parent) if i == parent)↵
print(num_connected_components)↵
↵
num_tests = int(input())↵
for _ in range(num_tests):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
#### [D. The Kittens Test](https://codeforces.com/gym/520688/problem/D)↵
↵
<spoiler summary = "Solution">↵
In this problem we are given a disjoint set union process with $n−1$ steps, merging $n$ initial $1$-element sets into one $n$-element set. We have to put elements into a linear array of cells, so that the cells to be joined at each step of the process were immediate neighbours (i.e. not separated by other cells).↵
↵
This problem can be solved in $O(nlogn)$ via standard disjoint-set data structure, additionally storing lists of elements in each set.↵
↵
The simplest solution is storing mapping from item to id (representative) of its current set, and the inverse mapping from set to the list of its elements when we have to merge two sets A and B, we make the smaller set part of the larger set and update mappings and concatenating the lists can be done in $O(min(|A|,|B|)))$.↵
↵
This gives us $O(nlogn)$: element can not change its set more than $logn$ times, because the change leads to (at least) doubling of the element's set size.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
n = int(sys.stdin.readline().strip())↵
parent = {}↵
elem = [[] for _ in range(n + 1)]↵
↵
for i in range(1, n + 1):↵
elem[i].append(i)↵
parent[i] = i↵
size = [1] * (n + 1)↵
↵
def find(x):↵
if parent[x] != x:↵
parent[x] = find(parent[x])↵
return parent[x]↵
↵
def union(x, y):↵
par_x = find(x)↵
par_y = find(y) ↵
if par_x != par_y:↵
if size[par_x] > size[par_y]:↵
parent[par_y] = par_x↵
elem[par_x].extend(elem[par_y])↵
size[par_x] += size[par_y]↵
else:↵
parent[par_x] = par_y↵
elem[par_y].extend(elem[par_x])↵
size[par_y] += size[par_x]↵
for _ in range(n - 1):↵
x, y = map(int, sys.stdin.readline().strip().split())↵
union(x, y)↵
↵
print(*elem[find(1)])↵
↵
```↵
</spoiler>↵
↵
↵
#### [E. Weighted Cycle Search](https://codeforces.com/gym/520688/problem/E)↵
↵
<spoiler summary = "Solution">↵
Let's sort the edges by their weight in descending order and merge the vertices in that order. Whenever you get an already merged vertices, it means the new edge will create cycle; we can update our answer to that edge. Finally, to get the cycle, we can do DFS from either end of that edge until we get to the other end.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
``` python3↵
from collections import defaultdict↵
from sys import stdin↵
↵
↵
def input(): return stdin.readline().strip()↵
↵
class DSU:↵
def __init__(self, n):↵
self.p = [i for i in range(n)]↵
self.size = [1 for _ in range(n)]↵
↵
def find(self, v):↵
while v != self.p[v]:↵
self.p[v] = self.p[self.p[v]]↵
v = self.p[v]↵
return v↵
↵
def merge(self, u, v):↵
pu = self.find(u)↵
pv = self.find(v)↵
if pu == pv:↵
return False↵
if self.size[pu] < self.size[pv]:↵
pu, pv = pv, pu↵
self.size[pu] += self.size[pv]↵
self.p[pv] = pu↵
return True↵
↵
T = int(input())↵
for _ in range(T):↵
N, M = map(int, input().split())↵
edges = []↵
adj = defaultdict(list)↵
for __ in range(M):↵
u, v, w = map(int, input().split())↵
u, v = u - 1, v - 1↵
edges.append((w, u, v))↵
adj[u].append(v)↵
adj[v].append(u)↵
↵
edges.sort(key=lambda edge: edge[0], reverse=True)↵
dsu = DSU(N)↵
for w, u, v in edges:↵
if not dsu.merge(u, v):↵
ans = (w, u, v)↵
↵
min_w, st, end = ans↵
stk = [st]↵
↵
↵
# DFS to get the cycle↵
p = [-1]*N↵
p[st] = st↵
while stk:↵
v = stk.pop()↵
for ch in adj[v]:↵
if v == st and ch == end: continue↵
if ch == end:↵
p[ch] = v↵
stk = []↵
break↵
if p[ch] == -1:↵
p[ch] = v↵
stk.append(ch)↵
v = end↵
path = []↵
while p[v] != v:↵
path.append(v)↵
v = p[v]↵
path.append(st)↵
↵
print(min_w, len(path))↵
for i in range(len(path)):↵
path[i] += 1↵
print(*path)↵
```↵
</spoiler>↵
↵
↵
↵
#### [A. Duale String](https://codeforces.com/gym/520688/problem/A)↵
↵
<spoiler summary="Solution">↵
<p>↵
If the length of the given string $s$ is odd, then the answer is $NO$, since it cannot be a concatenation of two equal strings. Otherwise, Let's slice the string into equal halves. If the two halves are equal the answer is $YES$, otherwise $NO$.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
t = int(input())↵
for _ in range(t):↵
s = input()↵
↵
if len(s)%2:↵
print('NO')↵
↵
else:↵
mid = len(s)//2↵
print('YES' if s[:mid] == s[mid:] else 'NO')↵
↵
```↵
</spoiler>↵
↵
↵
#### [B. Gelada baboon's Family Trees](https://codeforces.com/gym/520688/problem/B)↵
↵
<spoiler summary = "Hint 1">↵
<p>↵
Treat the forest as a union-find data structure.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
The key observation is that each baboon and its most distant relative on the same tree belong to the same tree (connected component). We can use this fact to identify the number of trees.↵
↵
Solution Approach:↵
↵
We can use a Union-Find data structure to efficiently group relative baboons in a single tree.↵
Initialize a union-find object with $n$ baboons (one for each baboon)↵
Iterate through the sequences $s$. For each baboon $i$, perform a union operation on $i$ and $(s[i] - 1)$. This connects baboon $i$ with its most distant relative.↵
Count the number of unique representatives in the union-find. That will be the answer. ↵
↵
↵
Time & Space Complexity ↵
↵
Time Complexity: $O(n)$, where $n$ is the number of baboons. This is due to the single loop for processing the $s$ sequence and another loop for finding representatives. ↵
Space Complexity: $O(n)$, due to the Union-Find data structure and the set used to store representatives.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
from collections import defaultdict↵
class UnionFind:↵
def __init__(self, size):↵
self.root = [i for i in range(size)]↵
self.size = [1] * size↵
↵
def find(self, x):↵
while x != self.root[x]:↵
self.root[x] = self.root[self.root[x]]↵
x = self.root[x]↵
return x↵
↵
def union(self, x, y):↵
rootX = self.find(x)↵
rootY = self.find(y)↵
if rootX != rootY:↵
if self.size[rootX] > self.size[rootY]:↵
self.root[rootY] = rootX↵
self.size[rootX] += self.size[rootY]↵
else:↵
self.root[rootX] = rootY↵
self.size[rootY] += self.size[rootX]↵
↵
↵
def main():↵
n = int(input())↵
seq = list(map(int, input().split()))↵
forest = UnionFind(n)↵
for i in range(n):↵
forest.union(i, seq[i] - 1)↵
↵
tree_numbers = set()↵
for i in range(n):↵
tree_numbers.add(forest.find(i))↵
↵
print(len(tree_numbers))↵
↵
if __name__ == '__main__':↵
main()↵
↵
```↵
</spoiler>↵
↵
↵
#### [C. Balanced Parentheses Clusters](https://codeforces.com/gym/520688/problem/C)↵
↵
<spoiler summary="Solution">↵
To track the valid parenthesis strings, we can use a stack. When encountering an opening bracket $($, we add its index to the stack. If it's a closing bracket $)$, we remove the last unpaired opening bracket. Whenever we remove the index of an opening bracket $i$, we can observe that the substring from $s_i$ to the current index forms a balanced bracket sequence. This is because when we remove an unpaired opening bracket, the substring between the removed index and the current index has matching opening and closing brackets. Thus, we unite the two indices to mark this valid substring as part of the connected components in Athanasius's graph. This process ensures that we account for all balanced bracket sequences in the graph construction.↵
Additionally, if the current bracket is a closing bracket $)$ and the next bracket (current index plus one) is an opening bracket $($, we unite them. This is because the current bracket marks the end of a balanced bracket sequence, and the next bracket marks the start of another balanced bracket sequence, and two balanced brackets together form a balanced bracket sequence.↵
</spoiler>↵
↵
↵
<spoiler summary="Code ">↵
```python↵
class UnionFind:↵
def __init__(self, size):↵
self.parent = list(range(size))↵
self.rank = [0] * size↵
↵
def find(self, element):↵
if self.parent[element] != element:↵
self.parent[element] = self.find(self.parent[element])↵
return self.parent[element]↵
↵
def union(self, element_a, element_b):↵
root_a, root_b = self.find(element_a), self.find(element_b)↵
if root_a != root_b:↵
if self.rank[root_a] > self.rank[root_b]:↵
self.parent[root_b] = root_a↵
elif self.rank[root_a] < self.rank[root_b]:↵
self.parent[root_a] = root_b↵
else:↵
self.parent[root_a] = root_b↵
self.rank[root_b] += 1↵
↵
def solve():↵
num_pairs = int(input())↵
brackets = input().strip()↵
uf = UnionFind(2 * num_pairs)↵
stack = []↵
for i, bracket in enumerate(brackets):↵
if bracket == "(":↵
stack.append(i)↵
else:↵
top = stack.pop()↵
uf.union(i, top)↵
if i + 1 < 2 * num_pairs and brackets[i + 1] == "(":↵
uf.union(i, i + 1)↵
num_connected_components = sum(1 for i, parent in enumerate(uf.parent) if i == parent)↵
print(num_connected_components)↵
↵
num_tests = int(input())↵
for _ in range(num_tests):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
#### [D. The Kittens Test](https://codeforces.com/gym/520688/problem/D)↵
↵
<spoiler summary = "Solution">↵
In this problem we are given a disjoint set union process with $n−1$ steps, merging $n$ initial $1$-element sets into one $n$-element set. We have to put elements into a linear array of cells, so that the cells to be joined at each step of the process were immediate neighbours (i.e. not separated by other cells).↵
↵
This problem can be solved in $O(nlogn)$ via standard disjoint-set data structure, additionally storing lists of elements in each set.↵
↵
The simplest solution is storing mapping from item to id (representative) of its current set, and the inverse mapping from set to the list of its elements when we have to merge two sets A and B, we make the smaller set part of the larger set and update mappings and concatenating the lists can be done in $O(min(|A|,|B|)))$.↵
↵
This gives us $O(nlogn)$: element can not change its set more than $logn$ times, because the change leads to (at least) doubling of the element's set size.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
n = int(sys.stdin.readline().strip())↵
parent = {}↵
elem = [[] for _ in range(n + 1)]↵
↵
for i in range(1, n + 1):↵
elem[i].append(i)↵
parent[i] = i↵
size = [1] * (n + 1)↵
↵
def find(x):↵
if parent[x] != x:↵
parent[x] = find(parent[x])↵
return parent[x]↵
↵
def union(x, y):↵
par_x = find(x)↵
par_y = find(y) ↵
if par_x != par_y:↵
if size[par_x] > size[par_y]:↵
parent[par_y] = par_x↵
elem[par_x].extend(elem[par_y])↵
size[par_x] += size[par_y]↵
else:↵
parent[par_x] = par_y↵
elem[par_y].extend(elem[par_x])↵
size[par_y] += size[par_x]↵
for _ in range(n - 1):↵
x, y = map(int, sys.stdin.readline().strip().split())↵
union(x, y)↵
↵
print(*elem[find(1)])↵
↵
```↵
</spoiler>↵
↵
↵
#### [E. Weighted Cycle Search](https://codeforces.com/gym/520688/problem/E)↵
↵
<spoiler summary = "Solution">↵
Let's sort the edges by their weight in descending order and merge the vertices in that order. Whenever you get an already merged vertices, it means the new edge will create cycle; we can update our answer to that edge. Finally, to get the cycle, we can do DFS from either end of that edge until we get to the other end.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
``` python3↵
from collections import defaultdict↵
from sys import stdin↵
↵
↵
def input(): return stdin.readline().strip()↵
↵
class DSU:↵
def __init__(self, n):↵
self.p = [i for i in range(n)]↵
self.size = [1 for _ in range(n)]↵
↵
def find(self, v):↵
while v != self.p[v]:↵
self.p[v] = self.p[self.p[v]]↵
v = self.p[v]↵
return v↵
↵
def merge(self, u, v):↵
pu = self.find(u)↵
pv = self.find(v)↵
if pu == pv:↵
return False↵
if self.size[pu] < self.size[pv]:↵
pu, pv = pv, pu↵
self.size[pu] += self.size[pv]↵
self.p[pv] = pu↵
return True↵
↵
T = int(input())↵
for _ in range(T):↵
N, M = map(int, input().split())↵
edges = []↵
adj = defaultdict(list)↵
for __ in range(M):↵
u, v, w = map(int, input().split())↵
u, v = u - 1, v - 1↵
edges.append((w, u, v))↵
adj[u].append(v)↵
adj[v].append(u)↵
↵
edges.sort(key=lambda edge: edge[0], reverse=True)↵
dsu = DSU(N)↵
for w, u, v in edges:↵
if not dsu.merge(u, v):↵
ans = (w, u, v)↵
↵
min_w, st, end = ans↵
stk = [st]↵
↵
↵
# DFS to get the cycle↵
p = [-1]*N↵
p[st] = st↵
while stk:↵
v = stk.pop()↵
for ch in adj[v]:↵
if v == st and ch == end: continue↵
if ch == end:↵
p[ch] = v↵
stk = []↵
break↵
if p[ch] == -1:↵
p[ch] = v↵
stk.append(ch)↵
v = end↵
path = []↵
while p[v] != v:↵
path.append(v)↵
v = p[v]↵
path.append(st)↵
↵
print(min_w, len(path))↵
for i in range(len(path)):↵
path[i] += 1↵
print(*path)↵
```↵
</spoiler>↵
↵
