Codeforces Round #416 (Div. 2) E. Vladik and Entertaining Flags

Problem Statement:

Codeforces Round #416 (Div. 2) E. Vladik and Entertaining Flags
Summary:
Given an integer matrix with size m x n with m <= 10, n <= 10^5, find the number of connected components in segment [l, r] of the matrix (i.e. rectangle (0, l) -> (m-1, r)). Two cells belong to the same connected component if they are adjacent (share the same edge) and have the same value.
There are q <= 10^5 such queries.

Solution:
A cool problem which can be solved using Segment Tree. This is made possible by the following observation: Consider two adjacent segments [l, m] and [m+1, r]. If we know the number of components on each segment, then we can iterate along the cells where the two segments meet to see if we can combine any adjacent components.

Codeforces Round #365 (Div. 2) - D. Mishka and Interesting sum

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

Summary:
Given array a[i] for N <= 10^6 integers, and M <= 10^6 queries (L, R): collect all integers in a[L..R] that occur even number of times, and compute their XOR. E.g. for a = {1, 2, 2, 3, 4, 4}, query (2, 7) returns 2 XOR 4 = 6. If no such element in a particular query, return 0.

Codeforces 455E - Function

Problem Statement:
http://codeforces.com/contest/455/problem/E

Summary:
Given a function f(i, j) = min (f(i-1, j), f(i-1, j-1)) + a[j], where f(1, j) = a[j], and m queries (m <= 10^5) in the form (i, j), compute f(i, j) of each queries.

Codeforces Round #355 (Div. 2) - D. Vanya and Treasure

Problem Statement:
Codeforces Round #355 (Div. 2) - D. Vanya and Treasure

Summary:
You have a 2D array m x n with values [1..p] on each cell (p <= n*m). Distance between two cells is defined as Manhattan distance. Compute the path with minimum total distance that passes through 1, 2, ..., p in order. [Additionally, the problem always starts from cell (1, 1)].

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 526F - Pudding Monsters

Problem Statement:
526F - Pudding Monsters


Solution:
A self note for a tough problem. The problem is equivalent to finding the number of segments in an array A, with a property that the elements in each valid segment is a permutation of a consecutive sequence of numbers. Furthermore, A itself is a permutation of [1..n].

The first way to solve this problem is by considering a divide and conquer strategy: Let A[1..n] be the sequence of numbers. Let S(i..j) be the number of valid segments in A[i..j]. Then we can find S(i..j) by splitting A[i..j] into 2 parts A[i..m] and A[m+1..j] where m is (i+j)/2. By recursion, assume we know how to compute S(i..m) and S(m+1..j). What is left is to compute the number of segments that crosses A[i..m] and A[m+1..j]. Let L denote A[i..m], while R denote A[m+1..j]. For all such valid segments M[u..v], we have:

Codeforces 529C - Rooks and Rectangles

Problem Statement:
529C - Rooks and Rectangles

Solution:
Just learnt a new technique for solving a segment tree problem, which involves an idea in computational geometry referred to as vertical/horizontal sweeping. To solve the problem effectively we need the following observation: a rectangle is well defended if (1) either every row of that rectangle contains a rook, or (2) every column in that rectangle contains a rook. We can check these two cases (1) and (2) separately. Let's focus on one of them.

Codeforces Round 296 Div. 1 B / Div. 2 D - Clique Problem

Problem Statement:
528B - Clique Problem

Solution:
This problem is brilliantly crafted. I really enjoy solving this problem, as the ideas are really natural.

Firstly, we notice that we can sort the vertices by its x coordinates, and we hope that some nice property can be established. Indeed,  suppose v[i] = (x[i], w[i]) is an array of vertices in sorted order with respect to x, then let C[i] be the maximum size of a clique that can be formed by choosing amongst v[1], v[2], to v[i], with the added constraint that v[i] must be included in C[i]. Then we claim that:
C[i] = max (C[j] + 1) where j is less than i.
Why is this true? Consider a clique C[j] for which we have:
|x[i] - x[j]| = x[i] - x[j] \(\geq \) w[i] + w[j].

Codeforces Round #296 (Div. 1 A / Div. 2 C) - Glass Carving

Problem Statement:
528A - Glass Carving

Solution:
Wow this round is so challenging. I solved this problem using 6 segment trees, but that makes me wonder if there are simpler way of solving it, because I see that average contestants actually solved this problem pretty quickly. Either this kind of segment tree galore is already a routine problem out there, or I am missing something cool.

The idea is to answer the following queries quickly:

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.

Codeforces Round #291 Div. 2 D - R2D2 and Droid Army

Problem Statement:
514D - R2D2 and Droid Army


Solution:
The problem statement is a bit hard to understand, but other than that the problem is excellent. I love the idea of combining binary search with segment tree / Fenwick tree!

The strategy is as follows: We want to know, for each i-th droid, what is the longest segment [j, i] possible such that we can kill all j-th to i-th droid using at most k shots (of course j \(\leq \) i). To find j, we can use binary search on [0, i] droids. If we need more than k shots to kill all droids in [j,i], we must increase j, since any choices of j less than the current j will also need more than k shots. Otherwise, if we need at most k shots to kill droids in [j,i], we can decrease j, since any choices of j bigger than the current j will also need at most k shots. What an awesome property.

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

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