We invite you to participate in CodeChef’s Starters 167, this Wednesday, 1st January, rated upto 5 stars (i.e. for users with rating < 2200).
Time: 8:00 PM — 10:00 PM IST
Joining us on the problem setting panel are:
Contest Admin and Statement Verifier: Shreyan Dominater069 Ray
Text Editorialists: Nishank IceKnight1093 Suresh
Tester: Sushil SmolBrain Raaja
Setters: Chromate chromate00, Shreyan Dominater069 Ray, Sushil SmolBrain Raaja, Yugandhar_Master.
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. Hope to see you participating.
Good Luck!
dom I am sorry i blamed you for Math puzzles. Its far better last weeks contest that my 10th grade brother could AK using gpt.
please atleast make div2 and div1 gpt proof. Last weeks contest was absolute dog shit.
happy new year and best of luck for contest.
I wish every honest participant a good first contest of 2025!
Reminder: The contest will start in ~50min.
Nice
How much time does rating update take?
Also I'm doing a contest on codechef after a long time. It doesn't seem to have any of the "cookoff" or other contests. Just "STARTERS". What happened?
When I see the ranking, it's all 1-star profiles. Since it's rated upto 5-stars, atleast some top rankers should be 5-star rated? Does no one do codechef anymore?
There are several divisions on CodeChef now and you likely opened the standings of Div. 4
Ratings are usually updated in a day. (I too don't recall the precise timing).
You will get the exact rating as shown on the Live Ratings section on the right pane of the Contest Page. I have been getting the exact same as shown on this right section at 120 min. (i.e., end of 2-hour contest duration) even though they say plagiarising users get a rating drop later when checks complete which makes me wonder if they get even eliminated from the leaderboard or not for genuine participants to get the right ratings deserved in a contest.
For all of 1-star rated users in your leaderboard, you had most-likely participated under the their Division 4 which is for users with rating $$$< 1400$$$. Other rated users will participate in different divisions (Div. 1 to 3) as per their rating band. The thresholds for ratings are given at the main contest page. For Example: https://www.codechef.com/START167 will include the Link to the Division-wise pages and explain the bounds of ratings which fit in each division. 5-stars and above will come under Div. 1 here https://www.codechef.com/START167A, while ratings will be impacted only for up to 5-star rated coders.
Thanks, looks like the problems (and constraints) were same for all irrespective of division atleast. Just that higher rated ones didn't have to go through the easy ones.
You're welcome.
Just checked, updated ratings have already reflected on our profile rating and graph. So, it takes under ~1.5 hours to update ratings post a Starters contest.
nvm I'm an idiot, ranklist shown is dependent based on your stars. I'm one starred so it showed me the "D" ranking by default. This is the ranking for 5 stars: https://www.codechef.com/rankings/START167A
Great Questions. Dom is back. Return of the king.
great problems !!! btw when is the editorial for icpc amritapuri regional round publish ?
Why was Grid Construction Even placed below Grid Construction Odd in the order? Ig it made difficult to solvers, just because it was below.
The order is dynamic and determined by the number of solves.
I mean in the beginning of the contest.
Its stupid question by me anyways.
Perhaps because it is possible to build a construction for even $$$N$$$ based on the construction for odd $$$N$$$ but not vice-versa. Check the editorial for details.
it is because we felt odd was easier than even (that may not correspond to your expectations ofcourse)
Can you please give tips how to solve constructive problems ? Is there any way to approach such problems?
upd i found the mistake
too many problems of same difficulty in $$$div2$$$
Number of successful submissions on the most solved three problems make it look like that. I could only solve the Delete Not Equal (DELNQ) and Lottery Tickets (LOTTERYTICK), and found Grid Construction (Odd) and Grid Construction (Even) in the increasing order of difficulty.
Grid construction both versions and Temperature balance were of same difficulties , I solved Grid Construction (Odd version) and temperature balance during contest
Disclaimer:
When I first set TEMPBAL I proved the solution alongside the MCMF formulation, and considered the construction nontrivial. Now apparently guessing the answer wasn't hard at all...
Is it only me or was the problem wasn't as easy as the number of submissions made it look like?
It shouldn't have been (I guess it was solved by o1)
Is there any way you think we could stop this kind of submissions by gpt, as they are anyways not allowed according to site guidelines?
Not easily in terms of administration. Currently the only way to find out if a user is cheating with an LLM is checking their code style, but they can just rewrite easily. The preferrable option right now is to just make tasks that can't be solved by o1 (but this is hard)
Also it seems as if they are easily able to do easy tasks of div 2. 3 and 4 making it hard to frame easier wuestion.
I don't know about MCMF or used o1, but the solution was fairly simple to think about. Just a few lines of code:
But yes I didn't expect it to have more solves than GRIDEVEN.
what was your mcmf based proof can you share ? i also think the construction is not at all trivial. nice proof thanks below
Consider the graph with $$$n+2$$$ vertices (including source and sink), which is almost a line graph with every edge having $$$1$$$ cost and $$$\infty$$$ capacity. The containers with positive temperature connects to the source, while the ones with negative temperature connects to the sink. The problem is equivalent to MCMF on this graph, except for some extra conditions.
We will prove that the extra condition does NOT change the optimal cost. For this, consider a condition for an MCMF instance to have optimal costs. An MCMF instance must not yield negative cycles to be optimal. In our problem, we can see that we must NOT flow heat on one wall through both directions to not yield any negative cycles. And conversely, if each wall pushes heat through only one direction, the cost will be optimal.
And there are constructions that achieve this. Consider a stack-based algorithm; you maintain two stacks $$$pos$$$ and $$$neg$$$ of tuples of $$$(index,flow)$$$. Whenever you find a vertex with nonzero demand/supply you push it to the corresponding stack. When $$$pos$$$ and $$$neg$$$ are both not empty, empty one of them by repeatedly sending flow from top of $$$pos$$$ to top of $$$neg$$$. Convenient invariants of this algorithm assure that at every moment, either every vertex in $$$pos$$$ leads $$$neg$$$, or every vertex in $$$neg$$$ leads $$$pos$$$. This, in turn, yields no wall pushing heat through both directions, meaning no negative cycles.
Please see the statistics — https://www.linkedin.com/posts/yash-raj-81974922b_codechef-competitiveprogramming-greedyalgorithm-activity-7280303264292622336-qdO4?utm_source=share&utm_medium=member_android
Why does every problem has to be based on a random observation ..CC Contest dissapoints everytime
skill issue
nice
I request Codechef to please at least provide a editorials of the contest for free.
If not then provide it for atleast 1 week for free.
I don't Know why they ask money for everyhting.
There is a discuss tab on top in CodeChef where the editorial is posted free for each question. You may check that.
https://discuss.codechef.com/
oh thankyou very much i take my words back sorry
No Problem, there was a time I didn't know where the editorial was published either. Happy Coding
Hello can anyone share approach for Sum Over Subarrays (SUMFSUB)
I tried using segment trees but the update can go upto N. Then I tried to calculate it subarray length wise but couldn't optimize it from O(n^2) like so:
s = 101101
1 -> 1 + 1 + 1 + 1 + 1 + 1 = 6
2 -> 1 + 1 + 2 + 1 + 1 = 6
3-> 2 + 2 + 2 + 2 = 8
4 -> 3 + 2 + 3 = 8
5 -> 3 + 3 = 6
6 -> 4 = 4
Any hints?
For the problem Grid Construction (Even) how is this output wrong?
S1+S2=(8×8)+(1×8)=72. The sum of any two adjacent rows or columns adds up to 72 as well
Are the solutions incorrectly checked?
column2 + column3 is not 72.
ohh damn, my bad missed the two 3's. Thank you!