Invitation to CodeChef February Cook-Off (Rated for all) — Today

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 mhq 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 mhq 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!

Comments (33)

• 43 hours ago, # ^ |

  is the round declared unrated?

• 2 days ago, # ^ |

  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)

  • 41 hour(s) ago, # ^ |

    I got the meaning of the problem statement wrong, and thought after queries of types '?' the whole graph gets reset back to initial and so was changing the cost to the initial minimum, guess I need English tuitions, LOL. But the basic idea of the question is just what you mentioned!

• 38 hours ago, # ^ |

  Actually the answer is simply ∑ni=1Ai−N(N−1)/2+2M∑i=1nAi−N(N−1)/2+2M

• 2 days ago, # ^ |

  Yes, the prize is very deeply disturbed.

• 2 days ago, # ^ |

  They are only for D1 users now . Announcement section has update here
  link

• 45 hours ago, # ^ |

  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.

  • 38 hours ago, # ^ |

    You are absolutely right, for me the toughest part was actually maintaining O(1)O(1) reverse (I had a bug in idea too, but still).

• 33 hours ago, # ^ |

  ← Rev. 2 →  

  0

  Slingshot solution: O((nm)2)O((nm)2) dp would be to process cells in decreasing order: dpi,j=max(i′,j′)|Ai′,j′>Ai,j,|i′−i|+|j−j′|>SAi,j+dpi′,j′dpi,j=max(i′,j′)|Ai′,j′>Ai,j,|i′−i|+|j−j′|>SAi,j+dpi′,j′. We can speed up the transition to O(log(n))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.

  • 32 hours ago, # ^ |

    Can you please elaborate a bit? Thanks

    • 31 hour(s) ago, # ^ |

      ← Rev. 2 →  

      +6

      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).

      Picture

      Actually there are 2 types of diagonals, one indexed by x+yx+y, other by x−yx−y. The x−yx−y diagonals are parallel to the orange and blue lines; and x+yx+y to the purple and green.

      Process cells in decreasing order of A. Let dpsum[d]dpsum[d] be the maximum dp value over processed cells (x,y)(x,y) with x+y=dx+y=d. Let dpdif[d]dpdif[d] be the maximum dp value over processed cells (x,y)(x,y) with x−y=dx−y=d. The answer for cell (x,y) is

      Ax,y+max(maxd<x+y−S or d>x+y+S dpsum[d],maxd<x−y−S or d>x−y+S dpdif[d])Ax,y+max(maxd<x+y−Sord>x+y+Sdpsum[d],maxd<x−y−Sord>x−y+Sdpdif[d])

      When we get the answer for (x,y)(x,y) we set dpsum[x+y]dpsum[x+y] to max(dpsum[x+y],ans)max(dpsum[x+y],ans) and update dpdifdpdif similarly.

      We can compute these suffix/prefix maximums and update the dp in O(log(n))O(log(n)) with a segtree.

      Code: https://www.codechef.com/viewsolution/58784071

      • 30 hours ago, # ^ |

        ← Rev. 2 →  

        +8

        Thanks a lot! That's a great explanation. I couldn't find a way to query the remaining region.

• 32 hours ago, # ^ |

  Go to the section where all coders rating is shown rating has updated there.

• 8 hours ago, # ^ |

  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.

• 8 hours ago, # ^ |

  a chef who cooks code