We invite you to participate in CodeChef’s Starters 161, this Wednesday, 20th November, rated for all. The contest duration will be 2.5 hours.
Time: 8:00 PM — 10:30 PM IST
Joining us on the problem setting panel are:
Contest Admin, Statement Verifier and Text Editorialist: Nishank IceKnight1093 Suresh
Tester: Takuki tabr Kurokawa
Setters: Nishank IceKnight1093 Suresh, Cozma tibinyte2006 Tiberiu-Stefan, KaiSuoShuTong.
Special thanks to satyam343 for discussing several problem ideas with me.
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Problem Distribution:
Division 1: 7 problems, one is a subtask
Division 2: 7 problems
Division 3: 8 problems
Division 4: 8 problems
Hope to see you participating.
Good luck!
Congrats to the top 5 in Div. 1!
My problem was proposed on 21 Jan 2022.
Finally,
Hell Yeah !!!!!!!!
Hopefully not a Math Chef today:)
Reminder: The contest starts in 30 minutes.
I struggled with ONETOTHREE during the contest and wondered why so many participants get AC with this problem, but after the contest, I noticed and was amazed that the following scheme is valid.
We can actually prove it by proving that we can never merge islands of 3's. (2's are fixed). I got 1e9+7 WAs before noticing that we have to run the loop backwards as well for smth like 233312 😭
damn I almost thought something like this going forward then backward but didnt try
When I came up with the problem, I had a more complicated casework-y solution, and only later realized that the simple greedy implementation is actually correct.
I was not sure how guessable this was so I briefly considered modifying the problem to ask for the answer for every prefix or something like that, but after discussing with the tester we decided it's fine to keep it as-is, since for the most part I feel like if you're able to think of this algorithm then it's not too hard to prove it either. (Also it makes for a simple implementation which is always nice.)
I did make sure to modify the samples so that just iterating forward would pass them though :) (you're welcome RoomTemperatureIQ)
What is the time Complexity of this ? I got TLE , is it (4*N)?
I assume you're doing "memset" for each case?
You are reinitializing it to dp[4][300005] in each testcase , which prolly gives the TLE, even if you don't get TLE , you will get WA, since this would not consider the cases that the backward iteration considers in the AC solution.
It was nice and tricky contest..
Good to see that I finally get 7 stars after this contest. My profile
Congrats hxu10 on being red !
Thanks for the contest. QUICKEXIT was such a beautiful problem!
The Constraints of QUICKEXIT made me think that I had to do it in O(N2) and my O(N) solution was missing something. ;-;
same, i thought that my greedy solution was missing something and did not end up implementing it
Codechef taught me to see constraints and reject solutions not accept it. Actually the harder version had an O(n^2) solution so they didnt change the constraints here too.
PS: It will be weird to have light constraints in harder version lol
those who solved the minmaxsubarray problem what were their ideas for proving answer at max can be min/max(P1,PN) depending on parity ?