244mhq's blog

December Lunchtime 2021
By 244mhq, history, 3 years ago, In English

This time contest admin is newbie, so it will be a little bit easier than usual :)

We invite you to participate in CodeChef’s December Lunchtime, this Saturday, 25th December, rated for all.

Time: 8:00 PM — 11:00 PM IST

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.

Also, 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
  • +127
  • Vote: I do not like it

Comments Comments (32)
| Write comment?
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

What about October Amazon pay vouchers

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

Contest to begin in less than 15 minutes.

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

I don't know why the problem "Optimal Sorting" turned out to be very hard for me to figure out. Spent around 2 hours on solving it!

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

Feels great to fully solve more that 1/2 problems for a change.
Thanks for the wonderful contest.
Adding an easier problem in div 1 was a nice touch. I hope Codechef continues it.

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

Nice balanced contest for div-1. Thank you.

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

    Understood, the community thinks otherwise.

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

      I think Div1 was much easier than usual, so its not balanced imo.

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

        I agree with you on the difficulty. Read your comment on Codechef as well and yes maybe the 5th problem was a bit too easy for D1 E but one problem being slightly easier shouldn't be too much I guess. Looking at the number of submissions I still feel it was balanced maybe could have been better with the 5th problem getting ~15 ACs and the last one ~5.

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

          The number of ACs are not a good estimate today, the 4th problem (interactive one) was also easier for its position.

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

How do you solve Div. 1 C? I've only got solution for A=1, but I guess that gives no hints. :P

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

Good Problems. Liked the Contest.

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

isn't MNULS's testcase too weak?

the greedy solution: go to the largest B. once B = A + k, it'll be that all the way.

will pass the test, but 5340 93 can hack this solution. (correct:61, greedy:62)

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

    We didn't come up with such a solution and it takes too many tests to cut off such stuff (

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

    Okey, I don't understand how it could go, because I cut off such a solution explicitly, for ~1900k :/

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

    This doesn't work even with n < k)))))

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

      This provably works for N < K, because you just spend all your time squaring anyways, which the greedy does. There are ~300 values of K <= 5000 which break this solution, here are the paths that I found so far: https://pastebin.com/YLw8e13p. (The number after BAD is K, the top path is the greedy, the bottom path is optimal.)

      Some of them are pretty interesting and require a few steps beyond K, like

      BAD 404 8
1 2 6 42 441 843 1245 1647 
1 2 6 42 441 840 1244 1648
      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

No one has sent a normal solution for last problems behind O(k^2loglog) :/

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

how to do NOL_LESS? My n*sqrt*log solution with fft passes in 0.69/2seconds. But I hope you have a solution with adequate complexity.

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

    I also passed the same, but it isn't n*sqrt(n)logn fully. I guess it's around nlog^2n or maybe even lesser.

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

    The complexity is bounded by $$$\displaystyle \sum_{k=1}^{\sqrt{n}} k \log n + \sum_{k=1}^{\sqrt n} \dfrac{n}{k}\log n$$$. The first sum is $$$ O(n\log n)$$$ and the second one is $$$nH_{\sqrt{n}}\log n= O(n\log^2 n)$$$ where $$$H_k$$$ are harmonic numbers.

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

How to solve Sleep Technique ?

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

How to solve Optimal Sorting ?

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

    Simple algorithm

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

      Can you explain your logic for once?

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

        Find the last position of every value in the sorted array then till the current index of that value in unsorted array is less than that original position we have to make at least a single operation to sort that subarray from I to that last position in between the way to that position check for other elements last position and update the current last position and finally when you reach the final last abort and. Do the operation.

        It will always give you minimum no matter what is the order of array

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

Greatly balanced contest!!

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

I guess the test cases for OPTSORT are weak. My Solution which is supposed to give TLE on large test cases, passed.

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

are there prizes in this contest (for top 100 div-1 participants) ?

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

This account and This have rankings 200 and 201 and their codes are exact same for all problems . They did the same in earlier CookOff . Activities like this take down the credibility of ratings .

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

"Sleep Technique" looks like combining 2 very standard problems.I wonder how it got approved by CodeChef admin

→ Reply