Errichto's blog

CodeChef February Lunchtime — with Limak
By Errichto, 8 years ago, In English

Hello Codeforces! Did you miss Limak?

I’d like you to invite for CodeChef February Lunchtime that will start at 19:35 IST / 17:05 MSK of 25-th February 2017 (check your time zone here) and will last 3 hours. The contest starts 5 minutes later than usually to allow you to catch a breath after the AtCoder Mujin Contest that ends at 17:00 MSK.

I am an author of problems and editorials, while niyaznigmatul is a tester. I want to thank PraveenDhinwa (who is a contest admin) and suraj_sharma for their technical help. Translators: CherryTree (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. I honestly think that all problems are interesting and valuable — some for beginners and some for experiences competitors (IMO one particular problem is so new and beautiful). 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 in the leaderboard!

EDIT: The time of start corrected to "19:35 IST / 17:05 MSK".

EDIT2: Bump, the contest starts in 24 hours.

EDIT3: The contest is over. I hope you enjoyed problems. You can find editorials here.

And congratulations to Petr, uwi and savinov for getting the top 3 places!

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

»
8 years ago, # |
  Vote: I like it +49 Vote: I do not like it

"I honestly think that all problems are interesting and valuable — some for beginners and some for experiences competitors (IMO one particular problem is so new and beautiful)."

Most probably joining based on this sentence.

→ Reply
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

bump, 3 minutes

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

I have noticed that:

Those who achieve the score first will be placed higher in the ranklist in case of a tie.

So, in case someone got 400, his rank should not be changed anymore as those who got 400 after him should rank lower than him.

However, when the ranklist first show my score was 400, my rank was 10. And just now when i refreshed the ranklist, I found out that my rank dropped to 14. Isn't this behavior impossible to happen?

Did I misunderstand the rules of ranking or there is something wrong with the ranklist?

UPD Some of the contestants ranked higher than me achieved 400 later than me.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks for letting us know. Indeed something is broken with the leaderboard. We'll investigate that.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    I think Codechef IOI style leaderboards take into account penalties. So maybe you have better solving time but more penalties.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      But the rules stated that:

      You can submit solutions as many times as you'd like, there are no penalties for incorrect submissions. Only your best correct submission will be considered.

      So there should not be any penalties to wrong submissions.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem is fixed. You can check your place now.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody give some edge cases/tricky test cases for Bear and Bribing Tree? I can't find the mistake in my logic.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Your submission wrong on this case:

    2
3 9
6 10 3 15 1 13 16 19
3 10
1 8 9 15 10 4 13 20

    The correct answer should be:

    4
5
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you don't mind providing the testcase for my solution, I'd be glad, the same nickname.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
        1
4 9
6 10 13 5 9 18 3 1 11 12 7 19 8 20 16 14

        The answer should be 7 instead of 8.

        BTW, it is harder to generate a counter case for you:)

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Alright, thanks!

      → Reply
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

From your codechef blog: "IMO one particular problem is so new and beautiful"

So which one was it?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    overflow-points problem — I've never seen something similar and the solution is just cute.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I believe, it's very sad that this problem can be solved with a purely random algorithm.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        How?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I also want to know how! I didn't see any AC solution that is a "purely randomized algorithm", though I agree that one part of the solution can be done with randomization.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Here is my solution. I think it's purely random algorithm.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Can you show me how to run the randomized part of your solution? It doesn't seem to finish in minutes on my machine, even for k = 2, what I guess tries to find 3 points.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Actually, there's no magic, I just waited. I think 2-3 minutes for one new point.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it +6 Vote: I do not like it

                  You are right, it found the next point. Apparently I didn't try hard enough during the problem preparation.

                  Are you able to explain why it works? I have no idea why this program is able to find more than 3-4 points.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  Of course I can't. During the contest I understood that I'm stupid enough to solve more than 2 problems and the only hope to get a better rank was to try this random algo... And I'm not very proud right now

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it +6 Vote: I do not like it

                  But trying this algo turned out be a great idea. You solved a problem so there is nothing be ashamed of. The question is: why it works? I will try to figure that out.

                  → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            ← Rev. 2   Vote: I like it +3 Vote: I do not like it

            I believe the main difficulty was to find ten non-collinear points with small (<=15) coordinates (after that just multiply each coordinate with 216)? I just did this: add the points with both coordinates  ≤ 15 in a vector. At each step consider the current element in the vector and if it is not in the same line as any two chosen points choose it (otherwise ignore it). This gave me 19 points which was more than enough. Code

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              ← Rev. 2   Vote: I like it +18 Vote: I do not like it

              This is intended. Still, what Djok216 described is completely different.

              Also, I don't agree with you about the main difficulty. Finding such non-collinear points is easy even without computer. I still think that the hardest part was to get the idea about coordinates divisible by 216.

              → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Just generating random points and checking if the new point is ok to be taken.

          → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but this particular problem is not IOI-style, is it? but it's interesting anyway

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Thought I couldn't solve this problem, I enjoyed solving the other three very much. Thanks for preparing such nice problemset.

      → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Will there be an editorial?

Is there a way to see the tests on codechef?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All editorials can be found here.

    You can't see tests. Likely stress testing your solution locally will help you to find a counter-test.

    → Reply