radoslav11's blog

By radoslav11, history, 6 weeks 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

»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
6 weeks 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).

»
6 weeks 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!

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Contest starts in 1.5 hours.

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Partial-Forces

»
6 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

This contest is too hard for me

»
6 weeks 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!

»
6 weeks 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 ?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    I solved it as a greedy construction:

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

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

      • »
        »
        »
        »
        5 weeks 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
»
6 weeks 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?

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

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

  • »
    »
    6 weeks 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})$$$

    • »
      »
      »
      6 weeks 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.

      • »
        »
        »
        »
        6 weeks 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.

        • »
          »
          »
          »
          »
          6 weeks 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.

»
6 weeks 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

  • »
    »
    6 weeks 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);
    
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    There is a solution without int128 and without factorization.

»
6 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

Very good and balanced contest, thank you!

»
6 weeks 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,

Spoiler

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

  • »
    »
    6 weeks 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] ?

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

Can someone please tell me what's wrong in my code to the problem MEDMAX ? It shows the solution is partially correct. I am not able to identify the test case that my code gives wrong answer to. Here's the link to my submission(My code). Thanks in advance.

Never mind, I debugged my code.

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

Why last testcase is failing Help please !

»
6 weeks 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 ?

  • »
    »
    6 weeks 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.

»
6 weeks 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

  • »
    »
    5 weeks 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""

  • »
    »
    5 weeks 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.

»
5 weeks 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?

»
12 hours ago, # |
Rev. 2   Vote: I like it 0 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?