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 #365 (Div. 2) - E. Mishka and Divisors

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

Summary:
Given an array of n <= 1000 integers a[i] <= 10^12, and an integer k <= 10^12. Find subset of the array which product of the elements is divisible by k, such that the size of the subset is minimised. If more than one such subsets exist, return the one with smallest sum over the elements.

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) - C. The Values You Can Make

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

Summary:
n, k <= 500, with n integers c[i] <= 500, output all x such that there exists a subset S of c with sum k, and S has a subset with sum x.

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 538E - Demiurges Play Again

Problem Statement:
538E - Demiurges Play Again

Solution:

Interesting problem. Although it seems to have large search space, by making use of interesting observations we can solve it in linear time (i.e. visiting each node exactly once).

First focus on trying to get the maximum result. Note that both player play optimally, hence the result of a game is deterministic. Consider a subtree T rooted at v. Let v.size be the number of leaves in T. Furthermore, let v.best be the maximum result obtained by an optimal labelling of leaves of T using label i = 1 .. v.size. We have two cases:
1. First player makes a move at node v. He will then choose a child of v that maximises result. For all w children of v, we check w.size and w.best. Pick the one that gives maximum of v.size - w.size + w.best (i.e. we place the biggest labels on the leaves of subtree rooted at w)
2. Second player makes a move at node v. He will choose a child w that minimises the result. Our job is to make the minimum choice as large as possible. It can be proved that the biggest possible will be \(1 + \sum_{w \text{ child of } v} (w.best - 1) \).

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:

UVa 607 - Scheduling Lectures

Problem Statement:
UVa 607 - Scheduling Lectures

Solution:
I think I've spent more time than I should on this problem.. But indeed there are tricky parts and non-obvious parts that make the assessment of the complexity of the solution difficult to intuitively comprehend.

Let D[i][k] be the minimum dissatisfaction index (DI) incurred if we have the i-th lecture ending at k-th topic. This translates to a very simple dynamic programming relationship: D[i][k] = min { D[i-1][j] + cost(j, k) } for all j that satisfy the constraints. The cost(j, k) function is the DI function given in the problem statement. With this approach, we have an \( O(LN^2) \) run time complexity, a very bad one.

UVa 12324 - Phillip J. Fry Problem

Problem Statement:
UVa 12324 - Phillip J. Fry Problem

Solution:
One of the classical dynamic programming problem. But might still be interesting to discuss.

Let S[i][k] be the minimum amount of time needed to finish trips [i..n]. Then the following relationship holds:
S[i][k] = min { S[i+1][k+b[i]] + t[i], S[i+1][k+b[i]-1] + t[i]/2 }
Direct implementation of this approach will result in a TLE at UVa, so you will need to prune the search space by considering the following observation: In a trip sequences with length n, you can consume at most n spheres. With that you can reduce the search space sufficiently to pass the time limit.

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

UVa 10690 - Expression Again

Problem Statement:
UVa 10690 - Expression Again

Solution:
I like this problem. Let A be the sum of the n numbers on the left, and S be the sum of all n+m numbers. Notice that the choice of A will determine the sum of the m numbers on the right, namely S-A. Our goal is to maximise and minimise A(S-A), where S is fixed. If we know beforehand all possible values of A, then the problem reduces to simply iterating through all choices of A and keeping track of the minimum and maximum A(S-A).

UVa 10364 - Square

Problem Statement :

UVa 10364 - Square

Solution:

This is an innocent looking problem, but actually it is a variant of set partitioning, an NP complete problem. To solve the problem, I used a bitmasking technique coupled with a dynamic programming technique to come up with an \( O(N2^N) \) solution. While I like the problem itself, to pass the time limit on UVa, you may require some optimisations to the plain DP implementation, which makes the experience a little bit unappealing to me.

Codeforces Round #295 (Div. 1 C / Div. 2 E) - Pluses everywhere

Problem Statement:
521C - Pluses everywhere

Solution:
Let's start from what we know and concretely find out what we don't know.

Let d[1..n] be the digits on the number that is given to us. Focus on d[i..j] for some i, j. We know exactly how many times it will appear by simple combinatorics deduction: there are \(n-1\) spaces to place '+' signs in between d[1], d[2], ..., d[n], but d[i..j] should not have any plus signs inside, which eliminates \(j-i\) candidates to place the sign, and finally we must place a sign right before d[i] and right after d[j], hence eliminating further 2 places, which gives us \( n-1-(j-i)-2 \) places to choose from. Furthermore, since we must use two plus signs to define d[i..j], we are left with k-2 plus signs to place. Hence in total, d[i..j] appears \({{n-1-(j-i)-2} \choose  {k-2}} \) times in the summations. Let's call this value M(i,j), the "multiplier" of d[i..j]. By the way, notice that we may also have cases where \(i = 1\) or \(j = n\) in which we only need to use a sign to define d[i..j], hence the computations will differ slightly, but can be computed precisely.

Codeforces Round #294 Div. 2 Problem D - A and B and Interesting Substrings

Problem Statement:
519D - A and B and Interesting Substrings

Solution:
Another cool problem. This problem can be solved using a dynamic programming approach.

Firstly let sum[i] be the cumulative sum of the values assigned to the letters in s[0 .. i]. This will allow us to find the sum of values between two letters in O(1).

Codeforces Round #291 Div. 2 E - Darth Vader and Tree

Problem Statement:
514E - Darth Vader and Tree

Solution:
Learnt something new! A very clever idea to use fast matrix exponentiation to solve for the DP states. Check the official editorial for a better understanding :) (Thank you for the enlightenment!)

Let V(m) be the number of vertices that are located exactly m unit distance away from root. Hence we can have the following relationship: \(V(m) = \sum_{i=0}^{100} c[i] V(m-i) \), where c[i] is the number of edges with length i amongst the n edges. What we want to find is \(S(x) = \sum_{i=0}^{x} V(x) \). The clever idea is to transform these equations into matrix multiplications!

Codeforces Rockethon 2015 Problem E1/E2 - Subarray Cuts

Problem Statement:
513E2 - Subarray Cuts

Solution:
This is another excellent problem, for which its solution demonstrates the power of dynamic programming. Unfortunately the implementation is very error prone due to the handling of edge cases (at least for me). The official editorial to this problem is also unfortunately very hard to read, partly because the TeX are not typed correctly. Anyway, here is my note about this problem.

The problem is difficult because we are presented with modulus operations. When we try to do a naive DP by keeping track of the value of \(s_j\), we will soon realize that we also need to keep track of the value for \(s_{j-1}\), which inflates the space search very badly. As it turns out, there is another way of looking into the problem which I think is very clever.

Codeforces Rockethon 2015 Problem C - Second price auction

Problem Statement:
513C - Second price auction

Solution:
This is a good problem :) The official editorial to this round is very well done and you are encouraged to check them out!

Apparently this problem can be solved using a pure mathematical approach, but I would like to describe the dynamic programming approach to solve this problem. In the editorial the author describes an \(O(N(R-L))\) solution to this problem, which requires some bounding on the states. But due to the small search space of N, I decided to write an \(O(N^3(R-L))\) solution because it is a bit more intuitive :)