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.

SPOJ TOURIST - Tourist

Problem Statement:
SPOJ - TOURIST

Solution:
Seems like a lot of work, seems like a some graph problem, seems like something convoluted... But once you've found the enlightenment, this is a pretty nice DP problem.

Firstly, realize that we can rephrase the problem as finding two paths from top-left corner (0,0) to the bottom-right corner (H-1, W-1) that maximizes the number of '*' covered. Then, realize that the length of the path is constant, H+W-2, no matter how we move.

SPOJ - Counting The Way of Bracket Replacement (MREPLBRC)

Problem Statement:
SPOJ - MREPLBRC

Summary:
A string s contains brackets of type "(){}[]" and question marks '?'. Make it a balanced string by changing '?' to appropriate brackets, and count the number of ways to do so.

Solution:
The DP idea goes as follows:
Let W(i,j) be the number of ways to replace the question marks such that the resulting string [i..j] is balanced. Now look at s[i], the character on index i. If s[i] is a right-hand side brackets, W(i,j) is 0, since there is no way to make [i..j] balanced. Otherwise, there might be a way to balance the string.

SPOJ - MARTIAN

Problem Statement:
SPOJ - MARTIAN

Summary:
A field of dimension RxC has some amount of minerals on each cell, such that each cell (i,j) has A[i][j] mineral of first type and B[i][j] mineral of second type. Mineral of first type is collectible only on the left side of the field, while mineral of second type is collectible only on the top side of the field. For each cell on the field, we can only build either a straight conveyor belt to the left, or a straight conveyor belt to the top. No conveyor belt can cross each other. Minerals are transported via such belts. Find the maximum possible amount of minerals collectible.

SPOJ - Another Tree Problem (MTREE)

Problem Statement:
SPOJ - Another Tree Problem (MTREE)

Summary:
Define weight of a path as the product of weights of edges in a path between node A and B in a tree, and define weight of a tree as the sum of the weight of path of all paths (inception!).
(Number of vertices  \(N \leq 10^5\))

SPOJ - Black or White (BORW)

Problem Statement:
SPOJ - BORW

Summary:
Given a sequence of number a[i], we can paint a number either white or black, or we can leave it unpainted. The white numbers must form a strictly decreasing subsequence, while the black numbers must be a strictly increasing subsequence. Find the minimum number of unpainted numbers.

Solution:
Lately I've been presented with problems that appears to be an LDS/LIS problem, but after working on them for quite a while then I realize that I've been fooled again (cry). Anyway, this problem can be solved recursively in a very simple manner: let S(dec, inc, idx) be the maximum number of painted numbers from idx to N, where the last element in the decreasing subsequence has index dec, and last element of the increasing subsequence has index inc. Then:
S(dec, inc, idx) = maximum of:
1. If a[dec] > a[idx], consider 1 + S(idx, inc, idx+1)
2. If a[inc] < a[idx], consider 1 + S(dec, inc, idx+1)
3. Either way, consider S(dec, inc, idx+1)

But the running time is pretty bad on SPOJ judge (like, nearly 40s wow), I think there are better implementations/ideas that can push it down to a few seconds top. The bottom up version of this approach will run faster for sure.

SPOJ - Nested Dolls (MDOLLS)

Problem Statement:
SPOJ - Nested Dolls (MDOLLS)

Summary:
Given a list of dolls with width[i] and height[i] such that doll[i] can be nested inside doll[j] if width[i] < width[j] and height[i] < height[j]. Find the number of minimum resulting nested dolls possible.

Solution:
It is a very interesting (and difficult) problem. I thought it was something to do with longest increasing subsequence (by the way the problem is phrased haha) but actually formally this problem is that of bipartite matching, and there is a greedy approach to solve this problem based on the following observations:

SPOJ - BRIDGE

Problem Statement
SPOJ - BRIDGE

Summary:
We are given N pairs of start-point and endpoint in which a bridge can be built from the starting point to the endpoint. Two bridges is said to cut each other iff they share a common point that is not endpoint. Find the maximum number of bridges can be built.

Solution:
At first I thought this it is a knapsack problem and tried to solve it as follows:
Firstly we need to sort the pairs such that the starting points are in increasing order.
Let M(i, x) be the maximum number of bridges that can be built between [i .. N] such that the lowest coordinate of endpoint is x. Then M(i,x) = max {M(i+1, x) , 1 + M(i+1, endpoint[i] (if endpoint[i] >= x) )}
The complexity of the algorithm is a pseudo polynomial \(O(N|M|)\) where N is the number of pairs, and M is the range of endpoints. Unfortunately this does not pass the time limit.

SPOJ - Musketeers (MUSKET)

Problem Statement:
SPOJ - MUSKET

Summary:
N people are standing in a circle. In each round, a person will fight his right neighbor. The loser leaves the circle and the circle tightens. Given a matrix A(i,j) where 1 indicates person i wins against person j and 0 otherwise, find the number of people who may be the last man standing, and output all of them.

Solution:
I think this problem is very difficult :O The DP idea goes as follows:
We focus on one person at a time to determine whether he can be the last man standing. Call this person P.

SPOJ - LSORT

Problem Statement:
SPOJ - LSORT

Summary:
Sort a permutation of [1..N] by the following rule:
1. Start with P the permutation of [1..N], and Q an empty set [].
2. For each step i, we can choose any element in P and append it to beginning or end of Q. We incur cost i*x, where x is the position of the element in P at that time.
3. In the end Q must be in sorted ascending order.

Find the minimal cost possible to perform this operation.

SPOJ - Three-coloring of Binary Trees (THREECOL)

Problem Statement:
SPOJ - THREECOL

Summary:
Given a binary tree as specified (may not be balanced nor complete),  we can color the tree with three colors: red, green and blue, with the following restrictions:
1. A node and its child cannot have the same color.
2. For nodes with two children, the node and its children must all have different colors.
Find the maximum and minimum number possible of nodes colored in green.

SPOJ - SERVICE

Problem Statement:
SPOJ - Mobile Service (SERVICE)

Summary:
A company has 3 staffs which are initially located at town 1, 2, and 3. There are M <= 200 towns and N <= 1000 requests. Each request is located at a particular town, and a staff has to move to that town to deliver the service. The requests are sequentially serviced. Staffs cannot move to a town without an accompanying request, and no staff can be in the same town at the same time. Given a table of costs of travel between towns, find the minimum cost needed to service all requests.

SPOJ - MSTRING

Problem Statement (the problem statement is quite ambiguous):
SPOJ - MSTRING

Summary:
Given two strings S and V, find the shortest subsequence of S that is not a subsequence of V.
( |S|, |V| <= 1000 )

Solution:
This is an interesting question in a sense that usually problems will ask for the longest subsequence. Here we are asked to find the shortest uncommon subsequence, the direct opposite of that, and surprisingly dynamic programming can also solve the problem equally well :D but first we need a few tricks.

SPOJ - Candy (SAMER08C)

Problem Statement:
SPOJ - Candy (SAMER08C)

Summary:
Given a box of candy of dimension NxM \(\leq 10^5\), where each cell contains at most 1000 candies, find the maximum number of candies can be collected, with the following rule:
If we pick a candy on cell (i,j), then the row i-1 and row i+1 will be emptied, as well as the neighboring cells to cell (i,j).

SPOJ - GNYR09F (Adjacent Bit Count)

Problem Statement:
SPOJ - Adjacent Bit Count (GNYR09F)

Summary:
In a string of bits s, we denote adj(s) as the number of pairs of adjacent bits with both bits are 1. Given n the length of string and k = adj(s), find the number of ways such strings can be constructed.
( \( n \leq 100 \) )

Solution:
The solution is by a DP approach. Let W(b, k, len) be the number of ways of constructing a string s of length len such that it ends with bit b, and have adj(s) = k. Then we have:
W(0, k, len) = W(0, k, len-1) + W(1, k, len-1)
W(1, k, len) = W(0, k, len-1) + W(1, k-1, len-1)
From this relationship we can work out the values using a bottom up DP in O(nk) time.

a bit of josephus: SPOJ - DANGER

Problem Statement:
SPOJ - DANGER

Summary:
The alternating Josephus problem.

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.

a bit of string balancing: SPOJ - ANARC09A

Problem Statement:
SPOJ - ANARC09A

Summary:
Given a string consisting of open and close brackets, find the number of operations needed to balance the brackets. An operation is defined as flipping a bracket. Balanced is in the usual sense: if S,T is balanced, then {}, {S}, ST are all balanced.

Solution:
I used DP approach which is quite expensive in terms of running time and memory, the idea is to keep track of the number of open brackets.
Let S(k, open) be the number of min operations to balance the string
with |open| open brackets by the time we start at k.
Let current bracket be cur. We have several cases:
1. open is 0, and cur = '}', then we have to flip.
   S(k, open) = 1 + S(k+1, open+1)
   open is 0 and cur = '{', then we cannot flip.
   S(k, open) = S(k+1, open+1)

a bit of dp: SPOJ - BABTWR

Problem Statement:
SPOJ - BABTWR

Summary:
Given N (N<30) types of 3D boxes with dimension x,y,z, find the maximum height of tower can be formed by stacking those boxes together with the condition:
1. each type of box can be used as many times as possible
2. if a box is stacked on top of another, its baselines must be smaller than the one below.

Solution:
Rather than building the boxes one by one, we make use of the property that the boxes can be arranged in sorted order. Hence once we derived a suitable order of boxes that can be exploited, we perform a procedure similar to one in LIS to find the maximum height possible.

/* Idea:
Bottom Up: sort all boxes and possible orientations in terms of width and height.
WLOG width < height, hence comparison can be done between widths and heights exclusively.
Then do checks similar to LIS
*/

vector<pair<pair<int,int>,int> > stack;
int box[33][3];
int dp[99];
int N;

int main(){
    while(cin >> N, N!=0){
        stack.clear();
        for(int i=0;i<N;++i){
            for(int j=0;j<3;++j){
                cin >> box[i][j];
            }
        }
        for(int i=0;i<N;++i){
            for(int j=0;j<3;++j){
                int a = box[i][j];
                int b = box[i][(j+1)%3];
                int c = box[i][(j+2)%3];
                if(a>b) swap(a,b);
                stack.push_back(make_pair(make_pair(a,b),c));
            }
        }
        sort(stack.begin(), stack.end());
        dp[0] = stack[0].second;
        int ans = 0;
        for(int i=1;i<3*N;++i){
            int h = stack[i].first.first;
            int w = stack[i].first.second;
            dp[i] = 0;
            for(int j=i-1;j>=0;--j){
                int ch = stack[j].first.first;
                int cw = stack[j].first.second;
                if(ch < h && cw < w) dp[i] = max(dp[i], dp[j]);
            }
            dp[i] += stack[i].second;
            ans = max(ans, dp[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

a bit of dp on string: SPOJ - DSUBSEQ

Problem Statement:
SPOJ - DSUBSEQ

Summary:
Given a string S, find the number of distinct subsequences.
S only contains uppercase characters.
\(|S| \leq 10^5\), 100 test cases, and time limit of 2s.

Solution:
Let D[i][j] be the number of distinct subsequences starting with alphabet j in a string of length i. Also define sum[i] be the total number of distinct subsequences in S[0..i].

Consider the case where we are appending S[i] to substring S[0..(i-1)]. Then we have the following
D[i][j] is equal to:
1. D[i-1][j] (for all j != S[i]),
2. sum[i] + 1 (for j == S[i])

Using this relationship, we consider i from 0 to |S|-1 incrementally and update D[i][j] and sum[i] accordingly, where sum[|S|-1] will be the answer. By updating D[i][j] as such, we will have , we will have an \(O(|S|)\) running time, but with a rather big constant hiding, and a space usage of \(O(|S|)\) with an equally high constant term.

Improving the algorithm, we can just maintain D[j] for each alphabet, and a variable sum which we will update on each iteration:
1. newsum = 2 * sum + 1 - D[current_alphabet]
2. D[current_alphabet] = sum + 1
3. sum = newsum

Cutting down the space to \(O(1)\) and resulting in a blazingly fast solution :D