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:
# https://www.codechef.com/SEPT18A/problems/BSHUFFLE investigation
from operator import itemgetter
from collections import defaultdict
lim = int(input())
pdic = {tuple(i+1 for i in range(lim)):1}
for spos in range(lim): # swap pos
tdic = defaultdict(int)
for pm,qy in pdic.items():
ad = list(pm)
for tpos in range(lim): # to pos
ad[tpos], ad[spos] = ad[spos], ad[tpos]
tdic[tuple(ad)] += qy
ad[tpos], ad[spos] = ad[spos], ad[tpos]
pdic = tdic
plist = sorted(pdic.items(), key=itemgetter(1))
print(*plist[:3], *plist[-3:], sep = '\n')
n=9 produces a result in ten seconds or so. n=10 is a couple of minutes.
@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
@vijju123 you have mistaken in Maximum Possible Permutation- 2,3,4,…,⌈\frac N 2⌉,1,⌈\frac N 2⌉+1,⌈\frac N 2⌉+2,…,N
it should be 2,3,4,…,⌈\frac N 2⌉,1,⌈\frac N 2⌉+2,…,N,⌈\frac N 2⌉+1
@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?
(N.B. I’m assuming that the original task (wrongly) assumed that the pattern continued indefinitely based on initial observations. The editorial seems to suggest that the pattern would continue, and the setter’s solution isn’t correct for n>17 either. If so, vijju123 links to a nice paper proving the initial task wrong.)
I have to say, I’m not too impressed how this problem made it into a competition without having any guarantees for correctness. From what I understand the original motivation was an appeal to pattern recognition that actually turned out to be wrong.
This whole thing actually highlights a very important takeaway: pattern recognition by itself is not a proof! For contrast TABGAME has a similar theme of pattern recognition, but in that case the pattern can be easily be shown to be general.
If the task would had been to print only the least likely configuration (which you have a proof for) that would have been perfectly fine, and actually quite a nice task.
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.
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…CodeChef: Practical coding for everyone
You need to initialize seed in srand so that numbers are different everytime, else same sequence is generated. Also, make sure number of simulations are sufficient for that value of N
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