Factorize boils down to Euler’s theorem and some cleverness. my code is somewhat commented, but I’m not sure how easy it is to follow. CodeChef: Practical coding for everyone The main idea can be found in Does knowing the totient of a number help factoring it? - Mathematics Stack Exchange but there are some things not caught by that, mainly prime powers.
It’s interesting that the bad permutations mentioned are called “empirical”. I expected there to be some motivation as to why the permutations were minimum/maximum.
3 Likes
@algmyr I got the same link but can’t understand anything except the fact that there are some keywords related to maths… 
This is it Gilbert’s Order, and as I realised it in this long challenge it’s pretty much efficient than normal sorting order (especially when queries are large compared to n)
1 Like
I was that close XD
send the link of this submission here.
Also the formula used should be
ans = (pairs having even values ) - (pairs having XOR =0 ) - (pairs having XOR= 2)
(pairs having even values ) = (n*(n-1)/2) - (pairs having odd sum)
Observe your answers for n=1 to 7 and rewrite program to make it O(n) just print pattern accordingly (yes it forms a pattern)
HERE is my solution
I don’t think that it is uploaded… but it will be uploaded soon…
Yes Pairs having even values = (total pairs i.e.(n*(n-1)/2))-(pairs having odd XOR (i.e. count of even no X count of odd numbers))
I actually remembered this was a question in CLRS (5.3.3). I researched for a bit in that direction. The Wikipedia link for Fisher-Yates mentions this incorrect shuffle and states that the most likely position for a digit to end up in is one position back, which turns out to not be the right answer. Had to brute force small cases to find the pattern. The OEIS link did not turn up in my search.
2 Likes
@rashomon: The Fisher-Yates shuffle is a bit different from BSHUFFLE. In Fisher-Yates, j can be chosen only between i and n - 1 (0 - indexing), whereas in BSHUFFLE, j can be chosen between 0 and n - 1 (when 0 - indexing).
Your code fails for this case:
2 2 3 3
Because a research paper on this exists => possibility of existence on OEIS.
I decided to write a small editorial on FCTR: FCTR - Unofficial Editorial - general - CodeChef Discuss
1 Like
@code_blast True. CLRS asks us to prove that this is a biased shuffle, which is fairly easy. However, finding the permutations which are most and least biased was much more difficult. I’m interested to know if there’s a theoretical proof as to why the target permutations follow the pattern that they do.
@aryanc403 Could you link to that research paper?
My code prints “pofik” for this isn’t that right?
@kunnu120: No, your code should print “Chefirnemo” because from initial state of (1, 1), Chef can just install ShareChat app once to make it (2, 2) which, as you can see, is reached irrespective of what the values x and y are.
@nitin21897: Your code fails on for the input 1 4 3 3. It prints Pofik while the answer is Chefirnemo because from an initial state of (1, 1), Chef can do a push-up increasing his power by 3 and hence reaching the state (1, 4). Note that adding X to N and Y to M are independent of each other. You may add any of them any number of times (even 0 times if needed). Hope this helps. 