PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There’s an array with X occurrences of 1 and Y occurrences of 2, where (X+Y) is a multiple of 3.
In one move, you take three previously unchosen elements and add their maximum to your score.
What’s the maximum score you can attain?
EXPLANATION:
Let N = X+Y be the length of the array.
We must then choose exactly \frac{N}{3} triplets, spanning all N elements.
Since each element is either 1 or 2, observe that the score of a triplet will be 2 if at least one of its elements is 2, and will be 1 only if all three elements are 1.
We want to maximize the score, so naturally it makes sense to try and maximize the number of triplets with score 2.
Let’s think about when we can make every triplet have a score of 2.
There are \frac{N}{3} triplets, so we certainly need at least \frac{N}{3} occurrences of 2, since we’ll need to give an occurrence to each triplet.
It’s now easy to see that if this condition is satisfied, i.e. we have at least \frac{N}{3} occurrences of 2, we can surely make every triplet have a score of 2 - just give one occurrence to each triplet, and then distribute the remaining elements however you like.
Thus, if Y \ge \frac{N}{3}, the answer is simply \frac{2N}{3}, since we’ll have \frac{N}{3} triplets with a score of 2 each.
That leaves the case of Y \lt \frac{N}{3}.
Here, we can only have Y triplets with a score of 2, by giving one occurrence of 2 to each of Y distinct triplets.
This is also clearly the best we can do.
Hence, there are \frac{N}{3} - Y triplets remaining, which will each have a score of 1.
So, the answer in this case is 2\cdot Y + (\frac{N}{3} - Y) = \frac{N}{3} + Y.
To summarize:
- If Y \ge \frac N 3, the answer is \frac{2N}{3}.
- Otherwise, the answer is \frac{N}{3} + Y.
You can technically avoid having to do casework by noting that this is equivalent to the expression \frac{N}{3} + \min(Y, \frac{N}{3}).
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
x, y = map(int, input().split())
n = x + y
if y >= n//3: print(2*(n//3))
else: print(y + n//3)