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

Count the number of set bits

Found something cool today. The problem is simple: Count the number of set bits in a bit representation of an integer. Of course the simplest solution will be to go through the bits one by one and count the number of 1s. The time complexity is O(n), where n is the length of the bit representation. Turns out, we can do better.

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 Good Bye 2014 Problem F - New Year Shopping

Problem Statement
500F - New Year Shopping

Solution:
A pretty tough problem which solution employs a very clever divide and conquer strategy. Learnt cool stuff :D.

Let's suppose that all the items are already sorted by \(t_i\) in increasing order. We know that item i will be available in the time segment \([t_i,t_i+p-1]\). Suppose that for each time \(T\), we know which are the segments that contain \(T\), i.e. the set of i such that \(T \in [t_i,t_i+p-1]\).

a bit of codeforces: Cool Divide and Conquer

Problem Statement:
448C - Painting Fence

Summary:
Given \(N \leq 5000\) sequences of numbers (fences), you can either:
- (paint horizontally) Substract 1 from the sequence consecutively from one end (may start from the first number, or from the next number after any 0s) to the other end (or when another 0 is encountered, whichever is earlier)
- (paint vertically) Set a number to 0

Given this operations, find the minimum number of operation needed to make all number equal to 0

Solution:
The solution to this problem is damn cool and it fits squarely under the divide and conquer paradigm.
Let S(L, R, H) be the minimum number of operations needed to paint the fences from L to R. H is the portion of the height of the fences that have already been painted.
Firstly, we can paint all fence vertically, that means at worst we need R-L+1 number of operations to pain all fences. Otherwise, we can paint the fence horizontally in hope of having a smaller amount of operations. When we paint the fence horizontally, we want to cover as much fences as possible. Furthermore, we want to horizontally paint until we hit the fence with minimum height, since otherwise we will be wasting operation, call this minimum height minH, hence we need minH - H operations. This leads to the formation of separate segments of uncolored fences, which form a smaller subproblem with exactly the same structure. We recursively process each segments and add up the total of each operation together with the operations incurred previously. Finally, we return whichever is smaller, the number of operations incurred when horizontal painting is used, or when only vertical painting is used.

I've written a code for the solution, which run in \(O(N\lg{N})\) time ( since the relationship \(T(N) \leq T(N/2) + O(N) \) holds ).

int minH(int L, int R){
    int ret = MAXINT;
    for(int i=L;i<=R;++i){
        ret = min(ret, a[i]);
    }
    return ret;
}

int rec(int L, int R, int H){
    int MH = minH(L,R);
    int ret = MH - H;
    int prev, state = 0;
    for(int i=L;i<=R;++i){
        if(a[i] > MH && state == 0){
            prev = i;
            state = 1;
        } else if( a[i] == MH && state  == 1){
            ret += rec(prev, i-1, MH);
            state = 0;
        }
    }
    if(state == 1) ret += rec(prev, R, MH);
    return min(R-L+1, ret);
}