Still waiting for AUG18 SAFPAR editorial…
4 Likes
Just because it exists on OEIS does not mean it was “copied”.
3 Likes
I first submitted with MO’s algorithm but got TLE, I thought of giving Gilbert’s order a try but I thought it won’t affect the solution much, and did it differently, but after seeing yours (@codebreaker123 's )submisson, I realised that Gilbert’s order is indeed very efficient.
My AC’ed solution for and segments is nothing more than ad-hoc.
there can be atmost LOG A, different numbers starting from some fixed L, Using this I calculate ans for range (0, R) for all R, now ans of a query l, r is
ans[r] -ans[l-1] - intersectingsolutions
intersecting solutions can be found out in LOG^2 A,
@meooow agreed. Oesis contains lot of things which we don’t know about and setters obviously can’t check each webpage on oesis to know that if it’s there
1 Like
In short: you can start off with at most 30 bits, AND can only change things by removing bits, you can remove at most 30 bits. Hence there can only be a handful of places where the value changes, and between those points the value is constant.
@vijju123 the normal sqrt will not pass because of O((n+ q)\sqrt{n}), and q is bit large, to get AC you will have to use Gilbert’s order
1 Like
Early bird catches the worm 
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. https://www.codechef.com/viewsolution/20093928 The main idea can be found in https://math.stackexchange.com/questions/191896/does-knowing-the-totient-of-a-number-help-factoring-it 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… 
Can someone help with the Factors problem, please?
https://www.codechef.com/viewsolution/20202540
PLEASE HELP,USING LONG LONG INT STILL GETTING 10.
APPROACH USED: Total pairs-(Pairs having odd Xor)-(Pairs Having XOR=0)-(Pairs Having Xor=2)
Hello,
Is there any editorial for BSHUFFLE ?
Thanks.
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
Can anyone please tell me what test case I’m failing for this [problem][1]
[My solution][2]
Thank you
[1]: https://www.codechef.com/SEPT18B/problems/CHEFADV/
[2]: https://www.codechef.com/viewsolution/20212619
I was that close XD
1 Like