SEPT18 - Problem Discussion

Still waiting for AUG18 SAFPAR editorial…


Just because it exists on OEIS does not mean it was “copied”.


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

I used Mo’s algo too…

As told above by @meooow and @pshishod2645 , I feel its a coincidence.

1 Like

Early bird catches the worm :stuck_out_tongue:

What is Gilbert’s order can you please tell @pshishod2645


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. The main idea can be found in 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.


@algmyr I got the same link but can’t understand anything except the fact that there are some keywords related to maths… :frowning:

Can someone help with the Factors problem, please?

APPROACH USED: Total pairs-(Pairs having odd Xor)-(Pairs Having XOR=0)-(Pairs Having Xor=2)


Is there any editorial for BSHUFFLE ?


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

I was that close XD

1 Like