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 #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?

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

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:

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

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.

Codeforces Round #277.5 Div. 2 Problem F

For complete discussion of this round : link to discussion

Problem Statement:
F. Special Matrices

Solution:
An interesting combinatorics DP problem. To solve this problem we need to find a way to reduce the number of parameters that matters. In the end, we only need 2 parameters, which is the current column that is being filled, and the number of rows which has all 0s in it, so we will have an \(O(N^2)\) solution.

Firstly we need to get the information of how many \(1\)s have to be filled in each column. Store this information in an array to_fill[i]. Furthermore, let D[R][k] be the number of ways to fill all columns in [0..k] where we initially have \(R\) empty rows). Define cur as the index of current column being considered. We keep a variable \(T\) initialized to 0, which keeps track of the number of 1s that we have filled as we progress from the first column to the current column (that is, the \(T\) = sum of to_fill[i] from i = 0 to index of cur). Suppose what at column cur, we have R empty rows and \(S\) rows that already has one '1' in each of them, and from [0..k] we need to fill \(T\) number of 1s. Then we have the following relationship:
\(T = 2*R + S\).

a bit of dp: SPOJ - M3TILE

Problem Statement:
SPOJ - M3TILE

Summary:
Compute the number of ways to place 1x2 tiles onto 3xN board. ( \( N \leq 30 \) )

Solution:
Years ago when I was in junior high school, I was presented with a similar combinatorics problem during a mathematics competition. The dimension was small, around 3x9 or 3x10. I was not familiar with the idea of recursion that time, so I tried to generate the tilings and desperately trying to find a pattern (haha). Anyway, the key to this problem is finding a suitable recursive relationship and use DP to cache the answers to each N, pretty simple.

Firstly let's agree that the number of ways to tile 3x0 board is 1 (in which we don't place any tiles at all). Now let S(n, k) be the number of ways to place the tiles on a 3xN boards with grid [1..k] on the N-th column covered. Then our job is just to consider each case one by one and figure out what is the recursive relation S of lower valued n. We have
\(S(n, 0) = 2S(n-1, 1) + S(n-2, 0) \)
\(S(n, 1) = S(n-1, 0) + S(n-1,2) \)
\(S(n, 2) = S(n-1, 1) \)
The answer will be S(N,0) for each N.