This is the problem asked yesterday in icpc kanpur regionals.How should approach this problem?
Problem Statement You have an array A (1-indexed) of N integers. You can perform any number of operations on this array. An operation goes like this,
(1) You pick an index i such that 1 ≤ i ≤ n-2 and a[i] + a[i+2] > a[i+1]
(2) Then you swap a[i] and a[i+2]
You have to output if you can sort the array in non-decreasing order after performing any number of operations. Constraints 1 ≤ T ≤ 10^5 1 ≤ N ≤ 10^5 1 ≤ Sum of N over all testcases ≤ 10^5 1 ≤ Ai ≤ 10^9
Are you sure you have correctly understood and restated the problem statement?
First of all for a case such as: n = 3, a = [1, 2, 1] it seems that there is no solution.
Even assuming -1 (or something similar) is printed in these cases, any solution would still be O(n^2) since this problem is quite similar to bubble sort. This would TLE most of the time for n <= 1e5.
According to me. Just sort the array, and check if the elements in even position of the original array is same as the elements in the even position of sorted array (vice versa for odd), as we cannot swap between parities. If the above condition is satisfied, the answer is always possible.