radoslav11's blog

Invitation to CodeChef June Long Challenge 2019 sponsored By ShareChat!
By radoslav11, history, 6 years ago, In English

Greetings Codeforces community!

The June Long Challenge, sponsored by ShareChat, is almost here and brings with itself happy programming tidings. Our curating chefs have been hard at work in their kitchens, and have created an engaging array of problems for you to crack.

Everyone is invited to participate in this long contest, starting from 7th June to 17th June. Here’s your chance to put your superior programming skills to test, to compete with the best of the best, while working hard to improve your ratings and climb up the ladder to glory.

And if that weren’t enough, ShareChat — India’s fastest growing social network — is seeking both interns and full-time employees to join their dynamic team. Job opportunities are open to programmers across the world and internship opportunities are exclusively aimed at final year B.Tech students who have already been placed and looking forward to gaining startup experience. Visit the contest page for more details.

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

Contest Details:

  • Start Date & Time: 7th June 2019 (1500 hrs) to 17th June 2019 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone

  • Contest link: https://www.codechef.com/JUNE19

  • 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 20 performers in Indian category and top 10 performers in Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here: https://goodies.codechef.com/ (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck!
Hope to see you participating!!
Happy Programming!!

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

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

I'm looking forward to it, I really liked the last challenge.

However, I still have one suggestion for improvement: After the challenge, short editorials can be provided at least for the difficult problems.

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

Please upload the editorials of last long challenge(May Challenge). Its been a month and next challenge is starting.

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

I understand that this question is not to blog's author, but still. What is the point of Codechef Laddus?

From my own experience, there can be months of delay before you finally get them (for example as for now I didn't receive Laddus for March Challenge).

But even if have, how can one spend them? I "bought" something almost two months ago, but in order details still written status: Not yet shipped and there wasn't any notification about this.

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

    I also understand that this question is not to blog's author, but still. :P If someone can convey them.

    I did create a blog detailing where all they should change. But nothing changed.

    February Long Challenge Laddus were credited on 27 May 2019, after repeated reminder for months. See here

    No one replies to emails. As of now, I never used laddus to redeem something. But I know some instances reported on discuss.codechef.com taking months to deliver goodies.

    Tbh, Atmax there are only two goodies in store, t-shirt(Generally people use this to redeem their initial laddus.) And CP3 book.

    I would love if they add "Looking For a Challenge".
    Maybe they should also add cash redemption or gift cards?
    So that user can use them to buy something on Amazon.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -21 Vote: I do not like it

Alex_2oo8
ETA of Challenge Problem?

P.S. -

A complimentary bump to an imposter AIex_2oo8.

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

Was the intended solution for COOLCHEF O(Q*sqrt(n)*log(n))? If that is the case, isn't the time limit too tight?

Also how to solve COUNTIT? I got the answer as summation(i^m-(i-1)^m)*(i^n-(i-1)^n), where i goes from 1 to k. But I dont know how to compute this efficiently

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

    Did the log(n) come from using maps?

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

      For COOLCHEF the required complexity is $$$O((N+Q)*\sqrt{N})$$$, so the $$$\sqrt{N}*\log N$$$ shouldn't pass.

      For COUNTIT, you can prove that the answer is a polynomial of degree $$$n+m$$$ and use Lagrange interpolation after that. To make it fast, we do Lagrange on $$$x = 0, 1, ..., n+m$$$.

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

    For COUNTIT : So we want to calculate $$$\sum_{i = 1}^{k} (i^n - (i - 1)^n)(i^m - (i - 1)^m)$$$.

    We can prove by induction that $$$\sum_{i = 1}^{n} i^k$$$ is a polynomial in n of degree k + 1.

    Therefore Our original summation is a polynomial in $$$k$$$ of degree $$$n + m - 1$$$. So we can just calculate the value of polynomial for $$$k$$$ in $$$[0, n + m - 1]$$$ in linear time and then do lagrange interpolation. Overall type complextiy : $$$O((n + m)logMOD))$$$

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

    My O($$$(N+Q)\sqrt N$$$) solution Link was also not passing for last 20 pts. It was more about optimizations.

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

How to solve problem COUNTIT? The problem was to calculate number of certain sequences

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

So the Fastest Solution for COOLCHEF is O(NQlogN)

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

Solving process of COUNTIT:

  1. finding one of AC code of Facebook Hacker Cup 2017 Final Round Problem A: Fox Patrols and submit it.

  2. Sadly knowing getting TLE.

  3. Finding codebook used to solve Educational Codeforces Round 7 F The Sum of the k-th Powers

  4. Pasting the code and do a little of modification.

  5. Getting AC.

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

    or better, just realise that the code is just 20 lines, and simply code it.

    → Reply