Hello CodeForces Community!
The calendar page has flipped to December. Take a break from your end planning and crack the codes by participating in December Long Challenge. Note down the details and be there. Joining me on the problem setting panel, we have:
- Problem Authors: gitesh18 (Gitesh Narula), (Shivam Singh), kingofbugs (Hruday Pabbisetty), (Goutam Saluja), (Yogendra Bhanu Singh), PraveenDhinwa (Praveen Dhinwa), kefaa (Kirill Gulin), iscsi (Istvan Nagy), Omelianenko (Andrii Omelianenko), kingofnumbers (Hasan Jaddouh)
- Problem Tester: mugurelionut (Mugurel-Ionut Andreica)
- Editorialist: kefaa (Kirill Gulin)
- Admin: kingofnumbers (Hasan Jaddouh)
- Russian Translator: CherryTree (Sergey Kulik)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: Team VNOI
I hope you will enjoy solving the problems. Please give your feedback on the problem set in the comments below after the contest.
Contest Details:
Time: 1st December 2017 (1500 hrs) to 11th December 2017 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: https://www.codechef.com/DEC17
Registration: You just need to have a CodeChef handle to participate. All those who are interested and do not have a CodeChef handle are requested to register in order to participate.
Prizes: Top 10 global and top 20 Indian winners get 300 Laddus each, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])
Good Luck! Hope to see you participating!
Nice problemset.
How to solve the last 2 problems : CHEFFIB and WESTAND.
If O(nlog2n) can pass then I think centroid decomposition can be used.
doesn't work. Gets TLE.
I am sorry, it does work. My code was not working since I had two update and query function. Once I merged both of them, my code ran. This is so dumb. My update function works in O(logn), while for a single query I have O(logn) updates. If I use two updates, it gets TLE. But if I use just one, it passes. Can't believe function overhead is so large. -_-
Incase anyone needs a video tutorial for problem CHEFEXQ, here is the video https://goo.gl/Wi3C5Y.
Its always exciting to see how SquareRoot Decomposition can be used to solve such a variety of questions.
Can you please tell me that why we have to update only bth bucket in every update query?
I mean all buckets after bth bucket should also change because the index i which has been changed is also in the prefix of all those later indexes.
A bucket is reponsible for only RTN elements. The complete array is divided into RTN sections or buckets, each of size RTN.
So update only that section or bucket that contains the index that is modified.
Oh right, I got it. Thanks for help.