usernameson's blog

Question: When to avoid square root decomposition?
By usernameson, history, 8 years ago, In English

Are there any good rules of thumb on when a square root decomposition will be too slow? I suspect if we have an interval of length 105 and 3 × 105 queries a square root decomposition is too slow but this is only based on my attempts to solve http://codeforces.me/problemset/problem/765/F with a square root decomposition where I calculated the complexity of my algorithm to be and exceeding the time limit. In general if you are given an interval of length N and Q queries what sort of values of do you want in order to be confident that a square root decomposition will pass the time constraint? Also are there standard limits used in Codeforces deliberately set to prevent square root decomposition based approaches?

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

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

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

→ Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Is it really ever possible to be confident in square root decomposition?

Probably as long as complexity yield less than 200m operations you are fine.

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

    Thanks I will use 200m operations as a rule of thumb for future problems.

    → Reply