Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit4d6b7b7

Browse files
authored
Merge branch 'main' into main
2 parents9b8c5b6 +82a06ff commit4d6b7b7

File tree

8 files changed

+106
-9
lines changed

8 files changed

+106
-9
lines changed

‎mkdocs.yml

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -61,8 +61,7 @@ plugins:
6161
hooks:
6262
on_env:"hooks:on_env"
6363
-search
64-
-tags:
65-
tags_file:tags.md
64+
-tags
6665
-literate-nav:
6766
nav_file:navigation.md
6867
-git-revision-date-localized:

‎src/combinatorics/burnside.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -266,3 +266,8 @@ int solve(int n, int m) {
266266
return sum / s.size();
267267
}
268268
```
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/)

‎src/dynamic_programming/divide-and-conquer-dp.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -113,7 +113,7 @@ both!
113113
- [SPOJ - LARMY](https://www.spoj.com/problems/LARMY/)
114114
- [SPOJ - NKLEAVES](https://www.spoj.com/problems/NKLEAVES/)
115115
- [Timus - Bicolored Horses](https://acm.timus.ru/problem.aspx?space=1&num=1167)
116-
- [USACO - Circular Barn](http://www.usaco.org/index.php?page=viewproblem2&cpid=616)
116+
- [USACO - Circular Barn](https://usaco.org/index.php?page=viewproblem2&cpid=626)
117117
- [UVA - Arranging Heaps](https://onlinejudge.org/external/125/12524.pdf)
118118
- [UVA - Naming Babies](https://onlinejudge.org/external/125/12594.pdf)
119119

‎src/graph/topological-sort.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,8 +65,9 @@ vector<int> ans;
6565
voiddfs(int v) {
6666
visited[v] = true;
6767
for (int u : adj[v]) {
68-
if (!visited[u])
68+
if (!visited[u]) {
6969
dfs(u);
70+
}
7071
}
7172
ans.push_back(v);
7273
}

‎src/num_methods/ternary_search.md

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -57,6 +57,20 @@ If $f(x)$ takes integer parameter, the interval $[l, r]$ becomes discrete. Since
5757

5858
The difference occurs in the stopping criterion of the algorithm. Ternary search will have to stop when $(r - l) < 3$, because in that case we can no longer select $m_1$ and $m_2$ to be different from each other as well as from $l$ and $r$, and this can cause an infinite loop. Once $(r - l) < 3$, the remaining pool of candidate points $(l, l + 1, \ldots, r)$ needs to be checked to find the point which produces the maximum value $f(x)$.
5959

60+
### Golden section search
61+
62+
In some cases computing $f(x)$ may be quite slow, but reducing the number of iterations is infeasible due to precision issues. Fortunately, it is possible to compute $f(x)$ only once at each iteration (except the first one).
63+
64+
To see how to do this, let's revisit the selection method for $m_1$ and $m_2$. Suppose that we select $m_1$ and $m_2$ on $[l, r]$ in such a way that $\frac{r - l}{r - m_1} = \frac{r - l}{m_2 - l} = \varphi$ where $\varphi$ is some constant. In order to reduce the amount of computations, we want to select such $\varphi$ that on the next iteration one of the new evaluation points $m_1'$, $m_2'$ will coincide with either $m_1$ or $m_2$, so that we can reuse the already computed function value.
65+
66+
Now suppose that after the current iteration we set $l = m_1$. Then the point $m_1'$ will satisfy $\frac{r - m_1}{r - m_1'} = \varphi$. We want this point to coincide with $m_2$, meaning that $\frac{r - m_1}{r - m_2} = \varphi$.
67+
68+
Multiplying both sides of $\frac{r - m_1}{r - m_2} = \varphi$ by $\frac{r - m_2}{r - l}$ we obtain $\frac{r - m_1}{r - l} = \varphi\frac{r - m_2}{r - l}$. Note that $\frac{r - m_1}{r - l} = \frac{1}{\varphi}$ and $\frac{r - m_2}{r - l} = \frac{r - l + l - m_2}{r - l} = 1 - \frac{1}{\varphi}$. Substituting that and multiplying by $\varphi$, we obtain the following equation:
69+
70+
$\varphi^2 - \varphi - 1 = 0$
71+
72+
This is a well-known golden section equation. Solving it yields $\frac{1 \pm \sqrt{5}}{2}$. Since $\varphi$ must be positive, we obtain $\varphi = \frac{1 + \sqrt{5}}{2}$. By applying the same logic to the case when we set $r = m_2$ and want $m_2'$ to coincide with $m_1$, we obtain the same value of $\varphi$ as well. So, if we choose $m_1 = l + \frac{r - l}{1 + \varphi}$ and $m_2 = r - \frac{r - l}{1 + \varphi}$, on each iteration we can re-use one of the values $f(x)$ computed on the previous iteration.
73+
6074
## Implementation
6175

6276
```cpp
@@ -81,6 +95,7 @@ Here `eps` is in fact the absolute error (not taking into account errors due to
8195
Instead of the criterion `r - l > eps`, we can select a constant number of iterations as a stopping criterion. The number of iterations should be chosen to ensure the required accuracy. Typically, in most programming challenges the error limit is ${10}^{-6}$ and thus 200 - 300 iterations are sufficient. Also, the number of iterations doesn't depend on the values of $l$ and $r$, so the number of iterations corresponds to the required relative error.
8296

8397
## Practice Problems
98+
8499
-[Codeforces - New Bakery](https://codeforces.com/problemset/problem/1978/B)
85100
-[Codechef - Race time](https://www.codechef.com/problems/AMCS03)
86101
-[Hackerearth - Rescuer](https://www.hackerearth.com/problem/algorithm/rescuer-2d2495cb/)
@@ -95,5 +110,8 @@ Instead of the criterion `r - l > eps`, we can select a constant number of itera
95110
* [Codeforces - Devu and his Brother](https://codeforces.com/problemset/problem/439/D)
96111
* [Codechef - Is This JEE ](https://www.codechef.com/problems/ICM2003)
97112
* [Codeforces - Restorer Distance](https://codeforces.com/contest/1355/problem/E)
113+
* [TIMUS 1058 Chocolate](https://acm.timus.ru/problem.aspx?space=1&num=1058)
114+
* [TIMUS 1436 Billboard](https://acm.timus.ru/problem.aspx?space=1&num=1436)
115+
* [TIMUS 1451 Beerhouse Tale](https://acm.timus.ru/problem.aspx?space=1&num=1451)
98116
* [TIMUS 1719 Kill the Shaitan-Boss](https://acm.timus.ru/problem.aspx?space=1&num=1719)
99117
* [TIMUS 1913 Titan Ruins: Alignment of Forces](https://acm.timus.ru/problem.aspx?space=1&num=1913)

‎src/string/manacher.md

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,7 @@ Such an algorithm is slow, it can calculate the answer only in $O(n^2)$.
4949
The implementation of the trivial algorithm is:
5050

5151
```cpp
52-
vector<int>manacher_odd(string s) {
52+
vector<int>manacher_odd_trivial(string s) {
5353
int n = s.size();
5454
s = "$" + s + "^";
5555
vector<int> p(n + 2);
@@ -68,7 +68,7 @@ Terminal characters `$` and `^` were used to avoid dealing with ends of the stri
6868
6969
We describe the algorithm to find all the sub-palindromes with odd length, i. e. to calculate $d_{odd}[]$.
7070
71-
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.
71+
For fast calculation we'll maintain the **exclusiveborders $(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.
7272
7373
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:
7474
@@ -140,12 +140,12 @@ For calculating $d_{odd}[]$, we get the following code. Things to note:
140140
- The while loop denotes the trivial algorithm. We launch it irrespective of the value of $k$.
141141
- If the size of palindrome centered at $i$ is $x$, then $d_{odd}[i]$ stores $\frac{x+1}{2}$.
142142
143-
```cpp
143+
```{.cpp file=manacher_odd}
144144
vector<int> manacher_odd(string s) {
145145
int n = s.size();
146146
s = "$" + s + "^";
147147
vector<int> p(n + 2);
148-
int l =1, r = 1;
148+
int l =0, r = 1;
149149
for(int i = 1; i <= n; i++) {
150150
p[i] = max(0, min(r - i, p[l + (r - i)]));
151151
while(s[i - p[i]] == s[i + p[i]]) {

‎src/tags.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,4 +2,4 @@
22

33
This file contains a global index of all tags used on the pages.
44

5-
[TAGS]
5+
<!-- material/tags-->

‎test/test_manacher_odd.cpp

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
#include<bits/stdc++.h>
2+
usingnamespacestd;
3+
4+
#include"manacher_odd.h"
5+
6+
stringgetRandomString(size_t n,uint32_t seed,char minLetter='a',char maxLetter='b') {
7+
assert(minLetter <= maxLetter);
8+
constsize_t nLetters =static_cast<int>(maxLetter) -static_cast<int>(minLetter) +1;
9+
std::uniform_int_distribution<size_t>distr(0, nLetters -1);
10+
std::mt19937gen(seed);
11+
12+
string res;
13+
res.reserve(n);
14+
15+
for (size_t i =0; i < n; ++i)
16+
res.push_back('a' +distr(gen));
17+
18+
return res;
19+
}
20+
21+
booltestManacherOdd(const std::string &s) {
22+
constauto n = s.size();
23+
constauto d_odd =manacher_odd(s);
24+
25+
if (d_odd.size() != n)
26+
returnfalse;
27+
28+
constauto inRange = [&](size_t idx) {
29+
return idx >=0 && idx < n;
30+
};
31+
32+
for (size_t i =0; i < n; ++i) {
33+
if (d_odd[i] <0)
34+
returnfalse;
35+
for (int d =0; d < d_odd[i]; ++d) {
36+
constauto idx1 = i - d;
37+
constauto idx2 = i + d;
38+
39+
if (!inRange(idx1) || !inRange(idx2))
40+
returnfalse;
41+
if (s[idx1] != s[idx2])
42+
returnfalse;
43+
}
44+
45+
constauto idx1 = i - d_odd[i];
46+
constauto idx2 = i + d_odd[i];
47+
if (inRange(idx1) &&inRange(idx2) && s[idx1] == s[idx2])
48+
returnfalse;
49+
}
50+
51+
returntrue;
52+
}
53+
54+
intmain() {
55+
vector<string> testCases;
56+
57+
testCases.push_back("");
58+
for (size_t i =1; i <=25; ++i) {
59+
auto s = string{};
60+
s.resize(i,'a');
61+
testCases.push_back(move(s));
62+
}
63+
testCases.push_back("abba");
64+
testCases.push_back("abccbaasd");
65+
for (size_t n =9; n <=100; n +=10)
66+
testCases.push_back(getRandomString(n,/* seed*/ n,'a','d'));
67+
for (size_t n =7; n <=100; n +=10)
68+
testCases.push_back(getRandomString(n,/* seed*/ n));
69+
70+
for (constauto &s: testCases)
71+
assert(testManacherOdd(s));
72+
73+
return0;
74+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp