123gjweq2's blog

By 123gjweq2, history, 5 weeks ago, In English

Hello everyone. If it took you a short time to implement C2 last contest, can you please share your solution? I'd really appreciate it.

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Here's mine, took a while to think of it but implementation was pretty smooth: 284569514

The strategy I used was:

  1. find some condition that must be true for all items (each person's first appearance in b must be before the first appearance of the person after them)
  2. find a data structure that can quickly check this condition for any single item, and process update queries (for each person there is a sorted set of the indices of their appearances in b)
  3. maintain a set of items for which the condition is/isn't true
  4. before processing an update, mark all items that may have changed as a result of this update (this strategy only works if only a few items can change validity per update)
  5. after processing the update, iterate through the items that may have changed, and insert/erase from the set in step 3 as needed
  6. output whether said set is full/empty

I believe a recent problem can be solved similarly

Another small trick I used was: if an edge case is hard to handle, consider mutating the input so it can't happen. To avoid dealing with the case where a person doesn't appear in b at all, I append a to the end of b, which doesn't affect the answer (edit: now that I think about it, it isn't that hard to handle, but committing to this while thinking of the algorithm made it easier to not have to keep track of it)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This does seem like a smooth way to do it. Thank you for explaining.