BALLS - Editorial






Given N(<=10^5) balls, each with a number on top and bottom, find minimum number of flips that can make at least half of the balls show same number on their top. Print “impossible”, if not possible.


This problem can be solved by keeping a track of how many times a number has occurred on top/bottom. Iterate through all possible numbers that we have and suppose that this number occurs on top, then find total number of moves for this number to show up on at least half of the total balls. The minimal number through all this will be the answer. To find the minimal number of turns to make we need to know two numbers: the number of balls with current color on the top and the number of balls with the current number on bottom (but not at the same time). Let it be integers a and b. Let m = (n + 1) / 2 — the minimal number count of current number to win the game. Then if a + b < m it is impossible won the game using current number at all. If a ≥ m then the answer is 0, otherwise the answer is m - a.


setter.cpp By Prateek Sachdev