We don’t have to check the common prefixes of all the given strings

We only need to find the longest common prefixes of the lexicographically smallest and largest strings among the given n strings.

First let’s accumulate the given strings in an array and sort them. Then if a prefix is common for both the first and the last strings, then it’s known for sure that it’s also a prefix for all the strings in between as the array is in sorted order the strings are binary strings. We can use one for loop and check up to which point the first and the last strings are identical and that will be our answer.

Time and space complexities

• Time Complexity: O(n)
• Space Complexity: O(n)

n = int(input())
strings = []
for _ in range(n):
    strings.append(input())

strings.sort()
length = 0
for i in range(len(strings[0])):
    if strings[0][i] == strings[-1][i]:
        length += 1
    else:
        break

print(length)

    

We have a forest of undirected trees on $$$n$$$ vertices labeled from $$$1$$$ to $$$n$$$. For each vertex $$$i$$$, we know $$$p_i$$$, the ID of its most distant relative in the same tree (ties broken by the smallest ID). We need to count the number of trees (connected components) consistent with this information.

1. Add an undirected edge between each $$$i$$$ and $$$p_i$$$.
2. This links all vertices within each tree; extra cycles don't affect connectivity.
3. Run DFS on the resulting graph, counting a new component whenever you start DFS at an unvisited vertex.

Time Complexity: $$$O(n)$$$ for building adjacency and DFS both linear.

Space Complexity: $$$O(n)$$$ for adjacency list and visited array.

import sys
sys.setrecursionlimit(10**7)

def main():
    input = sys.stdin.readline
    n = int(input())
    p = [0] + list(map(int, input().split()))

    # Build adjacency list: i <-> p[i]
    adj = [[] for _ in range(n+1)]
    for i in range(1, n+1):
        if p[i] != i:
            adj[i].append(p[i])
            adj[p[i]].append(i)

    visited = [False] * (n+1)

    def dfs(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs(v)

    components = 0
    for i in range(1, n+1):
        if not visited[i]:
            components += 1
            dfs(i)

    print(components)

if __name__ == '__main__':
    main()

1. Initialize a DSU for vertices $$$1\ldots n$$$.
2. For each $$$i$$$, union $$$i$$$ with $$$p_i$$$.
3. Count distinct roots at the end to get the number of trees.

Time Complexity: $$$O(n \alpha(n))\approx O(n)$$$ for nearly constant per union/find.

Space Complexity: $$$O(n)$$$ for parent and rank arrays.

import sys

class DSU:
    def __init__(self, n):
        self.parent = list(range(n+1))
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        if self.rank[a] < self.rank[b]:
            self.parent[a] = b
        elif self.rank[b] < self.rank[a]:
            self.parent[b] = a
        else:
            self.parent[b] = a
            self.rank[a] += 1


def main():
    input = sys.stdin.readline
    n = int(input())
    p = [0] + list(map(int, input().split()))

    dsu = DSU(n)
    for i in range(1, n+1):
        dsu.union(i, p[i])

    roots = set(dsu.find(i) for i in range(1, n+1))
    print(len(roots))

if __name__ == '__main__':
    main()

To minimize the size of the array after repeatedly removing pairs of different elements, consider how the frequency of the most common element affects your ability to perform such pairings.

The goal is to remove as many pairs of different elements as possible. The key idea is that each operation removes two elements of different values. To solve this efficiently, we observe:

• Use a frequency map to count occurrences of each distinct element in the array.
• The most frequent element determines the "bottleneck" — if one value occurs far more than the sum of the rest, we won’t be able to pair all of it.
• If the frequency of the most common element ≤ total number of other elements, we can fully pair up the entire array, leading to a final size of 0 (because each pairing removes two distinct elements).
• Otherwise, we’ll be left with an unpaired number of the most frequent element. Specifically, the answer is 2 * max_freq — n.

There’s an alternative way to simulate this using a max-heap, where we repeatedly remove the two highest-frequency elements and reduce their counts (since we pair one of each). This is reflected in the provided implementation.

from collections import Counter
from heapq import heappush, heappop

def solve():
    n = int(input())
    nums = list(map(int, input().split()))
    count = Counter(nums)
    heap = []
    
    for freq in count.values():
        heappush(heap, -freq)
    
    while len(heap) > 1:
        a = -heappop(heap)
        b = -heappop(heap)
        a -= 1
        b -= 1
        if a:
            heappush(heap, -a)
        if b:
            heappush(heap, -b)
    
    if heap:
        return -heap[0]
    else:
        return 0

for _ in range(int(input())):
    print(solve())

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.

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])

When building a graph edge by edge using Union-Find, encountering an edge that connects two already linked vertices reveals a fundamental cycle property. That is if vertices u and v are already connected when we attempt to add edge $$$(u,v)$$$, there must exist at least one alternate path between them. Hence, we can solve this problem by finding such an edge with the lightest weight by iterating in a sorted list of the edges, and finding the cycle that connects $$$u$$$ to $$$v$$$ by using BFS or DFS,

Complexity Analysis: - Time: $$$O(m log m)$$$ for sorting + $$$O(m α(n))$$$ for Union-Find - Space: $$$O(n)$$$ for Union-Find + $$$O(n + m)$$$ for graph storage

class UnionFind:
    def __init__(self, size):
        self.parent = {i:i for i in range(size)}
        self.sizes = {i:1 for i in range(size)}
    
    
    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
        
    def union(self, x, y):
        root1 = self.find(x)
        root2 = self.find(y)
        
        if root1 == root2:
            return False
        
        if self.sizes[root2] > self.sizes[root1]:
            root1,root2 = root2,root1
        
        self.parent[root2] = root1
        self.sizes[root1] += self.sizes[root2]
        
        return True



def find_cycle_path(start, end, graph):
    que = [start]
    visited = set([start])
    
    parent = {start : -1} # this will be useful to track our path back
    
    while que:
        curr = que.pop()
        
        if curr == end:
            break
        
        for nbr in graph[curr]:
            if curr == start and nbr == end: 
                # we dont want the direct path we want to cycle back so
                continue
            
            if nbr not in visited:
                parent[nbr] = curr # mark the next nodes come after curr
                
                visited.add(nbr)
                que.append(nbr)
    
    
    #now let’s track our path back
    path = []
    
    curr = end
    while curr != -1:
        path.append(curr)
        curr = parent[curr]
    
    
    return path[::-1] # since this path is a cycle there is no need for reversing.
    
        
        
def solve():
    n,m = map(int, input().split())
    
    edges = [] #lets store the edges
    graph = [[] for _ in range(n+1)]
    
    for _ in range(m):
        u, v, w =  map(int, input().split())

        #for the graph we realy don't need the weights
        graph[u].append(v)
        graph[v].append(u)
        
        edges.append((u, v, w))
    
    edges.sort(key = lambda x : x[2], reverse = True)
    
    
    dsu = UnionFind(n+1)
    
    start = end = b = -1
    for u, v, w in edges:
        if not dsu.union(u, v):
            #already connected
            #now we know there must be a cycle 
            #we can just find a way from u to v the other way around
            start = u
            end = v
            b = w
            #this can be an answer but we might find better answer
    
    path = find_cycle_path(start, end, graph)
    
    print(b, len(path))
    print(*path)
    
    



for _ in range(int(input())):
    solve()

In graph theory, bridges (or cut edges) are connections whose removal would disconnect the graph meaning they cannot be part of any cycle. Hence we can solve this problem by finding a non-bridge edge with the minimum weight. For this we will have to utilize a bridge finding algorithm (Like, Tarjan's Bridge finding Algorithm), then we can find a cycle between a non-bridge edge with the minimum weight using BFS or DFS.

econstruction (BFS/DFS): O(V + E) Complexity Analysis: - Time: $$$O(n + m)$$$ - Space: $$$O(n + m)$$$

from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc


def find_bridges(graph, N):
    discovered_time = [0] * (N+1)
    lowest_reach = [float('inf')] * (N+1)
    seen = [0] * (N+1)
    
    time = 1
    
    bridges = set()
    
    @bootstrap
    def dfs(node, parent):
        nonlocal time
        
        discovered_time[node] = time
        lowest_reach[node] = time
        time += 1
        seen[node] = 1
        
        for nbr in graph[node]:
            if nbr == parent: 
                continue

            if not seen[nbr]:
                yield dfs(nbr, node)
                
                lowest_reach[node] = min(lowest_reach[node], lowest_reach[nbr])
                
                if lowest_reach[nbr] > discovered_time[node]:
                    #this is a bridge edge
                    bridges.add((node, nbr))
                    bridges.add((nbr, node))
                    
            else:
                lowest_reach[node] = min(lowest_reach[node], discovered_time[nbr])

        yield
        
    for node in range(1, N+1):
        dfs(node, 0)
    
    return bridges
    

def find_cycle_path(start, end, graph):
    que = [start]
    visited = set([start])
    
    parent = {start : -1} # this will be useful to track our path back
    
    while que:
        curr = que.pop()
        
        if curr == end:
            break
        
        for nbr in graph[curr]:
            if curr == start and nbr == end: 
                # we dont want the direct path we want to cycle back so
                continue
            
            if nbr not in visited:
                parent[nbr] = curr # mark the next nodes come after curr
                
                visited.add(nbr)
                que.append(nbr)
    
    
    #now let’s track our path 
    path = []
    
    curr = end
    while curr != -1:
        path.append(curr)
        curr = parent[curr]
    
    
    return path[::-1] # since this path is a cycle there is no need for reversing.
    
        
        
def solve():
    n,m = map(int, input().split())
    
    edges = [] #lets store the edges
    graph = [[] for _ in range(n+1)]
    
    for _ in range(m):
        u, v, w =  map(int, input().split())

        #for the graph we realy don't need the weights
        graph[u].append(v)
        graph[v].append(u)
        
        edges.append((u, v, w))
    
    
    bridges = find_bridges(graph, n)
    
    min_edge = (-1 , -1)
    b = float('inf')
    
    # lets find the lightest non-bridge edge
    for u, v, w in edges:
        if (u, v) not in bridges:
            if w < b:
                min_edge = (u , v)
                b = w
    
    
    start, end = min_edge
    #cycle back from start to end the other way
    path = find_cycle_path(start, end, graph)
    
    print(b, len(path))
    print(*path)
    
        
for _ in range(int(input())):
    solve()