Merge branch 'cp-algorithms:main' into main

Proxihox · web-flow · commit a3db1b25e6c7 · 2025-01-27T08:48:49.000+05:30
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
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/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/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/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/test/test_planar_faces.cpp b/test/test_planar_faces.cpp
@@ -93,8 +93,34 @@ void test_cycle_with_chain() {
     assert(equal_cycles(faces[1], {2, 5, 4, 5, 2, 1, 0, 3}));
 }
 
+void test_ccw_angle() {
+    std::vector<Point> p = {
+        Point(0, 2),
+        Point(1, 3),
+        Point(0, 1),
+        Point(1, 0),
+        Point(-1, 0),
+        Point(-1, 3)
+    };
+
+    std::vector<std::vector<size_t>> adj = {
+        {1, 5},
+        {0, 2},
+        {1, 3},
+        {2, 4},
+        {3, 5},
+        {0, 4}
+    };
+
+    auto faces = find_faces(p, adj);
+    assert(faces.size() == 2u);
+    assert(equal_cycles(faces[0], {0, 1, 2, 3, 4, 5}));
+    assert(equal_cycles(faces[1], {5, 4, 3, 2, 1, 0}));
+}
+
 int main() {
     test_simple();
     test_degenerate();
     test_cycle_with_chain();
+    test_ccw_angle();
 }
