Division by Two and Permutation (Codeforces 1624C)
Tags: Greedy, flows

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers. You can perform operations on it.In one operation you can replace any element of the array $$$a_i$$$ with $$$\lfloor \frac{a_i}{2} \rfloor$$$, that is, by an integer part of dividing $$$a_i$$$ by $$$2$$$ (rounding down).See if you can apply the operation some number of times (possible $$$0$$$) to make the array $$$a$$$ become a permutation of numbers from $$$1$$$ to $$$n$$$ —that is, so that it contains all numbers from $$$1$$$ to $$$n$$$, each exactly once.For example, if $$$a = [1, 8, 25, 2]$$$, $$$n = 4$$$, then the answer is yes. You could do the following:  Replace $$$8$$$ with $$$\lfloor \frac{8}{2} \rfloor = 4$$$, then $$$a = [1, 4, 25, 2]$$$.  Replace $$$25$$$ with $$$\lfloor \frac{25}{2} \rfloor = 12$$$, then $$$a = [1, 4, 12, 2]$$$.  Replace $$$12$$$ with $$$\lfloor \frac{12}{2} \rfloor = 6$$$, then $$$a = [1, 4, 6, 2]$$$.  Replace $$$6$$$ with $$$\lfloor \frac{6}{2} \rfloor = 3$$$, then $$$a = [1, 4, 3, 2]$$$. 

Input: The first line of input data contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) —the number of test cases.Each test case contains exactly two lines. The first one contains an integer $$$n$$$ ($$$1 \le n \le 50$$$), the second one contains integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Output: For each test case, output on a separate line:  YES if you can make the array $$$a$$$ become a permutation of numbers from $$$1$$$ to $$$n$$$,  NO otherwise. You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

Note: The first test case is explained in the text of the problem statement.In the second test case, it is not possible to get a permutation.

Sample Inputs:
6
4
1 8 25 2
2
1 1
9
9 8 3 4 2 7 1 5 6
3
8 2 1
4
24 7 16 7
5
22 6 22 4 22

Sample Outputs:
YES
NO
YES
NO
NO
YES

Solution (Python):
def division_by_two_and_permutation():
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort(reverse=True)
    used = [False] * (n + 1)
    ok = True
    for h in arr:
        x = h
        while x > n or used[x]:
            x //= 2
        if x > 0:
            used[x] = True
        else:
            ok = False
    print('YES\n' if ok else 'NO\n')
t = int(input())
while t > 0:
    division_by_two_and_permutation()
    t -= 1

Solution (Python):
def is_arrangement_possible(n, arr):
    arr.sort(reverse=True)
    used = [False] * (n + 1)
    is_possible = True
    for num in arr:
        x = num
        while x > n or used[x]:
            x //= 2
        if x > 0:
            used[x] = True
        else:
            is_possible = False
    return is_possible
if __name__ == '__main__':
    test_cases = int(input())
    for _ in range(test_cases):
        n = int(input())
        arr = list(map(int, input().split()))
        result = is_arrangement_possible(n, arr)
        print('YES' if result else 'NO')

Solution (Python):
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort(reverse=True)
    used = [False] * (n + 1)
    ok = True
    for i in a:
        x = i
        while x > n or used[x]:
            x //= 2
        if x > 0:
            used[x] = True
        else:
            ok = False
    print('YES' if ok else 'NO')
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()