Explanation for the solution to Codeforces Round 707 1C?

Revision en3, by arvindr9, 2021-03-15 20:00:27

I was in the process of upsolving Codeforces Round 707. I'm not quite sure how to do 1C, and the editorial seems a bit difficult to understand.

It seems like I'm not the only one who is having difficulty understanding the editorial 1C. Thanks to towrist for posting a comment asking about why the $$$O(nm^2)$$$ solution works (here), which received 16 upvotes (many of whom I'm presuming also are unsure about that portion of the editorial).

I'm afraid there is not any clear solution that anyone has access to (one can only read accepted codes and watch ecnerwala's stream. On another note, I thank NiceClock for sending a link to code though, which seems rather elegant (here)). I would like there to be a clear explanation to on how to solve the problem though.

Most of the comments in the editorial blog post are about Div2 A — D, and I am thus creating a separate blog post for us to have a clutter-free area to discuss this problem. I personally feel that this seems like an interesting problem, and many people will hopefully be benefited by having a place to discuss the solution to it.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English arvindr9 2021-03-15 20:00:27 16 Tiny change: 'r elegant (here)(https://c' -> 'r elegant [(here)](https://c'
en2 English arvindr9 2021-03-15 19:55:05 5
en1 English arvindr9 2021-03-15 19:53:49 1347 Initial revision (published)