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!).
Reminder: starts in 1.5 hrs approx.
Perfectly unbalanced as all Cook-offs should be!
6 years since I last participated in a Codechef Cookoff but nothing has changed. Still the same unbalanced problemset.
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.
Seems they extended by half an hour. Maybe I can solve one now ;)
And the tradition of unbalanced contests on codechef continues!! Even their website is not functioning properly!!
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%
How do you solve DAND? I got TLE for an $$$O(T*LOGMAX)$$$ solution. Was this intended?
i think the contest still not ended...it's fair if u ask after the contest brother...
Can someone explain what is the complexity of your solution for The Inexplicable Giant Floating Baby Head
What was the intended complexity in CRSHIT? If it was $$$O(NQ)$$$, why do you make such big constraints?
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
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.
That's your problem for being inaccurate in estimating which solutions can pass. nq = 10^8, and with a constant small enough, it definitely should pass as usually you can get 10^9 operations per second. As I said in the comment above, the O(nq) solution runs very fast, and no constant optimizations were required. The best thing to do is to learn from this problem that this solution can indeed pass the TL easily instead of hating on it, so that next time you won't miss a problem like this again.
Two pointers is a well-known concept and all decent coders should know that you can change from binary search to two pointers in this problem very easily. Better learn it so you don't miss it next time.
Welcome to the world of "removing log factors from solutions". This happens all of the time in hard problems. If you want to be able to solve hard problems, you better start getting used to 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.
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.
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.
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 :|
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))$$$.
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 :(
How to solve Make 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).
YouKn0wWho Refer to this solution : https://www.codechef.com/viewsolution/28455991
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.
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
2 10 5 Your code gives 0 but answer is 2.
Oh cool. Thanks. Man, I should try stress tests more often
How to approach problems like this ?
I mean what should I start learning to solve problems like this during the contest timings.
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!
Could have been better if atleast the sample cases were correct.
Oh right, that problem I couldn't solve earlier, it was good tho.
Codechef should change their name to XORchef