*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!

- Square root decomposition — split the sequence into blocks of fixed size.
- Splitting objects (e.g. vertices) into light and heavy.
- Square root decomposition by the time of queries & rebuilding the structure.
- 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
- Strings — if the sum of lengths is $$$S$$$ then there are at most $$$\sqrt{S}$$$ distinct lengths.
- 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.

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

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

Knowing Mo's Algorithm finishes P2 and P3.

Also see this nice Atcoder problem.

Good problem: 1580C - Train Maintenance

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

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

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

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

Few good problems based on SQRT Decomposition on Queries:

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

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

Few good problems based on Mo's

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

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

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

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

I don't see why you would wanna use square root decomposition on this: https://www.codechef.com/problems/COW3E.

It can be solved in O(nm) time with 2D — prefix sums, square root decomposition would only make it more complicated..

Also, for good practice problems, USACO guide has a nice list of SQRT decomposition problems: https://usaco.guide/plat/sqrt?lang=cpp#set-a

Some really cool problems:

plug

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

`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

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

Another problem about diving block technique.

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

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.

CodeI 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

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!

Is there a place to submit P9?

https://codeforces.com/contest/487/problem/D

Another one ：

896E Welcome home, Chtholly

Subset sum, D Query

https://codeforces.com/problemset/problem/1491/H

A problem that uses the P6

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

Hint(Mo's algorithm with DSU rollbacks)

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

My submission — 135313235

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

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

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

I'm not aware of any such place :(

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