COLOR - editorial

editorial
, , ,
1

PROBLEM LINK:

[Practice][1]
[Contest][2]

Author: [Sunny Aggarwal][3]
Tester: [Sergey Kulik][4]
Editorialist: [Mugurel Ionut Andreica][5]

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

Chef has N rooms, each of them painted in one of 3 colors (R, G or B). He wants to repaint the minimum number of rooms such that, in the end, all the rooms have the same color.

QUICK EXPLANATION:

Paint all the rooms in the color which appears the largest number of times (of course, rooms which already have that color will not be repainted).

EXPLANATION:

Repainting the minimum number of rooms is equivalent to not repainting (i.e. keeping the initial color in) the maximum number of rooms. Since all the rooms must have the same color in the end, this means that we should find the color C in which the most rooms are painted and then repaint all the rooms which have a color other than C in color C.

In order to count how many rooms of each color we have, we can simply maintain three variables cntR, cntG and cntB. Then we traverse the string denoting the colors of the rooms and increment the corresponding variable depending on the color denoted by the current character in the string.

Time complexity: O(N).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.
[1]: http://www.codechef.com/problems/COLOR
[2]: http://www.codechef.com/APRIL16/problems/COLOR
[3]: http://www.codechef.com/users/ma5termind
[4]: http://www.codechef.com/users/xcwgf666
[5]: http://www.codechef.com/users/mugurelionut
[6]: X
[7]: Y

1 Like
2

Author’s and Tester’s solution links are not working .

3

@radeonguy Not a big deal…here is My Solution using the same approach.

1 Like
4

Simply put,
Solution = MIN(N-R,N-G,N-B)

5

https://www.codechef.com/viewsolution/9809741

6

#include
using namespace std;
int main(void)
{
int t,r,g,i,b,n,x;
scanf("%d",&t);
while(t–) {
scanf("%d",&n);
char color[n+1];
scanf("%s",color);
r=b=g=0;
for(i=0;i<n;i++)
{
if(color[i]==‘R’)
r++;
else if(color[i]==‘B’)
b++;
else if(color[i]==‘G’)
g++;
}
if (r>=b&&r>=g)
x=n-r;
else if (b>=r&&b>=g)
x=n-b;
else if(g>=r&&g>=b)
x=n-g;
printf("%d\n",x);
}
return 0;
}

7

Hi friends
can anyone help me out!!
check this code
on submitting it shows wrong answer 0 marks

#include<stdio.h>
int main(void)
{
int t,i,j,n,r,b,g,max;
char c[100];
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d",&n);
scanf("%s",&c);
r=b=g=0;
for(j=0;j<n;j++)
{
if(c[j]==‘r’)
r=r+1;
else if(c[j]==‘b’)
b=b+1;
else if(c[j]==‘g’)
g=g+1;
}
if((r>=b)&&(r>=g))
max=r;
else if((b>=r)&&(b>=g))
max=b;
else
max=g;
printf("%d",n-max);
}
return 0;
}

8

Why this code is not accepted by codechef and showing WRONG answer.
Can any help me.
Please!!!
#include<stdio.h>
#include<string.h>
char ch[100000];
long int n;
int main()
{
long int t,i,j,k,r1,g1,b1;
scanf("%ld",&t);
while(t–)
{
r1=0;g1=0;b1=0;

	scanf("%ld",&n);
	fflush(stdin);
	char ch[n];
	gets(ch);
	for(i=0;i<n;i++)
	{
		if(ch[i]=='G')
		r1++;
		else if(ch[i]=='R')
		g1++;
		else if(ch[i]=='B')
		b1++;
	}
	if(r1>=g1&& r1>=b1) 
	{
		//printf("%d\n",g1+b1);
		printf("%ld\n",n-r1);
	}
	else if(g1>=b1 && g1>=r1) 
	{
		printf("%d\n",n-g1);
		//printf("%ld\n",b1+r1);
	}
	else if(b1>=r1 && b1>=g1)
	{
		printf("%ld\n",n-b1);
		//printf("%d\n",g1+r1);
	}
}
return 0;

}

9

use N-Max(cntR,cntG,cntB)