SEPT18 - Problem Discussion

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

I used Mo’s algo too…

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

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

3 Likes

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… :frowning:

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
//