Merge branch 'main' into patch-1

adamant-pwn · web-flow · commit 14ba8cc2b74e · 2025-03-24T20:52:44.000+01:00
diff --git a/mkdocs.yml b/mkdocs.yml
@@ -29,7 +29,7 @@ theme:
 repo_url: https://github.com/cp-algorithms/cp-algorithms
 repo_name: cp-algorithms/cp-algorithms
 edit_uri: edit/main/src/
-copyright: Text is available under the <a href="https://github.com/cp-algorithms/cp-algorithms/blob/main/LICENSE">Creative Commons Attribution Share Alike 4.0 International</a> License<br/>Copyright &copy; 2014 - 2024 by <a href="https://github.com/cp-algorithms/cp-algorithms/graphs/contributors">cp-algorithms contributors</a>
+copyright: Text is available under the <a href="https://github.com/cp-algorithms/cp-algorithms/blob/main/LICENSE">Creative Commons Attribution Share Alike 4.0 International</a> License<br/>Copyright &copy; 2014 - 2025 by <a href="https://github.com/cp-algorithms/cp-algorithms/graphs/contributors">cp-algorithms contributors</a>
 extra_javascript:
   - javascript/config.js
   - https://cdnjs.cloudflare.com/polyfill/v3/polyfill.min.js?features=es6
@@ -61,8 +61,7 @@ plugins:
       hooks:
           on_env: "hooks:on_env"
   - search
-  - tags:
-      tags_file: tags.md
+  - tags
   - literate-nav:
       nav_file: navigation.md
   - git-revision-date-localized:
diff --git a/src/algebra/bit-manipulation.md b/src/algebra/bit-manipulation.md
@@ -207,7 +207,7 @@ We can see that the all the columns except the leftmost have $4$ (i.e. $2^2$) se
 With the new knowledge in hand we can come up with the following algorithm:
 
 - Find the highest power of $2$ that is lesser than or equal to the given number. Let this number be $x$.
-- Calculate the number of set bits from $1$ to $2^x - 1$ by using the formua $x \cdot 2^{x-1}$.
+- Calculate the number of set bits from $1$ to $2^x - 1$ by using the formula $x \cdot 2^{x-1}$.
 - Count the no. of set bits in the most significant bit from $2^x$ to $n$ and add it.
 - Subtract $2^x$ from $n$ and repeat the above steps using the new $n$.
 
diff --git a/src/algebra/fft.md b/src/algebra/fft.md
@@ -97,7 +97,7 @@ It is easy to see that
 
 $$A(x) = A_0(x^2) + x A_1(x^2).$$
 
-The polynomials $A_0$ and $A_1$ are only half as much coefficients as the polynomial $A$.
+The polynomials $A_0$ and $A_1$ have only half as many coefficients as the polynomial $A$.
 If we can compute the $\text{DFT}(A)$ in linear time using $\text{DFT}(A_0)$ and $\text{DFT}(A_1)$, then we get the recurrence $T_{\text{DFT}}(n) = 2 T_{\text{DFT}}\left(\frac{n}{2}\right) + O(n)$ for the time complexity, which results in $T_{\text{DFT}}(n) = O(n \log n)$ by the **master theorem**.
 
 Let's learn how we can accomplish that.
diff --git a/src/algebra/phi-function.md b/src/algebra/phi-function.md
@@ -73,7 +73,7 @@ int phi(int n) {
 
 ## Euler totient function from $1$ to $n$ in $O(n \log\log{n})$ { #etf_1_to_n data-toc-label="Euler totient function from 1 to n in <script type=\"math/tex\">O(n log log n)</script>" }
 
-If we need all all the totient of all numbers between $1$ and $n$, then factorizing all $n$ numbers is not efficient.
+If we need the totient of all numbers between $1$ and $n$, then factorizing all $n$ numbers is not efficient.
 We can use the same idea as the [Sieve of Eratosthenes](sieve-of-eratosthenes.md).
 It is still based on the property shown above, but instead of updating the temporary result for each prime factor for each number, we find all prime numbers and for each one update the temporary results of all numbers that are divisible by that prime number.
 
diff --git a/src/combinatorics/burnside.md b/src/combinatorics/burnside.md
@@ -266,3 +266,8 @@ int solve(int n, int m) {
     return sum / s.size();
 }
 ```
+## Practice Problems
+* [CSES - Counting Necklaces](https://cses.fi/problemset/task/2209)
+* [CSES - Counting Grids](https://cses.fi/problemset/task/2210)
+* [Codeforces - Buildings](https://codeforces.com/gym/101873/problem/B)
+* [CS Academy - Cube Coloring](https://csacademy.com/contest/beta-round-8/task/cube-coloring/)
diff --git a/src/data_structures/sqrt_decomposition.md b/src/data_structures/sqrt_decomposition.md
@@ -120,7 +120,7 @@ But in a lot of situations this method has advantages.
 During a normal sqrt decomposition, we have to precompute the answers for each block, and merge them during answering queries.
 In some problems this merging step can be quite problematic.
 E.g. when each queries asks to find the **mode** of its range (the number that appears the most often).
-For this each block would have to store the count of each number in it in some sort of data structure, and we cannot longer perform the merge step fast enough any more.
+For this each block would have to store the count of each number in it in some sort of data structure, and we can no longer perform the merge step fast enough any more.
 **Mo's algorithm** uses a completely different approach, that can answer these kind of queries fast, because it only keeps track of one data structure, and the only operations with it are easy and fast.
 
 The idea is to answer the queries in a special order based on the indices.
diff --git a/src/dynamic_programming/divide-and-conquer-dp.md b/src/dynamic_programming/divide-and-conquer-dp.md
@@ -113,7 +113,7 @@ both!
 - [SPOJ - LARMY](https://www.spoj.com/problems/LARMY/)
 - [SPOJ - NKLEAVES](https://www.spoj.com/problems/NKLEAVES/)
 - [Timus - Bicolored Horses](https://acm.timus.ru/problem.aspx?space=1&num=1167)
-- [USACO - Circular Barn](http://www.usaco.org/index.php?page=viewproblem2&cpid=616)
+- [USACO - Circular Barn](https://usaco.org/index.php?page=viewproblem2&cpid=626)
 - [UVA - Arranging Heaps](https://onlinejudge.org/external/125/12524.pdf)
 - [UVA - Naming Babies](https://onlinejudge.org/external/125/12594.pdf)
 
diff --git a/src/dynamic_programming/intro-to-dp.md b/src/dynamic_programming/intro-to-dp.md
@@ -7,7 +7,7 @@ tags:
 
 The essence of dynamic programming is to avoid repeated calculation.  Often, dynamic programming problems are naturally solvable by recursion. In such cases, it's easiest to write the recursive solution, then save repeated states in a lookup table. This process is known as top-down dynamic programming with memoization. That's read "memoization" (like we are writing in a memo pad) not memorization.
 
-One of the most basic, classic examples of this process is the fibonacci sequence. It's recursive formulation is $f(n) = f(n-1) + f(n-2)$ where $n \ge 2$ and $f(0)=0$ and $f(1)=1$. In C++, this would be expressed as:
+One of the most basic, classic examples of this process is the fibonacci sequence. Its recursive formulation is $f(n) = f(n-1) + f(n-2)$ where $n \ge 2$ and $f(0)=0$ and $f(1)=1$. In C++, this would be expressed as:
 
 ```cpp
 int f(int n) {
@@ -25,7 +25,7 @@ Our recursive function currently solves fibonacci in exponential time. This mean
 
 To increase the speed, we recognize that the number of subproblems is only $O(n)$. That is, in order to calculate $f(n)$ we only need to know $f(n-1),f(n-2), \dots ,f(0)$. Therefore, instead of recalculating these subproblems, we solve them once and then save the result in a lookup table.  Subsequent calls will use this lookup table and immediately return a result, thus eliminating exponential work! 
 
-Each recursive call will check against a lookup table to see if the value has been calculated. This is done in $O(1)$ time.  If we have previously calcuated it, return the result, otherwise, we calculate the function normally. The overall runtime is $O(n)$. This is an enormous improvement over our previous exponential time algorithm!
+Each recursive call will check against a lookup table to see if the value has been calculated. This is done in $O(1)$ time.  If we have previously calculated it, return the result, otherwise, we calculate the function normally. The overall runtime is $O(n)$. This is an enormous improvement over our previous exponential time algorithm!
 
 ```cpp
 const int MAXN = 100;
@@ -88,7 +88,7 @@ This approach is called top-down, as we can call the function with a query value
 Until now you've only seen top-down dynamic programming with memoization. However, we can also solve problems with bottom-up dynamic programming. 
 Bottom-up is exactly the opposite of top-down, you start at the bottom (base cases of the recursion), and extend it to more and more values.
 
-To create a bottom-up approach for fibonacci numbers, we initilize the base cases in an array. Then, we simply use the recursive definition on array:
+To create a bottom-up approach for fibonacci numbers, we initialize the base cases in an array. Then, we simply use the recursive definition on array:
 
 ```cpp
 const int MAXN = 100;
@@ -107,7 +107,7 @@ Of course, as written, this is a bit silly for two reasons:
 Firstly, we do repeated work if we call the function more than once. 
 Secondly, we only need to use the two previous values to calculate the current element. Therefore, we can reduce our memory from $O(n)$ to $O(1)$. 
 
-An example of a bottom-up dynamic programming solution for fibonacci which uses $O(1)$ might be:
+An example of a bottom-up dynamic programming solution for fibonacci which uses $O(1)$ memory might be:
 
 ```cpp
 const int MAX_SAVE = 3;
diff --git a/src/geometry/planar.md b/src/geometry/planar.md
@@ -125,20 +125,14 @@ std::vector<std::vector<size_t>> find_faces(std::vector<Point> vertices, std::ve
                 e = e1;
             }
             std::reverse(face.begin(), face.end());
-            int sign = 0;
-            for (size_t j = 0; j < face.size(); j++) {
-                size_t j1 = (j + 1) % face.size();
-                size_t j2 = (j + 2) % face.size();
-                int64_t val = vertices[face[j]].cross(vertices[face[j1]], vertices[face[j2]]);
-                if (val > 0) {
-                    sign = 1;
-                    break;
-                } else if (val < 0) {
-                    sign = -1;
-                    break;
-                }
+            Point p1 = vertices[face[0]];
+            __int128 sum = 0;
+            for (int j = 0; j < face.size(); ++j) {
+                Point p2 = vertices[face[j]];
+                Point p3 = vertices[face[(j + 1) % face.size()]];
+                sum += (p2 - p1).cross(p3 - p2);
             }
-            if (sign <= 0) {
+            if (sum <= 0) {
                 faces.insert(faces.begin(), face);
             } else {
                 faces.emplace_back(face);
diff --git a/src/graph/edge_vertex_connectivity.md b/src/graph/edge_vertex_connectivity.md
@@ -39,7 +39,7 @@ It is clear, that the vertex connectivity of a graph is equal to the minimal siz
 
 ### The Whitney inequalities
 
-The **Whitney inequalities** (1932) gives a relation between the edge connectivity $\lambda$, the vertex connectivity $\kappa$ and the smallest degree of the vertices $\delta$:
+The **Whitney inequalities** (1932) gives a relation between the edge connectivity $\lambda$, the vertex connectivity $\kappa$, and the minimum degree of any vertex in the graph $\delta$:
 
 $$\kappa \le \lambda \le \delta$$
 
@@ -77,7 +77,7 @@ Especially the algorithm will run pretty fast for random graphs.
 
 ### Special algorithm for edge connectivity 
 
-The task of finding the edge connectivity if equal to the task of finding the **global minimum cut**.
+The task of finding the edge connectivity is equal to the task of finding the **global minimum cut**.
 
 Special algorithms have been developed for this task.
 One of them is the Stoer-Wagner algorithm, which works in $O(V^3)$ or $O(V E)$ time.
diff --git a/src/graph/hld.md b/src/graph/hld.md
@@ -183,3 +183,8 @@ int query(int a, int b) {
 ## Practice problems
 
 - [SPOJ - QTREE - Query on a tree](https://www.spoj.com/problems/QTREE/)
+- [CSES - Path Queries II](https://cses.fi/problemset/task/2134)
+- [Codeforces - Subway Lines](https://codeforces.com/gym/101908/problem/L)
+- [Codeforces - Tree Queries](https://codeforces.com/contest/1254/problem/D)
+- [Codeforces - Tree or not Tree](https://codeforces.com/contest/117/problem/E)
+- [Codeforces - The Tree](https://codeforces.com/contest/1017/problem/G)
diff --git a/src/graph/topological-sort.md b/src/graph/topological-sort.md
@@ -26,14 +26,14 @@ The example graph also has multiple topological orders, a second topological ord
 
 A Topological order may **not exist** at all.
 It only exists, if the directed graph contains no cycles.
-Otherwise because there is a contradiction: if there is a cycle containing the vertices $a$ and $b$, then $a$ needs to have a smaller index than $b$ (since you can reach $b$ from $a$) and also a bigger one (as you can reach $a$ from $b$).
+Otherwise, there is a contradiction: if there is a cycle containing the vertices $a$ and $b$, then $a$ needs to have a smaller index than $b$ (since you can reach $b$ from $a$) and also a bigger one (as you can reach $a$ from $b$).
 The algorithm described in this article also shows by construction, that every acyclic directed graph contains at least one topological order.
 
-A common problem in which topological sorting occurs is the following. There are $n$ variables with unknown values. For some variables we know that one of them is less than the other. You have to check whether these constraints are contradictory, and if not, output the variables in ascending order (if several answers are possible, output any of them). It is easy to notice that this is exactly the problem of finding topological order of a graph with $n$ vertices.
+A common problem in which topological sorting occurs is the following. There are $n$ variables with unknown values. For some variables, we know that one of them is less than the other. You have to check whether these constraints are contradictory, and if not, output the variables in ascending order (if several answers are possible, output any of them). It is easy to notice that this is exactly the problem of finding the topological order of a graph with $n$ vertices.
 
 ## The Algorithm
 
-To solve this problem we will use [depth-first search](depth-first-search.md).
+To solve this problem, we will use [depth-first search](depth-first-search.md).
 
 Let's assume that the graph is acyclic. What does the depth-first search do?
 
@@ -65,8 +65,9 @@ vector<int> ans;
 void dfs(int v) {
     visited[v] = true;
     for (int u : adj[v]) {
-        if (!visited[u])
+        if (!visited[u]) {
             dfs(u);
+        }
     }
     ans.push_back(v);
 }
diff --git a/src/num_methods/binary_search.md b/src/num_methods/binary_search.md
@@ -82,10 +82,10 @@ f(0) \leq f(1) \leq \dots \leq f(n-1).
 $$
 
 The binary search, the way it is described above, finds the partition of the array by the predicate $f(M)$, holding the boolean value of $k < A_M$ expression.
-It is possible to use arbitrary monotonous predicate instead of $k < A_M$. It is particularly useful when the computation of $f(k)$ is requires too much time to actually compute it for every possible value.
+It is possible to use arbitrary monotonous predicate instead of $k < A_M$. It is particularly useful when the computation of $f(k)$ requires too much time to actually compute it for every possible value.
 In other words, binary search finds the unique index $L$ such that $f(L) = 0$ and $f(R)=f(L+1)=1$ if such a _transition point_ exists, or gives us $L = n-1$ if $f(0) = \dots = f(n-1) = 0$ or $L = -1$ if $f(0) = \dots = f(n-1) = 1$.
 
-Proof of correctness supposing a transition point exists, that is $f(0)=0$ and $f(n-1)=1$: The implementation maintaints the _loop invariant_ $f(l)=0, f(r)=1$. When $r - l > 1$, the choice of $m$ means $r-l$ will always decrease. The loop terminates when $r - l = 1$, giving us our desired transition point.
+Proof of correctness supposing a transition point exists, that is $f(0)=0$ and $f(n-1)=1$: The implementation maintains the _loop invariant_ $f(l)=0, f(r)=1$. When $r - l > 1$, the choice of $m$ means $r-l$ will always decrease. The loop terminates when $r - l = 1$, giving us our desired transition point.
 
 ```cpp
 ... // f(i) is a boolean function such that f(0) <= ... <= f(n-1)
diff --git a/src/others/tortoise_and_hare.md b/src/others/tortoise_and_hare.md
@@ -110,5 +110,6 @@ And since we let the slow pointer start at the start of the linked list, after $
 
 # Problems:
 - [Linked List Cycle (EASY)](https://leetcode.com/problems/linked-list-cycle/)
+- [Happy Number (Easy)](https://leetcode.com/problems/happy-number/)
 - [Find the Duplicate Number (Medium)](https://leetcode.com/problems/find-the-duplicate-number/)
 
diff --git a/src/sequences/longest_increasing_subsequence.md b/src/sequences/longest_increasing_subsequence.md
@@ -300,7 +300,7 @@ This is in fact nearly the same problem.
 Only now it is allowed to use identical numbers in the subsequence.
 
 The solution is essentially also nearly the same.
-We just have to change the inequality signs, and make a slightly modification to the binary search.
+We just have to change the inequality signs, and make a slight modification to the binary search.
 
 ### Number of longest increasing subsequences
 
diff --git a/src/string/manacher.md b/src/string/manacher.md
@@ -49,7 +49,7 @@ Such an algorithm is slow, it can calculate the answer only in $O(n^2)$.
 The implementation of the trivial algorithm is:
 
 ```cpp
-vector<int> manacher_odd(string s) {
+vector<int> manacher_odd_trivial(string s) {
     int n = s.size();
     s = "$" + s + "^";
     vector<int> p(n + 2);
@@ -68,7 +68,7 @@ Terminal characters `$` and `^` were used to avoid dealing with ends of the stri
 
 We describe the algorithm to find all the sub-palindromes with odd length, i. e. to calculate $d_{odd}[]$.
 
-For fast calculation we'll maintain the **borders $(l, r)$** of the rightmost found (sub-)palindrome (i. e. the current rightmost (sub-)palindrome is $s[l+1] s[l+2] \dots s[r-1]$). Initially we set $l = 0, r = 1$, which corresponds to the empty string.
+For fast calculation we'll maintain the **exclusive borders $(l, r)$** of the rightmost found (sub-)palindrome (i. e. the current rightmost (sub-)palindrome is $s[l+1] s[l+2] \dots s[r-1]$). Initially we set $l = 0, r = 1$, which corresponds to the empty string.
 
 So, we want to calculate $d_{odd}[i]$ for the next $i$, and all the previous values in $d_{odd}[]$ have been already calculated. We do the following:
 
@@ -140,12 +140,12 @@ For calculating $d_{odd}[]$, we get the following code. Things to note:
  - The while loop denotes the trivial algorithm. We launch it irrespective of the value of $k$.
  - If the size of palindrome centered at $i$ is $x$, then $d_{odd}[i]$ stores $\frac{x+1}{2}$.
 
-```cpp
+```{.cpp file=manacher_odd}
 vector<int> manacher_odd(string s) {
     int n = s.size();
     s = "$" + s + "^";
     vector<int> p(n + 2);
-    int l = 1, r = 1;
+    int l = 0, r = 1;
     for(int i = 1; i <= n; i++) {
         p[i] = max(0, min(r - i, p[l + (r - i)]));
         while(s[i - p[i]] == s[i + p[i]]) {
diff --git a/src/tags.md b/src/tags.md
@@ -2,4 +2,4 @@
 
 This file contains a global index of all tags used on the pages.
 
-[TAGS]
+<!-- material/tags -->
diff --git a/test/test_manacher_odd.cpp b/test/test_manacher_odd.cpp
@@ -0,0 +1,74 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+#include "manacher_odd.h"
+
+string getRandomString(size_t n, uint32_t seed, char minLetter='a', char maxLetter='b') {
+    assert(minLetter <= maxLetter);
+    const size_t nLetters = static_cast<int>(maxLetter) - static_cast<int>(minLetter) + 1;
+    std::uniform_int_distribution<size_t> distr(0, nLetters - 1);
+    std::mt19937 gen(seed);
+
+    string res;
+    res.reserve(n);
+
+    for (size_t i = 0; i < n; ++i)
+        res.push_back('a' + distr(gen));
+
+    return res;
+}
+
+bool testManacherOdd(const std::string &s) {
+    const auto n = s.size();
+    const auto d_odd = manacher_odd(s);
+
+    if (d_odd.size() != n)
+        return false;
+
+    const auto inRange = [&](size_t idx) {
+        return idx >= 0 && idx < n;
+    };
+
+    for (size_t i = 0; i < n; ++i) {
+        if (d_odd[i] < 0)
+            return false;
+        for (int d = 0; d < d_odd[i]; ++d) {
+            const auto idx1 = i - d;
+            const auto idx2 = i + d;
+
+            if (!inRange(idx1) || !inRange(idx2))
+                return false;
+            if (s[idx1] != s[idx2])
+                return false;
+        }
+
+        const auto idx1 = i - d_odd[i];
+        const auto idx2 = i + d_odd[i];
+        if (inRange(idx1) && inRange(idx2) && s[idx1] == s[idx2])
+            return false;
+    }
+
+    return true;
+}
+
+int main() {
+    vector<string> testCases;
+
+    testCases.push_back("");
+    for (size_t i = 1; i <= 25; ++i) {
+        auto s = string{};
+        s.resize(i, 'a');
+        testCases.push_back(move(s));
+    }
+    testCases.push_back("abba");
+    testCases.push_back("abccbaasd");
+    for (size_t n = 9; n <= 100; n += 10)
+        testCases.push_back(getRandomString(n, /* seed */ n, 'a', 'd'));
+    for (size_t n = 7; n <= 100; n += 10)
+        testCases.push_back(getRandomString(n, /* seed */ n));
+
+    for (const auto &s: testCases)
+        assert(testManacherOdd(s));
+
+    return 0;
+}
diff --git a/test/test_planar_faces.cpp b/test/test_planar_faces.cpp

Original file line number	Diff line number	Diff line change
`@@ -266,3 +266,8 @@ int solve(int n, int m) {`
`266`	`266`	`return sum / s.size();`
`267`	`267`	`}`
`268`	`268`	```
	`269`	`+## Practice Problems`
	`270`	`+* [CSES - Counting Necklaces](https://cses.fi/problemset/task/2209)`
	`271`	`+* [CSES - Counting Grids](https://cses.fi/problemset/task/2210)`
	`272`	`+* [Codeforces - Buildings](https://codeforces.com/gym/101873/problem/B)`
	`273`	`+* [CS Academy - Cube Coloring](https://csacademy.com/contest/beta-round-8/task/cube-coloring/)`
Original file line number	Diff line number	Diff line change
`@@ -2,4 +2,4 @@`
`2`	`2`
`3`	`3`	`This file contains a global index of all tags used on the pages.`
`4`	`4`
`5`		`-[TAGS]`
	`5`	`+<!-- material/tags -->`