Problem Statement:
512A - Fox and Names
Solution:
The idea to solve this problem is pretty intuitive, but I make no pretence that implementing it is easy, as I had a lot of trouble trying to write a correct one.
First of all we represent each letter as a node in a directed graph, where a directed edge from u to v means that u has higher "rank" than v. In this problem we are required to build such graph using the strings provided. There are a lot of ways to do this, and some are more clever than the other. My one is particularly messy, but it does the job after some debugging and patience.
Showing posts with label Topological Sort. Show all posts
Showing posts with label Topological Sort. Show all posts
Tuesday, February 3, 2015
Monday, January 19, 2015
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!
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!
Subscribe to:
Posts (Atom)