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

7 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

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

5

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

6

http://www.codechef.com/viewsolution/3922340 . Plz tell me what is wrong with this soon. Thnx in advance

7

http://www.codechef.com/viewsolution/3922340 . Plz tell me what is wrong with this soln. Thnx in advance

8

@invest123 You must take into account the separate test cases. you are printing for only one test case!

9

Thnx. OMG what a mistake :slight_smile: Dint notice that. I think i should use ideone to avoid these mistakes.

10

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

11

what is condition to test cases

12

He did not pass with this solution. I have updated the new solution.

13

Your solution is correct, but you are answering for a single test case only. You are not even reading number of test cases.

1 Like
14

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

15

I am not sure what the error was but the error was probably in map(int,s.split(" ")) , when I replaced it with [int(x) for x in s.split()] it worked .
Here is your corrected code .
http://www.codechef.com/viewsolution/3925500

1 Like
16

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

17

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

thanks a lot

18

You are declaring the array in while (testcase --) loop, which is not correct. Number of test cases could be very huge, If you keep allocating so much memory for so many loops, you will get TLE. Ideally you should use vector or you should declare the array globally.

19

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

20

your sorting step is O(N 2 ). You need faster algorithms for sorting. Eg quicksort, mergesort etc. Btw you can use simply STL function sort.