PROBLEM LINK:
Setter-
Tester-
Editorialist-Abhishek Pandey
DIFFICULTY:
Easy
PRE-REQUISITES:
Arrays, Looping, Logical thinking.
PROBLEM:
Formally, the problem can be put up as, you have to re-arrange a sequence of N numbers from [1,N], such that-
- The number at index S is Q.
- The maximum absolute difference between adjacent numbers is minimum,i.e. “minimize the maximum absolute difference”.
We need to print any such sequence satisfying the above along with the maximum absolute difference.
QUICK EXPLANTION:
After some examples, we see that we can always get a difference of 2 is possible. We can easily check if a difference of 1 is possible or not. If a difference of 1 is not possible, then the we can always minimize the “maximum absolute difference” to 2. This is done by printing numbers at difference of 2 (or 1 if needed), starting from index S. Take special care for N=1 case where the difference is 0!!
EXPLANTION:
The question in itself is pretty much straightforward. The editorial is divided into 3 sections, 1 each for each possible answer.
(Henceforth, I will refer to “minimized maximum absolute difference” as “answer”. Please dont get confused with the terminology.)
Cases when ans=0:
This is possible only for N=1 case, and is a special case which should be handled manually.
Cases where ans=1:
We can trivially see when its possible for the “maximum absolute difference” to be equal to 1. This happens if, and only if, the series is of either of the 2 forms-
- 1,2,3...N
- N,N-1,N-2....3,2,1
The first series is possible if and only if (S==Q) , while the other series is possible iff [Q==(N+1-S)].
Again, we can deal with this case manually and print the respective series for which the condition is satisfied.
When ans=2:
Now this is the heart of the question. There are 2 things that we must deal here-
- Proving that answer of 2 is possible (and answer greater than 2 are not.)
- Constructing the series (We will discuss 2 methods here)
We dealt with cases of N=0 and N=1. Intuitively, the number to consider is 2. Now, how to get an idea that answer of 2 is possible, and that its not anything else (like, logN for example). Fortunately, is a method to support (or develop) or intuition.
Write a brute force which checks all the permutations possible, and among the ones satisfying the conditions (The element at index S must Q), finds sequences with minimum answer and print them. There on you might catch the pattern there, and observe that answer doesnt grow with N, but stays at a constant 2, even for N=10,11..etc. This is the most standard method to do so. You can use STL to help you here as well (Read Chef Vijju’s corner).
A kind of informal proof will go on lines, that, numbers of same parity can be grouped together such that the endpoints (where they are “adjacent” to even numbers) are 1 and N-1 (assuming N is even). Now we can place N, and 2 at endpoints of even numbers, and arrange remaining N/2 numbers in form 2,4,6...N. For example, we can always form permutations of this kind by swapping-
N=8,S=3,Q=5 - [1,3,5,7,8,6,4,2]
N=8,S=4,Q=5 - [2,1,3,5,7,8,6,4] (here odd segment is “sandwiched” b/w 2 even ones).
Notice how the 2nd case is nothing but a “cyclic shift” of the above array. We can similarly cyclically shift the array till and until we get arr[S]=Q.
This is the first method of construction.
Second Method
Obviously, there are only 2 cases where ans=1 is possible, and only 1 with ans=0. Using some manipulations on smaller values of N, you can easily test for N=2 using this trick- First assign arr[S]=Q. Now assign arr[S+1]=Q+2, arr[S+2]=Q+4 &etc. and arr[S-1]=Q-2 , arr[S-2]=Q-4…and so on. If at any instance, S+i crosses N or 0, stop the series there. If at any instance,Q+2i exceeds N, then change pattern- start using numbers from (N-1),(N-3).... Similar case if (N-2i) drops below 1.
Dont worry, it seems confusing at first, but it will be clear with an example.
Lets say, our input is N=10, S=5 Q=7
Now-
- First, arr[S]=Q. So our array is [0,0,0,0,7,0,0,0,0,0]
- Lets start from right, and assign Q+2,Q+4 etc. (till we can) to subsequent indices. Our new array becomes [0,0,0,0,7,9,0,0,0,0].
- We see that we couldnt assign anything after 9 as next term is more than N(=10). Now, we change pattern. The next term after highest possible odd will be highest possible even, which in this case is 10. New array= [0,0,0,0,7,9,10,0,0,0].
- Again fill elements in right at a difference of 2. New array is [0,0,0,0,7,9,10,8,6,4]. We now reached the end here.
- Start filling left elements now, by Q-2,Q-4…etc, as far as we can. New array becomes [0,1,3,5,7,9,10,8,6,4]
- We cannot fill any more with odd terms and next term will be less than 0. Again, change pattern. Lowest odd should be followed by lowest even, which is 2. New array=[2,1,3,5,7,9,10,8,6,4]
We are done. Feel free to try some of your own experiments here!!.
SOLUTION:
Editorialist’s Solution- Pattern
Editorialist’s Solution- Cyclic Shift
TimeComplexity=O(N)
SpaceComplexity=O(N)
CHEF VIJJU’S CORNER:
1.Let me take the chance to introduce you to next_permutation() function of C++ STL. It saves you a lot of time in writing code where you have to generate all permutations. The brute force can be simplified to a great deal with this function. Also, if you;re a regular guy giving short contests at Codeforces etc. , then this function will come in handy quite many times.
2.The basic question in everybody’s mind is “How to approach constructive algorithm questions.” Honestly, I think the answer depends. The setter thought of something, noticed a pattern and framed the question. Going by different directions can, sometimes make problem really trivial, or complicate it to a great deal. I will say it again comes with practice. At least for me, I first solved the problem using brute force, observation and pattern making. Its after getting AC (and while writing this editorial), that the cyclic shift technique came in my mind. So, yes, just practice and keep your mind sharp. Thats the best advise anyone can give.