katana_handler's blog

By katana_handler, history, 13 months ago, ,

Hello Everyone!

I recently found an algorithm for finding the primes in O(n) in GeeksforGeeks and it was convincing also and then there is always the Sieve of Eratosthenes running in O(n log log n). The O(n) sieve is however a modification of the normal Sieve of Eratosthenes. But now what happened was that when I implemented the O(n) Sieve it should have run faster than the normal one(at least by a small margin) but it was always slower than the normal Sieve! Can someone please tell me why is it so?

But there a small catch also when we run both the programs for N up to 10^8 the normal sieve is faster by around 0.5 — 0.7 seconds but where as when we give N=10^9 though both takes more memory and time but the O(n) sieve works 0.5 3.0-5.0 seconds faster! so the second question that comes it that, Is the O(n) sieve better for larger numbers only??

PS: The codes I used is the same as shown in the GeeksforGeeks site!

EDIT: we just implemented it on our own and the result for N<=10^8 is the same but the for 10^9 O(n) runs in 12 sec and the normal one runs in 16 sec!!

• +17

By katana_handler, 18 months ago, ,

Hello everyone,

This is my first entry on Codeforces, so please excuse me if there are any mistakes. I know it i quite big but please read before down-voting.

This entry is about the VK Cup Wild Card Round 2. A lot of teams participated in this Round.There was only one problem and it was very interesting. Everyone tried their best to get the maximum score. We also got 21727 points before the system testing but during the system test we got zero points, this is because the solution which the judge considered for system testing was the latest solution with nonzero score and not the best solution which the team submitted! I am not saying it was their mistake in fact it was mentioned in the contest blog but I guess not every team read it properly and so was the case with me.

Now i believe that it becomes unfair sometimes like in our case we submitted many other solution hoping that our score would increase but due to bugs sometimes we got zero points or sometimes a small positive score because the first case was very trivial and in the last phase of the contest we tied to submit some extra solution since the contest was going to end but we couldn't get a better score but we didn't realize that this would cost us a lot! though we had a better solution submitted only our last buggy solution was judged and our rank fell considerably.

Though we participated unofficially it hurt us because we actually tried really hard to get a score of 21727 but at the end when you see that your real solution got rejected and a faulty one was judged anyone would feel very bad.

I am not requesting to change the final standing or anything because that would be too much for a request but it would be really great to see what our best solution could score. So i request MikeMirzayanov to please consider this request and let us know the score our best solution could get!

I am sorry if I offended anyone, it was not my intension at all, i just wanted to put forward this request because it was something that hit hard on our hopes of getting a good rank.

It would be great to know your opinion also!