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

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

You don't have to reduce 4 all the way to 0 because when we have 1 17 16 then we will decrease 1 and 17 because they are the biggest and smallest right now. This will retain our claim

If you want the median to be at least X, you need at least (n / 2) + 1 elements to be greater or equal than X.

Then binary search the value of the median. Let's say the value you want to check is X. Then you have to check, whether you can increase all numbers with indexes from N/2 to N up to X, using only k moves. For this you need: a) prefix sums of array elements, b) to search the first element in the second half of the array which is already larger than X (also binary search).

If you implement binary search correctly, it must be sth like ($$$n \log n + n \log A$$$) where $$$A = 2e9$$$ and $$$n = 2e5$$$. BTW I would really like to learn how $$$O(n)$$$ solution works...

Your binary search was TLE because mid was overflowing. int mid = (l+r)/2; l = 10^9 and r = 2*10^9

During the contest, your submissions are only tested on a limited set of test (pretests). It's possible that an incorrect solution can pass pretests, so during the contest, other people in your room who have solved the same problem can choose to lock their problem and "hack" your solution (provide a test case where your soln will fail). Hackers are awarded +100 pts for succesfull hack, -50 for unsuccessful.

The pretest doesn't cover all of test data. So although you passed pretest, it can be a wrong answer. After pretest passed, you can lock the problem. It means you cannot change your answer and you can read other user's code. When you reading code, if someone's code have counterexample, you can enter counterexample and if the hacking attempt's successful, you can get 100point. but if it failed, you lose 50point. Can you understand? (sorry for my poor english)

Yeah, I didn't consider this

Yeah, that could be done. That would remove the possibility of those minor error. I didn't think that way. There wouldn't be any other differences, capturing just makes the game more realistic.