[Solution] Adjacency Love solution codechef

Adjacency Love solution codechef – An array is called lovely if the sum of product of each adjacent pair of elements is odd.

More formally, the array SS of size MM is lovely if the value M1i=1∑i=1M−1 (Si.Si+1)(Si.Si+1) is odd.

Adjacency Love solution codechef

You are given an array AA consisting of NN positive integers. Find a permutation of array AA which is lovely.

If multiple such permutations are possible, output any. If there is no lovely permutation, output -1.

Input Format

  • The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
  • The first line of each test case contains an integer NN.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, if a lovely permutation of AA is possible, print a single line containing NN integers denoting the elements of any lovely permutation of AA. Otherwise, print -1.

Constraints

  • 1T10001≤T≤1000
  • 2N5002≤N≤500
  • 1Ai1061≤Ai≤106

Adjacency Love solution codechef

  • Subtask 1 (100 points): Original constraints.

Sample Input 1 

2
5
1 2 3 4 10
3
7 11 145

Sample Output 1 

3 1 10 2 4
-1

Adjacency Love solution codechef

Test Case 11: The sum of products of adjacent pair of elements of the given array is 12+23+34+410=2+6+12+40=601⋅2+2⋅3+3⋅4+4⋅10=2+6+12+40=60. Since this value is even, this is not a lovely permutation of the array.
lovely permutation of the given array is [3,1,10,2,4][3,1,10,2,4]. The sum of products for this array would be 31+110+102+24=413⋅1+1⋅10+10⋅2+2⋅4=41, which is odd.

Test Case 22: No permutation of the given array exists where the sum of products of adjacent pair of elements is odd. Thus, answer is 1−1.


For Solution

Click Here

Leave a Comment