1698C.md (1848B)
1 Source: https://codeforces.com/problemset/problem/1698/C 2 3 C. 3SUM Closure 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array $a$ of length $n$. The array is called 3SUM-closed if for all distinct indices $i$, $j$, $k$, the sum $a_i + a_j + a_k$ is an element of the array. More formally, $a$ is 3SUM-closed if for all integers $1 \leq i \lt j \lt k \leq n$, there exists some integer $1 \leq l \leq n$ such that $a_i + a_j + a_k = a_l$. 22 23 Determine if $a$ is 3SUM-closed. 24 25 Input 26 27 The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. 28 29 The first line of each test case contains an integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of the array. 30 31 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \leq a_i \leq 10^9$) — the elements of the array. 32 33 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 34 35 Output 36 37 For each test case, output "YES" (without quotes) if $a$ is 3SUM-closed and "NO" (without quotes) otherwise. 38 39 You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response). 40 41 Example 42 43 Input 44 45 ``` 46 4 47 48 3 49 50 -1 0 1 51 52 5 53 54 1 -2 -2 1 -3 55 56 6 57 58 0 0 0 0 0 0 59 60 4 61 62 -1 2 -3 4 63 ``` 64 65 Output 66 67 ``` 68 YES 69 NO 70 YES 71 NO 72 ``` 73 74 Note 75 76 In the first test case, there is only one triple where $i=1$, $j=2$, $k=3$. In this case, $a_1 + a_2 + a_3 = 0$, which is an element of the array ($a_2 = 0$), so the array is 3SUM-closed. 77 78 In the second test case, $a_1 + a_4 + a_5 = -1$, which is not an element of the array. Therefore, the array is not 3SUM-closed. 79 80 In the third test case, $a_i + a_j + a_k = 0$ for all distinct $i$, $j$, $k$, and $0$ is an element of the array, so the array is 3SUM-closed.