valeriu's blog

By valeriu, 3 years ago, In English

103449A — Mountains

Author: Gheal

Solution
Code

103449B — Antigo

Author: valeriu

Solution
Code

103449C — Find Set

Author: Hidden for their safety

Solution
Code

103449D — Updating Inversions

Author: Gheal

Solution
Code 1 (SQRT decomposition)
Code 2 (Fenwick + Bitwise Trie)

103449E — Rubik String

Author: Gheal

Solution
Code 1 (DP)
Code 2 (Greedy)

103449F — àPaPdnarG

Author: tibinyte

Solution
Code

103449G — Xor Plains

Author: Gheal

Solution
Code

103449H — Autumn

Author: valeriu

Solution
Code
damn it!
  • Vote: I like it
  • +25
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Great contest! The problems are very interesting. Hope to participate again next time!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Thank you! Glad you liked our problems!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Problem F is very classic problem. The same problem as bzoj 5125 (a Chinese Online Judge). That's only the bad thing, i think.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Well that problem was more like an educational problem, its purpose being the understanding of divide and conquer optimisation rather than being a challenge. That's why we decided to give it to this training round and not in official rounds.

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

I can't understand, in problem H, why you are doing updates on rnode[v] not in lnode[v]?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It doesn't really matter, updates could've might as well be done on lnode. Really, it's correct either way because of the properties that trees imply, i.e. any segment bounded by the lnode and rnode of some vertex is completely included in another such segment if the node denoting the latter segment is an ancestor of the original vertex, otherwise these seents are completely disjoint. Therefore, any ancestor segment still includes both lnode and rnode (therefore as long as we always update a node strictly only rnode or lnode everything is correct)