Maximum Pairwise Modular Sum solution codechef

Maximum Pairwise Modular Sum solution codechef

You are given an array AA containing NN integers, and a positive integer MM. Find the maximum value of

across all pairs 1≤i,j≤N1≤i,j≤N.

To submit a solution choose problem from list of problems and press button ‘Submit’ near the top right corner of the problem page. You can submit multiple solutions to each problem. Score for the problem is equal to the score of the best submitted solution.

To see the Statistic for problem choose problem from list of problems and press button ‘All submissions’ at the top of the problem description. To view the status, hover over the check box, cross or warning icon in the result column.

Note that xmodMxmodM refers to the smallest non-negative integer obtained as the remainder upon dividing xx by MM. For example, 4mod3=14mod3=1 and (−10)mod3=2(−10)mod3=2.

Input Format

Maximum Pairwise Modular Sum solution codechef

• The first line of input will contain a single integer TT, the number of test cases. The description of test cases follows.
• Each test case consists of two lines of input.
• The first line of each test case contains two space-separated integers NN and MM.
• The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

Output Format

• For each test case, output on a new line the maximum value of Ai+Aj+((Ai−Aj)modM)Ai+Aj+((Ai−Aj)modM).

Constraints

Maximum Pairwise Modular Sum solution codechef

• 1≤T≤1001≤T≤100
• 2≤N≤2⋅1052≤N≤2⋅105
• 2≤M≤5⋅1082≤M≤5⋅108
• 0≤Ai≤5⋅1080≤Ai≤5⋅108
• The sum of NN across all test cases won’t exceed 2⋅1052⋅105.

Subtasks

• Subtask 1 (10 points):
  • The sum of NN across all test cases won’t exceed 10001000
• Subtask 2 (20 points):
  • 2≤M≤10002≤M≤1000
• Subtask 3 (70 points):
  • Original constraints

Sample Input 1 

4
2 18
12 1
3 5
4 5 6
5 4
79 29 80 58 80
3 20
33 46 56

Sample Output 1

Maximum Pairwise Modular Sum solution codechef

24
15
162
112

Explanation

Test case 11: There are 44 possible pairs of indices to choose from. Their respective values are:

• i=1,j=1i=1,j=1, giving 12+12+((12−12)mod18)=24+0=2412+12+((12−12)mod18)=24+0=24
• i=1,j=2i=1,j=2, giving 12+1+((12−1)mod18)=13+11=2412+1+((12−1)mod18)=13+11=24
• i=2,j=1i=2,j=1, giving 1+12+((1−12)mod18)=13+7=201+12+((1−12)mod18)=13+7=20
• i=2,j=2i=2,j=2, giving 1+1+((1−1)mod18)=2+0=21+1+((1−1)mod18)=2+0=2

Of these, the largest value is 2424.

Test case 22: There are 3×3=93×3=9 choices for pairs (i,j)(i,j). Of these, one way to achieve the maximum is by choosing i=2,j=3i=2,j=3, giving 5+6+((5−6)mod5)=11+4=155+6+((5−6)mod5)=11+4=15.

Test case 33: Picking i=1,j=3i=1,j=3 gives a value of 79+80+((79−80)mod4)=159+3=16279+80+((79−80)mod4)=159+3=162, which is the largest possible.

Test case 44: Picking i=3,j=2i=3,j=2 gives a value of 56+46+((56−46)mod20)=102+10=11256+46+((56−46)mod20)=102+10=112, which is the largest possible.

SOLUTION

“Click here“