Minimum operations to form a correct bracket expression

The Problem

   We have an expression which consists of opening and closing brackets '('  and ')'. We have 1 operation. We can change any bracket into its reversed one (aka changing this  ')' to this '(' and vice versa). We need to perform the minimum number of operations which can turn it into a correct expression. 

The Solution

 We can solve this using simple Stack of C++ STL. (You can find more info on stack go here). The first thing we need to do is to remove every single correct bracket expression from our given expression. 

For example

1 2 3 4 5 6

} { } { } }

The 2nd and 3rd form a correct expression so we don't need them, that means we can remove them, the same goes for the elements 4 and 5. We will be down to 2 brackets ) ). 

Here is how we will do that

Obviously we can consider a expression correct if there are 2 brackets '( '  and ') ' following one another. For example

 ( ( ) )

When we remove the middle 2 brackets we will be down to an expression ( ) which is also correct.

So here is how stack will help us. We loop over our given string, if the current element is ')' and the top element of the stack is '(' that means that those 2 are correct and we don't need them, otherwise we push teh current element to the stack.

for( i from 0 to the size )

 if(s[i] is ')' and stack.top()=='(')

        continue;

   else

       stack.push(s[i]);

Now we down to a wrong expression which we need to change with minimum number of operations.

I can guarantee that it has this form )))))((((((((( or in other words there are some of this brackets ' )' and after there are some brackets '('. Suppose there are N brackets ')' and M brackets '('. First of all we all understand that the given string must have an even number of elements and the string we just got must have even number of elements as well. Here are 2 things possible If both N and M are even. IN this case we need (N+M)/ operations (by turning the half of those brackets '(' into ')' and turning the half of those ')' brackets into this '(' this, example ))))(( we cant switch the first 2 brackets thus removing the first 4 elements as correct expressions and then change the last element and we get a total correct expression in (N+M)/2 steps. If N and M are both odd ( there is no other case they both either have to be even or odd). Example )))((( then we should switch the middle elements so that we can remove both of them and we will be down to the case were N and M are both even. The total number of operations in this case would be (N+M-2)/2 + 2.

There is a good task in SPOJ which has the same question as this problem.

http://www.spoj.com/problems/ANARC09A/

If you want the full source code of this go here.

SPOJ 4557. Musical Chairs

http://www.spoj.com/problems/ANARC08H/

This is a basic task of a problem called "Josephus Problem". You can find info about Josephus Problem here.Also check the full source code.

       DOWNLOAD THE FULL SOURCE CODE

Josephus Problem

The problem

Imagine that you are in a situation where you and your soldiers are trapped and soon the enemy is going to get you, so you decide that you would rather die than fall to the hands of the enemy. Now you and your soldiers formed a cyrcle and you pick 2 integers D and K. Starting from the Dth spot you count up to K and every time the count reaches K that person standing on the current spot commits suicide. You need to figure out where should you stand so that you will be the last person standing. 

This is a true story which happened in the first century.

Implemetnation

First first of all we need to try the link between the problems A[n][k] and the previous ones. For doing that let's calculate the answer by hand for the first integers. Here is a list of the answers for integers form 1 to 6.

N              K	1	2	3	4	5	6
1	1	1	1	1	1	1
2	2	1	2	1	2	1
3	3	3	2	2	1	1
4	4	1	1	2	2	3
5	5	3	4	1	2	4
6	6	5	1	5	1	4

here we can notice and interesting link

when N is 1 for every K the answer is also 1.

A[I][J]=(A[I-1][J]+j-1)%n+1

Or if we want to turn it into a recursive code here is how it will look like

int rec(int n, int k)

{

       if(n==1)

                 return 1; (because for every K when N is 1 the answer is also 1)

       else

                return  (rec(n-1,k) + k - 1 ) %n +1;

}

Note that the smallest index is 1 not 0.

And here is another non recursive apporach

int ans=0;

for( i=1;i<=n;i++)

      ans=(ans+k)%i;

return ans+1;

There is a task in spoj which requires the knowledge of this problem , you can practice what you learnt there. 

http://www.spoj.com/problems/ANARC08H/

And here is the link for getting the full source code for the task above if you want to.