CSWEETS - Editorial

editorial
,
1

PROBLEM LINK:

Contest

Author: Rahul Sharma

Tester: Sumukh Bhardwaj

Editorialist: Rahul Sharma

DIFFICULTY:

Easy

PREREQUISITES:

Basic programming, Math, Pattern

PROBLEM:

Given two types of sweets with quantity A and B respectively. Each person will get 3 sweets with atleast one of each type. Find maximum number of people to distribute the sweets.

QUICK EXPLANATION:

Minimum of A, B, and (A+B)/3 will be the answer

EXPLANATION:

Let us first find the pairs of (A,B) which will be
pair = min(A,B).
Now excess of sweets left over of any type will be
singleSweetLeftOver = abs(A-B)

To complete the triplet with atleast on sweet of each typw we need to adjust these extra sweets to exsiting pair.

If singleSweetLeftOver >= pair then ans = pair because that many sweets can be added to each pair to compete the triplet.
Else ans = singleSweetLeftOver + tripletsFromLeftOverpair because triplet corresponding to number singleSweetLeftOver will be complete but we will still be having some left over pairs that can be readjusted to complete more valid triplet.

Let us consider when pairLeftOver = 1
it will be ab and no valid triplet can be formed thus tripletsFromLeftOverpair=0

pairLeftOver=2
ab
ab
1 valid triplet aab or bba can be formed thus tripletsFromLeftOverpair=1

pairLeftOver=3
ab
ab
ab
2 valid triplet aab and bba can be formed thus tripletsFromLeftOverpair=2

similarly for pairLeftOver=4, tripletsFromLeftOverpair=2 and we can continue this and note a pattern.

To generalize this

if (pairLeftOver % 3 == 0 or 1):
    tripletsFromLeftOVer = 2*(pairLeftOver/3)
else
    tripletsFromLeftOVer = 2*(pairLeftOVer/3)  + 1

COMPLEXITIES:

Time Complexity: O(1) for each test case
Space Complexity: O(1) for each test case

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

int main()
{
	long long int a, b, ans = 0;
	cin >> a >> b;

	long long int pair = min(a,b);
	long long int singleLeftover = abs(a-b);
	ans = min(pair, singleLeftover);

	long long int pairLeftover = pair - ans;

	if(pairLeftover % 3 == 0 || pairLeftover % 3 == 1)
		ans = ans + 2*(pairLeftover/3);
	else
		ans = ans + 2*(pairLeftover/3) + 1;

	cout << ans;
}