Problem link Precompute palindromic substrings, then backtrack Let palindrome[left][right] indicate whether the inclusive substring s[left..right] is a palindrome. A substring is palindromic ex...

Problem link Approach Map each person’s name to a parent name, and keep a component size for each root. Initially, every newly encountered name is its own root with size one. For a friendship, fi...

Problem link Treat the cities as vertices and the roads as undirected edges. An itinerary is possible exactly when every city listed in it belongs to the same connected component: then a path exis...

Problem The cost of merging two adjacent files is the sum of their sizes. After every merge, the result remains in the same sequence, so an optimal plan can be split at its final merge: the files ...

Problem link Let dist[u][v] be the shortest known directed distance from vertex u to vertex v. Initialize every entry to infinity, set dist[i][i] = 0, and record the minimum weight among parallel ...

Approach Let best[v][c] be the minimum travel time to reach airport v with total cost at most c. Initialize every entry to infinity except best[0][c] = 0 for every budget c, since the start is rea...

Problem link Let dist[i][j] be the shortest known cost from city i to city j. Initially, the only known routes are staying in the same city (cost zero) and the direct bus routes. If several routes...

Problem link Degree characterization Treat each trust pair [a, b] as a directed edge from person a to person b. A town judge trusts nobody, so their outdegree is 0. Everyone else trusts the jud...

Approach The graph is directed and may contain negative edge weights, so Dijkstra’s algorithm is not suitable. Bellman–Ford stores the best known distance from vertex 1 and relaxes every edge up t...

Problem link Approach For each test case, run Dijkstra from the source s and from both endpoints g and h of the designated edge. A candidate destination x qualifies exactly when some shortest rou...