[contest:520542]↵
### [A.Misha and Changing Handles](https://codeforces.me/gym/520542/problem/A)↵
↵
<spoiler summary="Solution">↵
↵
The problem can be formulated as follows: The directed graph is given, its vertices correspond to users' handles and edges — to requests. It consists of a number of chains, so every vertex ingoing and outgoing degree doesn't exceed one. One need to find number of chains and first and last vertices of every chain. The arcs of this graph can be stored in dictionary. with head of the arc as the key and the tail as the value.↵
↵
Each zero ingoing degree vertex corresponds to unique user as well as first vertex of some chain. We should iterate from such vertices through the arcs while it's possible. Thus we find relation between first and last vertices in the chain as well as relation between the original and the new handle of some user.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
def main():↵
q = int(input())↵
↵
edges = {}↵
nonBegin = set()↵
↵
for _ in range(q):↵
old, new = input().split()↵
edges[old] = new↵
nonBegin.add(new)↵
↵
ans = []↵
↵
for old, new in edges.items():↵
if old in nonBegin:↵
continue↵
↵
cur = old↵
while cur in edges:↵
cur = edges[cur]↵
ans.append((old, cur))↵
↵
print(len(ans))↵
for old, cur in ans:↵
print(old, cur)↵
↵
if __name__ == "__main__":↵
main()↵
~~~~~↵
</spoiler>↵
↵
### [B.News Distribution](https://codeforces.me/gym/520542/problem/B)↵
↵
<spoiler summary="Solution">↵
↵
Lets model the social network as a kind of graph, then we can see that if the news starts from user ‘a’, it will spread to all the other friends that belong to its component. Hence, we can use a union find to simulate the social network. Then, we can easily query the size of each friend’s component.↵
↵
NOTE — We have noticed a lot of TLE submissions on this question. While some were due to forgetting the two optimizations (sort by size/rank and path compression) or not implementing them correctly, most were caused by some clever test cases on the Codeforces website that make sure path compression never happens. When unioning two root nodes, path compression does not happen because there is no path above them to compress during find. If unions like this happen enough times, you will end up getting a very tall tree, regardless of whatever optimizations you implemented.↵
In cases like this, it is important to remember that every minor improvement counts. One major one that has not been discussed enough, but can make a big difference is:↵
Using sys.stdin.readline() is 10x faster than input() according to [this article](https://medium.com/@xkumiyu/8-speed-differences-you-need-to-know-in-python-db7266c3b177#:~:text=python%2Dspeed%2Dcomp-,Standard%20Input,-Although%20it%20may). This makes a substantial difference especially when taking input inside a loop.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
from sys import stdin↵
↵
n, m = map(int, input().split())↵
↵
reps = list(range(n + 1))↵
size = [1] * (n + 1)↵
↵
def find(x):↵
if reps[x] != x:↵
reps[x] = find(reps[x])↵
return reps[x]↵
↵
def union(node1, node2):↵
rep1 = find(node1)↵
rep2 = find(node2)↵
↵
if rep1 == rep2:↵
return↵
↵
if size[rep1] >= size[rep2]:↵
reps[rep2] = rep1↵
size[rep1] += size[rep2]↵
else:↵
reps[rep1] = rep2↵
size[rep2] += size[rep1]↵
↵
for _ in range(m):↵
g, *group = list(map(int, stdin.readline().split()))↵
↵
for i in range(1, g):↵
union(group[0], group[i])↵
↵
ans = [size[find(node)] for node in range(1, n+1)]↵
↵
print(*ans)↵
↵
~~~~~↵
</spoiler>↵
↵
### [C. Love Rescue](https://codeforces.me/gym/520542/problem/C)↵
↵
<spoiler summary="Solution">↵
↵
The key to this problem is realizing that once we buy a spell of form (c1, c2), we can turn any c1 to c2. If we then add a spell of form (c2, c3), we can turn any c1 into c2 and c3, any c2 into c1 and c3, etc. Basically, any two characters that are connected by a direct or indirect spell can be interchanged.↵
This brings the problem to a simple union find problem. As we iterate over the two strings, if the two characters at an index are not similar and are not part of the same group (connected by an already bought spell), we buy a spell to connect them and record that spell. Otherwise, we skip them.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
reps = list(range(n + 1))↵
size = [1] * (n + 1)↵
↵
def find(x):↵
if reps[x] != x:↵
reps[x] = find(reps[x])↵
return reps[x]↵
↵
def union(node1, node2):↵
rep1 = find(node1)↵
rep2 = find(node2)↵
↵
if rep1 == rep2:↵
return False↵
↵
if size[rep1] >= size[rep2]:↵
reps[rep2] = rep1↵
size[rep1] += size[rep2]↵
else:↵
reps[rep1] = rep2↵
size[rep2] += size[rep1]↵
↵
return True↵
↵
input()↵
s1 = input()↵
s2 = input()↵
↵
spells = []↵
for c1, c2 in zip(s1, s2):↵
if union(ord(c1) - ord('a'), ord(c2) - ord('a')):↵
spells.append([c1, c2])↵
↵
print(len(spells))↵
for spell in spells:↵
print(*spell)↵
~~~~~↵
</spoiler>↵
↵
### [D. Social Network](https://codeforces.me/gym/520542/problem/D)↵
↵
<spoiler summary="Solution">↵
↵
The tricky part about this problem is understanding the problem statement. It asks you to find the size of the largest group at the ith step, assuming that exactly i introductions have been made. This means that if you were asked to introduce two people that already know each other, you have not made that introduction. But since you were told to make exactly i introductions at each step, the question becomes how do you use that extra introduction optimally.↵
↵
To solve this problem, we use union find. At each condition, we union the two given people. If they already know each other, we have one extra introduction we can make. To find the maximal group that would exist if we had used the extra pairing, we assume to use it to introduce the two largest groups. For example, at a point, if we have groups of size 3, 5, 2 and 4:↵
↵
- If we have no extra introductions, the size of the maximal group will be 5↵
- If we have 1 extra introduction, the size of the maximal group will be 9 (since we can use the extra introduction to introduce two people from the groups of size 5 and 4)↵
- If we have 2 extra introductions, the size of the maximal group will be 12 (since we can use the extra introductions to merge the groups of size 3, 4, and 5.↵
↵
It is important to remember that we don’t actually union the groups with our extra introductions, since the group sizes change and the largest groups will always be changing. To find the k largest groups (assuming we have k extra introductions at a step), we can use a max heap. Converting the parents array into a max-heap at each union step is costly (n2), but it is manageable with the given constraints.↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
from heapq import *↵
from sys import stdin↵
↵
n, t = [int(i) for i in stdin.readline().split()]↵
reps = list(range(n + 1))↵
size = [1] * (n + 1)↵
extras = 0↵
↵
def find(x):↵
if reps[x] != x:↵
reps[x] = find(reps[x])↵
return reps[x]↵
↵
def union(node1, node2):↵
global extras↵
rep1 = find(node1)↵
rep2 = find(node2)↵
↵
if rep1 != rep2:↵
if size[rep1] >= size[rep2]:↵
reps[rep2] = rep1↵
size[rep1] += size[rep2]↵
else:↵
reps[rep1] = rep2↵
size[rep2] += size[rep1]↵
else:↵
extras += 1↵
↵
heap = [-s for n, s in enumerate(size) if reps[n] == n]↵
heapify(heap)↵
↵
max_cons = 0↵
for _ in range(extras + 1):↵
max_cons += abs(heappop(heap))↵
↵
print(max_cons - 1)↵
↵
for _ in range(t):↵
p1, p2 = [int(i) for i in stdin.readline().split()]↵
union(p1, p2)↵
↵
~~~~~↵
</spoiler>↵
↵
### [E. Make It Connected](https://codeforces.me/gym/520542/problem/E)↵
↵
<spoiler summary="Solution">↵
↵
This is a classic minimum spanning tree problem with a slight twist. If you are unfamiliar with minimum spanning trees, we suggest you read [this](https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/) material to get a general idea. Coming back to the question, it is important to realize that special offers are not necessarily more optimal than classic edges (creating an edge with a cost equal to the sum of the two nodes it connects). This means we need to consider normal edges as well as special offer edges in the same manner.↵
A straightforward implementation for this would be to just create all possible edges by combining every node with every other node and putting all those edges together with the special edges. We could then sort them based on weight and count the cost to connect the whole tree. However, it is not efficient to create every possible edge (it would take O(n2) time).↵
At this point, it is important to realize that although we are grouping items, creating groups in such a way that we make all the nodes join into a group with the smallest cost node is the most optimal way to use the normal edges. This arises from the fact that the cost of these edges is the sum of the two nodes, choosing one of the nodes to be as small as possible can help us.↵
Looking at the general solution, we create edges that connect the smallest node with every other node, and put them together with the special edges. We then sort all these edges by cost and start checking if they connect two separate components or if they are redundant edges that connect two nodes already in the same component. If the former is the case, we add the cost to our total, otherwise we skip this node. We do this for all our nodes and the running total will be the answer. This algorithm is known as Kruskal’s Algorithm and we encourage you to do your own further research on it.↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
from sys import stdin↵
↵
n, o = [int(i) for i in input().split()]↵
cost = [int(i) for i in input().split()]↵
↵
reps = list(range(n + 1))↵
size = [1] * (n + 1)↵
↵
def find(x):↵
if reps[x] != x:↵
reps[x] = find(reps[x])↵
return reps[x]↵
def union(node1, node2):↵
rep1 = find(node1)↵
rep2 = find(node2)↵
↵
if rep1 == rep2:↵
return False↵
if size[rep1] >= size[rep2]:↵
reps[rep2] = rep1↵
size[rep1] += size[rep2]↵
else:↵
reps[rep1] = rep2↵
size[rep2] += size[rep1]↵
↵
return True↵
↵
offers = []↵
for _ in range(o):↵
n1, n2, c = [int(i) for i in stdin.readline().split()]↵
offers.append((c, n1, n2))↵
↵
for i in range(n):↵
cost[i] = (cost[i], i + 1)↵
cost.sort()↵
↵
for i in range(1, n):↵
offers.append((cost[0][0] + cost[i][0], cost[0][1], cost[i][1]))↵
offers.sort()↵
↵
total = 0↵
for c, n1, n2 in offers:↵
if union(n1, n2):↵
total += c↵
↵
print(total)↵
↵
~~~~~↵
</spoiler>↵
↵
### [A.Misha and Changing Handles](https://codeforces.me/gym/520542/problem/A)↵
↵
<spoiler summary="Solution">↵
↵
The problem can be formulated as follows: The directed graph is given, its vertices correspond to users' handles and edges — to requests. It consists of a number of chains, so every vertex ingoing and outgoing degree doesn't exceed one. One need to find number of chains and first and last vertices of every chain. The arcs of this graph can be stored in dictionary. with head of the arc as the key and the tail as the value.↵
↵
Each zero ingoing degree vertex corresponds to unique user as well as first vertex of some chain. We should iterate from such vertices through the arcs while it's possible. Thus we find relation between first and last vertices in the chain as well as relation between the original and the new handle of some user.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
def main():↵
q = int(input())↵
↵
edges = {}↵
nonBegin = set()↵
↵
for _ in range(q):↵
old, new = input().split()↵
edges[old] = new↵
nonBegin.add(new)↵
↵
ans = []↵
↵
for old, new in edges.items():↵
if old in nonBegin:↵
continue↵
↵
cur = old↵
while cur in edges:↵
cur = edges[cur]↵
ans.append((old, cur))↵
↵
print(len(ans))↵
for old, cur in ans:↵
print(old, cur)↵
↵
if __name__ == "__main__":↵
main()↵
~~~~~↵
</spoiler>↵
↵
### [B.News Distribution](https://codeforces.me/gym/520542/problem/B)↵
↵
<spoiler summary="Solution">↵
↵
Lets model the social network as a kind of graph, then we can see that if the news starts from user ‘a’, it will spread to all the other friends that belong to its component. Hence, we can use a union find to simulate the social network. Then, we can easily query the size of each friend’s component.↵
↵
NOTE — We have noticed a lot of TLE submissions on this question. While some were due to forgetting the two optimizations (sort by size/rank and path compression) or not implementing them correctly, most were caused by some clever test cases on the Codeforces website that make sure path compression never happens. When unioning two root nodes, path compression does not happen because there is no path above them to compress during find. If unions like this happen enough times, you will end up getting a very tall tree, regardless of whatever optimizations you implemented.↵
In cases like this, it is important to remember that every minor improvement counts. One major one that has not been discussed enough, but can make a big difference is:↵
Using sys.stdin.readline() is 10x faster than input() according to [this article](https://medium.com/@xkumiyu/8-speed-differences-you-need-to-know-in-python-db7266c3b177#:~:text=python%2Dspeed%2Dcomp-,Standard%20Input,-Although%20it%20may). This makes a substantial difference especially when taking input inside a loop.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
from sys import stdin↵
↵
n, m = map(int, input().split())↵
↵
reps = list(range(n + 1))↵
size = [1] * (n + 1)↵
↵
def find(x):↵
if reps[x] != x:↵
reps[x] = find(reps[x])↵
return reps[x]↵
↵
def union(node1, node2):↵
rep1 = find(node1)↵
rep2 = find(node2)↵
↵
if rep1 == rep2:↵
return↵
↵
if size[rep1] >= size[rep2]:↵
reps[rep2] = rep1↵
size[rep1] += size[rep2]↵
else:↵
reps[rep1] = rep2↵
size[rep2] += size[rep1]↵
↵
for _ in range(m):↵
g, *group = list(map(int, stdin.readline().split()))↵
↵
for i in range(1, g):↵
union(group[0], group[i])↵
↵
ans = [size[find(node)] for node in range(1, n+1)]↵
↵
print(*ans)↵
↵
~~~~~↵
</spoiler>↵
↵
### [C. Love Rescue](https://codeforces.me/gym/520542/problem/C)↵
↵
<spoiler summary="Solution">↵
↵
The key to this problem is realizing that once we buy a spell of form (c1, c2), we can turn any c1 to c2. If we then add a spell of form (c2, c3), we can turn any c1 into c2 and c3, any c2 into c1 and c3, etc. Basically, any two characters that are connected by a direct or indirect spell can be interchanged.↵
This brings the problem to a simple union find problem. As we iterate over the two strings, if the two characters at an index are not similar and are not part of the same group (connected by an already bought spell), we buy a spell to connect them and record that spell. Otherwise, we skip them.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
reps = list(range(n + 1))↵
size = [1] * (n + 1)↵
↵
def find(x):↵
if reps[x] != x:↵
reps[x] = find(reps[x])↵
return reps[x]↵
↵
def union(node1, node2):↵
rep1 = find(node1)↵
rep2 = find(node2)↵
↵
if rep1 == rep2:↵
return False↵
↵
if size[rep1] >= size[rep2]:↵
reps[rep2] = rep1↵
size[rep1] += size[rep2]↵
else:↵
reps[rep1] = rep2↵
size[rep2] += size[rep1]↵
↵
return True↵
↵
input()↵
s1 = input()↵
s2 = input()↵
↵
spells = []↵
for c1, c2 in zip(s1, s2):↵
if union(ord(c1) - ord('a'), ord(c2) - ord('a')):↵
spells.append([c1, c2])↵
↵
print(len(spells))↵
for spell in spells:↵
print(*spell)↵
~~~~~↵
</spoiler>↵
↵
### [D. Social Network](https://codeforces.me/gym/520542/problem/D)↵
↵
<spoiler summary="Solution">↵
↵
The tricky part about this problem is understanding the problem statement. It asks you to find the size of the largest group at the ith step, assuming that exactly i introductions have been made. This means that if you were asked to introduce two people that already know each other, you have not made that introduction. But since you were told to make exactly i introductions at each step, the question becomes how do you use that extra introduction optimally.↵
↵
To solve this problem, we use union find. At each condition, we union the two given people. If they already know each other, we have one extra introduction we can make. To find the maximal group that would exist if we had used the extra pairing, we assume to use it to introduce the two largest groups. For example, at a point, if we have groups of size 3, 5, 2 and 4:↵
↵
- If we have no extra introductions, the size of the maximal group will be 5↵
- If we have 1 extra introduction, the size of the maximal group will be 9 (since we can use the extra introduction to introduce two people from the groups of size 5 and 4)↵
- If we have 2 extra introductions, the size of the maximal group will be 12 (since we can use the extra introductions to merge the groups of size 3, 4, and 5.↵
↵
It is important to remember that we don’t actually union the groups with our extra introductions, since the group sizes change and the largest groups will always be changing. To find the k largest groups (assuming we have k extra introductions at a step), we can use a max heap. Converting the parents array into a max-heap at each union step is costly (n2), but it is manageable with the given constraints.↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
from heapq import *↵
from sys import stdin↵
↵
n, t = [int(i) for i in stdin.readline().split()]↵
reps = list(range(n + 1))↵
size = [1] * (n + 1)↵
extras = 0↵
↵
def find(x):↵
if reps[x] != x:↵
reps[x] = find(reps[x])↵
return reps[x]↵
↵
def union(node1, node2):↵
global extras↵
rep1 = find(node1)↵
rep2 = find(node2)↵
↵
if rep1 != rep2:↵
if size[rep1] >= size[rep2]:↵
reps[rep2] = rep1↵
size[rep1] += size[rep2]↵
else:↵
reps[rep1] = rep2↵
size[rep2] += size[rep1]↵
else:↵
extras += 1↵
↵
heap = [-s for n, s in enumerate(size) if reps[n] == n]↵
heapify(heap)↵
↵
max_cons = 0↵
for _ in range(extras + 1):↵
max_cons += abs(heappop(heap))↵
↵
print(max_cons - 1)↵
↵
for _ in range(t):↵
p1, p2 = [int(i) for i in stdin.readline().split()]↵
union(p1, p2)↵
↵
~~~~~↵
</spoiler>↵
↵
### [E. Make It Connected](https://codeforces.me/gym/520542/problem/E)↵
↵
<spoiler summary="Solution">↵
↵
This is a classic minimum spanning tree problem with a slight twist. If you are unfamiliar with minimum spanning trees, we suggest you read [this](https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/) material to get a general idea. Coming back to the question, it is important to realize that special offers are not necessarily more optimal than classic edges (creating an edge with a cost equal to the sum of the two nodes it connects). This means we need to consider normal edges as well as special offer edges in the same manner.↵
A straightforward implementation for this would be to just create all possible edges by combining every node with every other node and putting all those edges together with the special edges. We could then sort them based on weight and count the cost to connect the whole tree. However, it is not efficient to create every possible edge (it would take O(n2) time).↵
At this point, it is important to realize that although we are grouping items, creating groups in such a way that we make all the nodes join into a group with the smallest cost node is the most optimal way to use the normal edges. This arises from the fact that the cost of these edges is the sum of the two nodes, choosing one of the nodes to be as small as possible can help us.↵
Looking at the general solution, we create edges that connect the smallest node with every other node, and put them together with the special edges. We then sort all these edges by cost and start checking if they connect two separate components or if they are redundant edges that connect two nodes already in the same component. If the former is the case, we add the cost to our total, otherwise we skip this node. We do this for all our nodes and the running total will be the answer. This algorithm is known as Kruskal’s Algorithm and we encourage you to do your own further research on it.↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
from sys import stdin↵
↵
n, o = [int(i) for i in input().split()]↵
cost = [int(i) for i in input().split()]↵
↵
reps = list(range(n + 1))↵
size = [1] * (n + 1)↵
↵
def find(x):↵
if reps[x] != x:↵
reps[x] = find(reps[x])↵
return reps[x]↵
def union(node1, node2):↵
rep1 = find(node1)↵
rep2 = find(node2)↵
↵
if rep1 == rep2:↵
return False↵
if size[rep1] >= size[rep2]:↵
reps[rep2] = rep1↵
size[rep1] += size[rep2]↵
else:↵
reps[rep1] = rep2↵
size[rep2] += size[rep1]↵
↵
return True↵
↵
offers = []↵
for _ in range(o):↵
n1, n2, c = [int(i) for i in stdin.readline().split()]↵
offers.append((c, n1, n2))↵
↵
for i in range(n):↵
cost[i] = (cost[i], i + 1)↵
cost.sort()↵
↵
for i in range(1, n):↵
offers.append((cost[0][0] + cost[i][0], cost[0][1], cost[i][1]))↵
offers.sort()↵
↵
total = 0↵
for c, n1, n2 in offers:↵
if union(n1, n2):↵
total += c↵
↵
print(total)↵
↵
~~~~~↵
</spoiler>↵
↵
