GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Tuesday 12 July 2022

[Solution] Yet Another Problem About Pairs Satisfying an Inequality Codeforces Solution



Yet Another Problem About Pairs Satisfying an Inequality solution codeforces – You are given an array 𝑎1,𝑎2,…𝑎𝑛a1,a2,…an. Count the number of pairs of indices 1≤𝑖,𝑗≤𝑛1≤i,j≤n such that 𝑎𝑖<𝑖<𝑎𝑗<𝑗ai<i<aj<j.
[Solution] Yet Another Problem About Pairs Satisfying an Inequality solution codeforces
The first line contains an integer 𝑡t (1≤𝑡≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains an integer 𝑛n (2≤𝑛≤2⋅1052≤n≤2⋅105) — the length of the array.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (0≤𝑎𝑖≤1090≤ai≤109) — the elements of the array.

Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

It is guaranteed that the sum of 𝑛n across all test cases does not exceed 2⋅1052⋅105.

Output
For each test case, output a single integer — the number of pairs of indices satisfying the condition in the statement.

Please note, that the answer for some test cases won’t fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).


[Solution] Yet Another Problem About Pairs Satisfying an Inequality solution codeforces
Example
input
Copy
5
8
1 1 2 3 8 2 1 4
2
1 2
10
0 2 1 6 3 4 1 2 8 3
2
1 1000000000
3
0 1000000000 2
output
Copy
3
0
10
0
1
[Solution] Yet Another Problem About Pairs Satisfying an Inequality solution codeforces
For the first test cases the pairs are (𝑖,𝑗)(i,j) = {(2,4),(2,8),(3,8)}{(2,4),(2,8),(3,8)}.

The pair (2,4)(2,4) is true because 𝑎2=1a2=1, 𝑎4=3a4=3 and 1<2<3<41<2<3<4.
The pair (2,8)(2,8) is true because 𝑎2=1a2=1, 𝑎8=4a8=4 and 1<2<4<81<2<4<8.
The pair (3,8)(3,8) is true because 𝑎3=2a3=2, 𝑎8=4a8=4 and 2<3<4<82<3<4<8.

No comments:

Post a Comment