Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

lrvideckis's blog

O(n),O(1) lca/rmq; not method of 4 russians
By lrvideckis, history, 6 months ago, In English

I came across this paper

On Finding Lowest Common Ancestors: Simplification and Parallelization by Baruch Schieber, Uzi Vishkin April, 1987

so naturally I tried to code golf it

lca https://judge.yosupo.jp/submission/188189

rmq https://judge.yosupo.jp/submission/188190

edit: minor golf

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

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Cool! This algorithm seems to be almost the same size of the one described here, although maybe a bit slower.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    rip

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    although looking at the test cases, this approach does worse on the small width query where the usual 4-russians approach would have an advantage: you hit the case with less operations

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    on cses rmq: your implementation: .10s, my implementation: 0.12s

    → Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    revisiting this, I code golfed it another way, and now it is a bit faster

    https://judge.yosupo.jp/submission/222428

    → Reply
»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Kudos for a clean, neat code and usage of C++20 features!

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply