Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip

Problem Statement:
Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip

Summary:
An integer array A of size n <= 5000 has entries which ranges from 1 to 5000. We pick disjoint segments of the array such that for each segment S:
1. If i in S, then any j s.t. a[j] == a[i] must also be in S
2. The score of S is computed as the XOR of its elements
Goal is to maximise the sum of scores of the chosen segments.

Solution:
I like this problem. This is solvable using a dynamic programming approach.

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 #415 (Div. 2) E. Find a car [or Div. 1 C]

Problem Statement:
Codeforces Round #415 (Div. 2) E. Find a car

Paraphrase:
An integer matrix M is defined as:
M[i][j] = the minimum integer x >= 1 such that:
- M[i][k] != x for all k < j
- M[k][j] != x for all k < i

Example:
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

Goal: Given a rectangular block in M {(x1, y1), (x2, y2)} and an integer K, compute the sum of elements in that rectangle, but exclude elements whose value is larger than K.

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 Codeforces Round #359 (Div. 1) - D. Kay and Eternity

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

Summary:
In an infinite 2D array, there are n < 10^5 cells (x[i], y[i]) with value 1, where -1e9 <= x[i], y[i] <= 1e9. The rest of the cells are 0. For each m = 1 to n, compute the number of squares with dimension k x k (k <= 300), with the property that each of those squares has exactly m non-zero cells in it.

Codeforces Round #359 (Div. 1) - C. Optimal Point

Problem Statement:
http://codeforces.com/contest/685/problem/C

Summary:
Find the minimum point M (x, y, z) in Z^3 such that the maximum Manhattan distance between M and a set of points {(x[i], y[i], z[i]) in Z^3} of size <= 100000 is the minimum. Manhattan distance between two points (x, y, z) and (a, b, c) is defined as |x-a| + |y-b| + |z-c|. Furthermore, x, y and z is in [-10^18, 10^18].

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 #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 #353 (Div. 2) - C. Money Transfers

Problem Statement:
Codeforces Round #353 (Div. 2) - C. Money Transfers

Summary:
Given a circular array A[1..n] such that the sum of all its elements is zero, find the minimum number of steps needed to make every A[i] equal zero, if at each step we can take any value from A[i] (with positive value) and move it to either A[i-1] or A[i+1] (elements on immediate left/right of A[i]).

[Square Root Decomposition] Codeforces 617E. XOR and Favorite Number

Problem Statement:
617E. XOR and Favorite Number

Solution:
Spent quite a long time trying to solve this problem using segment tree and suffix/prefix ideas... So it turns out that this problem is solvable using a new technique (to me)!

Square Root Decomposition
The type of problem that can be solved using this technique: Given an array A of numbers N, and a set of M queries in the form (i, j), find the maximum, minimum, sum, mean, or mode (or some other aggregate function), of A[i], A[i+1], ..., A[j].

Codeforces 586F - Lizard Era: Beginning

Problem Statement:
586F - Lizard Era : Beginning

Solution:
This problem has a very cool hashing and look-up idea. (This method is described in the official editorial as well)

First break the array of l[i], m[i], and w[i] into two halves, namely the upper half and the lower half. This helps to reduce down the \(O(3^n)\) component to \(O(3^{n/2})\), which actually allows us to solve the problem given \(n \leq 25\).

Suppose the upper part gives us (a, b, c) as the sum of the chosen configuration of l[i], m[i], and w[i]. Similarly, we suppose (a', b', c') are the sum for the lower part. Hence our job is actually to find such (a', b', c') that \(a+a' = b+b' = c+c' \).

Codeforces Education Round 1 C. Nearest Vectors

Problem Statement:
http://codeforces.com/contest/598/problem/C

Solution:
[Before you read any further, I think there is an official editorial for this round which may explain the approach to this problem better.]

The problem looks innocent enough, but actually it is quite a tedious one. Nevertheless, it links several interesting techniques and I find this problem quite interesting eventually.

Codeforces 547C - Mike and Foam

Problem Statement:
547C - Mike and Foam

Solution:
The most important observation: since \( a_i <= 5 \times 10^5 \), the maximum number of distinct prime factors \(a_i\) can have is 6, since \(2 \times 3 \times 5 \times 7 \times 11 \times 13 = 30030 < 5 \times 10^5\) while \( 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510 > 5 \times 10^5 \). This allows us to perform a fundamental counting principle called inclusion-exclusion principle.

Codeforces 536A - Tavas and Karafs

Problem Statement:
536A - Tavas and Karafs


Solution (from the official editorial, which is more succinctly written. I'm placing it here for my self reference.):
Given a sequence \(s_i\), we are only allowed to perform m-operation: choose at most m numbers in the sequence and decrease them by 1. Then it is provable that by performing at most t m-operation, we can reduce all \(s_i\) to 0, if and only if \( \max s_i \leq t\) and \( \sum_i s_i \leq tm \).
Proof:
Forward direction: if we can reduce all \(s_i\) using t operations, then it is clear that the biggest \(s_i\) must not exceed t, and that the total sum of \(s_i\) will not be more than \(mt\). The interesting part is to prove that this conditions are sufficient.

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.

UVa 11832 - Account Book

Problem Statement:
UVa 11832 - Account Book

Solution:
The solution to this problem employs a simple yet powerful idea. Let's call the given values as a[i]. Let S[i] be the set of values that can be reached using elements in a[1..i]. Then S[i+1] = everything in S[i] and anything that is reachable from elements in S[i] after addition or subtraction with a[i+1]. With this idea we can already solve the problem by iterating through each a[i] and test for each sign, but this approach is very inefficient, since we have to recompute the same values again and again for each a[i] we are focusing on, which gives us \( O(kN^2) \) with k at most 80000.

UVa 11088 - End up with More Teams

Problem Statement:
11088 - End up with More Teams


Solution:
This problem looks innocent enough, until it bit me with a few WA and TLE. The idea to solve this problem is by using a bitmask DP technique, which I will elaborate. This solution took \( O(kN2^N) \) time.

Firstly let B be the set for which \( i \in B\) if and only if i-th person is already chosen as a member of some team. Let a[i] be the "ability" value of i-th person, we know that a[i] \( \leq 30\). Lastly, let D[B][val] be the maximum number of groups that can be formed using people in B, and such that if the total number of people in B is not divisible by 3, val will be the total ability of the extra people in B not in any group yet. For every j not in B yet, we do:

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: