Water the Trees (Codeforces 1661C)
Tags: Greedy, binary search

There are $$$n$$$ trees in a park, numbered from $$$1$$$ to $$$n$$$. The initial height of the $$$i$$$-th tree is $$$h_i$$$.You want to water these trees, so they all grow to the same height.The watering process goes as follows. You start watering trees at day $$$1$$$. During the $$$j$$$-th day you can:   Choose a tree and water it. If the day is odd (e.g. $$$1, 3, 5, 7, \dots$$$), then the height of the tree increases by $$$1$$$. If the day is even (e.g. $$$2, 4, 6, 8, \dots$$$), then the height of the tree increases by $$$2$$$.  Or skip a day without watering any tree. Note that you can't water more than one tree in a day. Your task is to determine the minimum number of days required to water the trees so they grow to the same height.You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases.The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of trees.The second line of the test case contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$), where $$$h_i$$$ is the height of the $$$i$$$-th tree.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$ ($$$\sum n \le 3 \cdot 10^5$$$).

Output: For each test case, print one integer — the minimum number of days required to water the trees, so they grow to the same height.

Note: Consider the first test case of the example. The initial state of the trees is $$$[1, 2, 4]$$$.  During the first day, let's water the first tree, so the sequence of heights becomes $$$[2, 2, 4]$$$;  during the second day, let's water the second tree, so the sequence of heights becomes $$$[2, 4, 4]$$$;  let's skip the third day;  during the fourth day, let's water the first tree, so the sequence of heights becomes $$$[4, 4, 4]$$$. Thus, the answer is $$$4$$$.

Sample Inputs:
3
3
1 2 4
5
4 4 3 5 5
7
2 5 4 8 3 7 4

Sample Outputs:
4
3
16

Solution (Python):
def minimumDays(array):

    def balance_odd_even_days(n_odd_days, n_even_days):
        while n_even_days > n_odd_days:
            x = -(-(n_even_days - n_odd_days) // 3)
            n_even_days = n_even_days - x
            n_odd_days = n_odd_days + 2 * x
        return (n_odd_days, n_even_days)

    def get_odd_even_days(array, max_height):
        n_odd_days = 0
        n_even_days = 0
        for tree in array:
            n_odd_days += (max_height - tree) % 2
            n_even_days += int((max_height - tree) / 2)
        return (n_odd_days, n_even_days)
    (n_odd_days, n_even_days) = get_odd_even_days(array, max(array))
    if n_even_days == n_odd_days:
        return n_even_days + n_odd_days
    if n_even_days > n_odd_days:
        (n_odd_days, n_even_days) = balance_odd_even_days(n_odd_days, n_even_days)
        return n_even_days + n_odd_days
    old_result = n_odd_days + n_odd_days - 1
    (n_odd_days, n_even_days) = get_odd_even_days(array, max(array) + 1)
    if n_even_days == n_odd_days:
        return min(n_even_days + n_odd_days, old_result)
    if n_even_days > n_odd_days:
        (n_odd_days, n_even_days) = balance_odd_even_days(n_odd_days, n_even_days)
        return min(n_even_days + n_odd_days, old_result)
    return min(old_result, n_odd_days + n_odd_days - 1)
inp = int(input())
inputs = []
for _ in range(inp):
    length = int(input())
    a = list(map(int, input().strip().split()))[:length]
    inputs.append(a)
for l in inputs:
    print(minimumDays(l))

Solution (Python):
import sys
from os import path

def solve(word):
    hieghts = word.split(' ')
    trees = [int(i) for i in hieghts]
    Max = max(trees)
    Sum = 0
    c1 = 0
    Sum2 = 0
    c12 = 0
    for i in trees:
        dist = Max - i
        dist2 = Max - i + 1
        if dist % 2 == 1:
            Sum += dist // 2
            c1 += 1
        else:
            Sum += dist // 2
        if dist2 % 2 == 1:
            Sum2 += dist2 // 2
            c12 += 1
        else:
            Sum2 += dist2 // 2
    if c1 > Sum + 1:
        ans = c1 + c1 - 1
    elif Sum > c1:
        x = (Sum - c1) * 2
        if x % 3 == 0:
            ans = x // 3 * 2
        elif x % 3 == 1:
            ans = x // 3 * 2 + 1
        else:
            ans = x // 3 * 2 + 2
        ans += c1 * 2
    else:
        ans = c1 + Sum
    if c12 > Sum2 + 1:
        ans2 = c12 + c12 - 1
    elif Sum2 > c12:
        x = (Sum2 - c12) * 2
        if x % 3 == 0:
            ans2 = x // 3 * 2
        elif x % 3 == 1:
            ans2 = x // 3 * 2 + 1
        else:
            ans2 = x // 3 * 2 + 2
        ans2 += c12 * 2
    else:
        ans2 = c12 + Sum2
    return min(ans, ans2)

def get_int():
    """"""
    return int(sys.stdin.readline())

def get_string():
    """"""
    return sys.stdin.readline().strip()
n = get_int()
final_result = []
for i in range(n):
    num_trees = get_int()
    word = get_string()
    out = solve(word)
    final_result.append(out)
for item in final_result:
    sys.stdout.write(str(item))
    sys.stdout.write('\n')

Solution (Python):
from __future__ import division
import copy
import random
import heapq
import math
import sys
import bisect
import re
import time
import datetime
from functools import lru_cache
from collections import deque
from collections import Counter
from collections import defaultdict
from itertools import combinations
from itertools import permutations
from itertools import accumulate
from decimal import Decimal, getcontext, MAX_PREC
from types import GeneratorType
from functools import cmp_to_key
inf = float('inf')
sys.setrecursionlimit(10000000)
getcontext().prec = MAX_PREC

class FastIO:

    def __init__(self):
        return

    @staticmethod
    def _read():
        return sys.stdin.readline().strip()

    def read_int(self):
        return int(self._read())

    def read_float(self):
        return float(self._read())

    def read_ints(self):
        return map(int, self._read().split())

    def read_floats(self):
        return map(float, self._read().split())

    def read_ints_minus_one(self):
        return map(lambda x: int(x) - 1, self._read().split())

    def read_list_ints(self):
        return list(map(int, self._read().split()))

    def read_list_floats(self):
        return list(map(float, self._read().split()))

    def read_list_ints_minus_one(self):
        return list(map(lambda x: int(x) - 1, self._read().split()))

    def read_str(self):
        return self._read()

    def read_list_strs(self):
        return self._read().split()

    def read_list_str(self):
        return list(self._read())

    @staticmethod
    def st(x):
        return sys.stdout.write(str(x) + '\n')

    @staticmethod
    def lst(x):
        return sys.stdout.write(' '.join((str(w) for w in x)) + '\n')

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def bootstrap(f, stack=[]):

        def wrappedfunc(*args, **kwargs):
            if stack:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if isinstance(to, GeneratorType):
                        stack.append(to)
                        to = next(to)
                    else:
                        stack.pop()
                        if not stack:
                            break
                        to = stack[-1].send(to)
                return to
        return wrappedfunc

def main(ac=FastIO()):

    def check(x, y):
        if x == y:
            return 2 * x
        if x > y:
            return 2 * x - 1
        d = (y - x) * 2
        return 2 * x + 2 * (d // 3) + d % 3
    t = ac.read_int()
    for _ in range(t):
        ac.read_int()
        nums = ac.read_list_ints()
        ceil = max(nums)
        one = two = 0
        for num in nums:
            two += (ceil - num) // 2
            one += (ceil - num) % 2
        ans1 = check(one, two)
        ceil = max(nums) + 1
        one = two = 0
        for num in nums:
            two += (ceil - num) // 2
            one += (ceil - num) % 2
        ans2 = check(one, two)
        ac.st(ac.min(ans1, ans2))
    return
main()