okay man . it was just a suggestion... i couldn't understand what you wrote but I'm sorry if i upset you.

good luck!

This is why

i really do love farmer john! μ~~~

think it's just some dp on leftmost/rightmost element in each row. lots of typing

DP. Iterate over rows and for each treasure holding how fast you can reach that treasure with all treasures in the same row be gotten too.

That's just my thinking. Late for submiting. RIP rate:)

$$$dp_{row, lasty, lastcol}$$$, where $$$row$$$ is the number of row (we need to consider only rows with at last one treasure but in fact it does not matter), $$$lasty$$$ is either $$$0$$$ or $$$1$$$ and means that the last $$$y$$$ on the current row we visited is the leftmost $$$y$$$ of some treasure on the current row or the rightmost such $$$y$$$. And $$$lastcol$$$ is either $$$0$$$ or $$$1$$$ too and means that after visiting the leftmost/rightmost $$$y$$$ with the treasyre we go to the left safety column or to the right safety column from this $$$y$$$. Transitions are very easy to understand but hard do code.

???

I suppose you mean 4 numbers, (3, 3, 3, 5).

(1, 4), (1, 4), (2, 4), (2, 4), (3, 4), (1, 3), (2, 3).

• sum=14
• 5<=7

• 3 3 2 4

• 3 2 2 3
• .....
• 0 2 2 0
• .....
• 0 0 0 0

Use the last element with the first three, then it's 2,2,2,2 and it's easy.

Try to think number $$$x$$$ as $$$x$$$ balls of one color. We can match a ball with another ball with another color (pair with same balls is not allowed). Then, we note that if there are odd balls, we can't complete matching. This is first point. If we have too many balls of one color (by "too many", I mean more than half of all balls), by the pigeonhole principle (although it is pretty straightforward), at least one pair must contain two balls of that color.

• 2 2 2
• 1 1 2
• 0 1 1
• 0 0 0

If a color has cardinality over n/2, there is no solution because you will need to pair up two elements of a color at least once. Otherwise, we construct a solution as follows: make each move by choosing of the two largest groups of colors. It is intuitively clear to me that making this kind of move will ensure that, in subsequent moves, no color gets to cardinality over (total number of balls)/2. And if we always preserve this property, there will always be at least 2 piles.

It seems quite awkward for me to explain how I approached this problem since I struggled twice (If you take a look at my submission, you'll notice that I tried 2 completely different logic which both were not working).

However, I think for this problem some caseworks can help. I basically noticed second approach when I thought of following case :
2 numbers, (1, 7). Sum is even, but we can't do the task.

Here is the idea of proof

Answer is YES