CODEWITHSUNDEEP
algorithm
Akashdeep Saluja
Akashdeep Saluja

Reputation: 3089

Finding Maximum Matching Topcoder

This is an algoritm problem from Topcoder SRM 566 Div2.

The problem can viewed here.

For those not having topcoder account the problem is described below:

Penguin Pals is a match making service that matches penguins to new friends, using the following procedure:

  1. Each penguin is asked a single question: "Do you prefer the color blue, or the color red?"
  2. All penguins are arranged so that they stand on a circle, equally spaced.
  3. The organizers draw some straight lines, connecting some pairs of penguins. Each penguin may only be connected to at most one other penguin. Two penguins cannot be connected if they prefer a different color.
  4. Each penguin who is connected to some other penguin follows the line to find their match.

The only problem with the above system was that it allowed penguins to collide if two lines crossed each other. Therefore, a new additional rule was adopted: no two lines may cross. Penguin Pals now has some penguins arranged on a circle (after step 2 of the above procedure). They need to know the maximum number of pairs of penguins they can create.

You are given a String colors whose i-th character represents the prefered color of the i-th penguin (0-based index) in the circular arrangement. The i-th character is 'R' if the i-th penguin prefers red and 'B' if the i-th penguin prefers blue. Return the maximum number of matched pairs that can be formed.

Example:

"RRBRBRBB"

Returns: 3

"BBBBB"

Returns: 2

"RRRBRBRBRBRB"

Returns: 5

My Approach:

Call the string s of length n. (Note that 0th and n-1th index are consecutive).

I used a recursive function recurse(string s,int i,int j) which is as follows:

int recurse(string s,int i,int j)
{
     if(i>=j)
           return 0;
     if(s[i]==s[j])
        return(1+recurse(s,i+1,j-1));
     else return max(recurse(s,i,j-1),recurse(s,i+1,j));
}

I start from i=0 and j=n-1, as they both will be consecutive if they are equal, call the the function with (i+1,j-1) and if not take both the possibilities and call the function recurse(s,i,j-1) and recurse(s,i+1,j) and will take the maximum of these two.

I called this function for every possible starting pair i.e.

for input "RRRBRRBB".

I called the function recurse() with inputs:

  1. s="RRRBRRBB" i=0 j=n-1
  2. s="RRBRRBBR" i=0 j=n-1 (Moved the string left and the earlier leftmost is now the rightmost)
  3. s="RBRRBBRR" i=0 j=n-1 (the same operation)

and so on until all the cases are covered.

But i got WA, and couldn't identify the flaw in my approach why it couldn't work.

Upvotes: 1

Views: 662

Answers (2)

m01
m01

Reputation: 9385

It's probably worthwhile mentioning that the expected solutions are documented on the Problem Set Analysis page for SRM566.

Upvotes: 1

Анатолий
Анатолий

Reputation: 2857

To correct you solution you should do following into each recursively call:

s="RRRBRRBB" i=0 j=n-1
s="RRBRRBBR" i=0 j=n-1 (Moved the string left and the earlier leftmost is now the rightmost)
s="RBRRBBRR" i=0 j=n-1 (the same operation)
and so on until all the cases are covered.

But I feels TLE on this case.

Solution: This is simple problem.

1) Remove all pairs from string where s[i] == s[(i+1) % n], and calculate count. (i from 0 to n-1).

2) Iterate #1 till your string not converted to "RBRBRBRB...RB" or "BRBRBRBRBR...BR", for this special casing result (length / 2) - 1;

Upvotes: 3

Related Questions