That’s because for n > 17, the most likely permutation doesn’t follow the same pattern as for n \leq 17. It is the identity permutation (1,2,3, ... n) that is most likely to occur for n > 17. The least likely permutation, however, follows the same pattern even for greater values of n.
1 Like
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 
Your level of maths is poor thats why you resort to simulation. Else derive it during contest, no one stopped you.
Guessing patterns from few first cases is neither science nor programming.
Get more exposure.
I want to know how u checked for n>=10
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.
2 Likes
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.
1 Like
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.
3 Likes
Its your personal opinion when you call such problems poor, you need not disrespect things like that.
these kind of problem are not gonna be help in the future in any manner
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.
1 Like
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.
2 Likes
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.
Interesting! I think this fact is worth mentioning in the editorial. It means that observing the pattern, while the solution for the specific constraints, is not the solution for all N as it may sound.
Yes, but its always the editorialists dilemma. I felt mentioning it in editorial will make it feel contradictory, that at one hand editorialist shows a nice simulation solution and then he says its not the answer for all N XD.
@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.
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
Thanks,I corrected it ,
But with this approach it is showing TLE (time limit exceeded).
help me please .
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
Knuth Fisher-Yates Algorithm is worth mentioning.
How can we say that the proof by setter is correct? It just proves that the number of permutations for the least likely is {2}^{N-1} but there is no proof that it would be the least number?
The proof states that it proves “… is the least likely permutation and occurs 2^{M−1} times” however I think it only shows the later. Still you could do a similar induction proof to show that all permutations occur \ge 2^{M-1}.
You can just try go through all possible n^n possible sets of swaps and count the results (up to something like 8 or 9). I can guarantee it’s correct up to n=8, although it should be noted that for odd n there are two equally likely permutations.