Problem Statement:
http://codeforces.com/contest/704/problem/B
Summary:
We are given a graph with nodes 1 to n, such that the cost of going from node i to node j is:
1) |x[i] - x[j]| + c[i] + b[j] if j < i
2) |x[i] - x[j]| + d[i] + a[j] if i < j.
Given a start node s and an end node e, find a hamiltonian path from s to e (hamiltonian path: a path that visits all nodes in the graph once) such that the total cost is minimised. (Also, x[i] is monotonically increasing. n <= 5000).
Showing posts with label Directed Acyclic Graph. Show all posts
Showing posts with label Directed Acyclic Graph. Show all posts
Monday, August 15, 2016
Saturday, June 4, 2016
Codeforces Round #353 (Div. 2) - E. Trains and Statistic
Problem Statement:
Codeforces Round #353 (Div. 2) - E. Trains and StatisticSummary:
A graph with node 1..n such that node i have an edge to every nodes in i+1 to a[i] inclusive (where i+1 <= a[i] <= n). Calculate the sum of all the length shortest path from every pair of nodes.
Wednesday, March 11, 2015
Codeforces Round #295 (Div. 1 B / Div. 2 D) - Cubes
Problem Statement:
521B - Cubes
Solution:
This is a nice problem. Firstly, you can build a DAG out of the stacks of cubes, in which for each cube C(x, y), draw a directed edge from C to all C' with coordinates (x-1, y+1), (x, y+1) and (x+1, y+1). We also keep track of the total number of in-degree of each cubes, for which stored in an array support[i], which intuitively means cube i is supported by support[i] cubes.
521B - Cubes
Solution:
This is a nice problem. Firstly, you can build a DAG out of the stacks of cubes, in which for each cube C(x, y), draw a directed edge from C to all C' with coordinates (x-1, y+1), (x, y+1) and (x+1, y+1). We also keep track of the total number of in-degree of each cubes, for which stored in an array support[i], which intuitively means cube i is supported by support[i] cubes.
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!
Tuesday, December 16, 2014
Codeforces Round #282 Div. 1 Problem C - Helping People
Problem Statement:
494C - Helping People
Solution:
Another challenging problem, with a very interesting DP solution. The official editorial to this round is very detailed and well-written :)
The idea is to build a tree-like directed acyclic graph (DAG) and keep track on some cumulative probabilities.
To find:
the expectation of maximum element in [1..N]. This is equal to sum of P[X=x] * x, for all x possible.
Structure:
Each segments can be thought of as nodes. We first add a root to the DAG, which will be our entry point on traversing this graph. This root is a segment [1 .. N] with probability of being chosen 0. Call this node as e. Afterwards we sort the segments in increasing left index, and breaking ties with decreasing right index. Then we incrementally build the DAG as follows: For each segment u, we consider each segment v in increasing order. Add a directed edge from u to v if v is fully contained by u, but cannot be contained by any segment w that has already been pointed by u.
494C - Helping People
Solution:
Another challenging problem, with a very interesting DP solution. The official editorial to this round is very detailed and well-written :)
The idea is to build a tree-like directed acyclic graph (DAG) and keep track on some cumulative probabilities.
To find:
the expectation of maximum element in [1..N]. This is equal to sum of P[X=x] * x, for all x possible.
Structure:
Each segments can be thought of as nodes. We first add a root to the DAG, which will be our entry point on traversing this graph. This root is a segment [1 .. N] with probability of being chosen 0. Call this node as e. Afterwards we sort the segments in increasing left index, and breaking ties with decreasing right index. Then we incrementally build the DAG as follows: For each segment u, we consider each segment v in increasing order. Add a directed edge from u to v if v is fully contained by u, but cannot be contained by any segment w that has already been pointed by u.
Subscribe to:
Posts (Atom)