×

QM10P5A editorial

Author: Chandan Boruah
Tester: Taranpreet Singh
Editorialist: TaranPreet Singh

Simple

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()
{
for(int k=0;k<tests;k++)
{
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);
}
}
}


13311
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×303
×170

question asked: 12 Aug '18, 10:54

question was seen: 96 times

last updated: 12 Aug '18, 10:54