Блог пользователя radoslav11

Автор radoslav11, история, 3 года назад, По-английски

We invite you to participate in CodeChef’s October Lunchtime, this Wednesday, 27th October.

Time: 7:30 PM — 10:30 PM IST.

PS: Note the change in the date. The contest will be on a Wednesday this month instead of the usual Saturdays. The contest will be rated for all three Divisions. Joining us on the problem setting panel are:

Prizes:

Global Rank List:

Top 10 global Division One users will get $100 each. Non-Indians will receive the prize via money transfer to their account. Indian users will receive Amazon vouchers for the amount converted in INR.

Indian Rank List:

Top ten Indian Division One coders to get Amazon Vouchers worth Rs. 3750 each. The rest in the top 100 get Amazon Vouchers worth Rs. 1500 each. First-time winners in Div 2 who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each. First-time winners in Div 3 players who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each.

However, everything else about our previous Laddu system for Lunchtime will continue without any change. To call out specifically, the top 10 school students in Div 1 of Lunchtime will continue to get Laddus as well as the cash/Amazon vouchers as per the new system. The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

If you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating.

Good Luck!

  • Проголосовать: нравится
  • +148
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Will the cash prizes continue as usual or are they gone?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by radoslav11 (previous revision, new revision, compare).

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Number of problems in each division? Is there some specific reason why the number of problems in each division are published in cookoff, but not in lunchtime and starters? Thank you!

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Contest starts in 1.5 hours.

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Partial-Forces

»
3 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

This contest is too hard for me

»
3 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

Not sure if it was intended for anything, but first time I got to use 4D Mo's algorithm for anything. Nice!

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I think that the testcases for 35pts subtask on MAXSEG is weak. My $$$O(n^2)$$$ solution still passed. The problemset is actually great. Btw did anyone else also use counting sort in KTHGRID ?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help me with Median Rearrangement solution of original constraints??

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is a binary search-based problem. We need to find the n elements optimally lets binary search over the answer and find if the current element can be our required maximum of minimums and check the other condition with the help of an auxiliary function which can be simulated by below algorithm easily.

    Easy to Understand Code
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    I solved it as a greedy construction:

    Spoiler
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you provide some details on how you checked the arrangement?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        The codechef's editorial video provides a nice visualization for various things. My solution is similar in many aspects, but does processing in the reverse direction (starting from the maximum cost) and gets the answer directly. Instead of having it as a single step of a binary search.

        I have also submitted a simplified C++ version, which should be much easier to understand. It's possible to add debug prints for tracing updates of the p1 and p2 indexes to see how it works.

        Bonus: racer editions with faster i/o and faster sorting
»
3 года назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

In TreeUps how do you find the minimum?

As far as I can see:

  1. Any node at odd depth (considering root to be depth 1) will contribute abs(childCount — 1) nodes of a given color.

  2. Each node at odd depth is independent of any other odd depth node and all even depth nodes are decided by their parent nodes.

  3. So this becomes a problem of splitting these odd depth nodes into two sets with minimum difference of sum.

I can't think of any way to do this faster than $$$O(n ^ 2)$$$ so likely one or more of these points are wrong, but which?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +59 Проголосовать: не нравится

    $$$O(n^2)$$$ using bitsets

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +71 Проголосовать: не нравится

    Sum of numbers is $$$n$$$, so there are at most $$$O(\sqrt{n})$$$ different numbers and you can do knapsack in $$$O(n\sqrt{n})$$$

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      And you can actually add bitsets here too, getting $$$O(n \sqrt{n/64})$$$. I don't know if there is anything faster.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        How to do it using bitsets in $$$O(n \sqrt{n/64})$$$? $$$O(n \sqrt{n})$$$ soln editorial mentioned needs int in dp state instead of bool.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +11 Проголосовать: не нравится

          You only need int for small numbers, where you want to do sliding window. For big numbers add them one by one, even is they are equal, and use bitset.

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Problems are nice but what was the point of making people use bignum/int128 in MAXIMGCD.Having ai<=1e9 would have been much better imo

»
3 года назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

Very good and balanced contest, thank you!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

For C, I did something like this but i don't understand why it is wrong,

Спойлер

Please help me to figure out what is wrong with this approach

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You approach is correct. Did you use correct limits for binary search i.e [n / 2, (n / 2) * n] ?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Spoiler

Why last testcase is failing Help please !

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

Um_nik,radoslav11 there is no editorial for last two problems in div1, neither for the last month too, I just checked. Why is it so ?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Editorials for the last two problems of last month Lunchtime, I don't know what you just checked. We are working on editorials for the last two problems of this contest, they will be published soon.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What is the intended solution for kth grid?My O(n^(5/2)+q*n^(3/2)) got 95 points.Edit:got 98 points after optimizing block size

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

     Also Um_nik — ""both 100 solutions from contestants are different and not present in this list 98 solution from contestant is also not present in this list, but our tester had it implemented yesterday""

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    I have finally described my original solution here. I will add more solutions later.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

First-time winners in Div 3 players who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each.

I Got global rank of 129 in October Lunch Time Div3 for the first time in top 200. How do I redeem the prize?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

I wasn't able to find the Editorial for MAXSEG, can someone explain the solution or share the Editorial if exist?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    This contest happened long ago but what I can remember by looking at my soln is -

    • First solve for q=1, while is just simulation/greedy.
    1. Look at prefix sum of a,b and from a particular index i it's always optimal to jump to j (where B_prefix[i]=B_prefix[j]+1 which has smallest A_prefix[j] which is more than A_prefix[i] and add 1 to answer, if there doesn't exist any such, just to smallest possible value of A_prefix[j].
    2. Only exception to this condition is when B_prefix[i]+1==B_prefix[R], we don't really have any choice here.
    • For multiple queries solution remains the same.
    1. For each index there is an optimal position to jump if we can add +1 to answer and another optimal position to jump if we cant add +1 to answer if we assume R=inf
    2. So the idea is binary lifting until we reach an index that has B_prefix[i]+1==B_prefix[R]. After that, we don't really have a choice.

    I may miss out on some crucial conditions since it's too old. But that was the idea.

    My submissions — 35 pts 100 pts

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have got 135 rank in Div 2. There have been around 2 months after the contest still I haven't received any confirmation mail about the prize. CodeChef_admin