Make that Array! solution codechef

Make that Array! solution codechef

Chef is given two arrays A and B, each having N elements.

In one move, Chef can choose an index i (1iN1), get (AiAi+1) points, and then swap Ai and Ai+1.

For example: If Chef has the array – [10,7,5] and Chef chooses index 1 during his move, he will get 107=3 points and the new array will become [7,10,5]

Can you help Chef in finding the maximum number of points he can get while converting the array A into array B?

Note: It is guaranteed in the input that there exists a sequence of moves which can convert array A into B.

Make that Array! solution codechef

Input Format

  • The first line of input contains a single integer T, denoting the number of testcases. The description of the T testcases follows.
  • The first line of each test case contains a single integer N denoting the number of elements in A and B.
  • The second line of each test case contains N space separated integers A1,A2,...,AN.
  • The third line of each test case contains N space separated integers B1,B2,...,BN.

Output Format

For each test case, print a single line containing one integer, which is the maximum number of points that Chef can get while converting the array A into array B

Constraints

  • 1T5104
  • 2N5105
  • 1Ai105
  • 1Bi105
  • The sum of N over all test cases does not exceed 5105

Sample Input 1 Make that Array! solution codechef

3
2
1 2
2 1
3
3 2 1
1 2 3
3
1 2 3
1 2 3

Sample Output 1 Make that Array! solution codechef

-1
4
0

Explanation Make that Array! solution codechef

Test Case 1: Chef can choose i=1 in the first move, get 12=1 points and swap A1 and A2. After this move, A is converted into B. We can prove that there exists no other sequence of moves which can result in higher score while converting A into B.

Make that Array! solution codechef

Test Case 2: One possible sequence of moves is the following:

  • Choose i=2. Total points =1, and A will become [3,1,2].
  • Choose i=1. Total points =1+2, and A will become [1,3,2].
  • Choose i=2. Total points =1+2+1, and A will become [1,2,3].

There are other possible sequences of moves which can result in total 4 points, but no such sequence exists which can result in more than 4 points, and simultaneously convert A into B.

Leave a Reply

Your email address will not be published. Required fields are marked *

*