A virtual contest was held this week. Problems were taken from various sources. Three of the four problems were few classic but interesting applications of shortest path algorithms. The last one was a relatively simpler graph theory problem.
Abridged Statement: You are given $N \, (\le 10\,000)$ and an allowed set of digits $A$. Find the smallest multiple of $N$ that consists of digits only from $A$.
Solution: Make a graph where nodes are numberes from $0$ to $(N-1)$. For all $u \in [0, N)$ and $d \in A$ add directed edges from $u$ to $(10u + d) \mod N$ with label $d$. Now the minimum multiple of $N$, that consists only of digits from $A$ is the string that you will get by walking on the lexicographically smallest shortest path from some node $d \mod N \, (d \in A)$ to the node $0$.
Abridged Statement: You are given a directed weighted (both nodes and edges have weights, node $u$ have weight $f_u$ and edge weight is denoted by $t(u, v)$). "Average" of a cycle $c_1 \rightarrow c_2 \rightarrow \ldots \rightarrow c_k \rightarrow c_{k+1} = c_1$ is defined as: $$\frac{\sum_{i=1}^{k}f_i}{\sum_{i=1}^{k}t(c_i, c_{i+1})}$$ Find the maximum average cycle.
Solution: We will binary search the answer. The answer is greater than some guessed average $g$ iff there exists some cycle $c_1 \rightarrow c_2 \rightarrow \ldots \rightarrow c_k \rightarrow c_{k+1} = c_1$ whose average is $> g$. That is: $$\frac{\sum_{i=1}^{k}f_i}{\sum_{i=1}^{k}t(c_i, c_{i+1})} > g.$$ By doing some trivial algebraic manipulation we arrive at: $$\sum_{i=1}^{k}f_i > g \cdot (\sum_{i=1}^{k}t(c_i, c_{i+1}))$$ $$\sum_{i=1}^{k}f_i > \sum_{i=1}^{k} g \cdot t(c_i, c_{i+1})$$ $$\sum_{i=1}^{k}f_i - \sum_{i=1}^{k} g \cdot t(c_i, c_{i+1}) > 0$$ $$\sum_{i=1}^{k} g \cdot t(c_i, c_{i+1}) - \sum_{i=1}^{k}f_i < 0.$$ We can pair up each term from those two $\sum$ and get: $$\sum_{i=1}^{k} g \cdot t(c_i, c_{i+1}) - f_i < 0.$$ And Checking this is equivalent to checking if there is any negative cycle in such a graph where everything is same as the given graph except there is no weight on the nodes in the new graph and the weight of the directed edge from $u$ to $v$ is $g \cdot t(u, v) - f_u$.
Abridged Statement: For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice.
Solution: To solve for $u$, take the shortest path tree rooted at $u$. For each non-tree edge, if the endpoints of it belong to two subtrees of two different children of $u$ then relax the answer by the cycle $u \leadsto \text{one end} \leadsto \text{other end} \leadsto u$.
Abridged Statement: The group of people consists of N members. Every member has one or more friends in the group. You are to write program that divides this group into two teams. Every member of each team must have friends in another team.
Solution: Take any arbitrary spannning tree and put nodes at odd depth in the first set and others in the second.