Codeforces Round #286 (Div. 1 B / Div.2 D) - Mr. Kitayuta's Technology

Problem Statement:
506B - Mr. Kitayuta's Technology

Solution:
Very interesting problem. This round indeed has challenging yet amazing problems.

Given a graph G, we want to find the minimum number of edges needed so as to satisfy a certain set of connectivity constraint between M pair of vertices. Let's first consider a simplistic view of the problem: Given a graph G containing N vertices such that G is a direct acyclic graph (DAG), what is the minimum number of directed edges needed to satisfy the connectivity requirements? The answer will always be N-1. Why? Think of topologically sorting the vertices. This DAG can be transformed to a "linked list" DAG: All vertices maintain their relative positions, and for each vertices u, v such that there is no path from u to v and vice versa, we can draw a directed edge from u to v or from v to u (it does not matter!) in our final DAG. Hence in the end we will need N-1 edges!

Codeforces Round 267 Div. 2 Problem D - Fedor and Essay

Problem Statement:
467D - Fedor and Essay

Solution:
A pretty fun problem to solve! One thing to notice is that the replacement rule is not bidirectional, i.e. if \(x_i\) and \(y_i\) are synonyms, it only says we can replace \(x_i\) with \(y_i\), but not the other way around. So in other words, we have a directed edge from \(x_i\) to \(y_i\). Each word acts as a vertex, and hence for each vertex u, we would like to know, amongst all vertices v that is reachable from u, what is the minimum number of \(R\) and minimum length of such synonym.