PROBLEM LINK:Setter Bogdan Ciobanu DIFFICULTY:EASY PREREQUISITES:Observation, Simulation, Probability, Implementation and Data Structures  namely vectors and unordered maps/HashMaps/Hash tables, Hashing, Logic and Knack of Programming. PROBLEM:Given a value $N$ and an algorithm in the statement, find the most and least probable permutation of $N$ which the given algorithm can generate. QUICKEXPLANATION:Key to AC Simulating the algorithm for small $N$ huge number of times, and observing pattern for different values of $N$ led to an easy AC This type of question must be specially handled. Write a brute force program which would simulate the algorithm given in the question a large number $(\approx 2*10^6)$ times. Observe the pattern for various values of $N$. You'd observe the following pattern Maximum Possible Permutation $[2,3,4,\dots ,\lceil \frac{N}{2} \rceil,1,\lceil \frac{N}{2} \rceil+1,\lceil \frac{N}{2} \rceil+2, \dots, N$ Here $\lceil \frac{N}{2} \rceil$ represents $\frac{N}{2}$ rounded up to nearest integer (if decimal). Least Possible Permutation $[N,1,2,3,\dots,N1]$ EXPLANATION:I had been eternally waiting for such type of a question to come on codechef :) . The beauty of such a problem is, that you HAVE to think out of the box. The typical way of "making a program which would do all computations and simulations quickly with Time limit of the question and get AC" doesnt work, and this causes lot of contestants to go puzzled on what to do. Lets first discuss about these questions in general and then use the conclusion to solve this problem. Editorial is divided into $3$ parts, the beginning one is a just a short note on how and why we came to use the given approach, second tells details about how to make simulator, and third is final answer. Editorialist's Solution 1. Why Simulation? Lets begin it by discussing about first subtask. $N \le 7$, which seems strange to contestants. Too large to make cases by hand and see/print the handwritten result, and still too "small" for some reason, (perhaps too small to make a dp table to find the answer). Turns out, there is a method for which this value is "justfine" :). That method is Simulation! Usually, for these type of questions, the math required is too high. We are computer programmers, not math scientists! (No offence intended for anyone who is a computer programmer AND math scientist). The first principle of computer programming is, "Let the Machine do things for you :)". But anyways, I have attached a research paper which might help you guys get an insight on the question, the link is in my bonus corner as usual :) Honestly though, after trying and brainstorming for a few attempts, we cannot come at any link/conclusion which would help us decipher this mathematical mystery. While its easy to see how many possibilities are there, its not intuitive to count how probable they are, except from the few which are impossible (if any). Also, we are to answer it with respect to the algorithm given in the question. Usually, it does good to first study and observe the behavior of the algorithm. So, lets first discuss how to write the simulator :) 2. Writing Simulator A knowledge of Data Structures is needed. Go through links in prerequisites if you dont know about vectors (dynamic arrays) and unordered_map (Hashmap/Hashtable). The first thing to do is, to decide how many times we must simulate. This value is derived experimentally. Ideally, the value should be such that
Once that is done, all we have to do is to copy the algorithm given in the question. A C++ implementation is given below, its simply converting the pseudocode given in question to your language. Now, comes the tricky part. After doing above, we got a permutation, but how do we count a permutation's frequency?! There are multiple ways to get over it :). Some of them are
Once we get that, simply print the permutations appearing maximum and minimal number of times. A sample code is shown below. I used vectors and maps, the easy way out XD. However, my original/alternate simulation used unordered map and string, which is given in bonus corner :). You can also find some tips in my bonus corner for simulator :) Remember that, the simulation in the program must go for sufficiently large number of times, and you must run simulator to check even same value of $N$ multiple times. If the answer is stable, then number of simulations is sufficiently good for that value of $N$ (note that more simulations are needed to get an accurate result as $N$ increases), else try increasing it more. :) 3. Concluding notes and final answer Now once you find a set of candidate permutations, try to find a pattern on how to generate them. The permutations which I found were of patter as shown in quick explanation Maximum Possible Permutation $[2,3,4,\dots ,\lceil \frac{N}{2} \rceil,1,\lceil \frac{N}{2} \rceil+1,\lceil \frac{N}{2} \rceil+2, \dots, N$ Here $\lceil \frac{N}{2} \rceil$ represents $\frac{N}{2}$ rounded up to nearest integer (if decimal). Least Possible Permutation $[N,1,2,3,\dots,N1]$ You can refer to my code on how to generate it, although this type of implementation is trivial :). My code for generation SOLUTIONThe solutions are given in tab below in case the links dont work. This is done as to avoid any delay in solutions being accessbile to you guys. Copy them to your favorite editor and give a read :) $Time$ $Complexity=O(N)$ CHEF VIJJU'S CORNER :D1. Some tips on simulator
2. Research paper link  https://arxiv.org/pdf/math/0010066.pdf 3. Unordered map +Strings simulator. 4. Setter's proof on leastlikelihood permutation 5. Related Problems asked 08 Sep '18, 19:35

You can also "simulate" the problem without random number generation. How I simulated this was by recursively swaping each number by the rest of the n1 numbers. I did this up to N = 8, then observed the pattern by printing first five permutations, and last five permutations. Example: 1 2 3
The next number will produce N^2 permutations; the third will produce N^3. Thus, by the end of the recursion, you have N^N permutations distributed among N! distinct permutations. Now each of the first three permutations will apply the above steps by using the next number to swap with the others until we get to last number. The least probable permutation looked very obvious. But for the most probable, when I looked at the pattern for the most probable permutations, I wasn't sure if my observation was right, so I manually hardcoded my most probable permutations up to N = 17 to see if my solution would pass. Indeed, it did pass, unfortunately I decided to move to next problem without modifying my code. I feel my solution (hardcoding) was a terrible one. answered 18 Sep '18, 17:17
I want to know how u checked for n>=10
(19 Sep '18, 19:23)
1
Well, I couldn't, and didn't need to. My limit was N = 8. I tried N = 9 and it took me a couple of minutes, and finally a StackOverflow (which I already anticipated). I recognized a pattern after my first 8, and generated the rest of the permutations by hand.
(19 Sep '18, 19:54)
@rajput1999 see below for my code that can check n=10 in a couple of minutes. However any such exhaustive approach isn't going to get all the way to 17.
(19 Sep '18, 21:28)
thx joffan for your answer and yeah I also got till N = 8 and then recognized the pattern however I was curious whether we can go till N = 17 or above
(20 Sep '18, 17:28)

For N up to 7 I found the answer by brute force of all possible combinations. For higher numbers, I spotted the pattern and guessed that it would continue. The way that submissions are marked, there is no requirement for a proof that the answer is correct, and no penalty for a wrong answer. So it is reasonable to make a guess and submit it. It may not be good programming, but it earns the points. You can see my solution here at https://www.codechef.com/viewsolution/20130095 answered 25 Sep '18, 08:09

@vijju123 you have mistaken in Maximum Possible Permutation $2,3,4,…,⌈\frac N 2⌉,1,⌈\frac N 2⌉+1,⌈\frac N 2⌉+2,…,N$
link
This answer is marked "community wiki".
answered 19 Sep '18, 02:42
Ouch! And to think that 3 people beta reading will surely catch all the typos XD. Thanks dear!
(19 Sep '18, 09:51)

My simulator. It is probability independent. Maybe using the keyword answered 18 Sep '18, 14:31
Can you explain your simulator ?
(18 Sep '18, 21:07)
My simulator is explained by @anaphase21 https://discuss.codechef.com/questions/135048/bshuffleeditorial/135520 . My code is an implementation of this. Will add explanation by tomorrow :P .
(19 Sep '18, 11:48)

It's fairly easy in Python, at least, to produce the entire distribution up to n=8  $8!$ is not so large. This only requires that you count the permutations from the previous swaps rather than modifying them one by one. Code for this investigation:
n=9 produces a result in ten seconds or so. n=10 is a couple of minutes. answered 18 Sep '18, 19:07

@bciobanu Hey did you created this question just by checking this solution for smaller numbers? I mean do you have proof for the larger number? Thank you answered 19 Sep '18, 00:24
The setter has it, but its very complicated and hence its discussion isnt covered by the editorial.
(19 Sep '18, 01:23)
Ok. Thanks @vijju123 .
(19 Sep '18, 05:14)
The proof for larger numbers for the most likely permutation is given in the research paper attached in point 2. For the least likely permutation, setter's proof is given in point 4.
(19 Sep '18, 15:21)
Yup, I gave further reading for interested ones. If you can get those and explain them, you're always welcome to grab those karma/reputation points :)
(19 Sep '18, 15:54)

@vijju123 I was trying to do this question both in Java and Python. Because I was using random function I wasnt getting values with uniform distribution as given in the question. Which random function would give me uniform distribution in Java and Python? answered 19 Sep '18, 10:20
Can you show your simulator code? There can be many reasons why you didnt get the pattern, eg Number of simulations being insufficient OR $N$ being too small that multiple answers are possible etc.
(19 Sep '18, 10:34)
https://www.codechef.com/viewsolution/20235348 I am getting different permutations every time having min and max frequency. I intentionally submitted wrong code so that i could share my code with you.
(19 Sep '18, 10:58)
Try for a larger value of $N$, like $N=8$. Also, simulations should be at least $10^6$ or more. You should get same result when compile and run again and again for same input.
(19 Sep '18, 20:50)

Guessing patterns from few first cases is neither science nor programming. This is a low quality problem. answered 19 Sep '18, 14:53
Your level of maths is poor thats why you resort to simulation. Else derive it during contest, no one stopped you. :)
Get more exposure.
(19 Sep '18, 16:00)
3
I agree with @ygj_kurwa it's very disappointing to see problems which can be solved without any intuition at all...these kind of problem are not gonna be help in the future in any manner....I saw people wasting hours to simulate the program and find the pattern in the answer....even it is the same case with tabgame but still it has some logic behind it's pattern...but it's even more disappointing to see people like @vijju123 to insult someone simply because you always defend codechef it's policy and what not....have some sense pls...be grown up.
(19 Sep '18, 19:46)
2
Now this doesn't make sense. Saying that guessing is neither science nor programming is not an accurate statement. Even mathematicians would sometimes resort to conjectures and guessing at the very initial stages of their works, working all the way to obtain elegant solutions. You probably aren't aware of all the trial and error they go through. It's not all problems that can be solved rigorously just like that. Many great mathematicians in the past have made conjectures which were latter disproved by people who were equipped with better tools. Educated guesses are a part of science.
(19 Sep '18, 20:31)
1
Its your personal opinion when you call such problems poor, you need not disrespect things like that.
Guess what? Same holds for that persistent segment tree problem  you aint using that in real life. Or other $80\%$ problems of competitive coding. I hope this makes you realize that the argument is completely invalid. Be mature enough to understand that such ranting is uncalled for. You are welcome to give your opinion, but not at all welcome to bash your opinion and go on calling it a low quality problem.
(19 Sep '18, 20:33)
2
If you solved it without any intuition at all, good for you. But you should be educated enough to know that we are not all equal  not everyone is as bright as you, to be able to solve this with zero intuition. Pattern recognition involves intuition.
(19 Sep '18, 20:41)

@aryanc403, I submitted "Fooling Around" problem but it is showing wrong answer ,could you please check my code thanks. answered 19 Sep '18, 19:54
Try these test cases  1 17 and then 2 11 17 You will be able to figure out how your soln is test cases dependent which should not be the case. And do comment if you need more help. :)
(20 Sep '18, 08:09)
Thanks,I corrected it , But with this approach it is showing TLE (time limit exceeded). https://ide.geeksforgeeks.org/NmdZX8dmYp help me please .
(20 Sep '18, 18:24)
I found the sequence to be 3,8,11,32,35,56,59,64,67,118,121,208,211,216,219,622,625...... here difference betwween two elements is 3 alternatively but difference between other elements is varying . I am unable to figure it out ,please help me
(20 Sep '18, 20:54)

Hi! I used a different pattern but I'm not sure how to prove it's correct or not. I got AC tho. P1  N,1,2,3,....,N1 P2  swap(all consecutive numbers in the first half) + swap(all consecutive numbers in the second half) https://www.codechef.com/viewsolution/20172571 answered 22 Sep '18, 23:11
There are 2 possible permutations for odd n. And one possible permutation for even n.
(22 Sep '18, 23:19)

to find the permutation p2, one can just do left cyclic shift of original array p and then swap(p[n/2],p[n]) and you are done!!. here is the link..https://www.codechef.com/viewsolution/20106025
@vijju123 can you please provide a list of contests in which you have been the editorialist? I really like your editorials.
I think I served as an editorialist for April and Sept long. I think I did June LTIME and July Cookoff as well apart from that. Thats it pretty much XD
Related Problem 
2018 Asia Singapore Preliminary Contest  Fooling Around
Knuth FisherYates Algorithm is worth mentioning.