radoslav11's blog

By radoslav11, history, 3 years ago, In English

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!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Contest starts in 1.5 hours.

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Partial-Forces

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

This contest is too hard for me

»
3 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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

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

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I solved it as a greedy construction:

    Spoiler
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

        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 years ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

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

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

    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 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

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

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

        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 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          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 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    How to find $$$\text{gcd}(x, yz)$$$:

    long long g = gcd(x, y);
    return g * gcd(x / g, z);
    
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    There is a solution without int128 and without factorization.

»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Very good and balanced contest, thank you!

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
Spoiler

Why last testcase is failing Help please !

»
3 years ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

     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 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Codechef mails you, I got my voucher after 3 months probably.

»
3 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    I received an Amazon voucher for September Lunchtime around 10 days ago. So may be in a few weeks you will get your voucher.