codeforces-scrape

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

1677A.md (1735B)


      1 Source: https://codeforces.com/problemset/problem/1677/A
      2 
      3 A. Tokitsukaze and Strange Inequality
      4 
      5 time limit per test
      6 
      7 1.5 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 Tokitsukaze has a permutation $p$ of length $n$. Recall that a permutation $p$ of length $n$ is a sequence $p_1, p_2, \ldots, p_n$ consisting of $n$ distinct integers, each of which from $1$ to $n$ ($1 \leq p_i \leq n$).
     22 
     23 She wants to know how many different indices tuples $[a,b,c,d]$ ($1 \leq a \lt b \lt c \lt d \leq n$) in this permutation satisfy the following two inequalities:
     24 
     25  $p_a \lt p_c$ and $p_b \gt p_d$. 
     26 
     27 Note that two tuples $[a_1,b_1,c_1,d_1]$ and $[a_2,b_2,c_2,d_2]$ are considered to be different if $a_1 \ne a_2$ or $b_1 \ne b_2$ or $c_1 \ne c_2$ or $d_1 \ne d_2$.
     28 
     29 Input
     30 
     31 The first line contains one integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. Each test case consists of two lines.
     32 
     33 The first line contains a single integer $n$ ($4 \leq n \leq 5000$) — the length of permutation $p$.
     34 
     35 The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$) — the permutation $p$.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.
     38 
     39 Output
     40 
     41 For each test case, print a single integer — the number of different $[a,b,c,d]$ tuples.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 6
     51 
     52 5 3 6 1 4 2
     53 
     54 4
     55 
     56 1 2 3 4
     57 
     58 10
     59 
     60 5 1 6 2 8 3 4 10 9 7
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 3
     67 0
     68 28
     69 ```
     70 
     71 Note
     72 
     73 In the first test case, there are $3$ different $[a,b,c,d]$ tuples.
     74 
     75 $p_1 = 5$, $p_2 = 3$, $p_3 = 6$, $p_4 = 1$, where $p_1 \lt p_3$ and $p_2 \gt p_4$ satisfies the inequality, so one of $[a,b,c,d]$ tuples is $[1,2,3,4]$.
     76 
     77 Similarly, other two tuples are $[1,2,3,6]$, $[2,3,5,6]$.