Codeforces Round #809 Editorial

Some stats about the round

Solutions

Problem A

Problem B

Problem C

Problem D1

Problem D2

Problem E

• 19 minutes ago, # ^ | To make the problem harder

• 17 minutes ago, # ^ | (copy-pasted from here) There is a two-pointers memory solution in D2 that we wanted to cut off. We decided it would be fine since all of the correct memory solutions (from testers, authors, and the coordinator, including in Python and Java) use less than 1/6 of that memory.

  • 3 minutes ago, # ^ | And this two-pointer method can be optimized to linear memory by getting the sqrt(ai) distinct values online(one by one). That is, instead of preprocess all the sqrt(n) values, we get only a current value for ai and get the next value one by one during the process of two-pointer, which costs linear memory since one ai have only one current value.

    • 1 minute ago, # ^ | You're right. Unfortunately none of the setters or testers came up with this idea :(

• 3 minutes ago, # ^ | If you use query lca methods (such as euler tour + sparse table) and use another sparse table to query lca of a range, you can achieve time per query.

• a moment ago, # ^ | I had the same solution: 164776738

• 10 minutes ago, # ^ | You don't release the memory from hold[start-1]. The memory is still reserved, it doesn't get released just because the vector became empty. You can use hold[start-1].shrink_to_fit() at the end, or swap it with an empty vector to release it.