CF1646B Quality vs Quantity

$ \def\myred#1{\color{red}{\underline{\bf{#1}}}} \def\myblue#1{\color{blue}{\overline{\bf{#1}}}} $ $ \def\RED{\myred{Red}} \def\BLUE{\myblue{Blue}} $ You are given a sequence of $ n $ non-negative integers $ a_1, a_2, \ldots, a_n $ . Initially, all the elements of the sequence are unpainted. You can paint each number $ \RED $ or $ \BLUE $ (but not both), or leave it unpainted. For a color $ c $ , $ \text{Count}(c) $ is the number of elements in the sequence painted with that color and $ \text{Sum}(c) $ is the sum of the elements in the sequence painted with that color. For example, if the given sequence is $ [2, 8, 6, 3, 1] $ and it is painted this way: $ [\myblue{2}, 8, \myred{6}, \myblue{3}, 1] $ (where $ 6 $ is painted red, $ 2 $ and $ 3 $ are painted blue, $ 1 $ and $ 8 $ are unpainted) then $ \text{Sum}(\RED)=6 $ , $ \text{Sum}(\BLUE)=2+3=5 $ , $ \text{Count}(\RED)=1 $ , and $ \text{Count}(\BLUE)=2 $ . Determine if it is possible to paint the sequence so that $ \text{Sum}(\RED) > \text{Sum}(\BLUE) $ and $ \text{Count}(\RED) < \text{Count}(\BLUE) $ .

N/A

N/A

In the first test case, there is no possible way to paint the sequence. For example, if you paint the sequence this way: $ [\myblue{1},\myblue{2},\myred{3}] $ (where $ 3 $ is painted red, $ 1 $ and $ 2 $ are painted blue) then $ \text{Count}(\RED)=1 < \text{Count}(\BLUE)=2 $ , but $ \text{Sum}(\RED)=3 \ngtr \text{Sum}(\BLUE)=3 $ . So, this is not a possible way to paint the sequence. In the second test case, a possible way to paint the sequence is described in the statement. We can see that $ \text{Sum}(\RED)=6 > \text{Sum}(\BLUE)=5 $ and $ \text{Count}(\RED)=1 < \text{Count}(\BLUE)=2 $ . In the third test case, there is no possible way to paint the sequence. For example, if you paint the sequence this way: $ [\myred{3},\myred{5},\myblue{4}, \myblue{2}] $ (where $ 3 $ and $ 5 $ are painted red, $ 4 $ and $ 2 $ are painted blue) then $ \text{Sum}(\RED) = 8 > \text{Sum}(\BLUE) = 6 $ but $ \text{Count}(\RED) = 2 \nless \text{Count}(\BLUE) = 2 $ . So, this is not a possible way to paint the sequence. In the fourth test case, it can be proven that there is no possible way to paint the sequence satisfying sum and count constraints.