COLOUR - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Kanhaiya Mohan
Testers: Utkarsh Gupta, Jatin Garg
Editorialist: Nishank Suresh

DIFFICULTY:

1373

PREREQUISITES:

None

PROBLEM:

You have X, Y, Z units of the three primary colors. Two primary colors can be combined to make one secondary color.
What is the maximum number of distinct colors you can have?

EXPLANATION

There are a couple of ways to solve this problem: greedy/casework and bruteforce.

The bruteforce solution is simpler to think about and will be explained here.

It is enough to create either 0 or 1 drop of each secondary color, any more is pointless.
This gives us 8 possibilities for which secondary colors are created.
Simply try all 8 possibilities and take the best answer among them.
There are a few ways to implement this, perhaps the easiest is to use bitmasks. You can look at the editorialist’s code for this.

If you tried a greedy solution and got WA, you likely failed on a testcase like

3
2 2 3
2 3 2
3 2 2

Note that they should all have the same answer (5).
Your greedy will probably work if you sort the input in descending order first.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Setter's code (C++) (Greedy)
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
void solve()
{
    vector<int> a(3);
    a[0]=readInt(0,100,' ');
    a[1]=readInt(0,100,' ');
    a[2]=readInt(0,100,'\n');
    
    sort(a.rbegin(), a.rend());
    int ans = 0;

    for(int i = 0; i<3; i++) {
        if(a[i]){
            ans++;
            a[i]--;
        }
    }

    for(int i = 0; i<3; i++) {
        for(int j = i+1; j<3; j++) {
            if(a[i] && a[j]) {
                ans++;
                a[i]--;
                a[j]--;
            }
        }
    }
    cout<<ans<<endl;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,100000,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist's code (Python) (Bitmasking)
for _ in range(int(input())):
	x, y, z = map(int, input().split())
	ans = 0
	for mask in range(8):
		nx = ny = nz = 0
		if mask & 1:
			nx += 1
			ny += 1
		if mask & 2:
			nx += 1
			nz += 1
		if mask & 4:
			nz += 1
			ny += 1
		if nx > x or ny > y or nz > z:
			continue
		have = bin(mask)[2:].count('1')
		have += (nx < x) + (ny < y) + (nz < z)
		ans = max(ans, have)
	print(ans)

MY SOLUTION

Hi. Can anyone please tell me at what point does my code goes wrong?

try the edge case given in editorial, you’ll see why, also looks like in the end you added those three if statements unneccessarily

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

the answer(logic) is wrong in this however can anyone tell why am i getting a runtime error

Evey time you are calling the colour function inside the colour function you are not storing the return value anywhere.

Like this :

int ans =0;

int colour(int x,int y,int z,bool e1,bool e2,bool e3)
{
	if(x>=2 && y>=2)
	{
		x--;
		y--;
		e1=1;
		//debug(e1);
		ans = colour(x,y,z,e1,e2,e3);
	}
	else if(y>=2 && z>=2)
	{
		y--;
		z--;
		e2=1;
		ans  = colour(x,y,z,e1,e2,e3);
	}
	else if(x>=2 && z>=2)
	{
		x--;
		z--;
		e3=1;
		ans  = colour(x,y,z,e1,e2,e3);
	}
	else
	{
		int count =0;
		if(x>=1) count++;
		if(y>=1) count++;
		if(z>=1) count++;
		//debug(e1)
		if(e1==1) count++;
		if(e2==1) count++;
		if(e3==1) count++;
		return count;
	}
	
	return ans;
}

First you need to sort rgb in decending order.
IG your code will get stuck in the test case 2 2 3 which should ideally give 5 but your code will give 4 as output. So sort it first.

1 Like

Can you tell me which test case is not accepted and why? Here is my code:
/* 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
{
Scanner sc=new Scanner(System.in);
long t=sc.nextLong();
for (int i=0;i<t;i++){
int r=sc.nextInt();
int g=sc.nextInt();
int b=sc.nextInt();
int s=r+g+b;
if(s<=3)
System.out.println(s);
else if(r==0||g==0||b==0)
System.out.println(3);
else if(s<6)
System.out.println(s-1);
else if(s==6)
System.out.println(4);
else if(s>6 && s<9)
System.out.println(5);
else if(s>9)
System.out.println(6);
}
}
}

Thank you so much!!!

https://www.codechef.com/viewsolution/74153598
Hi coders, Not able to understand what is wrong. Please give it a look.

https://www.codechef.com/viewsolution/74153598
Bro can you help me what is wrong in this code??

CAN ANYONE HELP ME WHY MY CODE IS WRONG ??

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define all(x) (x).begin(),(x).end()
#define amax(x) *max_element(all(x))
#define amin(x) *min_element(all(x))
#define pb push_back
#define endl “\n”
const ll N = 1e9+7;
void solve()
{
ll x,y,z; cin>>x>>y>>z;
ll res = 0;
if(x!=0){
res++;
}
if(y!=0){
res++;
}
if(z!=0){
res++;
}
if(x > 1 && y > 1){
res++;
–x;
–y;
}
if(y > 1 && z > 1){
res++;
–y;
–z;
}
if(z > 1 && x > 1){
res++;
–z;
–x;
}
cout<<res<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll t; cin>>t;
while(t–)
{
solve();
}
return 0;
}

1 Like

I did the same thing and I am also stuck at the part where my code got wrong I tried quite a lot of sample testing and all of them came correct but when ever I am trying to submit it always the second sample test is getting stuck my code :


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


int color_comb(int x , int y , int z)
{

    int result = 0 ;
    if (x >= 1) 
    {
        result += 1;
        x--;
    }    
    if (y >= 1)
    {
        result += 1;
        y--;
    }  
    if (z >= 1)
    {
        result += 1;
        z--;
    }  
    

    if(x != 0 && y != 0)
    {
        x--;
        y--;
        result += 1;
    }

    if(x != 0 && z != 0)
    {
        x--;
        z--;
        result += 1;
    }

    if(y != 0 && z != 0)
    {
        z--;
        y--;
        result += 1;
    }


    return result;
}



int main () 
{

    
    long int test_case ;
    cin >> test_case;

    while(test_case --)
    {
    	int x , y , z ;
        cin >> x >> y >> z;

        cout << color_comb(x , y , z) << "\n";

    }
}

okay so after checking a lot I got the problem that is if you run the test case of

2 2 3

you will likely get a value of 4 that is incorrect
it should have been 5

2 Likes

greedy fails on 2 2 3 , but i cannot find any other test case where greedy fails , but when i treat 2 2 3 as separate case and solve using greedy it still fails , im curious to know the other test case where it fails , can anyone help and provide me a counter test case

thanks bro, thats what I was looking for

take those inputs in form of array and just sort it. After sorting just apply the same logic u will get the answer