Codeforces 441E - Valera and Number

Problem Statement:
441E - Valera and Number

Solution:
Another tedious DP problem, but it has some interesting ideas. The official editorial to this problem is pretty easy to understand.

There are two types of operation we can have on a given bit string: left shift and increment by one. Notice that since there are at most 200 increment operations, we can show that it suffices to keep track of the last 8 bit of the bit string. This is because in each increment operation, we can have either:

Codeforces 441D - Valera and Swaps

Problem Statement:
441D - Valera and Swaps

Solution:
This problem is somewhat tedious in a sense that we need accuracy in swapping indexes and content of arrays.

The idea to solve this problem is from the (might be routine, but not so obvious on first try) observation that the minimum number of swaps required to place every element to its correct position is equal to the total number of elements in the "misplaced chain" minus one. What I mean by the misplaced chain is: Let a[i] be the elements in the sequence, and p[i] be the index of element i in array a[i]. If we start from position cur = i, and trace down all elements cur = p[cur], we will get a chain of misplaced elements. There will be several disjoint chains, and hence we can total up the total minimum number of swaps necessary to restore each element in each chain to its correct position, call this sum S. We can compare S and m, which leads us to three cases:

Codeforces Round #288 Problem E - Arthur and Brackets

Problem Statement:
508E - Arthur and Brackets

Solution:
The problem statement in my opinion is not exactly clear. It should have been stated that the "corresponding closing bracket" must be the first available closing bracket closest to the open bracket, i.e. the a pair of brackets should not be intertwining with other pair of bracket, as demonstrated below:
( [ ) ]      /* not a valid bracketing */

With that the problem is more manageable. Let D[i][j] is set to 1 if we can build the required bracketing using i-th to j-th constraints. Then we have:
D[i][j] = OR of all k [ D[i+1][i+k] AND D[i+k+1][j] ].

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 #287 Problem D - The Maths Lecture

Problem Statement:
507D - The Maths Lecture

Solution:
An insightful use of dynamic programmings in number theoretic combinatorics...

The idea is for each length i, we wan to compute how many y with length i are there such that it is exactly divisible by k. Hence for each y with length i, digit 0-9 can be padded in front of y to form x. However, we do not want any y to be a suffix of another y, as it will lead to double counting of x. How should we approach the problem?

How does it feel to be an Ironman?

Last three days I had been writing a 3D rendering engine using Javascript and HTML5 Canvas. It was an accidental decision, I was thinking of writing a game that I did not realize need a 3D rendering capability, so I decided to try rendering cubes. Alas I did the whole thing using linear algebra and perspective projection, and now I have a functional engine that can render any type shapes defined using points and segments. However it does not support surface rendering, only wireframes. The result is pretty satisfying! The debugging was extremely challenging as it involved trigonometric functions and matrices, but the end product was very pleasing to see. Here you can see the demo to the engine, which I titled:

link:  "How does it feel to be an Ironman".

(Note: for more fluid rendering, I recommend using Google Chrome. The computation is indeed pretty heavy. )

Codeforces 442C - Artem and Array

Problem Statement:
442C - Artem and Array

Solution:
As per normal, greedy problem is difficult to fathom, but always a nice exercise for this lazy mind such as mine.

First and foremost, we should use a random access linked list to solve this problem. You can create a random access linked list by using an array representing the nodes, and use the array indexes to point to each other. So by representing linked list in an array, we can have the best of both worlds (at least for this problem).

Codeforces Round #286 (Div.1 C / Div.2 E) - Mr. Kitayuta vs. Bamboos

Problem Statement:
506C - Mr. Kitayuta vs. Bamboos

Solution:
A very nice problem, another problem that I would never solve if not for the official tutorial :D The official tutorial is very well-written, so you should check them out! Kudos for the problem setter and the writer for the editorial! Only read this if you are still stuck :P This post is more for my self-referential note.

Since there is no easy way to construct an instance of the solution with a global minimum, one should think, is it easier if we guess the answer instead? Hence we turn ourselves to binary search. Let's assume we have a value X, we have a nice property on the search space: if it is possible to hit the bamboos such that at the end of M day all the bamboos are at most of height X, then all bigger X will be feasible, hence we want to find smaller X. Otherwise, if X is not feasible, then all smaller X will not be feasible too, hence in this case we want to find bigger X instead. This forms the basis of the binary search.

Codeforces 442B - Andrey and Problem

Problem Statement:
442B - Andrey and Problem

Solution:
An interesting mathematical problem. The official editorial to this problem is excellent, so this post is more for my self reference.

First of all find a neat representation of the function we are going to optimize:
Let $K = \{ p_1, p_2, \ldots, p_k \}$ be the probabilities of friends chosen, then the probability of having one problem is:
$F = p_1(1-p_2)(1-p_3)\ldots (1-p_k) + (1-p_1)p_2(1-p_3)\ldots (1-p_k) + \ldots$
       $+ (1-p_1)(1-p_2)(1-p_3)\ldots p_k$,
which can be simplified as
$F = (1-p_1)(1-p_2)\ldots (1-p_k) \{ \sum_{i=1}^{k} \frac{p_i}{1-p_i}  \}$
Let $P = (1-p_1)(1-p_2)\ldots (1-p_k)$ and $S =  \sum_{i=1}^{k} \frac{p_i}{1-p_i}$.

Codeforces 442A - Borya and Hanabi

Problem Statement:
442A - Borya and Hanabi

Solution:
Not an easy problem for me.. The first and easiest thing to say is there are 10 type of hints and hence we can do a complete search on each $2^{10}$ combination of them. Now the hardest part is that, given a combination of hints, check whether they will allow us to differentiate amongst all the cards. For me this is not an obvious task.. One observation is that if a type of cards occurs more than once, we can consider them as one. This is because given a hint (color or value) in which the type belongs to, we will open up all cards belonging to that type, which can be considered as one set. Each type of cards belong to only one set at most, and these sets are disjoint, hence the observation is valid. So it suffices to keep track on the type of cards present.

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 Round #286 (Div. 1 A / Div. 2 C) - Mr. Kitayuta, the Treasure Hunter

Problem Statement:
506A - Mr. Kitayuta, the Treasure Hunter

Solution:
This is a standard dynamic programming problem, with a non-standard twist!

Firstly, let's forget about the constraints, define M(i, len) be the maximum number of gems can be collected if we start from island i after making a jump of length len. This is simply M(i, len) = max of  {M(i+len-1, len-1), M(i+len, len), M(i+len+1, len+1)} + [whether there is a gem in island i or not]. But we have a problem: Doing this will take $O(N^2)$ where $N \leq 30000$, which will not going to cut it in 1 second time constraint.

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 449C - Jzzhu and Apples

Problem Statement:
449C - Jzzhu and Apples

Solution:
The approach to this problem is already very clear in the official editorial, this is mainly written for my self reference.

The strategy to solve this problem is through a constructive algorithm. Firstly we ignore all primes P bigger than $\lfloor \frac{N}{2} \rfloor$ since those primes will not be able to matched. For all other P less than  $\lfloor \frac{N}{2} \rfloor$, we iterate from the biggest prime down to the lowest prime:

Codeforces 449B - Jzzhu and Cities

Problem Statement:
449B - Jzzhu and Cities

Solution:
An interesting graph problem. In both Bellman-Ford and Dijkstra single source shortest path algorithms, we have the concept of "relaxed" edges, in which intuitively can be viewed this way: We are given a set of balls connected together with strings. If we choose a ball as the "source" and pick it up, other balls will be hanging with some strings tight and some strings slack. The tight strings are the "relaxed" edges in single source shortest path algorithm. Those which are not relaxed can actually be removed from the shortest path graph.

Codeforces Round 285 Div. 1 Problem D - Misha and XOR

Problem Statement:
504D - Misha and XOR

Solution:
Another tedious problem. The strategy is to apply the idea of linear independence. Let's say we already transformed every decimal strings into binaries, and place them in rows such that they form a matrix of 0s and 1s. We want to apply Gauss Elimination such that we achieve linear independence between the rows. Eg :

numbers     binaries
7           111
5           101

initial matrix:
111
101

linear independence between rows, after Gauss Elimination:
111
010

Codeforces Round 285 (Div.2 E / Div. 1 C) - Misha and Palindrome Degree

Problem Statement:
504C - Misha and Palindrome Degree

Solution:
The official editorial to this problem is pretty much clearly explained. This post is mostly a self-note.

In a palindrome, there must be at most only one element with an odd number of occurrences, i.e. the rest of the elements must occur in even number of time. Next, given an array $a_i$, we can first match all $a_i$ with $a_{N-i-1}$ from leftmost element, and stop when they differ.

Codeforces Round 285 (Div. 2 D or Div. 1 B) - Misha and Permutations Summation

Problem Statement:
504B - Misha and Permutations Summation

Solution:
Another nice problem. Firstly we need to exactly understand how to compute the "position" of a certain lexicographical permutation, where the convention is that P(0) = [0,1,2,3,...,n-1] while P(n!-1) = [n-1,n-2,...,0].

Let's consider the following example:

pos: 0 1 2 3 4 5 6
a  : 4 5 3 6 1 2 0

Now, we know that for '4' to reach '0' position, first from [0,1,2,3,4,5,6], it has to go to [1,0,2,3,4,5,6], then to [2,0,1,3,4,5,6], then to [3,0,1,2,4,5,6] and finally [4,0,1,2,3,5,6]. In reach each subsequent permutation state, each of them needs to go through 6! lexicographical permutations, so in total we need 4 * 6! to move 4 from its original position in P(0) to position 0. We iteratively compute on subsequent elements, in exactly the same way using the same reasoning. However, since each iteration removes one number from the next subsequent consideration, we need an efficient way to check what numbers have been removed. Here segment tree plays the hero again! Without segment tree, in total we will have $O(N^2)$, but implementation using segment tree will push it down to $O(N\lg{N})$.

Codeforces Round 285 (Div. 2 C or Div. 1 A) - Misha and Forest

Problem Statement:
501C - Misha and Forest

Solution:
An interesting mix of tree structure and linear algebra. Since we are given the pair $(\text{degree}_v, s_v)$ for each v, we can approach it in an intuitive manner:
1. We will maintain a graph G with vertices v but with no edges just yet. So initially all vertices in G has no neighbouring vertices.
2. Iteratively, we would like to find a vertex v such that the difference between the number of neighbours it currently has and $\text{degree}_v$ is at most 1. This means that v is short of one vertex. Furthermore, this means that we can determine what vertex is that exactly in O(M) where M is the number of adjacent vertices v currently has, as follows:

SPOJ MORSE - Decoding Morse Sequences

Problem Statement:
SPOJ - MORSE

Solution:
This is a very... tedious problem. The idea is to build a trie structure for efficient search of words in the given dictionary. Since each letters in the dictionary is at most only 20 letters long, which can contain up to 26 letters, we can build the trie structure in O(M) time where M is the total sum of the lengths of the words.

Next, we do a depth first search like algorithm on the morse code (defined as morse[i]), starting from i = 0. Initially we also have a pointer cur pointing to the root of the trie. So the states of the algorithm is S(i, cur), where S(i,cur) gives us the number of ways to match morse[i..N] with words from dictionary.

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

parquer - a neo classical space shooting game

I've just completed writing a new game I call parquer, which features an inertial physics and a 360 shooting experience. It's pretty fun to play and looks quite good! I've also used quadtree to handle collision checking between the bullets and the enemy dots, which was pretty fun work. Here is the game, check it out :D

Be sure in the lookout for the parquers, which grant unprecedented powers to their beholder!

Link:
parquer

Codeforces 451D - Count Good Substring & 451E - Devu and Flowers

451D - Count Good Substring

Problem Statement:
451D - Count Good Substring

Solution:
Simple $O(N^2)$ check will be too slow, so there must be a better way, and indeed we have an
(O(N)\) solution that makes use of several observations. Firstly, if we compress the given string, you will always end up with an alternating sequence of 'a' and 'b's. This means that if a substring of our choice starts and ends with the same letter, it is definitely is a good palindrome. Secondly, a substring [i..j] will have an odd length if parity of i and j are the same, otherwise it will have an even length.

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 453B - Little Pony and Harmony Chest

Problem Statement:
453B - Little Pony and Harmony Chest

Solution:
Learnt new thing thanks to the official editorial :)

The low constraints for both n and $a_i$ suggests that we can do a complete search, and in fact we can use a bitmasking technique to perform this search more efficiently. Firstly, to minimize $|a_i-b_i|$, we would like to choose $b_i$ that can do better than just simply assigning 1 to $b_i$. This means that $b_i$ should be between [1..$2a_i-1$], and thus 2*30-1 = 59 marks the upperbound for $b_i$. Our strategy would be simply try each of these 59 numbers on each i, but simply trying all combinations would be too slow. So what we can do a dynamic programming approach: d[i][bm] be the minimum possible $\sum_{k=1}^{i} |a_k-b_k|$, while bm indicates the bitmask, where if k-th bit is on, then we have assigned number k a $b_i$. However, using such bitmask prove to be too big in space, since bm can go up to $2^{59}$. We can do better, but just bitmasking the prime factors that have been used (i.e. if bit k is set, then some $b_i$ is divisible by k-th prime)! There are only 17 primes in [1..59], so we reduced the bitmask states to $2^{17}$ :D

Codeforces 455C - Civilization

Problem Statement:
455C - Civilization

Solution:
An nice problem, but my implementation is a bit messy :P

The most important observation that greatly simplify the problem:
If node u has the property such that for every v reachable from u, $max_{v \text{ reachable from } u} \{ d(u,v) \}$ is minimum, then u must be on the longest path in that connected component. Furthermore, u must be on the middle of that path.

Firstly, why do we want to find such node u? We can think a node with that kind of property as the "midpoint" or "center" of the whole tree, where d(u,v) will be analogous to the "radius" of the tree. So when we have to merge to connected component, all we need to do is to connect the two "centers" of the connected components, and it is guaranteed that the resulting connected component will have the minimum longest path possible.

Codeforces 455B - A Lot of Games

Problem Statement:
455B - A Lot of Games

Solution:
An interesting game theory problem. As usual, game theory problems tend to be pretty creative. First of all, we need to build a prefix tree using all the strings, which can be done in $O(N)$. The root of the tree is an empty string, which is also the initial state of the game. The tree hence represent the graph of valid moves on each state of the game. We want to know, assuming both players play optimally, whether First can force his way to win and also whether he can lose a given game. We can use Sprague Grundy Theorem, but for this particular problem it is not necessary, as we can use a simple dynamic programming reasoning. First denote win[u] and lose[u] as the table which tells us whether the current player who has to move at state u can eventually win or lose. Suppose we want to fill up win[u], we check all states v that is directly pointed by u, and win[u] is only true if and only if there is a state with win[v] which is false. This reasoning also applies for filling up lose[u].

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 459D - Pashmak and Parmida's Problem

Problem Statement:
459D - Pashmak and Parmida's Problem

Solution:
One interesting use of segment tree. The idea is to first build left[i] and right[i] arrays, where left[i] = f(1,i,$a_i$) while right[i] = (i,n,$a_i$). Then realize that both left[i] and right[i] is at most $10^6$, which is good because we can build a segment tree on them!

Codeforces 463D - Gargari and Permutations

Problem Statement:
463D - Gargari and Permutations

Solution:

An interesting extension to the idea of longest common subsequence. By simply extending the classical $O(n^2)$ longest common subsequence algorithm to $k$ strings, we have an $O(kn^2)$ run time complexity.

Codeforces 463E - Caisa and Tree

Problem Statement:
463E - Caisa and Tree

Solution:
The approach to solve this problem is simply a brutal and forceful one :P

First of all, factorize all a[i]. Then, traverse the tree from the root. On each node, we maintain an array index[f], which means the index of the most recent node we encountered such that a[index[f]] is divisible by f. For each node v, the answer to query type 1 is simply the closest node index[f] to v amongst all f that divides a[v].

Codeforces 465E - Substitutes in Number

Problem Statement:
465E - Substitutes in Number

Solution:
A nice DP problem. Let val[i] be the "real" value of digit i. At first, val[i] = i, since every digit is not yet replaced by any strings. We compute val[i] after every replacement operations have been carried out, then in the end we can just iterate through the original string of digits $s$ and replace each digit i in $s$ by val[i].

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 284 Div.1 Problem D - Traffic Jams in the Land

Problem Statement:
498D - Traffic Jams in the Land

Solution:
This problem abuses segment tree so bad :)

The idea is to build 60 (which is gcd of 2,3,4,5,6) segment trees, each segment tree i answers the particular query: what is the time needed to pass through roads in [L..R] given that I start at time T = i mod 60. As such, we can serve all queries in $O(N\lg{N})$ time. The hardest part is of course to implement the trees (or plant the forest).

Live Archive 6831 - Knights of the Round Table

Problem Statement:
6831 - Knights of the Round Table

Solution:
Essentially a combinatorics problem, and hence pretty mathematical, but can be solved intuitively. To simplify the problem let's label the knights from 1 to K as well, where the knight's label determines which seat he is supposed to sit on. To get the idea on how to solve this problem, let's discuss the following test case:

Codeforces Good Bye 2014 Problem F - New Year Shopping

Problem Statement
500F - New Year Shopping

Solution:
A pretty tough problem which solution employs a very clever divide and conquer strategy. Learnt cool stuff :D.

Let's suppose that all the items are already sorted by $t_i$ in increasing order. We know that item i will be available in the time segment $[t_i,t_i+p-1]$. Suppose that for each time $T$, we know which are the segments that contain $T$, i.e. the set of i such that $T \in [t_i,t_i+p-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.