Codeforces Round #366 (Div. 1) - B. Ant Man

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).

Codeforces Round #360 (Div. 1) - D. Dividing Kingdom II

Problem Statement:
http://codeforces.com/contest/687/problem/D

Summary:
n < 1000 vertices, m = O(n^2) weighted edges (numbered from 1 to m), and q < 1000 queries (L, R) to consider all edges number L to R, group the endpoints of the edges into two groups 0 or 1, and minimize the weight of the edge with the largest weight having its endpoints in the same group.

Codeforces Round #356 (Div. 1) - D. Bear and Chase

Problem Statement:
Codeforces Round #356 (Div. 1) - D. Bear and Chase

Summary:
We are to maximise the probability of guessing the position of a target in an undirected graph, given that the procedure that we must follow is:
Step 1. Choose a node. The shortest distance to the target is revealed. We either guess where the target is, or go to step 2.
Step 2. Target moves to another node via an edge. Now choose a node again and the shortest distance to the target is revealed. Guess where the target is.
Initially each node has equal probability of containing the target. After Step 1, target moves to a neighbouring node with equal probability among the neighbours.

Codeforces Round #353 (Div. 2) - E. Trains and Statistic

Problem Statement:

Codeforces Round #353 (Div. 2) - E. Trains and Statistic
Summary:
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.

Codeforces Round #290 (Div. 1 A / Div. 2 C) - Fox and Names

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.

Codeforces Round #288 Problem D - Tanya and Password

Problem Statement:
508D - Tanya and Password

Solution:
An interesting graph problem, with a very insightful idea. This post is more for my self reference, but you are welcome to learn from this too.

Most of us can straight away realize that this is a graph problem, but I think what makes the problem very interesting is the choice of nodes and edges that works for this problem. If we represent each of the 3-letter string as a node, then we are presented with a NP problem of finding a hamiltonian path in the graph. However, if we represent each string as an edge instead, the problem is reduced to finding an eulerian path for which O(N) solutions exist! A very subtle and insightful problem design.

Codeforces Round #287 Problem E - Breaking Good

Problem Statement:
507E - Breaking Good

Solution:
[Off topic: btw, Breaking Bad is damn awesome!]
This problem employs an interesting trick using Dijkstra Algorithm, which is quite intuitive to discover.

First suppose there are no broken roads, i.e. every edges are valid edges. In this case, we can simply run a BFS to find the shortest path between node 1 (city) and node N (headquarter), and for all other roads not in this path, we just blow them up. However, in the problem, we can have roads which must be repaired before it can be used. Hence naturally BFS is not applicable to this case anymore and we need something else to account for the cost of repairing a road. Yet, we also need the property that the shortest path will still have the same length as the ones that are produced if we are to run BFS.

Codeforces Round #286 (Div. 1) Problem D - Mr. Kitayuta's Colorful Graph

Problem Statement:
506D - Mr. Kitayuta's Colorful Graph

Solution:
The problem can be divided into (although not mutually exclusive) parts, first one is to effectively build the connectivity information in O(N), and the second part is to manage the queries. I am not so sure about the complexity analysis for the query handling part, but the following works.

First part: building the connectivity information using disjoint set union. Here is a simple yet powerful idea I learnt from the submissions made by clever gods who had solved the problem during the contest. We start out with an empty graph G. Then we incrementally add a new edge e. This edge has a color c and has two end points u and v. Before we add the edge and connect those vertices, we examine first whether each of u and v belong to any edges with color c. Let's say u indeed has such edge, call one of them e'. Since the addition of e to u will lead to e' and e being connected, we can simply represent this connection using a disjoint set union! So upon addition of e to u, e and e' are in the same set. Notice that we only need one of such edge e', since we have the invariant that every other e' incident to u will already be in the same disjoint set as e'! This is a very powerful observation, and this simplify the construction of the disjoint set union structure to O(N) overall.

Codeforces 444A - DZY Loves Physics

Problem Statement:
444A - DZY Loves Physics

Solution:
This problem is pretty cool mathematically, learnt new stuff :)

We claim that there is always an optimal induced subgraph containing only 2 vertices (or in other words, we can find an optimal induced subgraph amongst all the edges in G(V,E) ). If this is true, then to solve this problem, we just need to find the edge in G with the maximum density, which can be done in \(O(m)\) time. So why is this claim true? Here's a proof which I learnt from the official editorial, which I will write here for my future references. But feel free to read them through :)

Codeforces 453C - Little Pony and Summer Sun Celebration

Problem Statement:
453C - Little Pony and Summer Sun Celebration

Solution:
(How did they come up with such a cute name for a problem statement, I wonder)
A pretty interesting graph problem, which is more of a test on structure construction. The official editorial to this problem is already perfectly clear, I'm writing this purely for my future references.

To solve the problem the brute force way, one can choose any node as a root, and run a DFS on this root, in the following manner: From root, visit the next available odd-parity node, and come back. This works because every nodes in between the path between root and the odd-parity node will be visited twice as the person go forth and back to root. Hence each time we will be eliminating one odd-parity node from consideration, which is nice. Finally, we check how many times we visited root, and if the parity does not match, we simply remove a root node on the tail of the path (i.e., the person did not come back to the root eventually). However, this approach does not guarantee the final path to be within 4n limit.

Codeforces 459E- Pashmak and Graph

Problem Statement:
459E - Pashmak and Graph

Solution:
A graph problem which solution does not require building any graph at all :P Things to note are that the edges are directed, and all valid path are strictly increasing. We can view this problem as an extension to the classical longest increasing subsequence, but instead of a nice linear array, we have a directed graph here. Let's define L[u] as the longest increasing weight path starting from vertex u.

Codeforces 466E - Information Graph

Problem Statement:
466E - Information Graph

Solution:
The main idea is to build the whole relationship graph before answering the queries of type 3. We can make use of the fact that if we run DFS on the root of a graph and maintain the time information when we first enter and leave a certain node, we can check whether u is a parent of v on the DFS tree in O(1) by comparing the time information. While building the information graph, we also use a disjoint set union structure to maintain information about the parents of each nodes in the connected components currently being built. Finally, a node x receives a packet with index i if and only if x is in between the vertex u that received that packet and the vertex v that was the parent of u when it received the packet. After we build the graph and the disjoint set union structures, we can serve each queries of type 3 in O(1).

Codeforces Round: Goodbye 2014

A really nice set of problems :) Well done for the problem setters!
Have just solved problem A to E, loved them so far. Haven't tried F and G yet.

EDIT: just found out that the official tutorial has been released, and it looks really good!

Problem A 
Problem Statement:
500A - New Year Transportation

Solution:
Wow, a pretty intimidating problem A!

The idea is very straight forward, since \(a_i\) is actually a representation of a directed edge connecting vertex \(i\) with \(i+a_i\). Simply run a DFS from node 1 and return YES if we reached the destination node.

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.

Codeforces Round 270 Problem D - Design Tutorial: Inverse The Problem

Problem Statement:
472D - Design Tutorial: Inverse The Problem

Solution:
Pretty interesting problem. Given a matrix of distances between nodes dist[u][v], return a weighted tree that satisfies this matrix. Here is my approach (I believe this is not the most efficient (or even efficient) or clever idea, but it worked :P)

Codeforces Round #263 Div. 1 Problem D - 2 SAT problem

Problem Statement:
461D - Appleman and Complicated Task

Solution:
I took a few days to solve this haha. The idea is already explained pretty clearly in the official tutorial:
1. Consider cell(i,j). This cell is in the neighbourhood of cell(i-1, j), hence it must fulfil the requirement: cell(i-1,j-1) XOR cell(i-1, j+1) XOR cell(i-1, j-2) XOR cell(i,j) = 0   (so that the number of cell with 'o' is even). This means that cell(i,j) can be totally determinable from those corresponding cells.
2. From 1, we can prove by induction that if the first row of the table is known, then we can fully determine the rest of the rows using the above relationship.
3. Another key observation: cell(i,j) is determined by a sequence of consecutive odd or even-indexed elements of the top row. To see this, you need to draw out the relationship and find the pattern.

Treeland Tour (Codeforces Round #279 Div. 2 Problem F)

Problem Statement:
Codeforces Round #279 Div. 2
Problem F. Treeland Tour

Solution:
The editorial for this round is already up and quite clearly written :)

I think this problem is pretty tedious to get right.. The dynamic programming idea is as follows:
- the "state" of our DP table will be the edges. Pretty interesting.
- Let M(u,v) be the maximum number of concerts if the path ends with edge (u,v). Also, we want vertex v to be where the last concert is held.
- M(u,v) can be calculated by traversing down the tree rooted at u. We traverse down the children of u which does not start with v.
- In each subtree, as we traverse down using DFS, we find an edge (x, y) such that r[y] is less than that of r[v]. Then we update M(u,v) = max(M(u,v), M(x,y)).
- Don't forget to take care of leaves.

Topcoder SRM 638 Div. 1 Hard - CandleTimer

Follow up to this post

Problem Statement:
Topcoder SRM 638 Div. 1 HARD - CandleTimer

Solution:
Just solved this problem, and I must say that this problem is very challenging (at least for me) in a sense that there are quite a lot of stuff going on. The way the candles are burnt rings some bells to the intuition behind Dijkstra algorithm, and indeed the way to solve this problem is through some modification of Dijkstra.

Codeforces Round #277 (Div. 2) Problem E. LIS of Sequence

Follow Up to this post.

Problem Statement:
E. LIS of Sequence

Solution:
This problem is quite nice to think about :D. Before attempting this problem, it might be useful to have a knowledge beforehand on how to solve LIS problem in \(O(N\lg{N})\) complexity using binary search.

This problem is more or less an extension to that idea. First we have an array of stacks stack[i] which is initialized with the following conditions:
1. the size of the array is initially 1.
2. push \(a_1\) into stack[0], so stack[0] contains \(a_1\).
Now we iterate from \(a_2,\ldots\) onwards till the end of the elements:
1. find the position of the maximum element amongst all elements on top of the stacks such that \(a_i\) is equal or larger.
2. if such position exist, push our current \(a_i\) into that stack. Otherwise, we add a new stack (hence incrementing the size of the array by 1) and push \(a_i\) to that newly created stack.

Codeforces Round #277 (Div. 2)

Problem C:
C. Palindrome Transformation

Solution:
Divide the string into two halves. Depending on which half \(p\) is, we can implement a greedy (an very intuitive) strategy to make that half exactly mirror the other half.