SEPT18 - Problem Discussion

general
,
21

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

22

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

23

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

24

You will love TABGAME :smiley:

25

Same here XDDDDDDD

26

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

can you explain this line??

27

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

28

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

1 Like
29

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

My solution using Mo’s algorithm.

2 Likes
30

@admin @vijju123 Please look into this matter

31

Still waiting for AUG18 SAFPAR editorial…

4 Likes
32

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

3 Likes
33

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.

34

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,

35

@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
36

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.

37

@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
38

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

1 Like
39

Early bird catches the worm :stuck_out_tongue:

40

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

3 Likes