Codeforces Round 267 Div. 2 Problem E - Alex and Complicated Task

Problem Statement:
467E - Alex and Complicated Task

Solution:
We maintain an array P and a set S, and we consider the elements from left to right:
1. If $v = a_i$ is not in S yet, add it in and note its index. Hence S will store the index j of the first occurrence of the number $v$.
2. Else, we set P[i] to index of j of $v = a_i$ we stored in S.
3. If between P[i] and i there exist P[j] that is less than P[i], then the element P[j], P[i], j, and i forms one desired sequence! Store them and reset S.

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 284 Div.1 Problem C - Array and Operations

Problem Statement:
498C - Array and Operations

Solution:
Another interesting max-flow problem, but I think coming up with the correct model may require some level of familiarity with the concept and intuition, since the runtime complexity analysis can be a bit subtle.

The clever idea behind this problem is to consider each prime one by one. We start out with a source S and a sink T. Then since $i_k + j_k$ is guaranteed to be an odd number, we conclude that $i_k$ and $i_j$ has different parity, i.e. one is odd, and another is even. So we actually have a bipartite matching task, between the odd-indexed and the even-indexed $a_i$s. From here, we build a graph as follows:
1. Choose a prime $p$.
2. For each pair of odd indexed $a_i$ and even indexed $a_j$, we find the maximum number of times each of them can be divided by $p$, call it n and m respectively.
3. Next, we connect S to $a_i$, $a_i$ to $a_j$ and $a_j$ to T.
4. The capacity of the edges are set as follows:
    - capacity of (S, $a_i$) is n.
    - capacity of ($a_j$, T) is m.
    - and capacity of ($a_i$, $a_j$) is the minimum of n and m.

TopCoder SRM 371 Div. 1 Medium - ChessMatchup

Problem Statement:
TopCoder SRM 371 Div. 1 Medium - ChessMatchup

Solution:
Just learnt Kuhn-Munkres algorithm, and tried a related problem. The problem is a straight forward modification of maximum weight perfect matching. Here is an implementation:

Codeforces Round 272 Div. 1 Problem D - Dreamon and Binary

Problem Statement:
477D - Dreamon and Binary

Solution:
A loaded DP problem.. And it features an interesting use of suffix array prefix doubling technique. The official editorial to this problem seems to be quite detailed, but somehow I find it a bit hard to understand. You may find my explanation even more confusing, but hopefully still useful.

Codeforces Round 284 Div. 1 Problem B - Name That Tune

Problem Statement:
498B - Name That Tune

Solution:
A tough problem, not only because it is a conceptually difficult problem on probability, but also coupled by the fact that the problem constrain is very, very tight. In fact I have rewrote my implementation, which all are based by the idea described in the official editorial, just to reduce constant term in the running time complexity. But a good problem nevertheless :)

DP state that works here is as follows:
Let D[i][k] be the probability of the person guessing i-th song exactly at time k seconds. The base case for D is that of D[0][0] which means guessing none of the song exactly at time 0 second.

Codeforces Round 271 Div. 2 Problem E - Pillars

Problem Statement:
474E - Pillars

Solution:
This problem has a very interesting use of segment tree in combination with DP. The DP idea is very standard: let f[i] be the maximum length of jumps using pillars from [1..i], ending at i. Then f[i] = max of f[j] + 1, for all j such that $|h_i-h_j| \geq d$. Then what's left is to find an efficient way to find those j that satisfies the requirement, and at the same time, find the maximum f[j] amongst all such j. This is where the segment tree comes in.

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 269 Div. 2 Problem D - MUH and Cube Walls

Problem Statement:
471D - MUH and Cube Walls

Solution:
And interesting string matching problem since it does not so obviously look like one. For the $a_i$ and $b_i$ given, store $s_i$ and $p_i$ as follows: $s_i = a_i - a_{i-1}$ and $p_i = b_i - b_{i-1}$, which are basically array of differences. Then the problem reduces to finding occurrences of p in s, which can be done efficiently in $O(N)$ using KMP algorithm. Don't forget about one special case where b has only one element.

Codeforcees Round 283 Div. 2 Problem E - Distributing Parts

Problem Statement:
496E - Distributing Parts

Solution:
This is more for self-reference, I suggest you read the official tutorial on Codeforces for a better discussion on this problem.

This problem is a bipartite matching problem: match smaller "job" segments into bigger container "worker" segments, where each worker segment has certain capacity. If we model each segments as vertices, then we have a graph with $V$ vertices. This problem cannot be solved efficiently using maxflow algorithm, since V can be very huge, hence there must be some greedy idea behind it. And as I learnt from the editorial, the idea is to consider both jobs and workers in increasing order of their lower bounds. In this iteration, we keep track of a set S of workers that we have encountered, which has the following invariant:
For all i, by the time we reach i-th segment, the lower-bound of this segment is always bigger or equal to any lower bounds of segments in S.

Hence if the i-th segment we are facing is currently a job segment, we just need to find a worker segment in S that has a bigger upper bound than that of the job segment. If there are multiple choices, we must choose the lowest one available. I think this choice can be proven to yield optimal matching by exchange arguments.

If the implementation of S is done by using RB tree, the running time of this algorithm will be $O(V\lg{V})$.

Codeforces Round #283 Div. 2 Problem D - Tennis Game

Problem Statement:
496D - Tennis Game

Solution:
Another problem where harmonic series comes into the picture! Just realized on how to solve this problem after the contest finished :P

Firstly build 2 arrays of cumulative scores of both players. Then we try every possible t from 1 to N:
1. We search for all positions in which the set ends using binary search several times. At any junction, if we cannot find the desired cumulative scores in which a set can end, it means that t is not valid.
2. Keep track on the scores of of the player, and who scored the last point.
3. t is valid iff the scores are not equal, and the last player who scored the last point is also the one who have higher score.

SPOJ TOURIST - Tourist

Problem Statement:
SPOJ - TOURIST

Solution:
Seems like a lot of work, seems like a some graph problem, seems like something convoluted... But once you've found the enlightenment, this is a pretty nice DP problem.

Firstly, realize that we can rephrase the problem as finding two paths from top-left corner (0,0) to the bottom-right corner (H-1, W-1) that maximizes the number of '*' covered. Then, realize that the length of the path is constant, H+W-2, no matter how we move.

UVa 11167: Monkeys in the Emei Mountain

Problem Statement:
UVa 11167 - Monkeys in the Emei Mountain

Solution:
A pretty tough maxflow problem. Oh yes, this is a bipartite matching problem between N monkeys and 50000 time intervals. The simplest way to think about this problem is to have N nodes representing monkeys, 50000 nodes representing time intervals, and two nodes S and T which are source and sink respectively. A monkey has to drink v times, hence we add an edge between S and that monkey with capacity v. This monkey can drink from time interval s to t, so we add an edge to each time interval from s to t by capacity 1 each. Finally, each time interval can only be shared between M monkeys, so for each time interval we add an edge to T with capacity M. The maximum flow from S to T will give us the maximum bipartite matching between the monkeys and the time intervals. If this maximum flow exactly equals to the total times all monkeys have to drink, we have found a valid matching.

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.

Codeforces Round #282 Div. 1 - Obsessive String

Problem Statement:
494B - Obsessive String

Solution:
I like this problem, and for me it is a particularly challenging one. Thankfully the editorial for this round is very well-written and detailed. I learnt quite a lot from this problem.

Firstly we need to find an efficient way to mark all occurrence of t in s, and here we can employ the $O(N)$ Knuth-Morris-Pratt string matching algorithm. We keep track of all indexes i of s such that s[i-|t|+1 .. i] matches t exactly in an array g[i], setting such indexes g[i] as 1, and 0 otherwise. The hardest part is to come up with the right DP state. Here, the one that will work is: let f[i] be the number of ways to choose the substrings from [1..i], such that the last (right-most) substring ends with index i.

TopCoder SRM 640 Div.1 550 - MaximumBipartiteMatchingProblem

Problem Statement:
SRM 640 Div.1 550 - MaximumBipartiteMatchingProblem

Solution:
A very mathematical problem I guess, we will get to optimise a quadratic function. Firstly, take ans vertices from both n1 and n2, and match them like this:

ans pairs of vertices:

o o o o o  -> upper-end
| | | | |
o o o o o  -> lower-end

That means we have (n1-ans) unmatched vertices from the first set F, and (n2-ans) unmatched vertices from the second set S. We cannot match any of these unmatched vertices amongst themselves, because it will immediately increase the number of bipartite matching. So we can only match them with those ans paired vertices

TopCoder SRM 641 Div. 1 250 - TrianglesContainOrigin

Problem Statement:
SRM 641 Div. 1 250 - TrianglesContainOrigin

Solution:
A pretty error prone computational geometry problem. The idea is actually quite simple, but the implementation can be quite tedious. Since no three points can form a collinear line, we can draw a line to each point P from the origin O and deterministically define that point by the angle defined by the line and the x-axis (that means the vector OP and the unit normal vector i of x-axis). Once we have converted every points as these angles and sort them, we can make use of another observation: if we choose two points with corresponding angles alpha and beta, then to form a triangle that contains the origin, we need to choose those points with angles between (alpha + 180, beta + 180). Otherwise, any triangle formed using points beyond these region will not contain the origin. This means that we can use binary search to find the number of points lying in the desired region. Overall we will have a $O(N^2 \lg{N})$ running time complexity.

Topcoder SRM 640 Div. 1 250 - ChristmasTreeDecoration

Problem Statement:
SRM 640 Div. 1 250 - ChristmasTreeDecoration

Solution:
We can employ a greedy scheme:
1. For each possible remaining edge, choose the one that connects two vertices with different colors and that does not result in a loop.
2. If it is not possible anymore to do that, the remaining edges needed to form the tree will all need to connect vertices of the same color.

Topcoder SRM 633 Div. 1 600 - DoubleTree

Problem Statement:
SRM 633 Div. 1 600 - DoubleTree

Solution:
It is interesting to know that this problem is actually a Maximum Flow problem. When we fix a node as the root of both of the trees, we reduce the problem to maximum weight connected sub graph problem. Let's say we have chosen a root R. R will be inside the subset S in question. We run a depth first search on both tree starting at R, forming two trees A and B. Then we build a graph G such that:
1. for each node v, we connect v with its parent u in A and B each with an edge with infinite capacity. This means that if we pick node v, then we have to also pick u, so we ensure that v and R is connected.
2. introduce two new nodes, source s and sink t. For each v in G, if v has a positive score m, add an edge between s to v with capacity m. Otherwise, m is negative, then we connect v with t using an edge with capacity -m.

Fross: Trapped in a Hamiltonian World

Just now my friend Andhieka Putra (github.com/andhieka) and I have just finished writing a pretty cute game, called Fross, inspired from Hamiltonian Path. Well, not exactly hamiltonian, but yeah. You are trapped in a maze in which you can only proceed to the next level and escape the maze if you have stepped on all the tiles in the maze, and only then a door will appear before your eyes..

Try it out here: Fross

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.

Codeforces 461C - Appleman and a Sheet of Paper

Problem Statement:
461C - Appleman and a Sheet of Paper

Solution:
The idea is use segment tree, since each fold we will reduce the length for the fold by the length of the smaller part, there will be at most $O(N)$ updates. Hence the running time of the tree will be $O(N\lg{N})$ overall.

The catch is to "flip" the perspective of the tree when we are face with the case where folding one part on top of the other will lead to the top part covering the whole of lower part. This is bad since we will end up with a very big indexes. By folding the smaller part on top of the lower part instead, and flipping our perspective afterwards, we can limit the size of the tree into $O(N)$.

Performance of HTML5 Canvas and CSS Border

I've just discovered that if you use CSS Border property on HTML5 Canvas, there will be a very severe performance hit! I realized this strange (or maybe not so strange for someone who knows the implementation details/documentations or related standards) behavior when I wrote the last game, Deterra. At first I have a very slow rendering of the quadtree, at that time I thought my implementation might have been not efficient in some ways. But once I removed the border lines (unintentionally, that time I was just thinking of making the game page looks better), the game suddenly became very smooth and fluid! (thats why I spammed lots of red block afterwards haha)

To confirm my suspicion, I rechecked BOOM, a game I previously written. It was so edgy and blocky like my unshaven face, that I thought ray casting might be too heavy for the machine. But once I removed the border lines, the game is smoother than Korean skin (haha if I offended anyone, I don't intend to and I apologize).

I am not that motivated to find out what are the reasons behind this, and I expect there will be more quirky stuffs lurking out when doing development on top of high level abstraction such as the HTML/CSS/JS development stack.

Take away point: If one day you think that an implementation of some data structure that you think should be efficient has performed badly, and you are pretty sure that you have implemented it pretty damn well, then you might want to check other factors regarding the abstraction layers you are working on to learn whether there are things that can be optimized.

Fun stuff.

Deterra: A simple game of survival based on Quadtree

I've just finished prototyping a experimental game which makes extensive use of Quadtree for creating the terrain and handling collisions. The game play is simple: there are bombers falling to the terrain and destroy parts of the terrain. How long can you survive before you fall?

Try the game here: Deterra :D

Dynamic Programming on Tree: Forming up Subtrees with One Black Node

This problem is from Codeforces Round #263 (Div. 1) Problem B:

Problem Statement:
461B - Appleman and Tree

Solution:
The dynamic programming approach to this tree problem is quite interesting. The focus of the problem is to find the number of ways such that the subtrees formed have one and only one black node each. The idea behind the DP might not be that intuitive though, and in a sense its implementation is also not as straight forward, although its final implementation looks very simple.