Errichto's blog

By Errichto, 7 months ago, In English,

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, gainullin.ildar, and big help from PraveenDhinwa. Main tester: lewin. Editorials: mgch. Translators: gainullin.ildar (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!

 
 
 
 
  • Vote: I like it  
  • +51
  • Vote: I do not like it  

»
7 months ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    One of possible approaches is described in the editorial: link.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it -32 Vote: I do not like it

      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.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        I am author, my solution complexity is

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          Why not to describe it in editorial?

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it +47 Vote: I do not like it

            I don't know why editorialist described some strange slow solution. My solution and lewin's are not that thing from the editorial.

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it +26 Vote: I do not like it

              Can you explain your solution?

              • »
                »
                »
                »
                »
                »
                »
                »
                7 months ago, # ^ |
                  Vote: I like it +15 Vote: I do not like it

                It is too difficult for me to describe my solution in english

                :(

                Check my code, maybe you will understand: code.

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it +41 Vote: I do not like it

            But looks like author's mind is weak.

            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.

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it -55 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 months ago, # ^ |
                  Vote: I like it +62 Vote: I do not like it

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 months ago, # ^ |
                    Vote: I like it +22 Vote: I do not like it

                  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.

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Test data of problem CLOSESTQ is to weak. Look at this submission. This code's time complexity is so strange.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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)

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    I don't think tests were weak, instead I think author's mind was weak.