BOUQUET - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Kulik
Tester: Misha Chorniy
Editorialist: Pawel Kacprzak

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

Given availability of 3 types of leaves and availability of 3 different colors for each type of a leaf find out what is the maximum number of leaves that can be chosen in such a way that all chosen leaves are of the same type or of the same color and the number of chosen leaves is odd. If there is no way to choose the leaves according to these rules, then answer is 0. In one test file there are multiple test cases to handle.

QUICK EXPLANATION:

First, for each type of leaves calculate the result when only leaves of this type are chosen. Next, for each color of leaves also calculate the result when only leaves of this color are chosen. Since there are 3 types and 3 colors, then the final result is the maximum from these total 6 possibilities.

EXPLANATION:

Subtask 1

In the first subtask there are at most 5 leaves of any type and color in any test case. This allows some solutions taking advantage of this fact to pass test cases with such low constraints. On can for example try to iterate over all possible sizes of the resulting bouquet and for each such size decide if it is possible to create it.

Subtask 2

In the second subtask there are up to 10^9 leaves of any type and color, however, the task is still very easy. Since in the result all leaves has to have the same type or the same color (both type and color are also valid), we can iterate over all types first and for each type, sum up all the leaves of this type and subtract 1 from this sum if it is even (because we want the number of chosen leaves to be odd). After that, we can do the same with color, i.e. iterate over all colors and for each color sum up all the leaves of this color and subtract 1 from this sum if it is even. The final result is the maximum from these 6 values computed this way.

Let c[i][j] denotes the number of leaves from the i-th type and the j-th. The below pseudocode illustrates the approach:

res = 0
for i = 1 to 3:
   subres = c[i][1] + c[i][2] + c[i][3]
   if subres % 2 == 0
      subres = subres - 1
   res = max(res, subres)

for j = 1 to 3:
   subres = c[1][j] + c[2][j] + c[3][j]
   if subres % 2 == 0
      subres = subres - 1
   res = max(res, subres)

print res

Last but not least, be aware that the result can be bigger than 32-bit integer.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution will be posted soon.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

Add the 3x3 matrix row and column wise find that maximum sum and if sum = 0 PRINT “0” else if(sum % 2 == 0) PRINT “sum-1” else PRINT “sum”

2 Likes

Unable to debug.Please help

#include<bits/stdc++.h>
using namespace std;
//#include<iostream.h>
int main()
{
int T,i;
long long int mg,my,mr,og,oy,ori,pg,py,pr;
cin>>T;
//while(T)
for(i=0;i<T;i++)
{
cin>>mg>>my>>mr;
cin>>og>>oy>>ori;
cin>>pg>>py>>pr;
if((mr+mg+my)>0||(ori+oy+og)>0||(py+pg+pr)>0){

	if(((mr+my+mg)>=((my+oy+py)||(mg+pg+og)||(mr+ori+pr)))||((oy+ori+og)>=((my+oy+py)||(mg+pg+og)||(mr+ori+pr)))||((py+pr+pg)>=((my+oy+py)||(mg+pg+og)||(mr+ori+pr)))){
		if(((mr+my+mg)>=(pr+pg+py))&&((mr+my+mg)>=(ori+og+oy))){
		
		if((mr+my+mg)%2==0)
		{
		
		cout<<((mr+my+mg)-1)<<endl;
		//break;
		}
		else{
		
		cout<<(mr+my+mg)<<endl;
	//	break;
	}
		}
	else	if(((pr+py+pg)>=(mr+mg+my))&&((pr+py+pg)>=(ori+og+oy))){
		
		if((pr+py+pg)%2==0){
		
		cout<<((pr+py+pg)-1)<<endl;
	//	break;
	}
		else{
		
		cout<<(pr+py+pg)<<endl;
	//	break;
	}
		}
	
	else	if(((ori+oy+og)>=(mr+mg+my))&&((pr+py+pg)<=(ori+og+oy))){
		
		if((ori+oy+og)%2==0){
		
		cout<<((ori+oy+og)-1)<<endl;
	//	break;
	}
		else{
		
		cout<<(ori+oy+og)<<endl;
	//	break;
	}	}	
			

}
	else if((my+oy+py)>=(mg+pg+og)&&(my+oy+py)>=(mr+ori+pr)){
	
		if((my+oy+py)%2==0){
		
		cout<<((my+oy+py)-1)<<endl;
	//	break;
	}
		else{
		
		cout<<(my+oy+py)<<endl;
	//	break;
	}
}
	else if((mg+og+pg)>=(my+py+oy)&&(mg+og+pg)>=(mr+ori+pr)){
	
		if((mg+og+pg)%2==0){
		
		cout<<((mg+og+pg)-1)<<endl;
	//	break;
	}
		else{
		
		cout<<(mg+og+pg)<<endl;
	//	break;
	}
	}
	else if((mr+ori+pr)>=(mg+pg+og)&&(my+oy+py)<=(mr+ori+pr)){
	
		if((mr+ori+pr)%2==0){
		
		cout<<((mr+ori+pr)-1)<<endl;
	//	break;
	}
		else{
		
		cout<<mr+ori+pr<<endl;
	//	break;
}
	}
}
	else
	printf("0 \n");
	//T--;	
}

}

plz find the testcases in which the following code doesn’t work:

without any loop
int main()
{
int t;long long y1,y2,y3,g1,g2,g3,r1,r2,r3;
scanf("%d",&t);
while(t–)
{
unsigned long long ans=0;
scanf("%lld%lld%lld",&g1,&y1,&r1);
scanf("%lld%lld%lld",&g2,&y2,&r2);
scanf("%lld%lld%lld",&g3,&y3,&r3);
long long a=g1+g2+g3,b=y1+y2+y3,c=r1+r2+r3;
long long d=g1+y1+r1;
long long e=g2+y2+r2;
long long f=g3+y3+r3;
if(a>=b && a>=c)
ans=a;
else if(b>=a && b>=c)
ans=b;
else if(c>=b && c>=a)
ans=c;

                    if(d>=e && d>=f && d>ans)
                        ans=d;
                    else if(e>=d && e>=f && e>ans)
                        ans=e;
                    else if(f>=d && f>=e && f>ans)
                        ans=f;
                    if(ans%2==0 && ans>0)
                    printf("%llu\n",ans-1);
                    else
                    printf("%llu\n",ans);

                }
                return 0;
            }

@pjrocks I guess you missed the “\n” after every printf

@pjrocks
Your code has a small mistake according to me “\n”.
Rest works perfectly fine with the test cases I checked myself

thnks for pointing it out @shawnbam_96 and @monalshadi . bad luck :frowning:

check out my solution. No need to use matrix.
https://www.codechef.com/viewsolution/11973956

unable to debug,please help in finding the error
https://www.codechef.com/viewsolution/11973091

i think some more cases should also be considered
example consider this case
if c[i][1] + c[i][2] + c[i][3] is odd for all i=1 to 3 then it will not contribute to answer
now also res=0

also if c[1][j] + c[2][j] + c[3][j] is odd for all j=1 to 3 then it will not contribute to answer
now also res=0

but still possibilities are there to make res !=0

example
c[i][1] + c[i][2] for i=1 to 3 and it is even and greater than zero which is not considered and lead to res non zero(towards maximum)
also
consider this possibilities
c[i][2] + c[i][3] for i=1 to 3
also c[i][1] + c[i][3] for i=1 to 3

this were few other possibilities for same leaf different color(all leaves of same type)

similarly other possibilities for
c[1][j] + c[2][j] and j=1 to 3 and its is even and greater than res=0
but not considered

please correct me if i am wrong

Can you point out the mistake in this code …

#include<stdio.h>

int main(){
	long long int a[3][3], t, i, j, k, max;
	scanf("%lld", &t);
	while(t--){
		max = 0;
		for(i = 0; i < 3; i++){
			for(j = 0; j < 3; j++){
				scanf("%lld", &a[i][j]);
			}
			if(max < (a[i][0] + a[i][1] + a[i][2])){
				max = (a[i][0] + a[i][1] + a[i][2]);
			}
		}
		for(i = 0; i< 3; i++){
			if(max < (a[0][i] + a[1][i] + a[2][i])){
				max = (a[0][i] + a[1][i] + a[2][i]);
			}
		}
		if(max % 2 == 0)
			max = max - 1;
		printf("%lld\n", max);
	}
	return 0;
}

@pkacprzak
i think some more cases should also be considered
example consider this case if c[i][1] + c[i][2] + c[i][3] is odd for all i=1 to 3 then it will not contribute to answer
now also res=0
also if c[1][j] + c[2][j] + c[3][j] is odd for all j=1 to 3 then it will not contribute to answer
now also res=0

but still possibilities are there to make res !=0

example
c[i][1] + c[i][2] for i=1 to 3 and it is even and greater than zero which is not considered and lead to res non zero(towards maximum)
also
consider this possibilities
c[i][2] + c[i][3] for i=1 to 3

@vijayiota77 I don’t know exactly what you are talking about. If the sum of leaves of the same type or color is odd, we take all of them. If it’s even, then the best we can do is to take all minus one such leaf.