QM10P5A editorial

editorial
, ,
1

PROBLEM LINK:

Practice

Contest

Author: Chandan Boruah

Tester: Taranpreet Singh

Editorialist: TaranPreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

Greedy

PROBLEM:

Given N balls, each ball colored either red or blue, we have to find maximum number of green balls we can make. A Green ball can be made by merging consecutive red and blue ball.

QUICK EXPLANATION

  • Final composition of balls would never have consecutive balls are red and blue, since we can always merge them to obtain one more green ball.
  •   So, merging balls greedily would generate maximum number of green balls.

EXPLANATION

All we need to do is to merge red and blue ball whenever we find a pair of such balls. All we need to prove now is that this approach is optimal.

Consider example: RBRB

Here, if we choose to merge second and third ball, our final compostion would look something like this RGB. Since we cannot move Green ball from in-between, we cannot merge the remaining red and blue ball. This proves that we should perform the merge operation as early as possible, otherwise Green ball might block future merge operation.

Instead of pair (2, 3), had we chosen (1, 2), we can still merge (3, 4) getting 2 green balls in the end, thus, being the optimal approach for merging.

Complexity:
Time Complexity is O(N).

AUTHOR’S SOLUTIONS:

using System;
using System.Collections.Generic;
class some
{
	public static void Main()
	{
		int tests=int.Parse(Console.ReadLine());
		for(int k=0;k<tests;k++)
		{
			int t=int.Parse(Console.ReadLine());
			string s=Console.ReadLine();
			int max=0;
			int count=0;
			for(int i=0;i<t-1;)
			{
				if(s[i]!=s[i+1]){count++;i+=2;}
	else i++;
			}
			max=count;
			count=0;
			for(int i=1;i<t;)
			{
				if(s[i]!=s[i-1]){count++;i+=2;}
	else i++;
			}
			max=Math.Max(count,max);
			Console.WriteLine(max);
		}
	}
}