LMP5 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: kingmessi
Tester: pols_agyi_pols
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given a rectangle with dimensions L\times W.
You also have three colors of paint - red, green, blue - with quantities R, G, B respectively.
It’s guaranteed that R+G+B = 2\cdot (L + W).

All four sides of the rectangle must be painted with the given colors.
The cost of painting a side is the number of distinct colors used.
Find the minimum total cost of painting the rectangle.

EXPLANATION:

Without loss of generality, we assume L \le W, i.e. the length is smaller than the width (if not, swap them and the answer doesn’t change.)

Each side has a cost of between 1 and 3, depending on how many colors are used.
So, the answer lies between 4 and 12.

However, we can in fact obtain a much better upper bound on the answer.

Consider the following greedy coloring:

  • Start from some vertex of the rectangle, and move clockwise.
  • First, use as much red as possible, till it runs out.
  • Then, use as much green as possible, till it runs out.
  • Finally, use blue to color the remaining part.

It can be observed that this strategy attains a cost of no more than 6.
This is because each side has a base cost of 1, and then:

  • There is at most one side containing both red and green (which is when we change from red to green), adding 1 to the cost.
  • There is at most one side containing both green and blue (which is when we change from green to blue), adding 1 to the cost.
    • If these happen on different sides, these together give a maximum cost of 4+1+1 = 6.
  • If some side contains both red and blue, then it will also contain the entirety of green; and hence the other three sides will each be single-colored (either red or blue).
    Thus, in this case also the cost is 3+1+1+1 = 6.

So, with the answer being no more than 6, we only need to check if it’s 4 or 5 - if neither work, 6 is the answer.

Now, this upper bound actually heavily restricts the types of colorings possible in an optimal solution.

First, consider checking for answer = 4.
Here, each side receives exactly one color.
Since there are three colors (each with positive quantity) and four sides, this means two colors will receive one color each and the third color will receive two sides.

This can be easily checked via brute-force: there are \binom{4}{2} = 6 choices for which pair of sides will receive the same color (technically only 3 choices because of symmetry of lengths), and after fixing this pair, 3! = 6 orders of colors to check against the side assignments.

If any of these work, the answer is 4.

Next, we consider checking for answer = 5.

Here, one side receives two colors and the others receive a single color each.

To check for this easily: suppose one side receives red and blue.
Then, note that green must cover an entire subset of edges by itself; so this is a necessary condition.
Further, if green is able to cover a subset of edges by itself, it’s always possible to make red and blue cover the remaining edges (while also ensuring at most one edge has both red and blue), so this condition is also sufficient.

Thus, to check for whether a single red+blue edge works, we only really need to check if green can cover an entire subset of edges by itself.

This applies to the other combinations too - so, answer = 5 can happen only when there exists at least one color which can cover some subset of edges by itself.
This is easy to check by just bruteforcing color + a subset of edges, since there are 3 colors and 2^4 - 1 = 15 subsets.

If the answer is neither 4 nor 5, then it must be 6 as noted above.

TIME COMPLEXITY:

\mathcal{O}(1) but with somewhat high constant - around 100 operations per testcase.

CODE:

Editorialist's code (PyPy3) 
import itertools

for _ in range(int(input())):
    l, w, r, g, b = map(int, input().split())
    lens = [l, w, l, w]
    
    ans = 6
    
    # ans = 4
    for colp in itertools.permutations([r, g, b]):
        for lensp in itertools.permutations(lens):
            if lensp[0] + lensp[1] == colp[0] and lensp[2] == colp[1] and lensp[3] == colp[2]:
                ans = 4
    
    # ans = 5
    sums = []
    for mask in range(1, 2**4):
        sm = 0
        for i in range(4):
            if mask & 2**i: sm += lens[i]
        sums.append(sm)
    
    for col in [r, g, b]:
        if col in sums:
            ans = min(ans, 5)
    
    print(ans)