[Solution] Good Pairs solution codechef

Good Pairs solution codechef – You are given arrays AA and BB of length NN each. Determine the number of good pairs.

[Solution] Good Pairs solution codechef

A pair (i,j)(i,j) (1i,jN)(1≤i,j≤N) is said to be good if all of the following conditions are satisfied:

  • i<j;i<j;
  • Ai=Bj;Ai=Bj;
  • Aj=Bi;Aj=Bi;

Input Format

  • First line will contain TT, the number of test cases. Then the test cases follow.

Description of each test case:

  • First line contains an integer NN – denoting the length of the arrays.
  • Second line contains NN space-separated integers A1,A2,ANA1,A2,…AN – denoting the array AA.
  • Third line contains NN space-separated integers B1,B2,BNB1,B2,…BN – denoting the array BB.

[Solution] Good Pairs solution codechef

For each test case, output the number of good pairs.

Constraints

  • 1T10001≤T≤1000
  • 2N1052≤N≤105
  • 1Ai,Bi1091≤Ai,Bi≤109
  • Sum of NN over all test cases does not exceed 21052⋅105.

Sample Input 1 

4
3
1 2 3
3 2 1
4
1 2 3 4
5 6 6 7
3
10 10 10
10 10 10
4
4 8 1 1
8 4 1 1

[Solution] Good Pairs solution codechef

 

1
0
3
2

Explanation

Test Case 11: The only good pair (i,j)(i,j) is (1,3)(1,3). Here,

  • 1<31<3
  • A1=1A1=1 and B3=1B3=1. Thus, A1=B3A1=B3.
  • A3=3A3=3 and B1=3B1=3. Thus, A3=B1A3=B1.

Test Case 22: There are no good pairs.

Test Case 33: There are 33 good pairs (i,j)(i,j). These are (1,2),(1,3),(1,2),(1,3), and (2,3)(2,3).

Test Case 44: There are 22 good pairs (i,j)(i,j). These are (1,2)(1,2) and (3,4)(3,4).

For Solution

Click here

Leave a Comment