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

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)