PROBLEM LINK:
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.