PROBLEM LINK:Setter DIFFICULTY:Easy PREREQUISITES:Arrays, Looping, Logical thinking. PROBLEM:Formally, the problem can be put up as, you have to rearrange a sequence of $N$ numbers from $[1,N]$, such that
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
The first series is possible if and only if $(S==Q)$ , while the other series is possible iff $[Q==(N+1S)]$. 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
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 $N1$ (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[S1]=Q2$ , $arr[S2]=Q4$...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 $(N1),(N3)...$. Similar case if $(N2i)$ 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
We are done. Feel free to try some of your own experiments here!!. SOLUTION:Editorialist's Solution Pattern $TimeComplexity=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.
This question is marked "community wiki".
asked 12 Jan '18, 15:48
