We invite you to participate in CodeChef’s April Cook-Off, this Sunday, 18th April.
Time: 9:30 PM — 12:30 AM IST. Please note the change in contest duration.
The April Cook-Off is going to have Amazon as the official contest recruiter! Amazon is hiring for Software Development Engineer 1, Software Development Engineer 2, and Support Engineer roles for its fast-paced environment.
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.
Joining us on the problem setting panel are:
Setters: Tushar lazywitt Gupta, Harshil Harshil_ Tagadiya, Hazem zoooma13 Issa, Mradul bhatnagar.mradul Bhatnagar, Jay JaySharma1048576 Sharma, Narkhan nkamzabek Kamzabek, Yash yash_daga Daga, Martin Martin53 Daniel Kopchev
Tester & Statement Verifier: Riley Monogon Borgard
Editorialist: Aman Retired_cherry Dwivedi
Admins: Radoslav radoslav11 Dimitrov, Ashish Ashishgup Gupta
Video Editorialists: Chirayu Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Yashodhan ay21 Agnihotri, Bharat Singla, Shivam Bohra, Radoslav radoslav11 Dimitrov, Aryan Agarwala, Meet myth_gemphir Singh Gambhir
Mandarin Translator: Qingchuan qingczha Zhang
Vietnamese Translator: Team VNOI
Russian Translator: Fedor Mediocrity Korobeinikov
Bengali Translator: Sakib SakibAbrar Abrar
Prizes:
The winners will receive 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! Hope to see you participating!! Happy Programming!!
Google kick start and cook-off timings are matching , please change the cook-off time if you can, both are important for me , because through cook-off Amazon is hiring.
Kickstart starts 4 hours after cook-off ends
On kickstart schedule page, turn on the switch that reads,
'Display in local time'
thanks, sorry for the comment.
How can someone be Problem setter?
By setting a problem :)
Jokes apart, the announcement has a relevant link.
As a problem setter, I want some contribution.
The problems are interesting and I wish I could have participated.
Give me one moment where a Tester have said that the problems are not at all interesting. As it seems that by default all problems and all contests are interesting.
The definition of interesting may vary though and it can't be generalized.
If a problem isn't interesting, it has less chances to appear in a rated contest.
However, I agree with you that interesting is a subjective term and may differ from person to person. What I meant to say was that I found most of the problems interesting.
If a tester thinks that the problems aren't interesting, they usually don't comment "As a tester, the problems are garbage."
But they should if they are a real tester . But Guts are needed for that!
As a problem setter...
They were quite interesting indeed. :)
Reminder — the contest starts in less than 15 minutes.
Long queue again :( anyone else with the same issue?
Why ques are sorted in some contests and aren't sorted in some contests? This is really confusing. radoslav11
Did I cheese VALET by coding O(N*max(T)) solution or is that intended?
Intended was $$$O(nlog(n) + Tmax^2)$$$
While creating tests I tried to fail these solutions, the fastest O(NT) soln took more than 1.5 seconds so I thought maybe we were safe, still 1-2 O(NT) solutions passed, I'm sorry about this :(
I see XD. Straightforward O(N*max(T)) seems to pass within TL without any pragma shenanigans if you only do basic operations. (tho took me 7 tries to fully optimize...)
But still is this problem worth "Div1 only"? I personally think that this problem is quite easy in terms of logic.
I think SANITIZE is relatively easy but seldom people try it during contest.
Yes, this problem was intended to be easier than both VALET and ARRAYOPS. But surprisingly, it got only 3 submissions in Division 1. Maybe people didn't even try it seeing the less number of solves.
I think a lot of people did see that simple solution that we need two queryies foreach point. But the most of them cannot or are not willing to write down that formular stuff needed to acutually calculate the coordinates.
In that sense the story of the problem was a bad one. Because you could have also written: Read 2N point IDs and the distances to 2N lines from stdin, calculate the points.
You would had got the same small number of submissions.
What? Of course, intersecting lines is not the hard part of the solution. You probably don't understand the problem. You can't choose the point you query.
You get the points ID as an answer to the queryies, and whenever we got an ID two times we can calculate the point with that ID.
So why the story, why interactive? Instead just give answers to the queries as input. This whole story is a pseudo problem, because the real one is to write down the formulars correctly, nothing more.
But that formular part is fairly hard, compared to the simple insight we need to see that we need two not parallel lines to construct a crossing point of them.
Well if you consider solving 2x2 matrix equation part hard you probably need to work on your arithmetic skill first....
I did read the problem during the contest but I couldn't immediately come up with how to get rid of the "interactive" part of the problem, and I did not give more thought during contest because of low # of solves.
I don't agree with you that obtaining formulas and solving simultaneous linear equations in two variables was the hard part. The hard part of the problem was to make sure that no two lines are parallel by taking suitable values of A and B and to simplify the absolute value part in the formula by taking suitable values of A, B and C. And to test these parts, the problem was made interactive.
This is just my opinion, no hatred. I found that the difficulty of problems was not evenly distributed, like for div2, C and D had a huge level difference. Also I didn't like the problems this time.
C wasn't easy ( medium i would say ) but a doable constructive problem in my opinion. But I agree with you that the contest wasnt easy as in I expected much more solves for D ( since it's a div2 ) but to my surprise only 5 solved :0 , and I disagree completely with the fact that they gave an "Easy" tag to C.
how to solve GCD SUMS problem?
That's just an overview of the whole solution: We will have a $$$O(n (\log n + \log C) \log C)$$$ precompute (actually it's less than that, because the final $$$\log C$$$ comes from computing the GCD) and we'll answer queries in $$$O(1)$$$ after that.
Consider an arbitrary query $$$(L, R)$$$. Then if we have done some divide and conquer, there would have been a unique position $$$M$$$, such that in the DnC we split at it and $$$L$$$ was in the left subinterval, while $$$R$$$ was in the right subinterval. Then, we can split our answer as $$$f(L, R) = f(L, M) + f(M+1, R) +$$$ contribution_merge. The first two terms can be precomputed during the divide and conquer and after that, the merge can be easily done in $$$O(log^2 C)$$$ per query as for every position we will only care about $$$O(\log C)$$$ different GCDs. This is still too slow, so we need to realise that all merges for some fixed $$$M$$$ are very similar. Hence, we can do a 2D partial sums precompute in every DnC node. The complexity of the precompute would be $$$O(\min(M-L, \log C) * \min(R-M, \log C))$$$, which we can prove is $$$O(n \log C)$$$.
Unfortunately during the contest, some people were able to optimise their $$$O(\log^2 n)$$$ solutions, but I still think the intended solution is pretty fun.