(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.
You will be able to figure out how your soln is test cases dependent which should not be the case.
Click to view
In your soln you have added 3,8 and later you are checking using them and no already found. But to find a winner for N will have to know all the situations of 1 to N-1. For example in this test case, you have missed 11 between 1 to 16. So you are getting different results for 17.
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
I knew that you would get TLE. That is why I wrote comment again xD.
Your approach is correct. Now you will have to optimize it.
Pre Req - Sieve1, Sieve2, Bitset
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}.
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 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.
