# SEPT18 - Problem Discussion

I learned MO algorithm but was unable to come up with a soln.

I have asked @admin to move the editorials, they should be there soon, except for the 4 problems I mentioned in announcement thread.

A good sqrt solution has a reserved spot in hall of fame solutions of this long for ANDSQR. Got any?

You will love TABGAME

Same here XDDDDDDD

“We can see for a specific L, there are at most 30 different ranges that will produce different values.”

can you explain this line??

So for a fixed L, consider a range [R1…R2] that when ANDing all numbers from L to R in this range, you always get the same value. And since there are at most 30 bits to be lost, there are at most 30 different ranges corresponding to 30 different values for this L

I used mo’s algorithm to solve the problem
My AC solution:
https://www.codechef.com/viewsolution/20007964

1 Like

https://www.codechef.com/viewsolution/20007964

My solution using Mo’s algorithm.

2 Likes

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

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

1 Like

Early bird catches the worm

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

3 Likes