[Solution] Best Pair solution codeforces

Best Pair solution codeforces – You are given an array 𝑎a of length 𝑛n. Let 𝑐𝑛𝑡𝑥cntx be the number of elements from the array which are equal to 𝑥x. Let’s also define 𝑓(𝑥,𝑦)f(x,y) as (𝑐𝑛𝑡𝑥+𝑐𝑛𝑡𝑦)(𝑥+𝑦)(cntx+cnty)⋅(x+y).

Also you are given 𝑚m bad pairs (𝑥𝑖,𝑦𝑖)(xi,yi). Note that if (𝑥,𝑦)(x,y) is a bad pair, then (𝑦,𝑥)(y,x) is also bad.

Your task is to find the maximum value of 𝑓(𝑢,𝑣)f(u,v) over all pairs (𝑢,𝑣)(u,v), such that 𝑢𝑣u≠v, that this pair is not bad, and also that 𝑢u and 𝑣v each occur in the array 𝑎a. It is guaranteed that such a pair exists.

Best Pair solution codeforces

The first line contains a single integer 𝑡t (1𝑡100001≤t≤10000) — the number of test cases.

The first line of each test case contains two integers 𝑛n and 𝑚m (2𝑛31052≤n≤3⋅1050𝑚31050≤m≤3⋅105) — the length of the array and the number of bad pairs.

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

The 𝑖i-th of the next 𝑚m lines contains two integers 𝑥𝑖xi and 𝑦𝑖yi (1𝑥𝑖<𝑦𝑖1091≤xi<yi≤109), which represent a bad pair. It is guaranteed that no bad pair occurs twice in the input. It is also guaranteed that 𝑐𝑛𝑡𝑥𝑖>0cntxi>0 and 𝑐𝑛𝑡𝑦𝑖>0cntyi>0.

It is guaranteed that for each test case there is a pair of integers (𝑢,𝑣)(u,v)𝑢𝑣u≠v, that is not bad, and such that both of these numbers occur in 𝑎a.

It is guaranteed that the total sum of 𝑛n and the total sum of 𝑚m don’t exceed 31053⋅105.


For each test case print a single integer — the answer to the problem.

Best Pair solution codeforces

6 1
6 3 6 7 3 3
3 6
2 0
3 4
7 4
1 2 2 3 1 5 1
1 5
3 5
1 3
2 5


Best Pair solution codeforces Note

In the first test case 336677 occur in the array.

  • 𝑓(3,6)=(𝑐𝑛𝑡3+𝑐𝑛𝑡6)(3+6)=(3+2)(3+6)=45f(3,6)=(cnt3+cnt6)⋅(3+6)=(3+2)⋅(3+6)=45. But (3,6)(3,6) is bad so we ignore it.
  • 𝑓(3,7)=(𝑐𝑛𝑡3+𝑐𝑛𝑡7)(3+7)=(3+1)(3+7)=40f(3,7)=(cnt3+cnt7)⋅(3+7)=(3+1)⋅(3+7)=40.
  • 𝑓(6,7)=(𝑐𝑛𝑡6+𝑐𝑛𝑡7)(6+7)=(2+1)(6+7)=39f(6,7)=(cnt6+cnt7)⋅(6+7)=(2+1)⋅(6+7)=39.

The answer to the problem is max(40,39)=40max(40,39)=40.

Leave a Comment