Table Decorations

This post is in reference to CodeForces Table Decorations.

You have 3 piles — of size A B & C — and you can take a triplet from them as long as you take from more than one. So what is the maximum number of triplets?

e.g.
Piles delim{lbrace}{10,2,1}{rbrace}: take delim{lbrace}{2,0,1}{rbrace},delim{lbrace}{2,1,0}{rbrace}, and delim{lbrace}{2,1,0}{rbrace}.
Max triplets = 3

N.B. we have left over delim{lbrace}{4,0,0}{rbrace} which can’t be used.

I must admit, when I began to work on this, I took the wrong track. I tried to iterate over the input, pulling out triplets in a greedy fashion. This pile is biggest so take from that. But do I take 2 plus 1 from the next? Or take from all? And because the inputs are so large, how many triplets do I pull at once? How do I guarantee I’m making the best next move? etc.

But no, we aren’t calculating a list of triplets, just how many. So the question becomes: which inputs can’t be used? Then everything else can be, it doesn’t matter how exactly.

If A > 2(B+C), we can’t use anything above 2(B+C). And the same for B & ┬áC. So, after these are chopped off, we get the following:

max triplets = floor({A_chopped + B_chopped + C_chopped}/3)

Leave a Reply

Your email address will not be published. Required fields are marked *