Bear and Company
Contest: VK Cup 2017 - Round 1
Difficulty rating: 2500
Tags: dp

Bear Limak prepares problems for a programming competition. Of course, it would be unprofessional to mention the sponsor name in the statement. Limak takes it seriously and he is going to change some words. To make it still possible to read, he will try to modify each word as little as possible.

Limak has a string s that consists of uppercase English letters. In one move he can swap two adjacent letters of the string. For example, he can transform a string "ABBC" into "BABC" or "ABCB" in one move.

Limak wants to obtain a string without a substring "VK" (i.e. there should be no letter 'V' immediately followed by letter 'K'). It can be easily proved that it's possible for any initial string s.

What is the minimum possible number of moves Limak can do?

Input format:
The first line of the input contains an integer n (1 ≤ n ≤ 75) — the length of the string.

The second line contains a string s, consisting of uppercase English letters. The length of the string is equal to n.

Output format:
Print one integer, denoting the minimum possible number of moves Limak can do, in order to obtain a string without a substring "VK".

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample, the initial string is "VKVK". The minimum possible number of moves is 3. One optimal sequence of moves is:

1. Swap two last letters. The string becomes "VKKV".
2. Swap first two letters. The string becomes "KVKV".
3. Swap the second and the third letter. The string becomes "KKVV". Indeed, this string doesn't have a substring "VK".

In the second sample, there are two optimal sequences of moves. One is "BVVKV"  →  "VBVKV"  →  "VVBKV". The other is "BVVKV"  →  "BVKVV"  →  "BKVVV".

In the fifth sample, no swaps are necessary.

Example input:
4
VKVK

Example output:
3

Example input:
5
BVVKV

Example output:
2

Editorial:
Letters different than 'V' and 'K' are indistinguishable, so we can treat all of them as the same letter 'X'.
We will try to build the final string from left to right Let dp[v][k][x] denote the number of moves needed to move first v letters 'V', first k letters 'K' and first x letters 'X' to the beginning of the string (those letters should become first v + k + x letters of the string). We should also remember the last used letter (to ensure that there is no 'K' just after 'V') so let's extend the state to dp[v][k][x][lastLetter] (or it can be dp[v][k][x][is_the_last_letter_V]).
To move from a state, we should consider taking the next 'K' (i.e. the k + 1-th letter 'K' in the initial string), the next 'V' or the next 'X'. Of course, we can't take 'K' if the last used letter was 'V'.
The last step is to see how we should add to the score when we add a new letter. It turns out that it isn't enough to just add the difference between indices (where the letter was and where it will be) and the third sample test ("VVKEVKK") showed that. Instead, we should notice that we know which letters are already moved to the beginning (first k letters 'K' and so on) so we know how exactly the string looks like currently.
For example, let's consider the string "VVKXXVKVV" and moving from the state v = 4, k = 1, x = 1 by taking a new letter 'K'. We know that first 4 letters 'V', 1 letter 'K' and 1 letter 'X' are already moved to the beginning. To move the next letter 'K' (underlined in blue on the drawing below) to the left, we must swap it with all not-used letters that were initially on the left from this 'K'. Counting them in linear time gives the total complexity O(n4) but you can also think a bit and get O(n3) - it's quite easy but it wasn't required to get AC. On the drawing below, used letters are crossed out. There is only 1 not-crossed-out letter on the left from 'K' so we should increase the score by 1 (because we need 1 swap to move this 'K' to the x + k + v + 1-th position).