Errichto's blog

CodeChef March Lunchtime
By Errichto, 8 years ago, In English

Hello Codeforces!

I’d like you to invite for CodeChef March Lunchtime that will start at 19:30 IST of 25-th March 2017 (check your time zone here) and will last 3 hours.

I'm a setter. Testers: kingofnumbers, CherryTree. 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. 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
  • +72
  • Vote: I do not like it

Comments Comments (36)
| Write comment?
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

will start in less than 2 hours!

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

I'm wondering, how many problems do you write a year (on average)? How many of them are at least as hard as TC d1 med or CF d1 C?

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

    EDIT: my guess/estimation is: 75 and 30 respectively

    I think that TC coordinator (you before, now cgy4ever) prepares more problems. Or am I wrong?

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

      cgy4ever was 69.

      https://www.topcoder.com/tc?module=ProblemArchive&sr=1&er=50&sc=&sd=&class=&cat=&div1l=&div2l=&mind1s=&mind2s=&maxd1s=&maxd2s=&wr=cgy4ever

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

      If prepares also includes testing (and trying to solve those tasks that were rejected in the end) — then yes, there are lots of them.

      But ideally coordinator should not write too many tasks on its own platform. rng_58 only need to write 18, 19, 17, 15 tasks during 2012 — 2015.

      Btw, nowadays there are a lot of platforms (and type of contests) to write, how do you choose which one to write?

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

        There are a lot of factors.

        Some platforms are cooler than others. It's good to work with experienced coordinators, and I can also learn something new from time to time. Codeforces has the best infrastructure, while Topcoder software is less convenient (at least for me). I like using bear Limak in statements, so I avoid platforms that forbid that. A few more things: money, being able to use Latex, a big number of participants, friendly staff, a language verifier, time zone that fits me and my friends (though, working with e.g. a tester in different time zone was never a problem for me). One other small thing I remember: someone from Hackerearth can make drawings if a setter needs it.

        I'm also curious how things work like everywhere, so I try various platforms. I can think of two that I haven't tried out yet: csacademy and atcoder — maybe I will change it one day.

        Different contests requires different type of problems. An obvious example is that DS problems can't be used in TC. I don't really enjoy preparing easy contests, and I'm sure I have some specific taste in topics. Maybe it's easier for me to invent hard problems for some particular contests but I'm not able to describe it. In some cases it's more obvious: for example, Arterm likes math.

        I like onsite contests so it would be nice to prepare and visit those more often. And I often give problems for the VK Cup, because I can't participate myself (I don't know Russian) and it was the first CF contest for which I prepared some problems (I'm slightly sentimental). My first ever problem was used in TCO btw. :)

        And now I'm preparing a lot of problems for Codechef because I'm a coordinator there, and we don't have enough problems. A few things will change soon, and I hope to attract more setters then. Anybody is welcome to send me problem ideas btw.

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

Sadly it coincides with COCI.

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

    I participated in COCI because of hardest round of year.

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

I stil have not received laddus points for March Cook-Off. Is that OK?

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

    The round was declared unrated. Laddus usually come after the rating changes, so my guess is no one will receive laddus for this round.

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

      They said in the forums that laddus will be awarded

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

    I asked someone to check it. You should get an answer here very soon.

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

    Laddus will be rewarded. The team got busy with a few other things. Regret the delay. We will try and be more prompt in allocating laddus from next contest onwards.

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

      Plz Tell Us Approx Date for March challenge Rating Update.

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

        We have found a bug in the recent rating changes that we did. While the bug is small, it will have quite a big impact on the rating distribution, due to which we are taking some time to fix the bug and carefully update the ratings and also re-assign the distribution.

        It will take us a few days to update all ratings. Please bear with us untl then.

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

Was C a DP using binary search + deque ?

Can you add problems to practice please. Yes it got accepted! Nice problem.

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

    I solved task with DP + Binary search + Segment tree :D

    code : https://paste.ubuntu.com/24248165/ (really bad written, I was debuging it more than 1 hour, I believe there is much shorter codes).

    Generally for me it looks similar as finding LIS:

    DPi is denoting maximum amount of numbers such that last interval is finishing on position i. Now I separated two options : Case when previous finished interval was in range [ Ci -a , Ci-b] and case when it was before Ci -b. In the second case just finding maximum value of DP before ci-b and pick all possible elements greedly after it, for elements in the range find maximum value DPj- X (Cj is in the range) , where X is the total amount of elements in the range [ 1 , Cj+a ] — I done this part with segment tree.

    I wasn't very clear, but I hope it is helpful.

    Problems were good, I am happy with place and unhappy with time spent in finding bugs :)

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

Can anyone share any ideas/approaches for the last (toughest) problem?

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

    The editorial should be posted soon.

    Special vertices are endpoints of given extra edges (there are O(k) of them). Run floyd-warshall to find distances between them. Now we can forget about initial extra edges.

    Special vertices divide the whole row of n vertices into O(k) regions. It's good to first solve a subtask with n ≤ 200 000 in complexity . For each of O(k·n) pairs (vertex, region) we can quickly find the sum of distances from vertex to everything in region. To do it, you should use the precomputed distances to calculate distances from vertex to endpoints of region, let A and B denote them. Then distances are A, A + 1, A + 2, ..., X - 1, X, X - 1, ..., B + 1, B, where the biggest distance X is something like , where L is the size of region. And don't forget about a special case — when vertex belongs to region.

    To get the full score, one must handle pairs (region1, region2) fast, what is much harder. I did it by analyzing how the sum of distances changes from (v, region) to (v + 1, region). It turns out that changes are quite regular, e.g. for a long time the sum of distances decreases by L, or for a long time it decreases by 7, 5, 3, 1,  - 1,  - 3, ... (consecutive numbers of the same parity). More details will be provided in the edtiorial.

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

rng_58 was the only one to solve all problems and thus he won the contest, while Alex_2oo8 got the second place by correctly solving all special subtasks in the hardest problem. Congratulations!

Does anybody know about some current issue with the leadeboard (not correct sorting in case of ties)? It was wrong during a contest but I don't see any counterexample now.

As always, I will be happy to hear some feedback, including negative one.

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

    Gradient in difficulty of problems is nice :)

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

    Where would you rate the 3rd and 4th question in today's contest as compared to the questions in a DIV 1 round on Codeforces ? I mean which out of (A,B,C,D,E) would be the likely tag for those questions ?

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

      I think 3rd is as div1 B while 4th is between D and E.

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

      I agree with chemthan on his assessment of the 4th problem, but I think that 3rd one is closer to Div1 C.

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

        With my limited experience of solving Div1 B and Div1 C problems in practice, I too believe that the 3rd one was closer to a Div1 C than a Div1 B.

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

      kingofnumbers (a tester) thinks that the 3-rd question was div1B, while it was harder for me. I think his estimation is more accurate.

      The last question was C/D for the sum of n up to 2e5, while maybe even E for the full score. It would be a bad problem for a CF round though, because it requires much time. It was better in this contest, where a strong participant could solve other problems fast and have a lot of time (more than 2 hours) for this one.

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

The best ever contest for me. I solved the second problem in the last 15 secs. I had lost hope completely of getting that problem.

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

When do the ratings usually update?

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

    It's codechef xD

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

    From what I've seen, ratings for all the contests held in a month update at the end of the month/beginning of the next month together.

    For example, ratings for March Challenge which started on March 3 and ended on March 13 have still not been updated.

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

    Just Saying "its codechef" should not really be an adequate excuse for delay. I read somewhere that with the new rating system that codechef has introduced, ratings update was going to be faster.

    Could Someone from codechef explain why exactly it takes them so long to update the ratings ?

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

      There are bugs in the new rating system. They will start updating once these bugs are fixed.

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

If you find Limak in your question, It is sure that you will have wonderful problems and editorials. Thanks @Errichto.

→ Reply