codeforces-scrape

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

2165.md (25611B)


      1 Source: https://codeforces.com/blog/entry/148452
      2 
      3 [2166A — Same Difference](https://codeforces.com/contest/2166/problem/A)
      4 
      5 idea & solution: [le0n](/profile/le0n "Legendary Grandmaster le0n")
      6 
      7 **Tutorial**
      8 
      9 It can be observed that $s_n$ will not change throughout the operations, therefore, for the final string to have every character the same, every character must be equal to $s_n$.
     10 
     11 To change every character to $s_n$, we can iterate over all characters from right to left, repeatedly setting $s_{i-1}\leftarrow s_i$ if $s_{i-1}\neq s_n$. Through this, we can need one operation for every character not equal to $s_n$, which is also obvious as a lower bound.
     12 
     13 Time complexity: $O(n)$.
     14 
     15 **Solution**
     16 
     17 ```
     18 #include <bits/stdc++.h>
     19 
     20 using namespace std;
     21 
     22 char s[100005];
     23 
     24 int main()
     25 {
     26 	int n, t, i, m;
     27 	scanf("%d", &t);
     28 	while(t--)
     29 	{
     30 		scanf("%d", &n);
     31 		scanf("%s", s + 1);
     32 		m = 0;
     33 		for(i = 1; i < n; i++)
     34 			m += (s[i] != s[n]);
     35 		printf("%d\n", m);
     36 	}
     37 	return 0;
     38 }
     39 ```
     40 
     41 [2166B — Tab Closing](https://codeforces.com/contest/2166/problem/B)
     42 
     43 idea & solution: [le0n](/profile/le0n "Legendary Grandmaster le0n")
     44 
     45 The problem statement arised naturally from closing tabs in any modern browser.
     46 
     47 **Tutorial**
     48 
     49 After some experimenting, it can be seen that the answer does not exceed $2$. Simply click at $a$ as long as there's still a tab at that point. After that, each tab must have length of $b$, move the cursor to $b$, and click until all tabs have been closed.
     50 
     51 Now it remains to be seen under what scenarios we can achieve $1$ move. Since the last tab closed will have length $b$, our cursor should be moved to $b$. Therefore, the answer will be $1$ when $nb\le a$, or $b=a$, and $2$ otherwise.
     52 
     53 Remember to use long long if using multiplication to calculate $nb$.
     54 
     55 Time Complexity: $O(1)$ per test case.
     56 
     57 **Solution**
     58 
     59 ```
     60 #include <bits/stdc++.h>
     61 
     62 using namespace std;
     63 
     64 int main()
     65 {
     66 	int t, n, a, b;
     67 	scanf("%d", &t);
     68 	while(t--)
     69 	{
     70 		scanf("%d%d%d", &a, &b, &n);
     71 		printf(((long long)b * n <= a || b >= a) ? "1\n" : "2\n");
     72 	}
     73 	return 0;
     74 }
     75 ```
     76 
     77 [2165A — Cyclic Merging](https://codeforces.com/contest/2165/problem/A)
     78 
     79 idea & solution: [le0n](/profile/le0n "Legendary Grandmaster le0n")
     80 
     81 **Tutorial**
     82 
     83 We consider a simple strategy: repeatedly merge the smallest element onto the smaller of its two neighbours.
     84 
     85 We will prove this greedy is correct: For any merge sequence, consider the smallest element $mn$, it must be merged into a larger element at some point in the future. However, its neighbour will not be smaller, which means that we can simply modify the merge sequence to merge $mn$ into its neighbours at the very first.
     86 
     87 Further observation will show that this value is equal to $\sum_{i=1}^{n-1}\max(a_i,a_{i+1})+\max(a_n,a_1)-\max({a_1,a_2,\cdots,a_n})$. A brief sketch of the proof is as follows: It can be shown that we can break the ring into a sequence at an arbitrary maxima, since the maxima will not be merged into others.
     88 
     89 For the problem on a sequence, consider each element $a_i$, find the closest element $a_x$ to the left of $a_i$, such that $a_x \gt a_i$ (when equal, break ties according to index). If there are elements between $a_x$ and $a_i$, then it's clear that in performing the aforementioned greedy, at some point we will merge everything in $a_{x+1},a_{x+2},\cdots,a_i$ into a single element, and then merge it into $a_i$. Therefore the answer will be increased by $a_i$ if $a_{i-1} \lt a_i$. The same thing will happen to the right of $a_i$. Therefore the answer is $\sum_{i=1}^{n-1}[a_i\ge a_{i+1}]a_i+[a_i \lt a_{i+1}]a_{i+1}$, which can be rephrased as $\sum_{i=1}^{n-1}\max(a_i,a_{i+1})$, which in turn is the formula above.
     90 
     91 However, this is not needed to pass the problem. We expected participants to pass using doubly linked lists, sets, or any other data structures which can support the operations needed.
     92 
     93 Time Complexity: $O(n)$ or $O(n\log n)$.
     94 
     95 **Solution**
     96 
     97 ```
     98 #include <bits/stdc++.h>
     99 
    100 using namespace std;
    101 typedef long long ll;
    102 
    103 const int N = 1e6 + 5;
    104 ll a[N];
    105 
    106 int main()
    107 {
    108 	int t, n, m, i;
    109 	ll k;
    110 	scanf("%d", &t);
    111 	while(t--)
    112 	{
    113 		scanf("%d", &n);
    114 		m = 0;
    115 		for(i = 0; i < n; i++)
    116 		{
    117 			scanf("%lld", a + i);
    118 			if(a[i] > a[m])
    119 				m = i;
    120 		}
    121 		a[n] = a[0];
    122 		k = -a[m];
    123 		for(i = 0; i < n; i++)
    124 			k += max(a[i], a[i + 1]);
    125 		printf("%lld\n", k);
    126 	}
    127 	return 0;
    128 }
    129 ```
    130 
    131 **Solution (linked lists, by Arpa)**
    132 
    133 ```
    134 // In the name of Allah.
    135  
    136 #include <bits/stdc++.h>
    137 using namespace std;
    138  
    139  
    140 int main() {
    141     ios::sync_with_stdio(false);
    142     cin.tie(nullptr);
    143     int t;
    144     cin >> t;
    145     while (t--) {
    146         int n;
    147         cin >> n;
    148         list<int> alive;
    149         int a[n];
    150         list<int>::iterator w[n];
    151         auto c_next = [&alive](const list<int>::iterator& it) {
    152             return next(it) == alive.end() ? alive.begin() : next(it);
    153         };
    154         auto c_prev = [&alive](const list<int>::iterator& it) {
    155             return it == alive.begin() ? --alive.end() : prev(it);
    156         };
    157         auto hole = [&](const list<int>::iterator& it) {
    158             return a[*it] <= min(a[*c_next(it)], a[*c_prev(it)]);
    159         };
    160         for (int i = 0; i < n; ++i) {
    161             cin >> a[i];
    162             w[i] = alive.insert(alive.end(), i);
    163         }
    164         queue<int> q;
    165         {
    166             int i = 0;
    167             for (auto it = alive.begin(); it != alive.end(); ++it, ++i)
    168                 if (hole(it))
    169                     q.push(i);
    170         }
    171         long long ans = 0;
    172         bool mark[n] = {};
    173         while (alive.size() > 1) {
    174             auto i = q.front();
    175             q.pop();
    176             if (mark[i])
    177                 continue;
    178             mark[i] = true;
    179             auto it = w[i];
    180             ans += min(a[*c_next(it)], a[*c_prev(it)]);
    181             auto jt = c_next(it);
    182             alive.erase(it);
    183             it = jt;
    184             if (hole(it))
    185                 q.push(*it);
    186             it = c_prev(it);
    187             if (hole(it))
    188                 q.push(*it);
    189         }
    190         cout << ans << '\n';
    191     }
    192 }
    193 ```
    194 
    195 [2165B — Marble Council](https://codeforces.com/contest/2165/problem/B)
    196 
    197 idea & solution: [Flamire](/profile/Flamire "Legendary Grandmaster Flamire")
    198 
    199 **Tutorial**
    200 
    201 For a multiset $S$, we will find a check to determine whether it can be generated.
    202 
    203 For each color $x$ not in $S$, we need to somehow "hide" all of the $x$'s in other sets. That is, for every partitioned set, the occurrence of $x$ must be less than or equal to the occurrence of the modes.
    204 
    205 For each color $c$ in $S$, no matter how many times $c$ appeared in $S$, or how we partition these $c$ into different sets, the color $c$ can provide at most $cnt_c$ "chances" to hide an element of $x$.
    206 
    207 Therefore, $cnt_x\le\sum_{c\in S}cnt_c$ must hold.
    208 
    209 It is easy to construct a partition once this condition is held for all $x$. Thus, we only need to count sets that satisfy $\max_{x\not\in S} cnt_x\le\sum_{c\in S} cnt_c$.
    210 
    211 This is a simple knapsack dp problem from here, you can either add elements in increasing order of $cnt$ and keep track if the last color is used at all, or observe that the condition is just $\sum_{c\in S}cnt_c\ge\max cnt$, and just running a completely vanilla knapsack dp.
    212 
    213 Time Complexity: $O(n^2)$.
    214 
    215 **Solution (By ZhouYuHang)**
    216 
    217 ```
    218 #include <bits/stdc++.h>
    219 using namespace std;
    220  
    221 const int N = 5e3 + 5, P = 998244353;
    222  
    223 int n;
    224 int a[N], cnt[N];
    225 int dp[N];
    226  
    227 void solve() {
    228 	cin >> n;
    229 	for (int i = 1; i <= n; ++i) cin >> a[i];
    230 	
    231 	memset(cnt, 0, sizeof cnt);
    232 	int max_cnt = 0;
    233 	for (int i = 1; i <= n; ++i) {
    234 		max_cnt = max(max_cnt, ++cnt[a[i]]);
    235 	}
    236  
    237 	memset(dp, 0, sizeof dp), dp[0] = 1;
    238 	for (int i = 1; i <= n; ++i) if (cnt[i]) {
    239 		for (int j = n; j >= cnt[i]; --j) {
    240 			dp[j] = (dp[j] + 1ll * cnt[i] * dp[j - cnt[i]]) % P;
    241 		}
    242 	}
    243 	
    244 	int ans = 0;
    245 	for (int i = max_cnt; i <= n; ++i) (ans += dp[i]) %= P;
    246 	cout << ans << endl;
    247 }
    248  
    249 int main() {
    250 	ios::sync_with_stdio(false);
    251 	cin.tie(nullptr);
    252  
    253 	int T;	
    254 	cin >> T;
    255 	while (T--) {
    256 		solve();
    257 	}
    258  
    259 	return 0;
    260 }
    261 ```
    262 
    263 [2165C — Binary Wine](https://codeforces.com/contest/2165/problem/C)
    264 
    265 idea & solution: [le0n](/profile/le0n "Legendary Grandmaster le0n")
    266 
    267 Some participants mentioned that similar ideas have appeared recently. We knew of at least one such problem, however, the problem was already proposed and accepted at that time.
    268 
    269 I believe that the problems are not identical, though similar ideas were used, it is also a show of skill to remember and reuse ideas learnt from previous problems. Therefore, I would like to think the problem does have a place in the contest.
    270 
    271 There was an oversight on the preparation of this problem, the tests did not include enough small tests, which allowed some codes with wrong implementation to pass. We apologize for the inconvenience.
    272 
    273 **Tutorial**
    274 
    275 There are many ways to approach this problem, my personal approach is as follows:
    276 
    277 Consider what kind of $a$ would satisfy the requirements, after some exploring, we can arrive at the following check: Sum each bit of $a$, resulting in an integer sequence, if this sequence is lexicographically larger or equal to the binary representation of $c$, then $a$ is ok.
    278 
    279 This can be explained by considering bits from high to low:
    280 
    281 * If at some point we have more $a$'s than $c$, we can use a 1-bit on this position to fix everything under this bit.
    282 * If at some point we have $0$ a's and the $c$ bit is $1$, it's then obvious that we cannot satisfy the conditions, since we also cannot use higher bits to change the situation, as this will cause higher bits to be less than $c$.
    283 
    284 Thus, we have obtained a clean check to $a$.
    285 
    286 To minimize the $+1$ operations, we will iterate bits from high to low, if the current $a$'s is less than $c$, we will have to select a single $a$ element, and increase it to the point that the current bit is $1$. Note that we will not increase two $a$ elements, since in reaching the state, we will inevitably reach the state where one of the $a$ is $1000\cdots00$, and the other one is $0111\cdots11$, this is already enough.
    287 
    288 From here, observe that only the maximum $O(\log V)$ elements are used, we can easily achieve a complexity of $O(n\log n+q\log^2V)$, or $O(n\log n+q\log V\log\log V)$ with heaps.
    289 
    290 **Solution**
    291 
    292 ```
    293 #include <bits/stdc++.h>
    294 #define N 500011
    295 #define ll long long
    296 using namespace std;
    297 int T,n,q,a[N];
    298 int main()
    299 {
    300 	scanf("%d",&T);while(T--)
    301 	{
    302 		scanf("%d%d",&n,&q);
    303 		for(int i=1;i<=n;++i)scanf("%d",a+i);
    304 		sort(a+1,a+1+n,greater<int>());
    305 		int nn=min(n,32);
    306 		while(q--)
    307 		{
    308 			int c;scanf("%d",&c);
    309 			static int b[44];ll ans=0;
    310 			for(int i=1;i<=nn;++i)b[i]=a[i];
    311 			for(int i=29;~i;--i)
    312 			{
    313 				int cc=0;
    314 				for(int j=1;j<=nn;++j)cc+=b[j]>>i&1;
    315 				if(cc>(c>>i&1))break;
    316 				if(cc<(c>>i&1))
    317 				{
    318 					int id=1;
    319 					for(int j=2;j<=nn;++j)if(b[j]>b[id])id=j;
    320 					ans+=(1<<i)-b[id];
    321 					b[id]=0;
    322 				}
    323 				else for(int j=1;j<=nn;++j)b[j]&=~(1<<i);
    324 			}
    325 			printf("%lld\n",ans);
    326 		}
    327 	}
    328 }
    329 ```
    330 
    331 [2165D — Path Split](https://codeforces.com/contest/2165/problem/D)
    332 
    333 idea & solution: [le0n](/profile/le0n "Legendary Grandmaster le0n")
    334 
    335 Some participants mentioned that similar ideas have appeared recently, we did not know of this.
    336 
    337 This problem was initially proposed with a Hall-dp solution, also with complexity $O(n)$, but testers told us of a simpler greedy solution.
    338 
    339 **Hint 1**
    340 
    341 Reduce the problem to bipartite matching.
    342 
    343 **Hint 2**
    344 
    345 Devise a greedy algorithm to solve the matching problem, and prove it (or not).
    346 
    347 **Tutorial**
    348 
    349 The problem can be formulated as a minimum path cover, which in turn can be converted into a bipartite matching problem:
    350 
    351 * For each element in $a$, create both a left side vertex and a right side vertex, each left side vertex with value $a_i$ can match right side vertices with index larger than $i$, and with value $a_i-1$ or $a_i+1$.
    352 
    353 It can be observed that the graph can be partitioned into two unconnected components by parity.
    354 
    355 A certain intuition the matching for $a_i=1$ stricter than $a_i=3$, maybe we can try just letting the $a_i=1$ greedily choose the next element, and just believe that it will work out.
    356 
    357 Therefore, we can propose a greedy algorithm: we iterate values $v$ from small to large, for every vertex with value $v$ on the left side, if it is unmatched, we match it with a $v+1$ on the right side with index closest to it, we do the same for value $v$ vertices on the right side.
    358 
    359 We can prove that this is correct: Consider an element with $a_i=1$, if it did not match the closest $a_i=2$ on the right, we will try to substitute this pair into the final matching.
    360 
    361 Suppose our $a_i=1$ vertex is $A$, the $a_i=2$ vertex on the right is $B$. If we insert $A-B$ into the matching, and discard any preexisting matches with $A$ or $B$, the only case where we our matching size decreases is when $A$ and $B$ are both matched with some $C$ and $D$, respectively.
    362 
    363 It can then be shown by simple reasoning that $C$ and $D$ can be matched, which means our matching size will not be reduced.
    364 
    365 Therefore, we can choose any $a_i=1$ and the closest $a_i=2$, and simply delete them from the graph.
    366 
    367 Thus, the greedy is proved.
    368 
    369 Implementation should be easy. Time Complexity: $O(n\log n)$ or $O(n)$.
    370 
    371 **Tutorial (Hall-dp)**
    372 
    373 Observation: construct a bipartite graph with $2n$ vertices, named $L_1,L_2,\dots,L_n$ and $R_1,R_2,\dots,R_n$. There is an edge between $L_i$ and $R_j$ iff $i \lt j$ and $|a_i-a_j|=1$. The answer to the original problem is $n$ minus the size of the maximum matching of this graph.
    374 
    375 Consider using hall theorem on $L_1,L_2,\dots,L_n$, thus we only need to calculate $\max |S|-|N(S)|$.
    376 
    377 Separate $L$ into $L_{odd}$ and $L_{even}$, which contains all the $L_i$ with odd $a_i$ and vice versa. Let $S_{odd}=S\cap L_{odd}$ and $S_{even}=S\cap L_{even}$ we can see that $|S|-|N(S)|=|S_{odd}|-|N(S_{odd})|+|S_{even}|-|N(S_{even})|$, so we can calculate the two parts separately.
    378 
    379 For $\max |S_{odd}|-|N(S_{odd})|$, if adding an element to $S_{odd}$ doesn't make $N(S_{odd})$ bigger, we can always add it. So we only need to consider $S_{odd}$ that for every odd value $x$, all the elements in $S_{odd}$ with value $x$ forms a suffix of all appearances of $x$ in array $a$.
    380 
    381 We can define $dp_{i,j}$ as the maximum $|S_{odd}|-|N(S_{odd})|$ when only considering elements with value $\leq i$ in $S_{odd}$ and $N(S_{odd})$ (where $i$ is always odd), and the elements with value $i$ forms the suffix starting from position $j$. Since $\sum cnt$ is bounded by $O(n)$, we have a total of $O(n)$ states. The dp transitions between $i$ and $i+2$ can be done easily in linear time, so the total complexity is $O(n)$.
    382 
    383 **Solution**
    384 
    385 ```
    386 #include <bits/stdc++.h>
    387  
    388 using namespace std;
    389  
    390 const int N = 1e6 + 5;
    391 bool vis[N];
    392 int a[N], n;
    393 vector<int> pos[N * 2];
    394 int solve()
    395 {
    396 	int i, p, ans = 0;
    397 	vector<int> tmp;
    398 	for(i = 1; i < 2 * n; i++)
    399 	{
    400 		if(i & 1)
    401 		{
    402 			p = 0;
    403 			for(auto o: pos[i])
    404 			{
    405 				while(p < pos[i + 1].size() && pos[i + 1][p] < o)
    406 					p++;
    407 				if(p < pos[i + 1].size())
    408 					vis[pos[i + 1][p++]] = 1;
    409 			}
    410 		}
    411 		else
    412 		{
    413 			p = pos[i + 1].size();
    414 			reverse(pos[i].begin(), pos[i].end());
    415 			for(auto o: pos[i])
    416 			{
    417 				while(p && pos[i + 1][p - 1] > o)
    418 					p--;
    419 				if(p)
    420 					vis[pos[i + 1][--p]] = 1;
    421 			}
    422 		}
    423 		tmp.clear();
    424 		for(auto o: pos[i + 1])
    425 			if(vis[o])
    426 				ans++;
    427 			else
    428 				tmp.emplace_back(o);
    429 		pos[i + 1] = tmp;
    430 	}
    431 	return ans;
    432 }
    433  
    434 int main()
    435 {
    436 	int t, i, ans;
    437 	scanf("%d", &t);
    438 	while(t--)
    439 	{
    440 		scanf("%d", &n);
    441 		for(i = 1; i <= n; i++)
    442 			scanf("%d", a + i);
    443 		for(i = 1; i <= n; i++)
    444 			vis[i] = 0;
    445 		for(i = 1; i <= 2 * n; i++)
    446 			pos[i].clear();
    447 		for(i = 1; i <= n; i++)
    448 			pos[a[i]].emplace_back(i);
    449 		ans = n - solve();
    450 		reverse(a + 1, a + n + 1);
    451 		for(i = 1; i <= n; i++)
    452 			vis[i] = 0;
    453 		for(i = 1; i <= 2 * n; i++)
    454 			pos[i].clear();
    455 		for(i = 1; i <= n; i++)
    456 			pos[a[i]].emplace_back(i);
    457 		ans -= solve();
    458 		printf("%d\n", ans);
    459 	}
    460 	return 0;
    461 }
    462 ```
    463 
    464 **Solution (Hall-dp)**
    465 
    466 ```
    467 #include <bits/stdc++.h>
    468 
    469 using namespace std;
    470 
    471 const int N = 1e6 + 5, inf = 1e9;
    472 int a[N], lp[N], rp[N], Lp[N], m;
    473 vector<int> pos[N * 2], dp[N * 2], tmp;
    474 int solve()
    475 {
    476 	int i, j, u, v, p;
    477 	dp[1].resize(pos[1].size());
    478 	for(i = 0; i < pos[1].size(); i++)
    479 		dp[1][i] = i;
    480 	for(i = 1; i < m; i += 2)
    481 	{
    482 		u = pos[i].size() - 1;
    483 		v = pos[i + 2].size() - 1;
    484 		tmp.clear();
    485 		tmp.resize(u + 1);
    486 		dp[i + 2].clear();
    487 		dp[i + 2].resize(v + 1);
    488 		for(j = 0; j <= u; j++)
    489 			tmp[j] = dp[i][j] - rp[pos[i][j]];
    490 		for(j = u; j > 0; j--)
    491 			tmp[j - 1] = max(tmp[j - 1], tmp[j]);
    492 		for(j = 0; j <= v; j++)
    493 		{
    494 			p = pos[i + 2][j];
    495 			if(j)
    496 				dp[i + 2][j] = dp[i + 2][j - 1];
    497 			if(Lp[p] < u)
    498 				dp[i + 2][j] = max(dp[i + 2][j], j + tmp[Lp[p] + 1]);
    499 			dp[i + 2][j] = max(dp[i + 2][j], j - lp[p] + dp[i][Lp[p]]);
    500 		}
    501 	}
    502 	return dp[m].back();
    503 }
    504 
    505 int main()
    506 {
    507 	int t, n, i, ans;
    508 	scanf("%d", &t);
    509 	while(t--)
    510 	{
    511 		scanf("%d", &n);
    512 		m = 0;
    513 		ans = n;
    514 		for(i = 1; i <= n; i++)
    515 		{
    516 			scanf("%d", a + i);
    517 			m = max(m, a[i]);
    518 			ans -= 2 * (a[i] & 1);
    519 		}
    520 		m |= 1;
    521 		for(i = 1; i <= m; i++)
    522 			pos[i] = {0};
    523 		for(i = 1; i <= n; i++)
    524 		{
    525 			pos[a[i]].emplace_back(i);
    526 			lp[i] = (a[i] > 1 ? pos[a[i] - 1].size() - 1 : 0);
    527 			rp[i] = (a[i] < m ? pos[a[i] + 1].size() - 1 : 0);
    528 			Lp[i] = (a[i] > 2 ? pos[a[i] - 2].size() - 1 : 0);
    529 		}
    530 		ans += solve();
    531 		reverse(a + 1, a + n + 1);
    532 		for(i = 1; i <= m; i++)
    533 			pos[i] = {0};
    534 		for(i = 1; i <= n; i++)
    535 		{
    536 			pos[a[i]].emplace_back(i);
    537 			lp[i] = (a[i] > 1 ? pos[a[i] - 1].size() - 1 : 0);
    538 			rp[i] = (a[i] < m ? pos[a[i] + 1].size() - 1 : 0);
    539 			Lp[i] = (a[i] > 2 ? pos[a[i] - 2].size() - 1 : 0);
    540 		}
    541 		ans += solve();
    542 		printf("%d\n", ans);
    543 	}
    544 	return 0;
    545 }
    546 ```
    547 
    548 [2165E — Rainbow Branch](https://codeforces.com/contest/2165/problem/E)
    549 
    550 idea & solution: [Flamire](/profile/Flamire "Legendary Grandmaster Flamire")
    551 
    552 Our testers had vastly different opinions on the difficulty on this problems, some were able to solve within 20mins, and others failed to solve within a sufficiently long time. We eventually decided to put it at E, and it seems to have did its work.
    553 
    554 **Hint 1**
    555 
    556 The answer is increasing, try solve for the maximum number of colors for a certain inconvenience $d$.
    557 
    558 **Hint 2**
    559 
    560 Every color is a connected component.
    561 
    562 **Hint 3**
    563 
    564 There exists a diameter-midpoint like structure.
    565 
    566 **Hint 4**
    567 
    568 The optimal answer has a certain structure, try finding it.
    569 
    570 **Tutorial**
    571 
    572 We switch the answer and the parameter, and solve for the maximum number of colors for a given diameter $d$.
    573 
    574 A simple intuition is that each color should be a connected component, this is also easily provable: If some color is not connected, we can choose one of its "outermost" components (a more rigorous definition would be the leaves of the auxiliary tree of its components), and change it to the color of its adjacent component. In doing this, the number of different components is decreased, and our inconvenience has not increased. Therefore, after enough changes, each color will be a connected component.
    575 
    576 The problem asks for a diameter-like value, therefore, we can try to find a diameter-midpoint-like structure:
    577 
    578 * When $d$ is odd, there exists a color component such that the distance to all other vertices does not exceed $\frac{d-1}2$.
    579 * When $d$ is even, there exists a vertex such that the distance to all other vertices does not exceed $\frac d2$.
    580 
    581 Now, observe that we can "push" colors away from the midpoint and out to the leaves, to increase the number of color used, our optimal solution would look something like this:
    582 
    583 ![ ](/predownloaded/12/54/125496eeb0e48ca5847492df46c65a8dddf79702.png)
    584 
    585 Therefore, the optimal solution is:
    586 
    587 * For odd $d$, remove the outermost $(d-1)/2$ levels of leaves.
    588 * For even $d$, remove the outermost $d/2-1$ levels of leaves, and choose a maximum degree vertex in the remaining tree.
    589 
    590 Time Complexity: $O(n\log n)$ or $O(n)$.
    591 
    592 **Solution**
    593 
    594 ```
    595 #include <bits/stdc++.h>
    596  
    597 using namespace std;
    598  
    599 const int N = 3e5 + 5;
    600 vector<int> e[N];
    601 int val[N], cnt[N], deg[N], h[N], d;
    602 queue<int> q;
    603 int del(int x)
    604 {
    605 	cnt[deg[x]]--;
    606 	cnt[--deg[x]]++;
    607 	return deg[x];
    608 }
    609  
    610 int main()
    611 {
    612 	int t, n, i, u, v, k, c;
    613 	scanf("%d", &t);
    614 	while(t--)
    615 	{
    616 		scanf("%d", &n);
    617 		for(i = 1; i <= n; i++)
    618 			e[i].clear();
    619 		for(i = 1; i < n; i++)
    620 		{
    621 			scanf("%d%d", &u, &v);
    622 			e[u].emplace_back(v);
    623 			e[v].emplace_back(u);
    624 		}
    625 		for(i = 0; i <= n; i++)
    626 		{
    627 			val[i] = 1e9;
    628 			cnt[i] = 0;
    629 			h[i] = 1;
    630 		}
    631 		for(i = 1; i <= n; i++)
    632 			cnt[deg[i] = e[i].size()]++;
    633 		for(i = 1; i <= n; i++)
    634 			if(deg[i] == 1)
    635 				q.push(i);
    636 		c = 0;
    637 		d = n;
    638 		while(!cnt[d])
    639 			d--;
    640 		val[1] = min(val[1], 1);
    641 		val[d] = min(val[d], 2);
    642 		while(!q.empty())
    643 		{
    644 			k = q.front();
    645 			q.pop();
    646 			for(auto o: e[k])
    647 				if(del(o) == 1)
    648 				{
    649 					h[o] = h[k] + 1;
    650 					q.push(o);
    651 				}
    652 			++c;
    653 			while(!cnt[d])
    654 				d--;
    655 			val[c + 1] = min(val[c + 1], 2 * h[k] + 1);
    656 			val[c + d] = min(val[c + d], 2 * h[k] + 2);
    657 		}
    658 		for(i = n - 1; i >= 1; i--)
    659 			val[i] = min(val[i], val[i + 1]);
    660 		for(i = 1; i < n; i++)
    661 			printf("%d ", val[i]);
    662 		printf("\n");
    663 	}
    664 	return 0;
    665 }
    666 ```
    667 
    668 [2165F — Arctic Acquisition](https://codeforces.com/contest/2165/problem/F)
    669 
    670 idea & solution: [Flamire](/profile/Flamire "Legendary Grandmaster Flamire")
    671 
    672 No, we did not propose a paper problem. We knew of the paper on permutation pattern matching in advance, but we assumed the paper would not help much in solving the problem, either due to coding complexity, or constants hidden by the notation that would make it impractical. I'll admit that I did not read the paper in full (procrastination), but from what I gathered, it seemed that understanding the paper would be harder than solving the problem in itself.
    673 
    674 If I am mistaken, please let me know.
    675 
    676 **Hint 1**
    677 
    678 We only need to calculate the minimum $r$ for each $l$, try breaking $21435$ into smaller parts.
    679 
    680 **Hint 2**
    681 
    682 When we fix the $21$-part, we need to append a $435$-part such that $val_3 \gt val_2$, and $index_4 \gt index_1$. (Here the footnotes refer to the value order, rather than index order.)
    683 
    684 Therefore, we need to find $435$-subsequences that are Left-Right-Min minimal, that is, there does not exist another $435$-subsequence that is better in all three aspects.
    685 
    686 **Hint 3**
    687 
    688 The number of such $435$-subsequences is small. Try analyzing what kind of subsequence are minimal.
    689 
    690 **Hint 4**
    691 
    692 Perform scanline on the value of "$3$" from large to small, at most one $435$ will be added each time.
    693 
    694 **Tutorial**
    695 
    696 It suffices to find the minimal $r$ such that $[l,r]$ contains a $21435$-avoiding subsequence for every $l$.
    697 
    698 We will refer to the elements by value order, instead of index order, in the following text, i.e. "$2$"-element refers to the leftmost element, with the second smallest value.
    699 
    700 When we have fixed $l$, the "$2$"-element will be fixed, the "$1$"-element will just be the next element that is smaller than it, therefore, we only need to append a $435$-subsequence to it.
    701 
    702 As we need to minimize $r$, and $val_3 \gt val_2,index_4 \gt index_1$ should be satisfied, we will need to consider all Left-Right-Min minimal $435$'s, that is, the ones where there does not exist another $435$ that is better in all three aspects.
    703 
    704 To analyze this, we can try performing scanline on the $val_3$ from large to small, we can perform some substitutions to reduce the number of $435$'s we need to consider.
    705 
    706 Through this, we can find a surprisingly strong restriction on minimal $435$'s: For each $i$ being considered as the "$3$"-element, the "$5$"-element must be $nxt(i)$, the closest element to the right of $i$, with value greater than $a_i$.
    707 
    708 We perform substitutions as follows:
    709 
    710 ![ ](/predownloaded/0c/f3/0cf36d8c5e3c93c6c85a8ac91ef191898bf411ac.png)
    711 
    712 The three cases corresponds to:
    713 
    714 * Left: $val_5 \lt val_{nxt(i)}$, by definition, $index_5 \gt index_{nxt(i)}$, substitute "$5$" by $nxt(i)$.
    715 * Middle: $val_5 \gt val_{nxt(i)},val_4 \lt val_{nxt(i)}$, substitute "$5$" by $nxt(i)$.
    716 * Right: $val_5 \gt val_{nxt(i)},val_4 \gt val_{nxt(i)}$, substitute $i$ by $nxt(i)$.
    717 
    718 When "$3$" and "$5$" are fixed, "$4$" is also fixed. Therefore, there are at most $n$ minimal $435$'s, and they can be found by simple data structure techniques.
    719 
    720 After finding the minimal $435$'s, the problem can be reduced to simple 2D-queries.
    721 
    722 Time Complexity: $O(n\log n)$.
    723 
    724 **Solution**
    725 
    726 ```
    727 #include <bits/stdc++.h>
    728 #define N 1000011
    729 using namespace std;
    730 int T,n,a[N],id[N];
    731 int R[N];
    732 struct sgt
    733 {
    734 	int D,mx[N*4];
    735 	int query(int l,int r)
    736 	{
    737 		l+=D-1;r+=D+1;int ans=0;
    738 		while(l^r^1)
    739 		{
    740 			if(!(l&1))ans=max(ans,mx[l^1]);
    741 			if(r&1)ans=max(ans,mx[r^1]);
    742 			l>>=1;r>>=1;
    743 		}
    744 		return ans;
    745 	}
    746 	void modi(int k,int p)
    747 	{
    748 		k+=D;mx[k]=p;
    749 		while(k>>=1)mx[k]=max(mx[k<<1],mx[k<<1|1]);
    750 	}
    751 	void clear()
    752 	{
    753 		D=1;while(D<=n+10)D<<=1;
    754 		for(int i=0;i<D+D;++i)mx[i]=0;
    755 	}
    756 }T1,T2;
    757 int pl[N],res[N],curr[N];
    758 int Rmn[N];
    759 void proc()
    760 {
    761 	for(int i=1;i<=n;++i)R[i]=Rmn[i]=i+1,id[a[i]]=i,pl[i]=0;
    762 	for(int i=n;i;--i)while(R[i]<=n&&a[R[i]]<a[i])R[i]=R[R[i]];
    763 	for(int i=n;i;--i)while(Rmn[i]<=n&&a[Rmn[i]]>a[i])Rmn[i]=Rmn[Rmn[i]];
    764 	T1.clear();
    765 	for(int i=1;i<=n;++i)
    766 	{
    767 		if(R[i]<=n)
    768 		{
    769 			int k=T1.query(a[i]+1,a[R[i]]-1);
    770 			pl[i]=k;
    771 		}
    772 		T1.modi(a[i],i);
    773 	}
    774 	T2.clear();
    775 	for(int i=1;i<=n;++i)curr[i]=res[i]=0;
    776 	for(int i=n;i;--i)
    777 	{
    778 		int x=id[i],y=Rmn[x];
    779 		if(y<=n)
    780 		{
    781 			int rr=n+1-T2.query(y+1,n);
    782 			if(rr<=n)res[rr]=max(res[rr],x);
    783 		}
    784 		if(pl[x])T2.modi(pl[x],curr[pl[x]]=max(curr[pl[x]],n+1-R[x]));
    785 	}
    786 	for(int i=1;i<=n;++i)res[i]=max(res[i],res[i-1]);
    787 }
    788 int main()
    789 {
    790 	scanf("%d",&T);while(T--)
    791 	{
    792 		scanf("%d",&n);
    793 		for(int i=1;i<=n;++i)scanf("%d",a+i);
    794 		proc();
    795 		long long ans=0;
    796 		for(int i=1;i<=n;++i)ans+=res[i];
    797 		printf("%lld\n",ans);
    798 	}
    799 }
    800 ```