arvindr9's blog

Explanation for the solution to Codeforces Round 707 1C?
By arvindr9, history, 4 years ago, In English

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.

  • Vote: I like it
  • +31
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'd also like to add another part of the editorial that's really not clear to me but the editorial seem to take as trivial. Why is it never optimal to sort a column more than once? Although sorting one column is stable, why does sorting another column (therefore changing the relative order) then sorting the same column again not change anything?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Let $$$c_1, c_2, c_3, \dots, c_k$$$ be the columns you sort, in that order. You can view the process as sorting the rows in increasing order of their value in column $$$c_k$$$, then breaking ties by their value in $$$c_{k-1}$$$, ..., then breaking ties by their value in $$$c_1$$$, then finally, breaking ties by their position in the initial matrix.

    Now, let's assume we sorted some column twice, so some subsegment of our answer looks like

    $$$c_i, c_{i+1}, \dots, c_i$$$

    As by the above interpretation, we sort the rows by their value in the last column we sort, and if there are ties, we refer to the next last column, et cetera. By the time we've reached the first (in answer order) $c_i$ sort, we're only using it as a tiebreaker for the second $$$c_i$$$ sort. Let's say that two rows are tied all the way from the last column to $$$c_{i+1}$$$. They will then still be tied on $$$c_i$$$, so this column will break no ties. So it will not affect the correctness of our answer if we only keep the latter $$$c_i$$$.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Ah yes. Thanks! I missed that it's easier to look at that particular observation backwards too.

      → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

+1 I would also appreciate if someone could write down an additional solution sketch too.

→ Reply