codeforces-scrape

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

1974C.md (2221B)


      1 Source: https://codeforces.com/problemset/problem/1974/C
      2 
      3 C. Beautiful Triple Pairs
      4 
      5 time limit per test
      6 
      7 4 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 Polycarp was given an array $a$ of $n$ integers. He really likes triples of numbers, so for each $j$ ($1 \le j \le n - 2$) he wrote down a triple of elements $[a_j, a_{j + 1}, a_{j + 2}]$.
     22 
     23 Polycarp considers a pair of triples $b$ and $c$ beautiful if they differ in exactly one position, that is, one of the following conditions is satisfied:
     24 
     25 * $b_1 \ne c_1$ and $b_2 = c_2$ and $b_3 = c_3$;
     26 * $b_1 = c_1$ and $b_2 \ne c_2$ and $b_3 = c_3$;
     27 * $b_1 = c_1$ and $b_2 = c_2$ and $b_3 \ne c_3$.
     28 
     29 Find the number of beautiful pairs of triples among the written triples $[a_j, a_{j + 1}, a_{j + 2}]$.
     30 
     31 Input
     32 
     33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     34 
     35 The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the length of the array $a$.
     36 
     37 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the elements of the array.
     38 
     39 It is guaranteed that the sum of the values of $n$ for all test cases in the test does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, output a single integer — the number of beautiful pairs of triples among the pairs of the form $[a_j, a_{j + 1}, a_{j + 2}]$.
     44 
     45 Note that the answer may not fit into 32-bit data types.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 8
     53 
     54 5
     55 
     56 3 2 2 2 3
     57 
     58 5
     59 
     60 1 2 1 2 1
     61 
     62 8
     63 
     64 1 2 3 2 2 3 4 2
     65 
     66 4
     67 
     68 2 1 1 1
     69 
     70 8
     71 
     72 2 1 1 2 1 1 1 1
     73 
     74 7
     75 
     76 2 1 1 1 1 1 1
     77 
     78 6
     79 
     80 2 1 1 1 1 1
     81 
     82 5
     83 
     84 2 1 1 1 1
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 2
     91 0
     92 3
     93 1
     94 8
     95 4
     96 3
     97 2
     98 ```
     99 
    100 Note
    101 
    102 In the first example, $a = [3, 2, 2, 2, 3]$, Polycarp will write the following triples:
    103 
    104 1. $[3, 2, 2]$;
    105 2. $[2, 2, 2]$;
    106 3. $[2, 2, 3]$.
    107 
    108 The beautiful pairs are triple $1$ with triple $2$ and triple $2$ with triple $3$.
    109 
    110 In the third example, $a = [1, 2, 3, 2, 2, 3, 4, 2]$, Polycarp will write the following triples:
    111 
    112 1. $[1, 2, 3]$;
    113 2. $[2, 3, 2]$;
    114 3. $[3, 2, 2]$;
    115 4. $[2, 2, 3]$;
    116 5. $[2, 3, 4]$;
    117 6. $[3, 4, 2]$;
    118 
    119 The beautiful pairs are triple $1$ with triple $4$, triple $2$ with triple $5$, and triple $3$ with triple $6$.