codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

392.md (26110B)


      1 Source: https://codeforces.com/blog/entry/83942
      2 
      3 Yesterday I saw [this](https://codeforces.com/blog/entry/83811) blog and thought that one bad editorial is better than zero good ones, right? So, enjoy it!
      4 
      5 Here are links to contests: [Div. 1](https://codeforces.com/contest/392), [Div. 2](https://codeforces.com/contest/393)
      6 
      7 Div2A
      8 
      9 **Editorial**
     10 
     11 ### [393A - Nineteen](/contest/393/problem/A "Codeforces Round 230 (Div. 2)")
     12 
     13 Looking at examples and thinking about different cases lead to the idea that the best result would be to build a string which starts with $nineteenineteenineteen...$. The first word $nineteen$ requires 3 letters $n$, 3 letters $e$, 1 letter $i$ and 1 letter $t$. Every next occurrence of $nineteen$ requires the same set of letters, but we need only two letters $n$ for each new word. In other words, we can start with $n$, and then every word will need exactly two extra $n$-s. Let $cnt[c]$ denote the number of characters $c$ in the string. Then the answer is $min\left(\left\lfloor\frac{cnt[n] - 1}{2}\right\rfloor, \,\left\lfloor\frac{cnt[e]}{3}\right\rfloor,\, cnt[i],\, cnt[t]\right)$. (In theory this minimum could be $-\left\lfloor\frac{1}{2}\right\rfloor$, but in C++ it is equal to zero, so everything works fine)
     14 
     15 **Code**
     16 
     17 ```
     18 #include <bits/stdc++.h>
     19 
     20 using namespace std;
     21 
     22 int main() {
     23     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
     24 
     25     string s;
     26     cin >> s;
     27     map<char, int> cnt;
     28     for (auto c : s) {
     29         cnt[c]++;
     30     }
     31     cout << min({(cnt['n'] - 1) / 2, cnt['e'] / 3, cnt['i'], cnt['t']}) << '\n';
     32 
     33     return 0;
     34 }
     35 ```
     36 
     37 Div2B
     38 
     39 **Editorial**
     40 
     41 ### [393B - Три матрицы](/contest/393/problem/B "Codeforces Round 230 (Div. 2)")
     42 
     43 We can write this system of equations, using the fact that $B[j][i] = -B[i][j]$ and $A[i][j] = A[j][i]$
     44 
     45 $ \begin{cases} A[i][j] + B[i][j] = W[i][j]\\ A[j][i] + B[j][i] = W[j][i] \end{cases} \quad\Rightarrow\quad \begin{cases} A[i][j] + B[i][j] = W[i][j]\\ A[i][j] - B[i][j] = W[j][i] \end{cases} $
     46 
     47 From that, it is easy to conclude that $A[i][j] = \frac{W[i][j] + W[j][i]}{2}$ and $B[i][j] = \frac{W[i][j] - W[j][i]}{2}$.
     48 
     49 By the way, there is some interesting math connected to this problem: [link](https://en.wikipedia.org/wiki/Symmetric_matrix#Decomposition_into_symmetric_and_skew-symmetric)
     50 
     51 **Code**
     52 
     53 ```
     54 #include <bits/stdc++.h>
     55 
     56 using namespace std;
     57 
     58 int main() {
     59     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
     60 
     61     int n;
     62     cin >> n;
     63     vector<vector<double>> w(n, vector<double>(n));
     64     for (int i = 0; i < n; ++i) {
     65         for (int j = 0; j < n; ++j) {
     66             cin >> w[i][j];
     67         }
     68     }
     69 
     70     vector<vector<double>> a(n, vector<double>(n));
     71     vector<vector<double>> b(n, vector<double>(n));
     72 
     73     for (int i = 0; i < n; ++i) {
     74         for (int j = 0; j < n; ++j) {
     75             a[i][j] = (w[i][j] + w[j][i]) / 2;
     76             b[i][j] = (w[i][j] - w[j][i]) / 2;
     77         }
     78     }
     79 
     80     for (int i = 0; i < n; ++i) {
     81         for (int j = 0; j < n; ++j) {
     82             cout << a[i][j] << ' ';
     83         }
     84         cout << '\n';
     85     }
     86 
     87     for (int i = 0; i < n; ++i) {
     88         for (int j = 0; j < n; ++j) {
     89             cout << b[i][j] << ' ';
     90         }
     91         cout << '\n';
     92     }
     93 
     94     return 0;
     95 }
     96 ```
     97 
     98 Div2C/Div1A
     99 
    100 **Editorial**
    101 
    102 ### [392A - Заблокированные точки](/contest/392/problem/A "Codeforces Round 230 (Div. 1)")
    103 
    104 Let's look at all pairs of neighboring points such that one of them is special and the other one is not. I claim that it is necessary and sufficient to block at least one point in every such pair
    105 
    106 **Proof**
    107 
    108 Necessity is obvious. Let's prove sufficiency. Assume that we blocked at least one point in each pair, but there are two points $A$ and $B$ such that $A$ is special, $B$ is not and they are 4-connected. Then look at the path between these points. It starts with a special point and ends with non-special. That means that there are two adjacent points in this path such that the first one is special and the second one is not. But it contradicts our statement that we blocked at least one of the points in each pair.
    109 
    110 Now let's look at these pairs. For simplicity, we will look at only $\frac18$-th of a circle.
    111 
    112 **This one**
    113 
    114 ![](/predownloaded/7d/61/7d611f05796069d4faf192020d1d5ddf25c32603.png)
    115 
    116 And let's draw all horizontal pairs with a point inside the selected piece.
    117 
    118 **Segments**
    119 
    120 ![](/predownloaded/0f/10/0f108b7b2303011f5f4782fedea4f8fe7ba2b84e.png)
    121 
    122 There are also some vertical segments, but it can be proven with some geometry that the segments on the neighboring horizontal line are either on the same x-coordinate, or one is shifted by one. This means that if we choose the leftmost point in each of these segments, we will cover all vertical pairs as well.
    123 
    124 With some symmetry, this can be done for other pieces of a circle.
    125 
    126 There is only one thing left — we need to bring all pieces together. It is easy when two pieces share a horizontal or vertical line, but in the other case, we need another picture.
    127 
    128 **Picture 1**
    129 
    130 ![](/predownloaded/5f/08/5f0834e361ad93ddf0a3223bdee54f8304b65af2.png)
    131 
    132 In this case, everything is already fine, we don't have any "leaks" between parts
    133 
    134 **Picture 2**
    135 
    136 ![ ](/predownloaded/0d/1b/0d1b101948380227a97deeb0ec250c24180f4f54.png)
    137 
    138 In that case, we don't have any leaks either, but we have overlapping segments, and that means that we case save 1 point here and 4 points total.
    139 
    140 All we need now is to calculate the number of segments in a circle sector (it is ${n}/\sqrt{2}+1$) and differentiate these two cases.
    141 
    142 **Code**
    143 
    144 ```
    145 #include <bits/stdc++.h>
    146 
    147 using namespace std;
    148 
    149 int main() {
    150     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    151 
    152     long long n;
    153     cin >> n;
    154 
    155     if (n == 0) {
    156         cout << 1 << '\n';
    157         return 0;
    158     }
    159 
    160     int L = sqrt(n * n / 2);
    161 
    162     pair<long long, long long> near = {L + 1, L};
    163 
    164     int ans = (L * 2 + 1) * 4;
    165 
    166     if (near.first * near.first + near.second * near.second > n * n)
    167         ans -= 4;
    168 
    169     cout << ans << '\n';
    170 
    171     return 0;
    172 }
    173 ```
    174 
    175 Div2D/Div1B
    176 
    177 **Editorial**
    178 
    179 ### [392B - Ханойская башня](/contest/392/problem/B "Codeforces Round 230 (Div. 1)")
    180 
    181 First, understand [this solution](https://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution) of the standard Hanoi puzzle, if you don't know it. I will use the same idea to solve this problem. Let's create a function $calc(from, to, n)$ which will count the minimal cost to move $n$ disks from $from$ to $to$. If $n=1$ then we either move the disk directly to $to$, or we first move it to the $mid$ (the remaining rod) and only then move to $to$. If $n \gt 1$ then again, there are two possible strategies. Either we use moves from standard solution — move $n-1$ disks to $mid$, move 1 disk from $from$ to $to$, then move $n-1$ disks to $to$. Or we can make more moves but possibly with less cost: move $n-1$ disks to $to$, then 1 disk from $from$ to $mid$, then $n-1$ disks back to $from$, then 1 disk to $to$, and finally $n-1$ disks to $to$. Here are pictures for both cases:
    182 
    183 **Case 1**
    184 
    185 ![ ](/predownloaded/af/92/af924321fd33f0a0760c8d575a8bc78c7cb797b9.png)
    186 
    187 [Better resolution](https://imgur.com/a/0fcc8YV)
    188 
    189 **Case 2**
    190 
    191 ![ ](/predownloaded/d2/f0/d2f04cb3d38115674d8188d6cf3701e784c6f7e2.png)
    192 
    193 [Better resolution](https://imgur.com/6ItXSCl)
    194 
    195 For moving $n-1$ disks we will make recursive calls. If we just do that, we will have an exponential solution, which is not very nice. But we only have $3\times 2 \times n $ different calls — 3 options for $from$, 2 for $to$ and $n$. That means that we can just store every value which we already counted (or I can say a fancy word *memoization*, which means the same thing)
    196 
    197 **Code**
    198 
    199 ```
    200 #include <bits/stdc++.h>
    201 
    202 using namespace std;
    203 
    204 #define ll   long long
    205 
    206 array<array<ll, 3>, 3> t;
    207 map<pair<pair<int, int>, ll>, ll> mem;
    208 
    209 ll calc(int from, int to, int n) {
    210     auto p = make_pair(make_pair(from, to), n);
    211     if (mem.count(p))
    212         return mem[p];
    213     int mid = 3 - from - to;
    214     if (n == 1) {
    215         return mem[p] = min(t[from][mid] + t[mid][to], t[from][to]);
    216     }
    217     return mem[p] = min(calc(from, mid, n - 1) + t[from][to]  + calc(mid,   to, n - 1),
    218                         calc(from,  to, n - 1) + t[from][mid] + calc( to, from, n - 1) + t[mid][to] + calc(from, to, n - 1));
    219 }
    220 
    221 int main() {
    222     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    223 
    224     for (int i = 0; i < 3; ++i) {
    225         for (int j = 0; j < 3; ++j) {
    226             cin >> t[i][j];
    227         }
    228     }
    229 
    230     int n;
    231     cin >> n;
    232 
    233     cout << calc(0, 2, n) << '\n';
    234 
    235     return 0;
    236 }
    237 ```
    238 
    239 Div2E/Div1C
    240 
    241 **Editorial**
    242 
    243 ### [392C - Еще одна последовательность чисел](/contest/392/problem/C "Codeforces Round 230 (Div. 1)")
    244 
    245 This is obviously some matrix-exponentiation problem. We just have to figure out the matrix. Well, let's look at what we have
    246 
    247 $ A_i(k) = F_i \cdot i^k = (F_{i-1} + F_{i-2}) \cdot i^k = F_{i-1}\cdot ((i-1)+1)^k + F_{i-2}\cdot ((i-2) + 2)^k =\\= \sum_{j=0}^k \binom{k}{j} F_{i-1}(i-1)^j + \sum_{j=0}^k \binom{k}{j} F_{i-2}(i-2)^j\cdot 2^{k-j}=\\= \sum_{j=0}^k \binom{k}{j} A_{i-1}(j) + \sum_{j=0}^k \binom{k}{j} A_{i-2}(j)\cdot 2^{k-j} $
    248 
    249 Then we just have to store $A_{i-1}(j)$ and $A_{i-2}(j)$ for every $j \in [0;k]$. And also we have to store the sum, so the matrix will be of size $2(k+1)+1$, resulting in $O(k^3\log n)$ in total.
    250 
    251 If you need more information about matrix exponentiation, consider watching the video from Errichto. Oh, and I almost forgot. He says *exponentation* instead of *exponentiation*. Now you will not able to forget this, enjoy! Here is the [link](https://www.youtube.com/watch?v=eMXNWcbw75E) :) (Errichto, no offence, if you are reading this :) )
    252 
    253 **Code**
    254 
    255 ```
    256 #include <bits/stdc++.h>
    257 
    258 using namespace std;
    259 
    260 #define ll   long long
    261 
    262 template<auto P>
    263 struct Modular {
    264     using value_type = decltype(P);
    265     value_type value;
    266 
    267     Modular(ll k = 0) : value(norm(k)) {}
    268 
    269     Modular<P>& operator += (const Modular<P>& m)       { value += m.value; if (value >= P) value -= P; return *this; }
    270     Modular<P>  operator +  (const Modular<P>& m) const { Modular<P> r = *this; return r += m; }
    271 
    272     Modular<P>& operator -= (const Modular<P>& m)       { value -= m.value; if (value <  0) value += P; return *this; }
    273     Modular<P>  operator -  (const Modular<P>& m) const { Modular<P> r = *this; return r -= m; }
    274     Modular<P>  operator -                     () const { return Modular<P>(-value); }
    275 
    276     Modular<P>& operator *= (const Modular<P> &m)       { value = value * 1ll * m.value % P; return *this; }
    277     Modular<P>  operator *  (const Modular<P>& m) const { Modular<P> r = *this; return r *= m; }
    278 
    279     Modular<P>& operator /= (const Modular<P> &m)       { return *this *= m.inv(); }
    280     Modular<P>  operator /  (const Modular<P>& m) const { Modular<P> r = *this; return r /= m; }
    281 
    282     Modular<P>& operator ++                    ()       { return *this += 1; }
    283     Modular<P>& operator --                    ()       { return *this -= 1; }
    284     Modular<P>  operator ++                 (int)       { Modular<P> r = *this; r += 1; return r; }
    285     Modular<P>  operator --                 (int)       { Modular<P> r = *this; r -= 1; return r; }
    286 
    287     bool        operator == (const Modular<P>& m) const { return value == m.value; }
    288     bool        operator != (const Modular<P>& m) const { return value != m.value; }
    289 
    290     value_type norm(ll k) {
    291         if (!(-P <= k && k < P)) k %= P;
    292         if (k < 0) k += P;
    293         return k;
    294     }
    295 
    296     Modular<P> inv() const {
    297         value_type a = value, b = P, x = 0, y = 1;
    298         while (a != 0) { value_type k = b / a; b -= k * a; x -= k * y; swap(a, b); swap(x, y); }
    299         return Modular<P>(x);
    300     }
    301 };
    302 
    303 template<auto P> Modular<P> pow(Modular<P> m, ll p) {
    304     Modular<P> r(1);
    305     while (p) {
    306         if (p & 1) r *= m;
    307         m *= m;
    308         p >>= 1;
    309     }
    310     return r;
    311 }
    312 
    313 template<auto P> ostream& operator << (ostream& o, const Modular<P> &m) { return o << m.value; }
    314 template<auto P> istream& operator >> (istream& i,       Modular<P> &m) { ll k; i >> k; m.value = m.norm(k); return i; }
    315 template<auto P> string   to_string(const Modular<P>& m) { return to_string(m.value); }
    316 
    317 using Mint = Modular<1000000007>;
    318 // using Mint = Modular<998244353>;
    319 // using Mint = long double;
    320 
    321 vector<vector<Mint>> operator * (vector<vector<Mint>> a, vector<vector<Mint>> b) {
    322     vector<vector<Mint>> c(a.size(), vector<Mint>(b[0].size(), 0));
    323     for (int i = 0; i < a.size(); ++i) {
    324         for (int j = 0; j < a[0].size(); ++j) {
    325             for (int k = 0; k < b[0].size(); ++k) {
    326                 c[i][k] += a[i][j] * b[j][k];
    327             }
    328         }
    329     }
    330     return c;
    331 }
    332 
    333 vector<vector<Mint>> pow(vector<vector<Mint>> a, ll p) {
    334     vector<vector<Mint>> res(a.size(), vector<Mint>(a.size(), 0));
    335     for (int i = 0; i < res.size(); ++i) {
    336         res[i][i] = 1;
    337     }
    338     while (p) {
    339         if (p & 1) {
    340             res = res * a;
    341         }
    342         a = a * a;
    343         p /= 2;
    344     }
    345     return res;
    346 }
    347 
    348 int main() {
    349     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    350 
    351     ll n;
    352     cin >> n;
    353     int k;
    354     cin >> k;
    355 
    356     vector<vector<Mint>> mt((k + 1) * 2 + 1, vector<Mint>((k + 1) * 2 + 1, 0));
    357 
    358     vector<vector<Mint>> vinit(mt.size(), vector<Mint>(1, 0));
    359 
    360     // first k+1 elements are for F_{i-1}, next k+1 are for F_{i-2}, the last one is for sum up to A_{i-2}
    361     for (int i = 0; i < k + 1; ++i) {
    362         vinit[i][0] = 1;
    363         vinit[i + k + 1][0] = 0;
    364         vinit.back()[0] = 0;
    365     }
    366     vinit[k + 1][0] = 1;
    367 
    368     vector<vector<Mint>> C(50, vector<Mint>(50, 0));
    369     for (int i = 0; i < C.size(); ++i) {
    370         C[0][i] = 0;
    371         C[i][0] = 1;
    372     }
    373 
    374     for (int i = 1; i < C.size(); ++i) {
    375         for (int j = 1; j < C.size(); ++j) {
    376             C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    377         }
    378     }
    379 
    380     vector<Mint> p2(50, 1);
    381     for (int i = 1; i < p2.size(); ++i)
    382         p2[i] = p2[i - 1] * 2;
    383 
    384     for (int p = 0; p < k + 1; ++p)
    385         mt[k + 1 + p][p] = 1;
    386     mt.back().back() = 1;
    387     mt.back()[k] = 1;
    388 
    389     for (int p = 0; p < k + 1; ++p) {
    390         for (int j = 0; j <= p; ++j) {
    391             mt[p][j] += C[p][j];
    392             mt[p][k + 1 + j] += C[p][j] * p2[p - j];
    393         }
    394     }
    395 
    396     auto res = pow(mt, n) * vinit;
    397     cout << res.back()[0] << '\n';
    398 
    399     return 0;
    400 }
    401 ```
    402 
    403 Div1D
    404 
    405 **Editorial**
    406 
    407 ### [392D - Три массива](/contest/392/problem/D "Codeforces Round 230 (Div. 1)")
    408 
    409 Let forget about $a$ for a minute and solve the problem for two arrays. Of course, it can be done with something like two pointers, but it is not extendable to three arrays (at least I don't know how). We need a more general approach. First, let's assume that $b$ has all elements, which $c$ contains. We can achieve that by copying $c$ at the end of $b$ (it is easy to see that this will not improve the answer).
    410 
    411 Suppose for some number $k$ it has only one occurrence in $b$ and only one in $c$. And $b[i] = c[j] = k$. Then we denote $pos[i] = j$. Now, if $k$ has multiple occurrences in $c$, we will take the smallest $j$. If it has multiple occurrences in $b$, we will set the first $pos[i]$ to $j$ and others to $0$. Why that? Good question. Now the answer for the problem is $min_i((i-1) + max_{j \gt i}pos[j])$. The expression in the brackets corresponds to the case when we take $i$ first elements from $b$. Then we look for all other elements ($j \gt i$) and choose the shortest prefix of $c$ which contains all these elements. That explains why we write the first occurrence of $k$ in $c$ to $pos$. And we fill other values with zero because we don't need them if we already took the first occurrence in $b$.
    412 
    413 Now get $a$ back. What changes if we have some numbers in $a$? Well, in that case, we can set $pos[i]=0$ for all occurrences of that number in $b$ (not only all except first). That means that if we iterate over prefix of $a$ from $0$ to $n$ then we will have to change some $pos$ to zero. But I prefer changing zeros to some values, so we will iterate from $n$ to $0$.
    414 
    415 Well, let's iterate. Suppose we decided not to take prefix of length $i$ in $a$, and instead took prefix of length $i-1$. If there are some occurrences of $a[i]$ before $i$, then nothing changes in $pos$. But if there is no $a[i]$ before $i$, we have to update some $pos$ and recalculate $min_i((i-1) + max_{j \gt i}pos[j])$. I believe there are different structs that can do it, I will describe what I used.
    416 
    417 In the expression, there are maximums on the suffix. They can be stored as pairs $(p, m)$ which means that up to position $p$ maximum on a suffix is at least $m$ (maximum-on-a-suffix is a non-increasing function, obviously). Now, to calculate the answer, we don't have to go through all $i$. We only need to consider such indices $p$ that some pair $(p-1, ?)$ exists in our set. That means that we have to check exactly one option for every pair of adjacent pairs. Remember, we only have to add pairs to this set. And it is easy — add a pair and remove enough pairs before it (while their $m$ less than new $m$). With every addition or removal, we have $O(1)$ additions or removals of options for an answer. Current answers can be stored in a multiset since we only need the minimal value. And if we are looking at a prefix $i$ of $a$, then we have to update the answer with $i$ + (the smallest value from multiset).
    418 
    419 This is probably not the cleanest explanation, so there is a random picture which can help:
    420 
    421 **Picture**
    422 
    423 ![ ](/predownloaded/bb/d8/bbd87383e017ca27905aca44e5e92fc829b1712c.png)
    424 
    425 *The picture can contain off-by-one error, depending on your indexing and my mistakes*.
    426 
    427 $pos = [1,\,0,\,5,\,3,\,0,\,3,\,2]$.
    428 
    429 The picture illustrates maximums on a suffix for every $i$. In a set, we store one pair for each horizontal segment. When we need to update the answer, we look at all points with a green circle (or actually 1 to the right of these points because in this picture maximum at $x=2$ is $5$, so we need $(3,3)$, not $(2,3)$, but that is exactly what I meant when I said about off-by-one errors).
    430 
    431 **Code**
    432 
    433 ```
    434 #include <bits/stdc++.h>
    435 
    436 using namespace std;
    437 
    438 int main() {
    439     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    440 
    441     int n;
    442     cin >> n;
    443     vector<int> a(n), b(n), c(n);
    444     for (int i = 0; i < n; ++i)
    445         cin >> a[i];
    446     for (int i = 0; i < n; ++i)
    447         cin >> b[i];
    448     for (int i = 0; i < n; ++i)
    449         cin >> c[i];
    450 
    451     for (auto k : c) {
    452         b.push_back(k);
    453     }
    454 
    455     map<int, int> whereb;
    456     map<int, int> wherec;
    457     for (int i = (int)b.size() - 1; i >= 0; --i)
    458         whereb[b[i]] = i;
    459     for (int i = (int)c.size() - 1; i >= 0; --i)
    460         wherec[c[i]] = i;
    461 
    462     vector<bool> first_in_a(a.size(), false);
    463     vector<bool> first_in_b(b.size(), false);
    464     set<int> ina, inb;
    465     for (int i = 0; i < a.size(); ++i) {
    466         if (!ina.count(a[i])) {
    467             ina.insert(a[i]);
    468             first_in_a[i] = true;
    469         }
    470     }
    471     for (int i = 0; i < b.size(); ++i) {
    472         if (!inb.count(b[i])) {
    473             inb.insert(b[i]);
    474             first_in_b[i] = true;
    475         }
    476     }
    477 
    478     set<pair<int, int>> maxs;
    479     multiset<int> res;
    480 
    481     maxs.emplace(1e9, 0);
    482     maxs.emplace(-1, 1e9 + 5);
    483     res.insert(maxs.begin()->first + next(maxs.begin())->second + 1);
    484 
    485     auto del = [&](pair<int, int> p) {
    486         auto it = maxs.find(p);
    487         assert(it != maxs.end());
    488         auto inext = next(it);
    489         auto iprev = prev(it);
    490 
    491         res.erase(res.find(iprev->first + it->second + 1));
    492         res.erase(res.find(it->first + inext->second + 1));
    493         maxs.erase(it);
    494         res.insert(iprev->first + inext->second + 1);
    495     };
    496 
    497     auto add = [&](pair<int, int> p) {
    498         auto it = maxs.lower_bound(make_pair(p.first, -5));
    499         if (it->second >= p.second) return;
    500         if (it->first == p.first) {
    501             ++it;
    502         }
    503         while (prev(it)->second <= p.second)
    504             del(*prev(it));
    505 
    506         maxs.insert(p);
    507         it = maxs.find(p);
    508         auto inext = next(it);
    509         auto iprev = prev(it);
    510 
    511         res.insert(iprev->first + it->second + 1);
    512         res.insert(it->first + inext->second + 1);
    513         res.erase(res.find(iprev->first + inext->second + 1));
    514     };
    515 
    516     for (int i = 0; i < b.size(); ++i) {
    517         if (first_in_b[i] && !ina.count(b[i])) {
    518             int inc = 1e9;
    519             if (wherec.count(b[i]))
    520                 inc = wherec[b[i]] + 1;
    521             add({i, inc});
    522         }
    523     }
    524 
    525     int ans = n + *res.begin();
    526 
    527     for (int i = n - 1; i >= 0; --i) {
    528         if (first_in_a[i]) {
    529             if (!inb.count(a[i])) break;
    530             int inc = 1e9;
    531             if (wherec.count(a[i]))
    532                 inc = wherec[a[i]] + 1;
    533             add({whereb[a[i]], inc});
    534         }
    535         ans = min(ans, i + *res.begin());
    536     }
    537 
    538     cout << ans << '\n';
    539 
    540     return 0;
    541 }
    542 ```
    543 
    544 Div1E
    545 
    546 **Editorial**
    547 
    548 ### [392E - Удаляем подстроки](/contest/392/problem/E "Codeforces Round 230 (Div. 1)")
    549 
    550 There will be three different $dp$, let's get that out of the way. I wanted to make $4$, but in the end decided to merge two of them.
    551 
    552 Also, before everything, let's update $v$ with $v[i] = max_j(v[j] + v[i - j])$. Because sometimes we want to remove segment of length $5$, but $2 + 3$ gives more points.
    553 
    554 First, let's discuss what a *good* substring is. It is either increasing, decreasing, or increasing up to something and then decreasing. And in any case, the difference between neighboring elements is exactly 1.
    555 
    556 $dp\_mon[l][r]$ — the biggest score we can get from segment $[l;r]$ if in the end we are left with monotonous sequence, starting from $w[l]$ and ending with $w[r]$ (that means that we cannot remove $w[l]$ or $w[r]$). If we can't do that, $dp\_mon[l][r] = -\infty$.
    557 
    558 $dp\_all[l][r]$ — the biggest score we can get from removing the whole segment $[l;r]$.
    559 
    560 $dp[l][r]$ — the best score we can get on segment $[l;r]$ (no restrictions).
    561 
    562 The answer will be $dp[1][n]$.
    563 
    564 When we have these $dp$, it is not very hard to calculate them. To get $dp\_mon[l][r]$ we either have to remove everything in between (if $|w[l] - w[r]| = 1$), or for each number between $l$ and $r$ check if it can be in that monotonous sequence, and if it can, split by this number and add two $dp\_mon[l][j] + dp\_mon[j][r]$ (with intersection, yes).
    565 
    566 Now $dp\_all$. First, let's update it with every $dp\_all[l][j] + dp\_all[j + 1][r]$. Now suppose there is an option, where we can't split the segment into two pieces. Consider the last segment we removed. It is some subsequence of our $[l;r]$ segment. Elements of that subsequence split this segment into pieces. Each of these pieces is independent of each other. That means that if the first element of the subsequence is $w[j]$ then $[l; j-1]$ and $[j; r]$ are independent and we already updated the answer with the sum of $dp\_all$, and similarly with $r$. There is one case, though. When this subsequence starts at $w[l]$ and ends in $w[r]$. But that's what we have $dp\_mon$ for! Now for every element on $[l;r]$ we have to check if this subsequence is increasing from $w[l]$ to $w[j]$ and then decreasing from $w[j]$ to $w[r]$. That means that we add two $dp\_mon$ and after that remove this subsequence with a score of $v[len\_of\_subsequence]$. The length can be calculated from $|w[l] - w[j]|$ and $|w[j] - w[r]|$.
    567 
    568 The last is $dp$. That's the easiest one. Either we remove everything — this is $dp\_all$, or there is some element which we decided not to remove. Then, as discussed in previous paragraph, it is enough to update $dp[l][r]$ by every $dp[l][j] + dp[j + 1][r]$.
    569 
    570 And I know that probably some of $dp$ are useless, but I feel like it is easier to understand the solution with multiple $dp$ with different purposes.
    571 
    572 **Code**
    573 
    574 ```
    575 #include <bits/stdc++.h>
    576 
    577 using namespace std;
    578 
    579 #define ll long long
    580 
    581 const int inf = 1e9;
    582 
    583 int main() {
    584     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    585 
    586     int n;
    587     cin >> n;
    588     vector<int> v(n);
    589     for (int i = 0; i < n; ++i) {
    590         cin >> v[i];
    591     }
    592 
    593     v.insert(v.begin(), 0);
    594     for (int i = 1; i <= n; ++i) {
    595         for (int j = 1; j < i; ++j) {
    596             v[i] = max(v[i], v[j] + v[i - j]);
    597         }
    598     }
    599 
    600     vector<int> w(n);
    601     for (int i = 0; i < n; ++i) {
    602         cin >> w[i];
    603     }
    604 
    605     auto getv = [&](int ln) {
    606         if (ln < v.size()) return v[ln];
    607         return -inf;
    608     };
    609 
    610     vector<vector<ll>> dp_all(n, vector<ll>(n, -inf));
    611     vector<vector<ll>> dp_mon(n, vector<ll>(n, -inf));
    612     vector<vector<ll>> dp(n, vector<ll>(n, 0));
    613 
    614     for (int i = 0; i < n; ++i) {
    615         dp_mon[i][i] = 0;
    616         dp_all[i][i] = v[1];
    617         if (i != 0)
    618             dp_all[i][i - 1] = 0;
    619     }
    620 
    621     for (int k = 1; k <= n; ++k) {
    622         for (int l = 0; l < n; ++l) {
    623             int r = l + k - 1;
    624             if (r >= n) break;
    625 
    626             for (int j = l + 1; j <= r; ++j) {
    627                 dp_all[l][r] = max(dp_all[l][r], dp_all[l][j - 1] + dp_all[j][r]);
    628             }
    629 
    630             if (w[l] != w[r]) {
    631                 if (abs(w[l] - w[r]) == 1) {
    632                     dp_mon[l][r] = dp_all[l + 1][r - 1];
    633                 } else {
    634                     for (int j = l + 1; j < r; ++j) {
    635                         if (w[l] != w[j] && w[r] != w[j] && ((w[l] < w[j]) == (w[j] < w[r]))) {
    636                             dp_mon[l][r] = max(dp_mon[l][r], dp_mon[l][j] + dp_mon[j][r]);
    637                         }
    638                     }
    639                 }
    640             }
    641 
    642             for (int j = l; j <= r; ++j)
    643                 if (w[j] >= w[l] && w[j] >= w[r])
    644                     dp_all[l][r] = max(dp_all[l][r], dp_mon[l][j] + dp_mon[j][r] + getv(abs(w[l] - w[j]) + abs(w[j] - w[r]) + 1));
    645 
    646             dp[l][r] = max(dp[l][r], dp_all[l][r]);
    647             for (int j = l + 1; j <= r; ++j)
    648                 dp[l][r] = max(dp[l][r], dp[l][j - 1] + dp[j][r]);
    649         }
    650     }
    651 
    652     cout << dp[0][n - 1] << '\n';
    653 
    654     return 0;
    655 }
    656 ```
    657 
    658 This is my first editorial (and first blog too), so any suggestions, improvements, etc are welcome.