Errichto's blog

By Errichto, 6 months ago, In English

This is my 100th CF blog!

This is a list of techniques with $$$O(\sqrt n)$$$ time complexity. Watch the lecture https://youtu.be/BJhzd_VG61k, with timestamps!

  1. Square root decomposition — split the sequence into blocks of fixed size.
  2. Splitting objects (e.g. vertices) into light and heavy.
  3. Square root decomposition by the time of queries & rebuilding the structure.
  4. Mo's algorithm — processing queries in proper order and updating the answer by erasing/inserting new elements. https://cp-algorithms.com/data_structures/sqrt_decomposition.html
  5. Strings — if the sum of lengths is $$$S$$$ then there are at most $$$\sqrt{S}$$$ distinct lengths.
  6. Birthday paradox & baby-step giant-step. See P4 and P6 here, and see https://cp-algorithms.com/algebra/discrete-log.html.

P1. 398D - Instant Messanger
P2. 220B - Little Elephant and Array
P3. 86D - Powerful array (actually, skip this one because it's boring)
P4. Count triangles in a graph, i.e. cycles of size 3.
P5. Given $$$N$$$ strings with total length $$$S$$$, find a pair where one string is a substring of the other, in $$$O(S \cdot \sqrt S)$$$.

Homework (will be discussed in a second stream soon)
P6. You are given $$$N$$$ positive integers $$$a_1, a_2, \ldots, a_N$$$ and target value $$$X$$$. Check if there is subset with sum equal to $$$X$$$, in $$$O(X \cdot \sqrt S)$$$ where $$$S = \sum a_i$$$.
P7. 13E - Holes
P8. 455D - Serega and Fun
P9. You're given a sequence $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$). It describes a functional graph: there is a directed edge from $$$i$$$ to $$$a_i$$$. Handle updates U i x (change $$$a_i$$$ to $$$x$$$) and answer queries Q v — if we start in $$$v$$$ and keep following edges, after how many steps do we get to an already visited node?

And two problems from recent contests: 1580C - Train Maintenance and ABC 219 G Propagation.

Thanks to krismaz for letting me use his list of techniques and problems.

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

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

Are there any easy problems as well? These looks like out of reach.

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

    Problems involving sqrt decomposition tend to have a problem rating of >2000, so I highly doubt that there are easy problems for this topic.

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

Knowing Mo's Algorithm finishes P2 and P3.

»
6 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Also see this nice Atcoder problem.

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

Coolest sqrt decomposition ive seen so far: https://codeforces.com/problemset/problem/13/E

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

Few good problems based on the Heavy set — Light set based SQRT Decomposition:

  1. https://www.hackerrank.com/contests/worldcupsemifinals/challenges/wccity/problem

  2. https://www.codechef.com/problems/KOL15C

Few good problems based on SQRT Decomposition on Queries:

  1. https://codeforces.com/contest/342/problem/E (Standard Centroid Decomposition Problem, but can also be solved using Query SQRT Decomposition)

  2. https://www.codechef.com/problems/COW3E

Few good problems based on Mo's

  1. https://codeforces.com/contest/86/problem/D

  2. https://codeforces.com/problemset/problem/940/F (Mo's with Updates)

  3. https://www.spoj.com/problems/XXXXXXXX/ (Mo's with Updates)

  4. https://codeforces.com/contest/576/problem/C

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

Some really cool problems:

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

plug

heavy/light example too: 1545F - AquaMoon and Potatoes

»
6 months ago, # |
Rev. 2   Vote: I like it -48 Vote: I do not like it

Strings — if the sum of lengths is S then there are at most sqrt(S) distinct lengths

i think it is wrong, for example:

S = 15 the strings can be of length: 1, 2, 3, 4, 5

there are 5 distinct lengths but $$$\sqrt 15$$$ is less than 4

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +50 Vote: I do not like it

    It's just the magnitude. The exact limit should be $$$\sqrt{2 * S}$$$.

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

problem on square root heuristic, (not sure if is under square root decomposition, but we do decompose into square root buckets)
https://www.codechef.com/JAN19A/problems/PARRTY
codeforces(2100 rated): Time to Raid Cowavans
codeforces(2400 rated): Mr. Kitayuta's Colorful Graph

»
6 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Update : I managed to find the bug and remove WA(was overcounting) but now I am getting TLE on test 63. I also tried various block sizes from 300-700 and it gave TLE on various tests. I am sure that my add,delete and update functions work in O(B) time. I don't know how to remove TLE now. Also changed set to unordered set but that too failed :(. Errichto if you can shed some light on how to select B and comment on if I have applied heavy/light trick correctly or not..then that would be helpful :) Thanks and sorry for tagging.

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

    I don't fully understand your code. For example, you sometimes check deg > B and sometimes deg >= B.

    Sets and unordered sets are slow. Change heavy to vector type. Let's see how to handle erasing:

    1) The first two heavy[x].erase(...) you can just skip. Whenever iterating heavy neighbours for(int x : heavy[u]){ in upd(u) function, remove all $$$x$$$ with too small degree.

    2) The other two occurrences heavy[v].erase(u); and heavy[u].erase(v) can be done linearly by iterating the vector. You might want to erase the small-degree elements here as well.

    Alternatively, see the author implementation 5926635

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

      Thank you for your insights! However I tried resubmitting the same code on GNU C++17 and GNU C++14 and it gave AC. Earlier I was submitting it on GNU C++17 (64) (Idk why it did not work here..but it took nearly 4 hours to figure that switching languages was optimal). Now I will try to implement the same using your idea to get even faster runtime. Thanks!

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

Is there a place to submit P9?

»
6 months ago, # |
Rev. 4   Vote: I like it +13 Vote: I do not like it
»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

https://www.codechef.com/problems/GERALD07

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

Anyone getting TLE on P1? I'm updating light and heavy nodes and getting TLE on test 32

My submission — 135313235

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

    I don't know if this problem can be accepted with sets. See my discussion with DontLookBack a few comments above.

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

      Thanks! changing the sets to vectors instantly gave AC, I forgot that the size of the heavy vector would also be small so deleting would be fast

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

Is there any place I can submit P4 (and other problems without an attached question)

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

A really nice recent problem directly based on this blog: 1619H - Permutation and Queries