ANUUND - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Anudeep Nekkanti
Tester: Gerald Agapov
Editorialist: Praveen Dhinwa

DIFFICULTY:

EASY

PREREQUISITES:

AD-HOC, sorting

PROBLEM:

Given an array A. Rearrange the array in such a way that A[1] <= A[2] but A[2] >= A[3] and A[3] <= A[4] upto A[N-1] <>= A[N] (depending on the parity of N) is satisfied.
More Formally,
A[i] <= A[i + 1] if i is odd.
A[i] >= A[i + 1] if i is even.

QUICK EXPLANATION

  1. O(N logN) Solution: Sort the array A. Pick A[1], then pick A[N - 1], A[2], A[N - 2] etc upto Nth element.
  2. O(N) Solution: Go from A[1] to A[N] in left to right order, if at any point of time, condition of given inequalities are not satisfied, then swap the elements in such a way that the condition is satisfied. We will prove in next section why this approach will always work.

EXPLANATION

O(N logN) Solution:

First step is to sort the array A.
Now we have to build an array B such that it contains the elements of A in rearranged way. They B array is our answer to the given problem.
We will first add A[1] in B, then A[N - 1], then A[2], A[N - 2], A[3], A[N - 3] etc.
Note that this approach is always going to produce correct result because at the current step we are always picking the smallest and largest possible numbers which we can still pick, hence the inequality conditions given in the problem are never violated.

Sample Execution:
Let A = [4, 3, 5, 1].
Sort the array A.
A now becomes = [1, 3, 4, 5].
Our array B will be [1, 5, 3, 4].

Complexity: O(N log N).
All we need to do is to sorting of an array, All other operation costs only O(N) time. Hence time complexity is O(N log N).

O(N) Solution

We will go from left to right from A[1] to A[N]. If at any position, our inequality condition is unsatisfied, we will make a swap of i and i + 1 entries.

Sample Execution:
Let A = [4, 3, 5, 1, 2].
If we are first element (i = 1): A[1] <= A[2] is not satisfied, so we will swap A[1] and A[2].
So A will now become: [3, 4, 5, 1, 2]
Now we are at second element (i = 2): A[2] >= A[3] is not satisfied, so we will swap A[2] and A[3].
So A will now become: [3, 5, 4, 1, 2]
Now we are at third element (i = 3): A[3] <= A[4] is not satisfied, so we will swap A[3] and A[4].
So A will now become: [3, 5, 1, 4, 2]
Now we are at fourth element (i = 4): A[4] >= A[5] is satisfied, so we dont need to swap.
So A will remain as it is: [3, 5, 1, 4, 2]

Proof Of Correctness:
Assume that a, b, c, be the leftmost(Ordered from A[1] to A[N], A[1] is leftmost, A[N] is rightmost) elements of the array A for which condition is not satisfied. Let us assume that a be the elements which just precedes b. (ie order of occurrence of elements is a, b, c)
Let us suppose we want b >= c. (a <= b).
According to our assumption, a <= b is already satisfied, but b >= c is not satisfied (ie b < c)
Now on swapping b and c, our new order of elements will be a, c, b.
Note that now in this order a <= c(because a <= b < c).
and we have c >= b. (because c > b).

We can handle the second case in the exactly similar way too (Case when a >= b is satisfied but b <= c is not satisfied). This case is left for readers to prove.

Complexity: O(N):
For each index i from 1 to N, we can make at most 1 swap, Swap operation is constant operation, Hence we will only make total O(N) operations.

AUTHOR’S, TESTER’S AND EDITORIALIST’s SOLUTIONS:

Author’s solution
Tester’s solution
Editorialists’s solution

10 Likes
2

O(n) time: Keep reading the elements into an array. If the new element does not conform to the pattern, just swap it with the last element.

3

I found a different solution. I’m posting my code that I submitted

#include <iostream>
#include <list>

using namespace std;

int main() {

long long t, n,input, i = 0,prev=0,counter = 0;

list <long long> a;

cin >> t;

while(t--)
{
	cin >> n;
	counter = -1;
	for(i = 0; i < n; i++) 
	{
		cin >> input;
		if( counter == -1  || ((counter == 1 && input > a.back()) || (counter==0 && input<a.back())))
		{
			a.push_back(input);
		}
		else
		{
			prev = a.back();
			a.pop_back();
			a.push_back(input);
			a.push_back(prev);
		}
		
		if(counter == -1 || counter == 0) counter = 1; else counter = 0;
	}
	
	for(i = 0; i < n; i++) {cout << a.front() << " "; a.pop_front();}
	cout<<endl;
	
}
return 0;
}
4

CodeChef: Practical coding for everyone . Plz tell me what is wrong with this soln. Thnx in advance

5

@Gerald, how did u manage to pass despite printing "FUCK THE SYSTEM!" at the end of the actual output in ur code? :wink:

6

anyone give me problem with my code
i am pretty sure its logic is good but giving me NZEC

http://www.codechef.com/viewsolution/3925302

regards

7

http://www.codechef.com/viewsolution/3925646
Why does my NlogN solution gets a TLE ?

8

awsome thanks
issue is with s.split()
i am using space as separator s.split(" ") while correct one is s.split()

thanks a lot

9

http://www.codechef.com/viewsolution/3921038
how i can improve this
it is exceeding time

10

CodeChef: Practical coding for everyone Can someone please tell me where I went wrong ?
Thanks in advance.

11

Please tell me why I am getting WA?
http://www.codechef.com/viewsolution/3943506

12

Can somebody please tell me why I am getting wrong answer?
I have applied same logic as in the explanation,but instead of changing array A to array B,I am just printing the elements of array A in swapped form.i.e. except first and last element I am printing every pair of elememnts ((a[1],a[2]),(a[3],a[4])) in swapped form. If this logic is wrong can you just give me a test case for which this logic is wrong.
My soln.is given below:
http://www.codechef.com/viewsolution/3957175

13

I don’t know why am i getting wrong answer for my code …seems to work fine…any kind of help will be appreciated …thanks

t=int(input())

while t>0:

    size=int(input())
    array=[int(i) for i in input().split()]
    array2=array
    array2.sort()

    i=1
    for i in range(i,len(array),2):
         if i==len(array2)or i==len(array2)-1:
            break

         else:
           j=i+1
           a=array2[i]
           array2[i]=array2[j]
           array2[j]=a
    print(array2)
    t-=1
14

can anyone help me out. Its working for all test cases still getting wrong answer.
2 approaches
http://www.codechef.com/viewsolution/6464869
http://www.codechef.com/viewsolution/6464697

15

In O(N) solution take A = {4,3,5,1,9}.
You will get wrong answer.

16

My Answer :
Sort the array.
print the first element , n den swap the next two
So, if input is,
5 4 3 2 1
it will sort: 1 2 3 4 5
n output will b like
1 3 2 5 4
Whats wrong in this?

1 Like
17

https://www.codechef.com/viewsolution/9114451
how can i remove the TLE? please help!

18

as you have said
“A now becomes = [1, 3, 4, 5].
Our array B will be [1, 5, 3, 4].”

but the solution of A = [1, 3, 4, 5] can also be [ 1 , 4 ,3 ,5] . This is also satisfying your condition. isn’t it ???

19

@Shashwat.delhi, The approach is already explained in the editorial :slight_smile:

20

@rhnvrm: Your solution is similar to O(N) solution explained in the editorial.