We invite you to participate in CodeChef’s April Lunchtime in collaboration with Dream In Code — IIIT, Lucknow, this Friday, 30th April.
Time: 7:30 PM — 10:30 PM IST.
The April Lunchtime 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: Anshul Garg, Sambhav MR_POssiBLE Jain, Milos vladalos Puric, Chahat agrawal117 Agrawal, Evgeny 74TrAkToR Karpovich, Yogesh lemme_sleeeep Kumar, Karanjeet Talwar, Daanish Mahajan
Testers: Taranpreet taran_1407 Singh & Daanish Mahajan
Statement Verifier: Riley Monogon Borgard
Editorialist: Taranpreet taran_1407 Singh
Admins: Radoslav radoslav11 Dimitrov & Jatin jtnydv25 Yadav
Coordinator/Admin: Alex Um_nik Danilyuk
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
Prizes:
The winners 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! Hope to see you participating!! Happy Programming!!
Reminder — the contest starts in less than 30 minutes.
Reminder: Starts in 5 minutes :)
What was the intended complexity for Intersection Matrix.
I tried the O(2^min(N, M) * min(2^max(N, M), max(N, M) * B))
It gave only 75/100
Wouldnt this be O(4096 * 12 * 100000) at worse? How did it get 75 pts?
Edit: sorry I thought B was outside.
If max(N, M) == 12 then I will use 2^max(N, M) instead of max(N, M)*B
XX: The number of ways are the first 1+k coefficients of generating function of e^(bx)*(1+f*e^(ax))^n which can be computed in $$$O(K*log(K))$$$ using newton's method.
ALLGRAPH: For all nodes appearing as endpoint of atleast 1 edge, we assume the edges are undirected, and try to run dijkstra from each node. Most of the outgoing edges from a node have same weight, we try to handle them together using segment tree to support queries of extracting min and updating min.
IMAT: Combination of Knapsack DP and Meet in the middle based on N and M is intended solution. Specifically, Meet in the middle approach fails for $$$M > 40$$$ where knapsack works. This editorial will be out soon.
The editorials for rest of the problems are out. Hope you guys enjoyed it.
Can you please elaborate the solution of XX?
You can write the expression for expected value as follows:
Writing the EGF of $$$f_k$$$, we have:
which can be simplified to get:
You can calculate this expression in $$$O(klog(k)log(N))$$$ or even in $$$O(klog(k))$$$ since $$$P(x)^n = e^{nlog(P(x))}$$$
Ohh !! I am quite weak at mathematical modifications T-T. Btw thanks a lot.
I just googled things to get required formulas and then plugged them into it.
I just look at the definition of Moment-generating function (MGF) found it while looking at binomial distribution Wikipedia page.
Multiplying coefficient of x^i with fac(i) would give us E(x^i)
The moment generating function of the sum of 2 independent variables is just a product of individual variables.
Now problem reduces to finding the MGF of the binomial distribution. Then finding nth power of that MGF. Then ith coefficient that with give us the expected value of r^i. We can open up (a*r+b)^j express it as powers of polynomials of r^i 0<=i<=j. One more convolution will give us generating function for the answer.
For implementation details, you can look at main function of my submission
Thanks for the approach.
The editorials for problems XX, ALLGRAPH and IMAT are also out.
Honest feedback.
Anyways problems are way out of the IOI syllabus.
Please stop awarding points for just brute forces in the last 3 problems of div 1.
I missed 30 more points on the last problem by few seconds and I don't see any point in awarding 25 points for the first subtask of Hackerman.
Both of them eventually cost me a top 5 rank.
The idea of lunchtimes is for them to be IOI style and it's quite normal to give partial points (which also might change your strategy). You might argue that the partial points on those problems are given for trivial solutions, but you still need time to implement them, which potentially decrease your chances to solve some other problems fully (you even mentioned that you didn't have time to fully implement the 30 points solution). If you don't give enough points for those subtasks, nobody will bother with solving them, and frankly I think the results won't be so interesting.
Seems that we have very different views on what subtasks should represent. Just 2sat is like half of the code in full solution for Hackerman, why shouldn't we award 1/4 of points for it? Yeah it's not groundbreaking in terms of idea, but you have to spend time to write it. In Graph problem subtask for 22 pts gives a hint on how to get 60 and 100 after that, one could say that 100 is just 22 + dijkstra with some data structures. Like in IOI, you are not supposed to get only 100 and 0, solving the right set of subtasks is a part of the contest.