Hello, Codeforces!
I’d like you to invite for CodeChef April Lunchtime that will start in less than 3 hours (check your time zone here). The contest will last 3 hours.
Setters: Errichto, 300iq, and big help from PraveenDhinwa. Main tester: Lewin. Editorials: mgch. Translators: 300iq (Russian), huzecong (Mandarin) and VNOI team (Vietnamese). Language verification: arjunarul.
There is no registration required, anybody with a CodeChef handle can participate. Top school participants can win CodeChef laddus (details on the contest page).
You will be provided 4 problems with subtasks (IOI-style grading). Ties are broken by time of reaching your final score. The contest should be a bit easier than a Div1 Codeforces round. Remember about subtasks if you can't solve a problem for the full score, and read the editorial after the contest.
I wish you great fun and no frustrating bugs. Hope to see a lot of you on the leaderboard!
How to solve D , efficiently ?
I had all the Points in a set and all the distances in a multiset . For each query I added or removed distances from the multiset . The complexity of each query is O(Nlog(N)) per query if there are N points at a time. Using this approach I was able to get 40 points
One of possible approaches is described in the editorial: link.
I thought that tests are weak. But looks like author's mind is weak.
My solution is
with not so small constant, and I submitted it only because I think that it is really hard to construct a countertest. And now you say that the intended complexity is even worse.
I am author, my solution complexity is
Why not to describe it in editorial?
I don't know why editorialist described some strange slow solution. My solution and Lewin's are not that thing from the editorial.
Can you explain your solution?
It is too difficult for me to describe my solution in english
:(
Check my code, maybe you will understand: code.
Insulting an author because you have better complexity than the one in the editorial? So mature.
The complexity in the editorial is my fault. When an editorialist came up with a solution and asked me if it's intended, I told him it's fine. I didn't calculate the complexity correctly and thought that it's
. Sorry for that.
No, because solution in editorial has proved number of operations about 1e10. And I'm sorry for insulting author, I should have been insulted editorialist.
It's complexity, not the number of operations. Fast O(n4) (e.g. doing about n4 / 24 simple operations) might work for n ≤ 300 in 3 seconds, even though the complexity suggests 8e9 operations.
Even if someone wrote something that looks stupid to you, what do you achieve by insulting him? You just behave like an asshole (in my opinion). Next time just point out a mistake.
It is not the same thing. When solution make C·3004 / 24 operations you can prove that it is OK. Can you prove that this solution doing no more than 3e9 operations (let's start with it)?
It is my way of communicating. I think that only meaning is valuable. You can find tons of my comments in Russian with -100 rating. I think that almost all of them received that for not being extremely polite.
I'm glad that community express its opinion that way. It will not change my style.
So you are basically saying that you are an unagreeable asshole that no one likes...
Yep, and you can go fuck yourself.
Test data of problem CLOSESTQ is to weak. Look at this submission. This code's time complexity is so strange.
Thanks for letting us know. We've just added a test against it. There will be no rejudge ofc. (an extra test will be used when someone submits in practice)