You are not logged in. Please login at www.codechef.com to post your questions!

×

QM10P5A editorial

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);
        }
    }
}

asked 12 Aug '18, 10:54

chandubaba's gravatar image

2★chandubaba ♢
13311
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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