Hello, Codeforces!
We are glad to invite you to the awesome (we've tried our best to make it such) CodeChef AlgoManiac 2021: Code For Future, brought to you by Chandigarh University and CodeChef, that will start on Thursday, September 02, 2021, at 20:00 IST (UTC + 5.5).
Joining me on the problem setting panel are:
- Contest Admin: nishant403
- Setters: hitch_hiker42, prasanna2425, ars9, ShivY08
- Testers: _runtimeTerror_, nishant403, Vichitr, infinitepro, hitch_hiker42, prasanna2425, ars9, ShivY08
- Editorialist: infinitepro
There will be 8 problems, and 3 hours to solve them. We have made sure the problems are well-distributed across various concepts, such that they are pairwise distinct with respect to the ideas involved. Also, we tried our best to make the problem set balanced so that there is a gradual growth in difficulty (subject to maybe, at most one exception) from one problem to the next. Finally, we made the tests sufficiently strong and the length of the problem statements is kept inversely proportional to the difficulty of the problem.
The contest will follow the rules of ICPC and will be rated for the participants of Division 3. Each problem is binary, which means you will either solve the problem (by passing all test cases across all test files) or fail. There are no subtasks or partial scores. All the problems have the same points allotted to them. Users are ranked according to the most problems solved. Ties will be broken by the total time for each user in ascending order of time. The total time is the sum of the time consumed for each problem solved. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submission of the first accepted run plus 10 penalty minutes for every previously rejected run for that problem. There is no time consumed for a problem that is not solved.
This is an open contest, and anyone (regardless of age, gender, nationality, etc) can register themselves by going through the contest link. Also, you can learn more about the event and Tech Invent 2021, the annual tech fest of Chandigarh University, the institution that is hosting the contest, along with CodeChef!
Finally, here are the prizes:
- $$$1^{st}$$$ Place: 50,000 INR
- $$$2^{nd}$$$ Place: 30,000 INR
- $$$3^{rd}$$$ Place: 20,000 INR
One final note: remember to read all the problems, and stay plugged in while the adrenaline lasts! Farewell, until we meet again.
Few Updates:
The contest is going to be rated for the participants of Division 3 (though everyone is eligible for the prizes).
The time and date of the contest have been updated to avoid a clash with September Long Challenge which will commence two hours before the earlier scheduled time, and because of CodeChef rules, the participants would then had to wait till the end of the Long Challenge for the rating changes.
The number of problems has been increased from 6 to 8.
Will the contest be rated?
Bhai sab mooh maya hai!
No, it is not rated. Actually, we didn't have much experience as problem setters (it's our second contest), so there would have been a lot of pressure if it was rated. Not that there isn't any now. We tried to not compromise on anything from our end, but to be confident, we need a little more experience. Hope it all goes well this time, and maybe someday, we will have a rated contest as well :)
Well the prizes say otherwise!
If you feel like that then you can clarify all your doubts by participating.
Please Clarify hitch_hiker42 Is Prize is available for Div 3 participants only or Div 2 participants in the top 3 are also eligible for prizes? Top 3 for Prizes taken from all participants of all divisions or from division 3 only? Please reply as soon as possible.
Yes, it is rated for Division 3 participants but open to all. The winners will be decided post contest, after merging the rank lists of all three divisions.
Since the editorials are yet to be released, would anyone like to explain their approach for OPDIV. I feel it requires FFT but am unsure of how to use it.
You just need to find coefficient of $$$x^K$$$ in:
Just use a simple divide and conquer trick(the polynomial tree in any NTT implementation). There will be $$$log(m)$$$ levels, in each level it will take atmost $$$Nlog(N)$$$ time, where $$$N = \sum\limits_{i=1}^{m} q_i$$$.
Overall : $$$O(N*log(N)*log(m))$$$