Valerii Against Everyone (Codeforces 1438B)
Tags: Greedy, sortings

You're given an array $$$b$$$ of length $$$n$$$. Let's define another array $$$a$$$, also of length $$$n$$$, for which $$$a_i = 2^{b_i}$$$ ($$$1 \leq i \leq n$$$). Valerii says that every two non-intersecting subarrays of $$$a$$$ have different sums of elements. You want to determine if he is wrong. More formally, you need to determine if there exist four integers $$$l_1,r_1,l_2,r_2$$$ that satisfy the following conditions:   $$$1 \leq l_1 \leq r_1 \lt l_2 \leq r_2 \leq n$$$;  $$$a_{l_1}+a_{l_1+1}+\ldots+a_{r_1-1}+a_{r_1} = a_{l_2}+a_{l_2+1}+\ldots+a_{r_2-1}+a_{r_2}$$$. If such four integers exist, you will prove Valerii wrong. Do they exist?An array $$$c$$$ is a subarray of an array $$$d$$$ if $$$c$$$ can be obtained from $$$d$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.The first line of every test case contains a single integer $$$n$$$ ($$$2 \le n \le 1000$$$).The second line of every test case contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$0 \le b_i \le 10^9$$$). 

Output: For every test case, if there exist two non-intersecting subarrays in $$$a$$$ that have the same sum, output YES on a separate line. Otherwise, output NO on a separate line. Also, note that each letter can be in any case. 

Note: In the first case, $$$a = [16,8,1,2,4,1]$$$. Choosing $$$l_1 = 1$$$, $$$r_1 = 1$$$, $$$l_2 = 2$$$ and $$$r_2 = 6$$$ works because $$$16 = (8+1+2+4+1)$$$.In the second case, you can verify that there is no way to select to such subarrays.

Sample Inputs:
2
6
4 3 0 1 2 0
2
2 5

Sample Outputs:
YES
NO

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    print('NO' if len(set(list(map(int, input().split())))) == n else 'YES')

Solution (Python):
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        n = int(input())
        b = list(map(int, input().split()))
        count = dict()
        response = 'NO'
        for i in range(n):
            if b[i] in count:
                response = 'YES'
                break
            else:
                count[b[i]] = 1
        print(response)

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    b = list(map(int, input().split()))
    if len(b) != len(set(b)):
        print('YES')
    else:
        print('NO')