codeforces-scrape

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

2275C.md (2010B)


      1 Source: https://codeforces.com/problemset/problem/2275/C
      2 
      3 C. Unrequited Love
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 K1o0n reached the stage where, for complete happiness, he only lacked a musical instrument, and bought a synthesizer second-hand. The instrument has $n$ keys, giving $a_1, a_2, \ldots, a_n$ units of audience love.
     22 
     23 Playing one note at a time is boring, so K1o0n learned a single technique — a triad: three keys with one key between each pair, pressed simultaneously. A triad starting at $x$ ($1 \le x \le n - 4$) is the keys $x$, $x+2$, and $x+4$, which brings $a_x + a_{x+2} - a_{x+4}$ units of audience love.
     24 
     25 The keys are old, and each can withstand exactly one press. Therefore, K1o0n wants to choose exactly two different triads that do not share any keys. In addition, he wants both triads to bring the same amount of audience love.
     26 
     27 Count the number of ways to choose two such triads.
     28 
     29 Input
     30 
     31 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of testcases.
     32 
     33 The first line of each testcase contains an integer $n$ ($6 \le n \le 2 \cdot 10^5$) — the number of keys.
     34 
     35 The second line of each testcase contains $n$ integers $a_i$ ($-10^4 \le a_i \le 10^4$) — the units of audience love.
     36 
     37 It is guaranteed that the sum of $n$ over all testcases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each testcase, output one integer — the number of unordered pairs of disjoint triads with equal audience love values.
     42 
     43 Note that the answer may not fit into a 32-bit type. Use a 64-bit type (long long in C++, long in Java).
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 3
     51 
     52 6
     53 
     54 5 1 4 2 2 -4
     55 
     56 7
     57 
     58 0 0 0 0 0 0 0
     59 
     60 12
     61 
     62 -4 3 0 -4 -4 -1 -4 1 -3 -2 -2 -1
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 1
     69 
     70 2
     71 
     72 5
     73 ```
     74 
     75 Note
     76 
     77 In the first testcase, such a pair is unique: $x = 1$, $y = 2$: $5 + 4 - 2 = 1 + 2 - (-4)$.
     78 
     79 In the second testcase, there are two such pairs: $x = 1$, $y = 2$ and $x = 3$, $y = 2$, and each triad brings $0$ units of audience love.