We invite you to participate in CodeChef’s February Cook-Off, this Monday, 21st February, rated for all.
Time: 8 PM — 10:30 PM IST
Joining me on the problem setting panel are:
Setters: Utkarsh Utkarsh.25dec Gupta, Hazem zoooma13 Tarek, Jeevan Jyot JeevanJyot Singh, Manuj DarkSparkle Nanthan, Nabil Boredom Boudra, Flamestorm flamestorm, Yahor 244mhq Dubovik, Leung arvindf232 Arvin, Cozma tibinyte Tiberiu-Stefan, Aruj arujbansal Bansal
Testers: Harris gamegame Leung
Statement Verifier: Jeevan Jyot JeevanJyot Singh
Editorialist: Aman Retired_cherry Dwivedi, Trung Đặng Kuroni Đoàn Đứ, Kanhaiya notsoloud1 Mohan
Contest Admin: Anton antontrygubO_o Trygub, Yahor 244mhq Dubovik
Head Admin: Alex Um_nik Danilyuk
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.
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!
Excited(because plagiarism checker is back and has spoiled many cheater's profile)^-^
why t <= 3e5 in D ? I got 2 unnecessary TLE.
How to solve div2 D ??...
Compute initial cost for the graph, by visiting vertices in non — decreasing order of A[i]. Call it C.
For each '+' query, C = C + 2
For each '-' query, C = C — 2
For each '?' query, print(C)
Thanks
Actually the answer is simply $$$\sum_{i = 1}^n {A_i} - N(N - 1) / 2 + 2 M$$$
Why so many constructive problem in Div2.
Is codechef prize still distributed?
Yes, the prize is very deeply disturbed.
They are only for D1 users now . Announcement section has update here
link
When will the remaining editorials be out ? . How to solve Slingshot problem (D1 E) ?
Tests in Tangling Tree seems to be weak. I've submitted small to large by merging large to small (which is essentially $$$O(n^2)$$$), but it still works in 0.11 code
UPD: here is the test generator
Hi. Apologies for the weak test — I did check it against a solution that merge to any set (which is effectively your large to small) and realised it will pass, but it was quite late (it was prepared in a rush) and didn’t find a construction quickly so I left it.
I figured it would not be so bad since no one who are able to code the whole thing would forget something like small to large. I was only very concerned about solutions that rebuild the whole set, since that enables a solution that does not implement reverse operation to pass.
Anyways, I will investigate adding this test.
You are absolutely right, for me the toughest part was actually maintaining $$$O(1)$$$ reverse (I had a bug in idea too, but still).
In my humble opinion Codechef should reward atleast the top 50 Indian coders with something. These contests' previous prize structure was very very motivating for many emerging coders from India. Sad that it's changed now. Anyways, we can't question them obviously , it's their decision to make ..
When can we expect editorials for the remaining problems? (particularly D1E)
Slingshot solution: $$$O((nm)^2)$$$ dp would be to process cells in decreasing order: $$$dp_{i, j} = max_{(i', j')| A_{i', j'}>A_{i, j}, |i'-i|+|j-j'|>S} A_{i,j}+dp_{i',j'}$$$. We can speed up the transition to $$$O(log(n))$$$ by using a segment tree (supporting range max + point update) for each diagonal (4n-2 total), and updating dp values there accordingly.
Can you please elaborate a bit? Thanks
Sure! So the set of cells that are >S manhattan distance away from a cell forms a diamond. In the dp, we need to take a max of dp values of cells that are NOT in this diamond. This can be split in to 4 regions of contiguous diagonals (one from each corner).
Actually there are 2 types of diagonals, one indexed by $$$x+y$$$, other by $$$x-y$$$. The $$$x-y$$$ diagonals are parallel to the orange and blue lines; and $$$x+y$$$ to the purple and green.
Process cells in decreasing order of A. Let $$$dpsum[d]$$$ be the maximum dp value over processed cells $$$(x,y)$$$ with $$$x+y=d$$$. Let $$$dpdif[d]$$$ be the maximum dp value over processed cells $$$(x,y)$$$ with $$$x-y=d$$$. The answer for cell (x,y) is
$$$A_{x,y}+max ( max_{d<x+y-S \ or\ d>x+y+S} \ dpsum[d], max_{d<x-y-S \ or\ d>x-y+S} \ dpdif[d]) $$$
When we get the answer for $$$(x,y)$$$ we set $$$dpsum[x+y]$$$ to $$$max(dpsum[x+y], ans)$$$ and update $$$dpdif$$$ similarly.
We can compute these suffix/prefix maximums and update the dp in $$$O(log(n))$$$ with a segtree.
Code: https://www.codechef.com/viewsolution/58784071
Thanks a lot! That's a great explanation. I couldn't find a way to query the remaining region.
rating update when??why so late?
why not ratting updated yet?
Go to the section where all coders rating is shown rating has updated there.
The ratings have been updated for all. For users who were affected by the issue in PREFPERM, and who would have had their ratings decrease, we have made the contest unrated for them (ie. +0 rating change). There were 286 such users across all divisions.
Thanks CodeChef_admin for this considerate decision. I spent almost an hour in trying to fix the solution for that problem, and I did not consider at all the likelihood that the reason for getting WA from the automatic judge would be an issue in the problem checker.