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:
Setters: Morphy (Alei Reyes), Danylo99 (Danylo Mocherniuk), Filya (Andrey Filimonov), Reshab Gupta, chakred_namor (Roman Derkach), rishup132 (Ritesh Gupta), Abhishek Vanjani, saurabhyadavz (Saurabh Yadav), kartik_24 (Kartik Singhal), its_ulure (Aman Kumar Singh), Lewin (Lewin Gan)
Admin: Alex_2oo8 (Alexey Zayakin)
Tester: radoslav11 (Radoslav Dimitrov)
Editorialist: teja349 (Teja Vardhan Reddy)
Statement Verifier: Xellos (Jakub Safin)
Russian Translator: Mediocrity (Fedor Korobeinikov)
Mandarin Translator: huzecong (Hu Zecong)
Vietnamese Translator: Team VNOI
Bengali Translator: solaimanope (Mohammad Solaiman)
Hindi Translator: Akash Shrivastava
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 [email protected])
Good Luck!
Hope to see you participating!!
Happy Programming!!
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.
Please upload the editorials of last long challenge(May Challenge). Its been a month and next challenge is starting.
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.
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.
Regarding Amazon gift cards, apparently, they cause some tax claim issues :(
Alex_2oo8
ETA of Challenge Problem?
I will be more happy if -
1. There is no extension in contest.
2. No challenge problem in contest.
A complimentary bump to an imposter AIex_2oo8.
How did he manage to create an account with the exact same username :O
It is a"I"ex_2oo8(capital i), which seems a lot like small l) :p
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
Did the log(n) come from using maps?
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$$$.
As usual, many people passed COOLCHEF for O(nq)
¯\_(ツ)_/¯How?
https://codeforces.net/blog/entry/67382?#comment-519631
Basically on each query iterate over all numbers which occur at least twice and find how many of them are inside $$$[l, r]$$$ using two binary searches (it's even $$$nq\log{n}$$$)
I used Mo's algorithm to answer queries offline. How to answer queries online?
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))$$$
Ok. Thanks a lot
COUNTIT is much similar in implementation to SUM OF KTH POWER FROM Educational Codeforces Round 7
My O($$$(N+Q)\sqrt N$$$) solution Link was also not passing for last 20 pts. It was more about optimizations.
How to solve problem COUNTIT? The problem was to calculate number of certain sequences
So the Fastest Solution for COOLCHEF is O(NQlogN)
Solving process of COUNTIT:
finding one of AC code of Facebook Hacker Cup 2017 Final Round Problem A: Fox Patrols and submit it.
Sadly knowing getting TLE.
Finding codebook used to solve Educational Codeforces Round 7 F The Sum of the k-th Powers
Pasting the code and do a little of modification.
Getting AC.
or better, just realise that the code is just 20 lines, and simply code it.