[Solved] Doubt in Codechef Question

Question

Hello guys, yesterday i have attended the codechef weekly contest in that i saw this problem statement. i'm not able to get any logic for this problem so can anyone help me to give get the logic for the below problem!

problem statement :
Anti Adjacent Swaps You are given an array A of N elements. In one operation you can swap any two elements if they are not adjacent.
That is, you can pick two indices i and j (1 <=i<j<=N) such that j-i > 1, and swap Ai and Aj.
Using this operation finitely many (possibly, zero) times, is it possible to turn A into a sorted array?

Here check out the full question :
https://www.codechef.com/problems/ANADSW

Answer 1

Thanks for your responses guys Rain , Steve , Wong Hei Ming.

Yeah Steve you're right, actually we don't have to check the array with the length of 4 or above because it's always sortable by swapping their anti adjacent values. In question they have clearly mentioned that we can pick any two indices if they're not adjacent so that the array with the length of 4 or above is always sortable.
Now we just have to focus on the array only with the length of 2 and 3.
For length 2 :
We just have to check that the array is sorted or not because we can't swap them due to the reason there are only two values and they are in the adjacent position.
For length 3 :
Here we can swap only the 1st and 3rd values because they're only in anti-adjacent position. For that we have to focus on the 2nd value, that value should be the second largest value then only the array will be sorted if we swap the 1st and 3rd value.
For length 4 or above:
It is always possible to sort the array so we can just simply print yes.

Answer 2

Here is the full description of the task, so we don't need to jump back and forth between screens.

Anti Adjacent Swaps

You are given an array A of N elements. In one operation you can swap any two elements if they are not adjacent.
That is, you can pick two indices i and j (1 <= i < j <= N) such that j - i > 1, and swap Ai​ and Aj​.

Using this operation finitely many (possibly, zero) times, is it possible to turn A into a sorted array?
Input Format

1. The first line of input will contain a single integer T, denoting the number of test cases.
2. Each test case consists of two lines of input.
2a. The first line of each test case contains an integer N, denoting the size of the array A.
2b. The second line of each test case contains N space-separated integers A1,A2,…,AN​, denoting the elements of the array A.

Output Format

For each test case, output on a new line the answer: YES, if you can sort the array A in finitely (possibly zero) operations, and NO otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings YeS, yEs, yes, and YES will all be treated as identical).
Constraints

1. 1 <= T <= 100
2. 1 <= N <= 1000
3. 1 <= Ai <= 1000

Input
3
2
3 5
2
5 3
3
6 6 2

Output
YES
NO
YES

Explanation:
Test case 1: The array is already sorted.
Test case 2: The array is not sorted and we can't swap the two elements as they are adjacent to each other.
Test case 3: The array can be sorted by swapping the first and the third element.

Answer 3

Steve ,

I already solved 1 3 2 4 5 in 3 swaps.

I was also thinking 4 or more is solvable, but I couldn't say why yet.

I like your randomized attack at trying to disprove 4+ is solvable. I've found noise to be a useful source of information more than once in life.

Answer 4

Guys Rain , Steve , Wong Hei Ming check out this code you'll understand the logic .
https://sololearn.com/compiler-playground/c4A32D54seVJ/?ref=app

Answer 5

My intuition is that the selected 2 elements can only swap once, since the task says "in one operation".
Also, it also mentioned "finitely", it seems like picking the elements through itreation.
eg.
array of 3
1st and 3rd elements

array of 4
1st and 3rd, 1st and 4th
2nd and 4th

array of 5
1st and 3rd, 1st and 4th, 1st and 5th
2nd and 4th, 2nd and 5th
3rd and 5th

Answer 6

Wong Hei Ming ,

Thanks for grabbing the description. I couldn't reach it from here. Not sure why. Maybe it didn't like my tracker blocker or something.

I read "in one operation" as describing the swap function, and "finitely" meaning any finite number of swaps including 0. An infinite loop is a fail.

Answer 7

Wong Hei Ming ,

"finitely many" means any finite number. 3 is a finite number, so a solution of 3 swaps is allowed. A solution of any finite number of swaps is allowed, but not stuck in infinite loop.

Answer 8

Wong Hei Ming ,

Don't over think it. This sentence is too wordy.

"Using this operation finitely many (possibly, zero) times, is it possible to turn A into a sorted array?"

It could be better phrased this way.

"Is it possible to sort A using zero or more swaps?"

Or even, "Is it possible to sort A with such swaps?"

Answer 9

Rain
Assuming you are right, then we only need to check if the size of the array is 2 and 3.
In case the array size is 2, then we check if it is sorted.
In case the array size is 3, then we check if it is sorted as it is, or sorted if 1st and 3rd elements are swapped.

However, an array with size of 2 is always sorted, I think. Either in ascending or descending.
Therefore, I said the description is ambiguous.

Answer 10

Steve
Your code doesn't fully simulate the sample input.

In the 3rd test case, there are duplicated elements (6 and 6).
But I don't think it will affect the result, if any, unless all elements are the same number.

Answer 11

Kabilan K ,

Nicely done. I believe that means you can add [Solved] to the discussion title.

See my other comment attached to your code.

Answer 12

Kabilan K ,

Thinking about it, the answer must be no, because some arrays would be impossible to sort only by swapping non-adjacent members, such as 10 30 20.

Answer 13

Yes Rain , in that case the output should be NO.

Actually we don't have to sort the array, we just have to check whether we can sort the array by swapping their anti adjacent values or not.

If it is possible check out the full question using the link

Answer 14

Kabilan K ,

The link doesn't work for me. The subdirectories give 505 error or 508 error. If I trim off all subdirectories and just go to the domain, it shows 403 Forbidden error.

Answer 15

Kabilan K ,

To judge if an inputted array is sortable that way, you could just try sorting it, and if you run out of valid swaps before the array is sorted, output no. (By valid swap, I mean a swap that puts the two items being swapped into their proper order relative to each other.)

There might be a clever shortcut, but I don't see it yet.

What language is that challenge for? I notice that it assumes the lowest array index to be 1, but most (not all) languages I know of have a lowest index of 0.

Answer 16

Kabilan K ,

Never mind about my idea of outputting no if you run out of valid swaps before it's sorted. That approach would output a false no if given the array 1 3 2 4 5, which has no valid swaps but has some invalid swaps that would temporarily be useful.

13245

swap 3 5

15243

swap 2 3

15342

swap 5 2

12345

It's a good challenge.

Answer 17

Kabilan K

My intuition is that it is always solvable for arrays of length 4 or more. But I can't prove that, and my intuition has been wrong many times before.

Answer 18

Here's my attempt to find a counter-example to always answering "Yes" for arrays longer than 3:

https://sololearn.com/compiler-playground/cQdt8TVPGkR9/?ref=app

Spoiler: I couldn't find one.

Answer 19

Rain
To me, the task description is ambiguous.

How is "finitely" defined?
In your previous example you make it sorted by swapping 3 times.
However, 1 is finite, 2 is also finite.
So the expression in python would become:
res = 1 (which is False) and 2 (which also is False) and 3 (that is True) and 4 and N
res = False and False and True and True and True (times N)
res = False

Answer 20

Rain
Then I have to ask:
Can you write a code to your manual solution, without using "while True (infinite loop)", yet also respect those 3 limitations in the task description?