ritik26's blog

Binary Lifting
By ritik26, history, 3 months ago, In English

I am learning Binary Lifting. Can someone suggest some good problems?

How to identify if a problems requires Binary Lifting technique to solve? From what I learned is that the every node must have one outdegree. Are there more?

Thank you for your time !!

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

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

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

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

Try cses problems. I remembered there were good binary lifting problems.

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

binary lifting is useful for LCA queries, maybe you can solve LCA problems, there are some good LCA problems on cf

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

These two articles from USACO Guide and this blog entry here, for something more advanced are pretty good for a start.

In terms of your other question, what you want to do is to either find a tree or a tree like structure you can do binary lifting on, or you can even do it on a functional graph just as well.

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

This recent problem Shortest Distances 101 from Codechef Starters is the best problem on Binary Lifting for beginners (mostly because everywhere else it's taught, it's clubbed with Trees, LCA, tin, tout, etc, forcing you to learn a lot of new things at the same time). However, this problem only deals with binary lifting on array, so it's easy to visualize the actual potential of what Binary Lifting can do.

Another good problem on Binary Lifting on arrays is ABC367E: Permute K times from a recent Atcoder contest.

If you think you understand Binary Lifting, try implementing an RMQ data structure for solving CSES: Static Range Minimum Queries using only Binary Lifting.

Sample Submission

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

1175E - Minimal Segment Cover

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

After you've solved some simple problems from CSES and USACO Guide you could try this (the problem not the subtasks). You might not loove the UI but this problem is quite good.

It isn't immediately obvious how you would use binary lifting. If you are stuck and need help feel free to message me.

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

Here are some good problems from codeforces problemset that can be solved using binary lifting

  1. 191C — Fools and Roads

  2. 1328E — Tree Queries

  3. 1702G2 — Passable Paths

  4. 832D — Misha, Grisha and Underground

→ Reply