We invite you to participate in CodeChef’s December Lunchtime, this Saturday, 26th December, from 9:30 pm to 12:30 am IST.
Note the unusual time. It starts at 9:30pm instead of the usual 7:30pm
You will be given a total of 8 problems (6 in Div2, 6 in Div1) to solve in a duration of 3 hours.
Joining us on the problem setting panel are:
Setters: Sahil sahi1422 Chimnani, Venkata Nikhil_Medam Nikhil Medam, Áron mraron Noszály, Nishant nishant403 Shah, Yogesh SeismicToss Sharma, Hriday the_hyp0cr1t3, Divyam divyamsingal01 Singal, Bhavyesh bhvdsi Desai
Tester: Rahul amnesiac_dusk Dugar
Editorialist: Taranpreet taran_1407 Singh
Video Editorialists: Chirayu Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Yashodhan ay21 Agnihotri, Bharat Singla, Shivam Bohra, Aryan Agarwala, Radoslav radoslav11 Dimitrov
Statement Verifier: Jakub Xellos Safin
Mandarin Translator: Gedi gediiiiiii Zheng
Vietnamese Translator: Team VNOI
Russian Translator: Fedor Mediocrity Korobeinikov
Bengali Translator: Mohammad solaimanope Solaiman
Hindi Translator: Akash Shrivastava
Problem Submission: If you have original problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Prizes: Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which they can claim cool CodeChef goodies. Know more here.
The video editorials of the problems will be available on our YouTube Channel as soon as the contest ends. Subscribe to get notifications about our new editorials.
Good luck and have fun!
As this is my first contest as CodeChef admin, I wanted to add few words from myself. Please do consider setting problems on CodeChef, we need your help to create great contests! One of the advantages of setting problems on CodeChef is that you don't have to create whole problemset by yourself (though it is certainly possible, you can write directly to admins to [email protected] for LunchTimes and to [email protected] for Cook-Offs). Many new authors can't create whole problemset without experience, and that's totally understandable! Sending problems for review allows you to get feedback for our admins (Um_nik, 300iq, jtnydv25, Ashishgup and Morphy), and if your problem is good, you will get the invaluable experience of setting a problem for thousands of participants worldwide while working side-by-side with some of the best minds in competitive programming. Some of the best problems in this contest are set by first-time problemsetters, at least on such a level, and they did a great job, I'm looking forward to working with them again.
Apologies to SeismicToss for messing up the announcement :)
The contest is unrated due to queue and server issues.
Should we start considering CodeChef as a regular place to compete xd?
By problems you can, servers you need to risk it.
Since revamping our judging infrastructure 8 months back, we have had virtually no issues with submission scalability, and can easily process more than 2000 submissions and IDE runs per minute. The issue with the last Cook-Off was that we were caught off-guard by the sudden increase in traffic, and it took time for the extra servers to be deployed. That is not a valid excuse though, and we apologize for the inconvenience. We'll make sure to have sufficient redundancies in the future :)
Server down well this certainly aged well :\
There Servers Are Not Working. Because, money is invested somewhere else, if you know, you know :P
Also, similar thing was happens in last contest there was some bugs, i seriously feels so bad for problem setters and things like this happens :(
"We'll make sure to have sufficient redundancies in the future." Yup, you totally did that.
cLoUD SerVeR Go BrRrRRRrrrRrr ...
This aged poorly
;)
Oof
Ouch.
I think you should stop trying at this point, we will give contests on CodeForces and AtCoder. You may continue on your conquest to monetize competitive programming on Unacademy and host Conversations with CodeChef on YouTube and while you're at it maybe start making video on Roadmaps as well like other “tech youtubers”. I understand there's no money in hosting competitions so it makes sense for a "For Profit" like you to not do it properly and place your resources on these. Also plagiarism issue isn't there on CF and AtCoder, you please continue on your path of becoming a “For Profit” with your “Parent” company Un-ethical-demy.
You are being way too much harsh for just one contest , They had did many awesome works in the past , You should not forget them . BTW, I too don't like what Unacademy is Doing(Paid) , But Still they have done so many awesome things in past and are still doing it , You should take them into consideration before writing such a huge comment
This is super disappointing. We became too confident about our judging capacity and so had way more test files than we usually do. Coupled with the large participation, we hit the limit which hasn't happened in the last 8 months. We are very sorry for the bad experience. We will be increasing our capacity in a couple of days.
kitna chutiya banaoge translation : How much fool you will make us ?
Bro, please don't use such words in a platform like this, if you don't like it just don't give those contests and move on, no need to harass people who make time from their busy schedules and make a contest for us. I too feel there's something off in codechef and would prefer codeforces anytime but I do respect both of them.
Last few short contests were really interesting in codechef which was the reason for high participation in this lunchtime. But again said that, we would see decrease in participant in upcoming short contests on codechef because of today's issue. I think upsolving contests would be useful than waiting for judgement for more than 45mins.
CodeChef_admin Seems like site is now up, Is there any possibility we can expect queue to decrease in next few mins? Else I think participants like me would upsolve problems later on. I am very much curious in checking my solutions for Even Sequence.
Not in the next few minutes, no. By current rate, the queue will decrease somewhere close to the end of the contest.
2020 came calling :)
Time travel at its best :) Read my first comment at the top.
tourist won 7 out of last 8 short codechef contests.
Quality of problems has improved significantly recently, I enjoyed the last few contests, would recommend for participation :P
Smh
It would be really nice if we could also submit.
I agree
the queue was long in the cookoff and the contest was lagging so if you could work on it then it would be great.
Yes, sorry about that. Please see the comment above regarding this.
Please make the website contest ready before holding the contests otherwise it seems to be frustrating. If users such as Ashishgup would write a blog on cookoff then it is obvious that there would be a heavy crowd in the contest.
Reminder 1 — Contest starts in 1 hour, 45 minutes.
Reminder 2 — Starts in 30 minutes!
Reminder 3- Judging 'may' start in 30 minutes
Queue kisi ko wafa ke Badle wafa nahin milti
Queue :(
We are working on it. Please continue to solve other problems.
round should be unrated . I got WA verdict after 20 minutes which i could have fixed early if there wasn't queue . Also website loading too slow.
Also please tell if it's rated or not now instead of wasting 3 hrs and telling after that it's unrated .
WHY PEOPLE DOWNVOTING THIS ?
There is no time penalty in Lunchtime, so you did not lose anything?
But there is something known as contest rank and acc. to what I know one would be lower in rank (and eventually lower in rating) if he/she doesn't solves the problem faster
Time taken to solve a problem is taken into account (Did CC lied to you about that ? ). I could have fixed that in 2 minutes but i fixed after 22 mins. So yes i lost 20 minutes which i didn't deserved.
Please make this unrated to recognize your fault at least . And please fix CC before hosting any rated round . It's now habit of CC to waste other people time.
In div1 solving A,B fast mattered a lot and this queue ruined it.
I was wrong, the time of last submission is used as a tie-breaker. Sorry.
Not offending you but curious how you became admin without knowing codechef contest rules ?
Also please make problems well balanced . First 2 submission 600 and 3rd only 35 . It should have been like 600,300,100 to be a well-balanced problem set.
I'm not writing rules or configure the system to enforce these rules. My job is to choose problems and make sure they are well prepared.
I know that IOI-style ignores time of submissions, so I assumed that it is the same here. I was wrong.
Sir, I admire you. But, We Know the fact that why So Many Grand masters are interested in CC, money! And, it is ok.
Also, i agrees that Question's Quality is good now, but don't just promote them blindly !!
What did I promote blindly?
Ok
I don't think you can judge difficulty gradient by contest that was basically stopped after 1 hour.
Submission count of 3rd and 4th problem is low due to long queue of submission in first two problems. Even i found 4th problem easier than 3rd one. But we can't judge on submission count
how to solve 3rd question?
I reduced the problem to find longest subsequence such that every segment of equal elements is of even length. And that is just simple dp.
submitted b 20 minutes ago still in queue.
Judge is too slow .
CC Judge..Please stop keep running and take some rest.
When you waited 15 mins for your submission and the website shows "unable to connect to codechef server" :(
sme bro showing unable to connect again and again
And here goes the queue...
its working very slow .
My solution for SWAP10HG has been stuck for 40 min now T_T
When I first submitted, it had like 100 submissions. Still showing server error.
Please declare it unrated now. It (judge servers) has reached the heights of all frustrations now!
These people make ICPC round in India. Do they really deserve to host ICPC ?
Anyone facing queues ?
bro issues!! im not even able to submit the code
bro issues? that's something new
Unable to connect to the codechef servers and then you are allowed to make one submission in 120s
cc is the internet explorer of the programming websites.
You are dis-respecting Internet explorer by comparing with cc
I trying to submit a problem for 30 minutes. but codechef do not want to take the solution. xD
for sure they were not few moments!
Ok now you can't deny the fact that it is getting frustrating now. Please make it unrated.
The codechef server is not loading. I have been waiting for 25 minutes to submit my code
Site loading too slow.
Make this shitty contest unrated! Unable to connect to codechef servers
Everyone when 300iq didn't make many tests last Codechef:
"Weak tests! Bad problems! So easy to cheese!"
But actually, he was just trying to lessen the load on the queue. Truly a 300 iq move.
Codechef is only focusing on their unacademy course.
Auto comment: topic has been updated by Um_nik (previous revision, new revision, compare).
Thanks for making it unrated now (after half the time) otherwise its really disappointing if a contest is declared unrated at the last moment.
Can you please also announce this on codechef contest page too? I don't think every participant is following this announcement on codeforces.
He has done that already
I can see that now, It was not present at the time when I checked before posting above comment. Maybe lag in comments also :P
codechef should do something because there are only two short contest in whole month and issue like this in those contest is very frustrating for all participants.
That was not a good way to end the year.
Well it's 2020, what do you expect ??
Every year is a 2020 in CodeChef.
Codeforces smoothly handles over 15K participants every contest , to the contrary , cc can't handle even half the load...
I think it is probably because of cf has pretests
CF also has features like hacking phase, announcements for which we get notifications, we can ask our doubts/questions to the problem setters, leaderboard that updates in real time unlike every 1 minute or so and a leaderboard which accounts for people who have 0 correct submissions too. Also CodeForces is non-profit where I have seen only HarbourSpace sponsoring rounds and imho that is fine. CodeChef is blatantly supporting a scammy educational institute and yet still does not want to spend on their servers. They also offer certificates for money which cost a lot. You would think after all this, they would have better servers compared to CF.
inb4downvotedbyindianfanboys
Why do you think Unacademy is a scammy corporation? Have you EVER been to their youtube channel to see how much free material they have uploaded there? Every corporation that asks for your money isn't scammy. Byju's and WhiteHatJr might be scammy but unacademy is definitely not.
Also codechef was only recently acquired by Unacademy. They asked Errichto to criticise them and tell them whats wrong. So they surely want to improve. Just give them their time. Its not like Codeforces didn't have any server problems in the past. Also, codechef is also non-profit. They don't tell you to buy their coure. They ASK you. Its completely upto you if you want to buy them. They dont even spam their homepage asking you to buy their courses.
Call me an Indian Fan boy but I disagreed with your comment and downvoted it :-)
Contest Authors just wasted their problems. It would've been nice if this contest was on cf. :'(
What a way to end the year, CodeChef!
[user:CodeChef_admin,2020-12-26]Does contestant got laddus in an Unrated contest in codechef? Anyone knows about that? CodeChef_admin
That is just happening from last 2 contest not every contest, you should not make such huge comment on the basis of a few time error
ahh, it was a cool problemset :'(. First atcoder doesn't allow to participate now this happens :/
same feelings
XOR palindrome problem was cool?
Is it not?
(I didn't want to answer before I got AC and the contest ended)
I didn't mean to say it is a bad problem, just not very interesting. To me most of the time it was just somewhat tedious DS bashing.
I thought it is an awesome problem with two nice observations and pretty simple implementation with trie. Maybe we have different solutions.
Ok, there's a nicer solution. Then I won't complain. It is possible I overcomplicated — I had lazy propagation on a compressed segment tree (with custom operations).
I really feel sad for problem setters , there were so nice problems , queue ruined their efforts
you should give us more time and solve the server issue.Not making this contest unrated will solve the problem
After submitting code
Stop spreading hate so much for CC, Don't forget what they have done for CP in Past in India.
Its very bad to see ppl cussing codechef, there can be problems like these and it happens in codeforces also (maybe less no. of time)... but I hope cc will show the reason officialy.
I am saying this is bad bcz, at first someone pay the authors to create contest for u to participate in and if something wrong happens than its totally their mistake... maybe they had judged it all wrong like no. of ppl and no. of files.
Actually as one of guy in comment was saying above, it more of seems very interesting case of how ur servers can get overwhelmed with these type pf things which no one can think of.
Is CodeChef worth giving the contest?? I had my submission queued for 25 mins. XD
Yes, I strongly feel so. U need to experience a variety of problems. There is some pattern of problems and so the diff. b/w cc and cf. If u want to do it right way then I think u should practice problems from 2-4 diff platforms (while giving time to good problems not just solving easy everywhere).
I totally agree with kesh4281 usually I have noticed nature of problems in codeforces and codechef are slightly different which really helps in learning.
.
And why so?
Even though contest is unrated, do try Sum of Digits — https://www.codechef.com/LTIME91A/problems/SUMDIGIT. It has been made with a lot of work.
Offcourse, we want codechef not queuechef
Will we get verdict this year or in 2021?
Me after getting WA after 52 minutes in queue-
how to solve even sequence problem??? any hint.. problems were really awsm....
Try using DP with 2 transitions, first transition is getting 2 equal number, and the second transition is delete the current number (delete a number and insert extra number to get a pair has tha same cost) .
"An even sequence has the following property: each maximal contiguous subsequence which contains only equal integers (i.e. the same integer repeated a number of times) has an even length. In particular, the empty sequence is even. A subsequence is maximal if it is not contained in a larger contiguous subsequence which contains only equal integers."
The example says seq "112" is not an even sequence. Why? The definition says it is.
equal digit length should be even in this case length of digit 2 is not even -> "only equal integers (i.e. the same integer repeated a number of times) has an even length"
Each maximal contigous subsequence...
The 2 is obviusly not maximal.
Yeah it is — it is not contained in any larger contiguous subsequence which contains only 2.
how to solve this problem??
Solution for Even Sequence: Dynamic Programming.
Main intuition: Deleting elements is beneficial only when you are merging two disjoint subsequences whose elements are equal. To do so, it is beneficial to always pick the nearest such subsequence. Otherwise you can only add elements.
First of all, condense all maximal contiguous subsequences. Then maintain answers for $$$dp[id][parity]$$$ which is equal to "the minimum cost such that i have processed till index id and all maximal contiguous subsequences are even except the last one, the last one has parity equal to the parity in the state".
For transitions: You can either choose the immediately maximal contiguous subsequence OR you can choose the nearest previous contiguous subsequence whose elements were equal to the elements of the current contiguous subsequence. (You will have to use some optimizations like prefix sum for full score, also you will have to keep track of the last occurance of each subsequence)
The answer is obviously — $$$dp[number of subsequences][0]$$$
Can anyone explain why is the answer for THREE (Three Letters) equal to $$$\displaystyle \text{min}\Big( \sum_{c \in A} \Big \lfloor \frac{f_c}{2} \Big \rfloor, \frac{|S|}{3}\Big)$$$ ?
you can create a palindrome using only two ways.
1st three same characters and 2nd 2 same characters and one different. So maximum number of palindrome of size 3 we can create is ∑c∈A⌊fc2⌋. Also it can't exceed size of string/3 so take minimum.
Thank you for replying.
I understand that these two things give two different upper-bounds on the answer, but can you prove why is the answer exactly the minimum of those? (i.e. why can't the answer be any other value that is lesser than those two things?)
Can any of the admins comment on that, please? I am still unclear of the proof of the formula. Um_nik, Ashishgup
Assume, you have an array of length n and there are x (x <= floor(n/3)) pair of numbers such that both of them are equal, you'll always have x numbers to insert between them to make them 3-length palindrome.
n = 5, floor(n/3) = 1, so we can't have more than 1 such palindrome.
{1,1,2,3,5}: You can always replace X in 1X1 by 2,3 or 5 to make it a 3-length palindrome.
n = 6, floor(n/3) = 2, so we can't have more than 2 such palindromes.
{1,1,2,2,3,4}: You can always replace X in 1X1 and Y in 2Y2 by 3 or 4.
So basically, you can never run out of the number of elements to insert between such pairs if x <= floor(n/3).
This makes total sense now. Thanks very much!
I wrote a greedy solution to even sequence solution link
Can anyone tell me any case of failure.
My rough approach is to maintain a set of all odd length numbers we got. If the next sequence is of even length and that number is already present in set than remove all other element and add to answer and only keep that element else just remove all the element from set and add to answer.
If sequence is of odd length then add only to if it's length if of 1 and if it's already present than add to answer size of set — 1 and clear it.
P.S. — I got AC but still asking because everyone wrote DP, So greedy maybe wrong.
Yeah my original solution was greedy as well, it basically depends on how you solve the underlying interval covering problem :D
If any one is stuck at even Sequence can watch this- https://youtu.be/EoQhlHe6PYA
Problem : K-Tuple Tree [Inclusion-Exclusion]
Did anyone try solving it using inclusion-exclusion principle? The idea is to first break the graph into different component by removing nodes labeled with 0 color. And then to calculate inverse, i.e total ways such the condition does not satisfy, i.e there are ATLEAST two nodes belonging to same component. Subtract above from total ways of assigning and you get the answer.
I was able to pass 4 subtasks but got WA on rest (for k > 3 I guess). I think there might be something wrong with my formulation of inclusion-exclusion. Can someone please help me with the solution?
Problem link : https://www.codechef.com/LTIME91A/problems/KTTREE
Solution link : https://www.codechef.com/viewsolution/40859580
Video editorials for 5 problems have been uploaded here. And editorials for 6 problems can be found here. The remaining editorials will be published soon.
Can anyone tell me what's the answer for problem Three Letters for case:
1 xxxyyyabc
To me it seems answer should be 2 but my code shows 3 & i got AC !!
Probably weak testcases
Do you guys have any idea about this DIV-3 thing on codechef?