KMAASZRAA's blog

Invitation to CodeChef December Cook-Off 2019
By KMAASZRAA, 5 years ago, In English

Merry Christmas y'all!

I invite you to join us at CodeChef’s December Cook-Off. A 2.5 hours contest with five challenging problems which will be a great chance for you to test your skills.

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

I hope you will participate with your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

  • Setter and Editorialist: KMAASZRAA (Kasra Mazaheri)
  • Tester: ckodser (Arshia Soltani)
  • Statement Verifier: Xellos (Jakub Safin)
  • Admin: teja349 (Teja Vardhan Reddy)
  • Mandarin Translator: qingczha (Qingchuan Zhang)
  • Vietnamese Translator: Team VNOI
  • Russian Translator: Mediocrity (Fedor Korobeinikov)
  • Bengali Translator: solaimanope (Mohammad Solaiman)
  • Hindi Translator: Akash Shrivastava

Contest Details:

  • Start Date & Time: 22nd December 2019 (2130 hrs) to 23rd December 2019 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
  • Contest link: http://bit.ly/COOK113-Codeforces
  • Registration: You just need to have a CodeChef handle to participate. For all those who are interested and do not have a CodeChef handle, are requested to register in order to participate.
  • Prizes: Top 10 performers in Global and top 10 performers in the Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/t/how-do-i-win-a-codechef-goodie/7344

Hope to see you guys in the ranking!

Update : We're truly sorry for the mistake in CRSHIT. Both the tester and I had the same bug in our solutions :(.

The round turned out to be harder than expected, div.1 also got started on the wrong foot as everyone tackled DAND (which was intended as 6th). I can only assume if the problems were ordered by difficulty, the round would've gone much better. One thing I didn't understand was why don't Div.1 contestants solve the common problems of both divisions first? It seemed unnatural to me that everyone was on DAND for the first hour or so.

Anyway, thanks for participating. I hope you enjoyed the round along with all it's flaws (or at least would enjoy upsolving it as I think the problems are interesting and educational!).

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

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

Reminder: starts in 1.5 hrs approx.

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

Perfectly unbalanced as all Cook-offs should be!

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

6 years since I last participated in a Codechef Cookoff but nothing has changed. Still the same unbalanced problemset.

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

    Maybe people are used to such contests. They are maybe giving up after solving 2-3 problems(like me) knowing that contest will be unbalanced and as a result causing it to be more unbalanced.

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

Seems they extended by half an hour. Maybe I can solve one now ;)

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

And the tradition of unbalanced contests on codechef continues!! Even their website is not functioning properly!!

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

for div1: unbalanced contest

for div2:typing contest ..type 4 lines in 2 minutes and then do any other work..u will still get into top 10%

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +14 Vote: I do not like it

How do you solve DAND? I got TLE for an $$$O(T*LOGMAX)$$$ solution. Was this intended?

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

    i think the contest still not ended...it's fair if u ask after the contest brother...

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

Can someone explain what is the complexity of your solution for The Inexplicable Giant Floating Baby Head

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

What was the intended complexity in CRSHIT? If it was $$$O(NQ)$$$, why do you make such big constraints?

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

    To make sure O(nqlogn) doesn't pass.

    The constant for the O(nq) solution is pretty small, passing in 0.49s: https://www.codechef.com/viewsolution/28448037

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

      I'm curious to know what's wrong with this problem or my comment. To me, it was perfectly fine. It wasn't like DAND, where solutions with the right complexity got TLE.

      If you thought that O(nq) shouldn't pass and are angry that you didn't attempt it
      If you only thought of O(nqlogn) and are angry that you didn't get the problem because of an extra log factor
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        I also don't get why your comment getting downvotes :(

        For example, I firstly wrote O(NQ) solution which works 4s on max test(I know that this is my problem writing inefficient code, but still...), and only after this implemented normal solution:)

        As for me, solution to the problem is rather straightforward once you know/notice that you can not to change directions, and difference between O(NQ) and O(NQlogN) is quite small. So personally I wonder why authors don't want to extra log to pass.

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

The reason for spending time on DAND: it's a straightforward digit dp problem to solve in O(BITS * T) if you don't know the TL is tight. Then it turns into a constant optimization task.

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

    Actually I was watching the submissions list for a while at the beginning of the contest, everybody was trying to squeeze $$$O(Q \times log(R)^2)$$$ solutions. Even the reds. The TL was a set to reject $$$O(Q \times log(R)^2)$$$ solutions but most of the accepted solutions passed under one second. One simply had to not code for failure.

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

      https://www.codechef.com/viewsolution/28444303 why does O(Q * log(R)) get TLE then? I think if you use any * or % then it's already TLE :|

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

        I can't make sense out of your code. It has too many operations than it's needed. You can refer to my solution to see the difference. Anyway, I couldn't have increased the TL as mentioned above, since there's a large difference between solving in $$$O(log(R)^2)$$$ and $$$O(log(R))$$$.

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

      Reading $$$3 * 10^6$$$ numbers of $$$19$$$ digits is not a good idea. Even the solutions in $$$O(Q * log(R))$$$ without many optimizations got TLE :(

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

How to solve Make It?

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

    k has at most 768 factors. We can precompute dp[n][768] = min sum to get a product of a particular factor of k for both prefixes and suffixes. To answer queries, we can use our precomputed prefixes and suffixes to answer each query in O(768).

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

    YouKn0wWho Refer to this solution : https://www.codechef.com/viewsolution/28455991

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

      Thanks for this solution... I got a hard time doing constant optimization.

      Upd: and I just realized it has a better compleixty than the author's.

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

Could someone please point out why this is incorrect? ( Verdict : WA )

What I have done is, greedily taken highest bit, if possible.

UPD: Updated submission link

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

How to approach problems like this ?

I mean what should I start learning to solve problems like this during the contest timings.

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

Loved the contest though, for a noob like me, the problems were tricky af! Especially the Crash It problem, I liked it a lot. Thanks man!

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

    Could have been better if atleast the sample cases were correct.

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

      Oh right, that problem I couldn't solve earlier, it was good tho.

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

Codechef should change their name to XORchef

→ Reply