Split and Maximize solution codechef

Split and Maximize solution codechef – Let f be a function, such that, for an array A of size Mf(A) is defined as

f(A) = \sum_{i=1}^{M}\sum_{j=1, j \ne i}^{j=M} (A_i\cdot A_j)

Split and Maximize solution codechef

You are given an array C of size N. In one operation on the array, you can:

  • Choose an index i (1\le i \le |C|)
  • Select two positive integers X and Y such that X+Y = C_i
  • Remove the element C_i from the array C
  • Insert the elements X and Y to the array C

Find the maximum value of f(C) that can be obtained using any (possibly zero) number of given operations. Since this value can be huge, output the answer modulo 998244353.

 

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of two lines of input.
    • The first line of each test case contains an integer N, denoting the size of the array.
    • The next line contains N space-separated integers C_1, C_2, \ldots, C_N, the elements of the array C.

Split and Maximize solution codechef

For each test case, output on a new line, the maximum value of f(C) that can be obtained using any (possibly zero) number of given operations. Since this value can be huge, output the answer modulo 998244353.

Constraints

  • 1 \leq T \leq 10^3
  • 1 \leq N \leq 2\cdot 10^5
  • 1 \leq C_i \leq 10^9
  • The sum of N over all test cases won’t exceed 2\cdot 10^5.

Sample 1:

Input

Output

2
2
1 2
2
1 3
6
12

Split and Maximize solution codechef

Test case 1: Using one operation, we choose i = 2, set X = 1 and Y = 1, remove 2 from the array, and insert X and Y. Thus, the final array is C = [1, 1, 1].
Here, f(C) = (A_1\cdot A_2) + (A_1\cdot A_3) + (A_2\cdot A_1) + (A_2\cdot A_3) + (A_3\cdot A_1) + (A_3\cdot A_2) = 1+1+1+1+1+1 = 6.

Test case 2:

  • Operation 1: We choose i = 2, set X = 1 and Y = 2, remove 3 from the array, and insert X and Y. Thus, the final array is C = [1, 1, 2].
  • Operation 2: We choose i = 3, set X = 1 and Y = 1, remove 3 from the array, and insert X and Y. Thus, the final array is C = [1, 1, 1, 1].

Here, f(C) = 12.

Post navigation

Leave a Reply

Your email address will not be published.