Codeforces Round #356 (Div. 2) E / (Div. 1) C - Bear and Square Grid

Problem Statement:
Codeforces Round #356 (Div. 2) E / (Div. 1) C - Bear and Square Grid

Summary:
A \(N \times N\) grid where a cell is either empty or not, has the following properties: an empty cell is connected to its up, left, right, or bottom neighbour if its neighbour is also an empty cell. Compute the largest possible connected component in the grid, if we can perform one operation of transforming a \(k \times k\) square in the grid into empty cells.

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

SPOJ MORSE - Decoding Morse Sequences

Problem Statement:
SPOJ - MORSE

Solution:
This is a very... tedious problem. The idea is to build a trie structure for efficient search of words in the given dictionary. Since each letters in the dictionary is at most only 20 letters long, which can contain up to 26 letters, we can build the trie structure in O(M) time where M is the total sum of the lengths of the words.

Next, we do a depth first search like algorithm on the morse code (defined as morse[i]), starting from i = 0. Initially we also have a pointer cur pointing to the root of the trie. So the states of the algorithm is S(i, cur), where S(i,cur) gives us the number of ways to match morse[i..N] with words from dictionary.

Codeforces 463E - Caisa and Tree

Problem Statement:
463E - Caisa and Tree

Solution:
The approach to solve this problem is simply a brutal and forceful one :P

First of all, factorize all a[i]. Then, traverse the tree from the root. On each node, we maintain an array index[f], which means the index of the most recent node we encountered such that a[index[f]] is divisible by f. For each node v, the answer to query type 1 is simply the closest node index[f] to v amongst all f that divides a[v].

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 #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 Round #277 (Div. 2)

Problem C:
C. Palindrome Transformation

Solution:
Divide the string into two halves. Depending on which half \(p\) is, we can implement a greedy (an very intuitive) strategy to make that half exactly mirror the other half.