codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.