codeforces-scrape

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

1915E.md (2355B)


      1 Source: https://codeforces.com/problemset/problem/1915/E
      2 
      3 E. Romantic Glasses
      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 Iulia has $n$ glasses arranged in a line. The $i$-th glass has $a_i$ units of juice in it. Iulia drinks only from odd-numbered glasses, while her date drinks only from even-numbered glasses.
     22 
     23 To impress her date, Iulia wants to find a contiguous subarray of these glasses such that both Iulia and her date will have the same amount of juice in total if only the glasses in this subarray are considered. Please help her to do that.
     24 
     25 More formally, find out if there exists two indices $l$, $r$ such that $1 \leq l \leq r \leq n$, and $a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r} = a_{l + 1} + a_{l + 3} + \dots + a_{r-1}$ if $l$ and $r$ have the same parity and $a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r - 1} = a_{l + 1} + a_{l + 3} + \dots + a_{r}$ otherwise.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the total number of glasses.
     32 
     33 The second line of each test case contains $n$ integers $a_1, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the amount of juice in each glass.
     34 
     35 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, output "YES" if there exists a subarray satisfying the condition, and "NO" otherwise.
     40 
     41 You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 6
     49 
     50 3
     51 
     52 1 3 2
     53 
     54 6
     55 
     56 1 1 1 1 1 1
     57 
     58 10
     59 
     60 1 6 9 8 55 3 14 2 7 2
     61 
     62 8
     63 
     64 1 2 11 4 1 5 1 2
     65 
     66 6
     67 
     68 2 6 1 5 7 8
     69 
     70 9
     71 
     72 2 5 10 4 4 9 6 7 8
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 YES
     79 YES
     80 NO
     81 YES
     82 NO
     83 YES
     84 ```
     85 
     86 Note
     87 
     88 In the first test case, Iulia can pick $l=1$ and $r=3$. Then she drinks $a_1+a_3=1+2=3$ units and her date drinks $a_2=3$ units of juice.
     89 
     90 In the second test case, Iulia can pick $l=2$ and $r=5$. Then she drinks $a_3+a_5=1+1=2$ units and her date drinks $a_2+a_4=1+1=2$ units of juice.
     91 
     92 In the third test case no such contiguous subarray works.
     93 
     94 In the fourth test case, Iulia can pick $l=2$ and $r=8$. Then she drinks $a_3+a_5+a_7=11+1+1=13$ units and her date drinks $a_2+a_4+a_6+a_8=2+4+5+2=13$ units of juice.