Prefix Sums solution codechef- For a positive, eveneven integer NN, we call a pair of arrays AA and BB to be interesting if they satisfy the following conditions : |A|=|B|=N/2|A|=|B|=N/2 i.e. the length of array AA is equal to the length of array BB.

Prefix Sums solution codechef

For a positive, eveneven integer NN, we call a pair of arrays AA and BB to be interesting if they satisfy the following conditions :

  • |A|=|B|=N/2|A|=|B|=N/2 i.e. the length of array AA is equal to the length of array BB.

  • Each integer from 11 to NN occurs exactly once in exactly one of the arrays.

  • The ithith prefix sum of AA is not equal to ithith prefix sum of BB for all 1iN/211≤i≤N/2−1. Formally, j=1iAjj=1iBj∑j=1iAj≠∑j=1iBj for all 1iN/211≤i≤N/2−1

  • Sum of all elements in AA is equal to sum of all elements in BB i.e. j=1N/2Aj=j=1N/2Bj∑j=1N/2Aj=∑j=1N/2Bj

You are given a positive, even integer NN. If there exists an interesting pair of arrays, then print “YES” followed by an interesting pair for this given NN. If there exists multiple interesting pairs of arrays for given NN, you can print any. Print “NO” in a single line if no such pair exists.

Prefix Sums solution codechef

  • First line of input will contain TT, the number of test cases. Then the test cases follow.
  • Each test case contains a single line of input, the integer NN.

Output Format

For each test case, if there exists an interesting pair of arrays, say (A,B)(A,B), then in the first line print “YES”, in the second line print array AA separated by spaces, and in third line print array BB separated by spaces. Print “NO” in a single line if no such pair exists. If there are multiple answers, print any of them.

Prefix Sums solution codechef

  • 1T1051≤T≤105
  • 1N1051≤N≤105
  • NN is guaranteed to be even.
  • Sum of NN over all test cases doesn’t exceed 106106

Prefix Sums solution codechef

  • Subtask 1 (100 points): Original constraints

Sample Input 1 

2
2
4

Sample Output 1 

NO
YES
1 4
2 3

Explanation

Test case 2: Consider A=[1,4]A=[1,4] and B=[2,3]B=[2,3]. Every integer from 11 to 44 occurs exactly once in exactly one of the arrays. Also, 11st prefix sum of AA is not equal to 11st prefix sum of BB (121≠2). And sum of the elements is equal to 55 for both arrays. So, (A,B)(A,B) is an interesting pair.

 

Leave a Comment

Your email address will not be published.