RODENT- Editorial

[chayan_d]

PROBLEM LINK:

Contest

Setter: chayan_d
Tester: debrc , mishra_roshan
Editorialist: chayan_d

DIFFICULTY:

Easy

PREREQUISITES:

Basic observations

PROBLEM

Arpita lives in the university hostel as many other students do. Along with the students, another species of animal lives with them i.e. rodents.

Rodents are of two colors: brown and red. There are NN rodents living in Arpita’s room.

Arpita just made all rodents living in her room to form a single straight line. As she is a artist, she would like the colors of rodents in the line to alternate. She has an acrylic color bottle of brown and red color each. In one turn she can :

• either swap any two rodents, or
• take any single rodent and change it’s color.

Help Arpita find out the minimum number of turns she needs to make the colors of rodents in the straight line alternate.

EXPLANATION

We can notice that there are only two possible final coloring of rodent that satisfy the problem statement: rbrbrb… or brbrbr…

Let’s go through both of these variants.

In the each case let’s count the number of red and brown rodent which are not standing in their places. Let’s denote these numbers as x and y. Then it is obvious that the min(x, y) pairs of rodent need to be swapped and the rest should be repaint.

In other words, the result for a fixed final coloring is exactly min(x, y) + max(x, y) - min(x, y) = max(x, y). The final answer for the problem is the minimum between the answers for the first and the second colorings.

Setter's Solution

C++

#include <bits/stdc++.h>
using namespace std;

void solve()
{

    int n, m = 0, t = 0, u = 0, v = 0;
    string s;

    cin >> n;
    cin >> s;

     for (int i = 0; i < n; i++)
    {
        if (i % 2 == 0)
        {
            if (s[i] == 'r')
                m++;
            if (s[i] == 'b')
                t++;
        }
        else
        {
            if (s[i] == 'r')
                u++;
            if (s[i] == 'b')
                v++;
        }
    }
    int x = max(t, u);
    int y = max(m, v);
    int z = min(x, y);
    cout << z << endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tc = 1;
    cin >> tc;
    while (tc--)
    {
        solve();
    }
}

Tester's Solution

Java

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc = new Scanner(System.in);
		int t=sc.nextInt();
		while(t-->0){
		    int n=sc.nextInt();
		    String s=sc.next();
		    int w1=0;
            int w2=0;

    
    for(int i = 0; i <n; i++){
        if(i%2==0){
            if(s.charAt(i)!='r')w1++;
        }
        else{
            if(s.charAt(i)!='b')w2++;
        }
    }

    int ans = Math.abs(w1-w2)+Math.min(w1,w2);

     w1 = 0;
     w2=0;

    for(int i = 0; i <n; i++){
        if(i%2==0){
            if(s.charAt(i)!='b')w1++;
        }
        else{
            if(s.charAt(i)!='r')w2++;
        }
    }

   int ans1 = Math.abs(w1-w2)+Math.min(w1,w2);
    ans = Math.min(ans,ans1);
   System.out.println(ans);
		}
	}
}

python

for _ in range(int(input())):
    n=int(input())
    s=input()
    c1,c2=0,0
    for i in range(n):
        if i&1:
            if s[i]!='b':
                c1+=1
        else:
            if s[i]!='r':
                c2+=1
    ans = abs(c1-c2)+min(c1,c2)
    c1,c2=0,0
    for i in range(n):
        if i&1:
            if s[i]!='r':
                c1+=1
        else:
            if s[i]!='b':
                c2+=1
    print(min(ans,abs(c1-c2)+min(c1,c2)))

---

Feel free to Share your approach.

Suggestions are welcomed as always had been.

---