MATDYS - Editorial

Can someone explain the author’s solution in details ?How he arrived at it.

Thanks in Advance

The idea was to give a small advantage to careful contestants and Python coders.

That was graceful. The concept was thoroughly tested. I like it now…although it made me pull my hair during contest cause i JUST couldnt get it right in c++ hahahahah. Should had been careful :slight_smile:

I am sorry this was the case for you!

Thanks for such a great problem! Such problems are the cause I give priority to contests over dinner

1 Like

Thank you for your feedback!

2 Likes

You only needed till 2^63, no? And even after summing, its 2^64-1. 2^64 is out of limits, but 2^64-1 is in limit

My point is the solution should’ve been AC then !! But it threw a RE (SIGFPE) error. WHY ??

It means you are doing infinite loop somewhere. And getting a RE due to this. Like when an array gets involved in a infinite loop.

Try this test case

1

64 18446744073709551615

Second number is 2^64-1.

Actually problem is value of total become 2^64 which cannot fit in unsigned long long.

2 Likes

With that attitude of yours, I’d rather not :slight_smile: . Go debug yourself, your code is none of my concern.

1 Like

BTW idk why nobody said this, but this is seriously a great editorial @likecs !!

4 Likes

THANKS @dushsingh1995

why we need to move the number to the left if it is on right?

My code was a simply while loop :stuck_out_tongue: , but our ideas are same . First time solved a Q in less than 15 lines XD

There is a shorted Python solution :slight_smile:
Check mine!

@anno, we are now actually moving number from left to right. It is just that calculating the number of left side is easier. So, we the number lies on right, we know that in i step it is 2^i plus that on left side. Thus, we add this contribution. I would recommend you to try some more examples on paper and also try to solve the problem mentioned in the link.

1 Like

Nice question! Inspired by FFT if I’m not wrong? :slight_smile:

2 Likes

@meooow Thank you! You are the first one to notice the FFT part. Yes, sorting by reverse_bits is the first step in the iterative implementation of FFT.

Try changing this while i<int(li2[0]): to while i<=int(li2[0]):