codeforces-scrape

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

1566.md (41653B)


      1 Source: https://codeforces.com/blog/entry/94803
      2 
      3 We hope that you enjoyed the contest. Let's get right into the editorial:
      4 
      5 **A: Median Maximization**
      6 
      7 [1566A - Median Maximization](/contest/1566/problem/A "Codeforces Global Round 16")
      8 
      9 **First solution**
     10 
     11 **Hint 1**
     12 
     13 Which numbers smaller than the median should be taken?
     14 
     15 **Hint 2**
     16 
     17 Which numbers bigger than the median should be taken?
     18 
     19 **Hint 3**
     20 
     21 Greedy algorithm.
     22 
     23 **Editorial**
     24 
     25 Let's consider the array of $n$ elements in non-decreasing order. We can make numbers before the median equal to zero, after that we have $m = \lfloor {\frac{n}{2}} \rfloor + 1$ numbers, which sum should be $n$ and the minimal of them (i.e. median value) should be maximized.
     26 
     27 To do so, it is enough to make all these numbers equal $\lfloor {\frac{s}{m}} \rfloor$, and then add what's left to the last number ($s \bmod m$). It's easy to see that such array matches all the conditions and it is impossible to make median greater.
     28 
     29 **Implementation (C++, shishin)**
     30 
     31 ```
     32 #include <bits/stdc++.h>
     33 using namespace std;
     34 
     35 int main() {
     36     int T;
     37     cin >> T;
     38     while (T --> 0) {
     39         int n, s;
     40         cin >> n >> s;
     41         int m = n / 2 + 1;
     42         cout << s / m << '\n';
     43     }
     44     return 0;
     45 }
     46 ```
     47 
     48 **Implementation (Python 3, shishin)**
     49 
     50 ```
     51 t = int(input())
     52 for test in range(t):
     53     n, s = map(int, input().split())
     54     m = n // 2 + 1
     55     print(s // m)
     56 ```
     57 
     58 **Second solution**
     59 
     60 **Hint 1**
     61 
     62 If it's possible to make the median element $m \gt 1$ then you can make it $m - 1$.
     63 
     64 **Hint 2**
     65 
     66 It is possible to make the median element any number from $0$ to some $M$.
     67 
     68 **Hint 3**
     69 
     70 We can use the binary search for the answer.
     71 
     72 **Editorial**
     73 
     74 Let's run a binary search for the answer. This will work because if the answer $M$ then we can decrease the median element by $d$ and add $d$ to the max element, so we can get any median element from $1$ to $M$, but we can't get more than $M$. In the binary search we will use the greedy technique. All numbers less than the median can be $0$ and all numbers from the median should be at least $M$. So there are $m = \lfloor {\frac{n}{2}} \rfloor + 1$ numbers and each of them should be at least $M$ and we find the $M$ using the binary search. Number $M$ is reachable if $M \cdot m \leq s$ because we can add $s - M \cdot m$ to the maximal number and the median will be $M$. Otherwise, the median element can not be $M$.
     75 
     76 **Implementation (C++, shishin)**
     77 
     78 ```
     79 #include <bits/stdc++.h>
     80 using namespace std;
     81 
     82 int main() {
     83     int T;
     84     cin >> T;
     85     while (T --> 0) {
     86         long long n, s;
     87         cin >> n >> s;
     88         long long L = 0, R = s + 1;
     89         while (R - L > 1) {
     90             long long M = (L + R) / 2;
     91             long long m = n / 2 + 1;
     92             if (m * M <= s) {
     93                 L = M;
     94             } else {
     95                 R = M;
     96             }
     97         }
     98         cout << L << '\n';
     99     }
    100     return 0;
    101 }
    102 ```
    103 
    104 **Implementation (Python, shishin)**
    105 
    106 ```
    107 t = int(input())
    108 for test in range(t):
    109     n, s = map(int, input().split())
    110     L = 0
    111     R = 10**10
    112     while R - L > 1:
    113         M = (L + R) // 2
    114         m = n // 2 + 1
    115         if m * M <= s:
    116             L = M
    117         else:
    118             R = M
    119     print(L)
    120 ```
    121 
    122 **B: MIN-MEX Cut**
    123 
    124 [1566B - MIN-MEX Cut](/contest/1566/problem/B "Codeforces Global Round 16")
    125 
    126 **Hint 1**
    127 
    128 The answer is never greater than $2$.
    129 
    130 **Hint 2**
    131 
    132 If a string consists only of $1$, then the answer is $0$.
    133 
    134 **Hint 3**
    135 
    136 If all zeroes are consequent, then the answer is $1$.
    137 
    138 **Editorial**
    139 
    140 The answer is never greater than $2$, because $\text{MEX}$ of the whole string is not greater than $2$.
    141 
    142 The answer is $0$ only if there are no zeroes in the string.
    143 
    144 Now we need to understand, when the answer is $1$ or when it is $2$. The sum of $\text{MEX}$ is $1$ only if all zeroes create a single segment without ones. Then we can cut this segment out, its $\text{MEX}$ is $1$, everything else is ones, their total $\text{MEX}$ is $0$.
    145 
    146 If the zeroes do not create a single segment without ones, the there are two such zeroes that there is a $1$ between them. Then either these zeroes are in a single segment with the $1$, so total $\text{MEX}$ is not less than $2$ or these zeroes are in different segments and the answer is still not less then $2$.
    147 
    148 **Implementation (C++, shishin)**
    149 
    150 ```
    151 #include <bits/stdc++.h>
    152 using namespace std;
    153 
    154 int main() {
    155     int T;
    156     cin >> T;
    157     while (T --> 0) {
    158         string s;
    159         cin >> s;
    160         int zeroes = count(s.begin(), s.end(), '0');
    161         if (zeroes == 0) {
    162             cout << 0 << '\n';
    163             continue;
    164         }
    165         int first = s.find('0');
    166         int last = s.rfind('0');
    167         if (last - first + 1 == zeroes) {
    168             cout << 1 << '\n';
    169         } else {
    170             cout << 2 << '\n';
    171         }
    172     }
    173     return 0;
    174 }
    175 ```
    176 
    177 **Implementation (Python, shishin)**
    178 
    179 ```
    180 t = int(input())
    181 for test in range(t):
    182     s = input()
    183     zeroes = s.count('0')
    184     if zeroes == 0:
    185         print(0)
    186         continue
    187 
    188     first = s.find('0')
    189     last = s.rfind('0')
    190     if last - first + 1 == zeroes:
    191         print(1)
    192     else:
    193         print(2)
    194 ```
    195 
    196 **C: MAX-MEX Cut**
    197 
    198 [1566C - MAX-MEX Cut](/contest/1566/problem/C "Codeforces Global Round 16")
    199 
    200 **First solution**
    201 
    202 **Hint 1**
    203 
    204 You can cut out the columns with both $0$ and $1$.
    205 
    206 **Hint 2**
    207 
    208 Now in each column there are only $0$ or only $1$. We only need to solve the problem for a string because the columns can be replaced by one digit (they consist of equal elements).
    209 
    210 **Hint 3**
    211 
    212 Let's be greedy, to each zero we will "join" not more than one $1$.
    213 
    214 **Editorial**
    215 
    216 Let's solve the same problem but for a string:
    217 
    218 It's needed to cut a binary string into segments so that each its element is in exactly one segment and the sum of $\text{MEX}$ for all segments is maximal.
    219 
    220 Initially we will say that the string is cut into segments of length 1. Then the answer is the number of zeroes in the string. After that the answer is increased every time we merge a segment of $0$ with a segment of $1$. Each such merge increases the answer by $1$. Let's make the merges greedily, maximizing the number of merges. Let's consider the first zero. If the previous element is a $1$, let's merge them and consider the next zero. Else, if the next element is a $1$, let's merge them and consider the next zero. Else, the next element is a zero and we should consider it instead of the current zero the same way. By doing so we get the answer as the number of zeroes + the number of merges.
    221 
    222 Now let's solve the initial problem. We can cut out the columns that contain both $0$ and $1$, because their $\text{MEX}$ is already maximized and the answer will not become worse.
    223 
    224 Now we solve the problem for all remaining bi-tables independently. Each their column consists either only of $0$ or only of $1$ so both rows are equal. We will solve the problem for one row of each remaining bi-table as mentioned before and then sum up the values to get the answer.
    225 
    226 **Implementation (C++, shishin)**
    227 
    228 ```
    229 #include <bits/stdc++.h>
    230 using namespace std;
    231 
    232 int solve(string s) {
    233     int ans = count(s.begin(), s.end(), '0');
    234     int n = s.size();
    235     bool a = false, b = false;
    236     for (int i = 0; i < n; ++i) {
    237         if (s[i] == '0') a = true;
    238         if (s[i] == '1') b = true;
    239         if (a && b) {
    240             ++ans;
    241             a = b = false;
    242         }
    243     }
    244     return ans;
    245 }
    246 
    247 int main() {
    248     ios_base::sync_with_stdio(false);
    249     cin.tie(nullptr);
    250     cout.tie(nullptr);
    251     int T;
    252     cin >> T;
    253     while (T --> 0) {
    254         int n, ans = 0;
    255         string a, b;
    256         cin >> n >> a >> b;
    257         string s = "";
    258         for (int i = 0; i < n; ++i) {
    259             if (a[i] != b[i]) {
    260                 ans += 2 + solve(s);
    261                 s = "";
    262             } else {
    263                 s += a[i];
    264             }
    265         }
    266         cout << ans + solve(s) << '\n';
    267     }
    268     return 0;
    269 }
    270 ```
    271 
    272 **Second solution (two similar solutions)**
    273 
    274 This problem could be solved in many ways using the dp. We will consider these solutions in short.
    275 
    276 Let's say that $dp_i$ — is the answer for a prefix until $i$. Then there are different approaches:
    277 
    278 We can calculate the dp values, iterating through all possible $\operatorname{MEX}$ values on the last segment. For example, if we want to make $\operatorname{MEX}$ equal $2$ on the last segment, then we need to find the closest $0$ and the closest $1$ to position $i$. Let it be $last_0$ and $last_1$. Then we should recalc the dp like this $dp_i = \max(dp_i, dp_{j-1} + 2)$, where $j = \min(last_0, last_1)$, because we take the shortest segment ending in $i$ which has both $0$ and $1$ and after that we add the answer for this segment and for prefix that ends in $j-1$.
    279 
    280 **Implementation(C++, kpw29)**
    281 
    282 ```
    283 #include <bits/stdc++.h>
    284 using namespace std;
    285 #define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
    286 #define rep(i, l, r) for(int i = (l); i < (r); ++i)
    287 typedef vector<int> vi;
    288 
    289 //Did you REAALLY consider sample tests?
    290 void solve(int tc) {
    291     string s[2];
    292     int n;
    293     cin >> n;
    294     cin >> s[0] >> s[1];
    295     vi dp(n + 1, 0);
    296     vi last(2, -1);
    297     
    298     auto take = [&](int i, bool take0, bool take1) {
    299         int MEX = 0;
    300         if (take0) {
    301             if (take1) MEX = 2;
    302             else MEX = 1;
    303         }
    304         
    305         int index = i;
    306         if (take0) index = min(index, last[0]);
    307         if (take1) index = min(index, last[1]);
    308         
    309         if (index != -1) return MEX + dp[index - 1];
    310         return -100000;
    311     };
    312     
    313     FOR(i, 1, n) {
    314         vi val(2);
    315         rep(j, 0, 2) last[s[j][i-1] - '0'] = i;
    316         dp[i] = dp[i-1];
    317         dp[i] = max(dp[i], take(i, 1, 0));
    318         dp[i] = max(dp[i], take(i, 0, 1));
    319         dp[i] = max(dp[i], take(i, 1, 1));
    320     }
    321     
    322     cout << dp[n] << "\n";
    323 }
    324  
    325 int main() {
    326     int tests;
    327     cin >> tests;
    328     FOR(test, 1, tests) {
    329         solve(test);
    330     }
    331 }
    332 ```
    333 
    334 Another possible solution with dp is based on the fact that we should not take any segments with length more than $x$, where $x$ is some small number. We can just take some random big enough $x$ and not prove anything. There exists a solution which does not consider segments with length bigger than $5$.
    335 
    336 **Implementation (C++, physics0523)**
    337 
    338 ```
    339 #include<bits/stdc++.h>
    340  
    341 using namespace std;
    342  
    343 int mex(string s){
    344   int fl=0;
    345   for(auto &nx : s){
    346     if(nx=='0'){fl|=1;}
    347     else if(nx=='1'){fl|=2;}
    348   }
    349   if(fl==3){return 2;}
    350   if(fl==1){return 1;}
    351   return 0;
    352 }
    353  
    354 int main(){
    355   ios::sync_with_stdio(false);
    356   cin.tie(nullptr);
    357   int t;
    358   cin >> t;
    359   while(t>0){
    360     t--;
    361     int n;
    362     string s1,s2;
    363     cin >> n >> s1 >> s2;
    364     vector<int> dp(n+1,0);
    365     for(int i=0;i<n;i++){
    366       string s;
    367       for(int j=0;j<5;j++){
    368         if(i+j>=n){break;}
    369         s.push_back(s1[i+j]);
    370         s.push_back(s2[i+j]);
    371         dp[i+j+1]=max(dp[i+j+1],dp[i]+mex(s));
    372       }
    373     }
    374     cout << dp[n] << '\n';
    375   }
    376   return 0;
    377 }
    378 ```
    379 
    380 **D: Seating Arrangements**
    381 
    382 [1566D2 - Seating Arrangements (hard version)](/contest/1566/problem/D2 "Codeforces Global Round 16")
    383 
    384 **Hint 1**
    385 
    386 Each person can be seated on some subsegment of places with people with the same level of sight.
    387 
    388 **Hint 2**
    389 
    390 If $n=1$ we should seat people on the maximal possible place.
    391 
    392 **Hint 3**
    393 
    394 The places available for some person may be a subsegment of a row or a suffix of a row + some full rows + a prefix of a row.
    395 
    396 **Editorial**
    397 
    398 Let's consider all seats in increasing order of their indices. For each seat we can consider the level of sight of a person that takes that seat. The considered sequence is non-decreasing. This means that people with the same level of sight should take consequent seats and for each level of sight $x$ we can determine which seats will be taken by people with level of sight $x$.
    399 
    400 Now we should find out how do people with level of sight $x$ sit in the cinema. For that $x$ we know that people with that level of sight should take places with indices from $l$ to $r$.
    401 
    402 Let's seat people with the same level of sight greedily. If all places from $l$ to $r$ are in the same row, then we should seat people in decreasing order of seat indices. Otherwise, these seats form a suffix of some row (maybe empty), some full rows (maybe zero), a prefix of some row (maybe empty). Firstly we need to seat people on the suffix in decreasing order of seat indices. This is not worse than other seatings, because the seats before that suffix may be taken in future and total inconvenience will increase. Seats on the prefix should be taken last of all in decreasing order of seat indices. This is not worse than other seatings, because if some people sit on that prefix then they will bother people on the right, increasing the total inconvenience. Full rows should be taken in decreasing order of seat indices, this does not increase the total inconvenience at all. So we should start by seating poeple on the suffix, then we should cover full rows and finally we should cover the prefix. In each case places should be taken in decreasing order of seat indices.
    403 
    404 The constraints for $m$ are low, so each time we want to seat someone we can consider all places in the row and find how many people increase our inconvenience.
    405 
    406 **Implementation (C++, pashka)**
    407 
    408 ```
    409 #include <bits/stdc++.h>
    410 #define long long long int
    411 using namespace std;
    412  
    413 // @author: pashka
    414  
    415 void solve_test() {
    416     int n, m;
    417     cin >> n >> m;
    418     vector<pair<int, int>> a(n * m);
    419     for (int i = 0; i < n * m; i++) {
    420         cin >> a[i].first;
    421         a[i].second = i;
    422     }
    423     sort(a.begin(), a.end());
    424     for (int i = 0; i < n * m; i++) {
    425         a[i].second = -a[i].second;
    426     }
    427     int res = 0;
    428     for (int i = 0; i < n; i++) {
    429         sort(a.begin() + (m * i), a.begin() + (m * i + m));
    430         for (int j = 0; j < m; j++) {
    431             for (int k = 0; k < j; k++) {
    432                 if (a[i * m + k].second > a[i * m + j].second) res++;
    433             }
    434         }
    435     }
    436     cout <<res << "\n";
    437 }
    438  
    439 int main() {
    440     ios::sync_with_stdio(false);
    441  
    442     int n;
    443     cin >> n;
    444     for (int i = 0; i < n; i++) {
    445         solve_test();
    446     }
    447  
    448     return 0;
    449 }
    450 ```
    451 
    452 **E: Buds Re-hanging**
    453 
    454 [1566E - Buds Re-hanging](/contest/1566/problem/E "Codeforces Global Round 16")
    455 
    456 **Hint 1**
    457 
    458 Re-hanging a bud to a leaf decreases the total amount of leaves by $1$.
    459 
    460 **Hint 2**
    461 
    462 Buds can be re-hanged that way so in the end there is only a root, buds that are connected to the root and leaves connected to the root or to the buds.
    463 
    464 **Hint 3**
    465 
    466 Now the answer depends only on the total amount of vertices, on the amount of buds and on the fact whether there is a leaf connected to the root or not.
    467 
    468 **Editorial**
    469 
    470 If we re-hang a bud from its parent to the root, the amount of leaves either doesn't change (if the parent has other children), or increases by $1$. By doing that we don't make the answer worse, because if there are leaves except for bud's leaves, then we can re-hang the bud to some leaf, decreasing the amount of leaves by $1$. So let's re-hang all buds to the root, until there are no free buds left.
    471 
    472 Now we will assume that all buds are hung to the root, and their amount is $k$. The answer is either $n - 2 \cdot k$ if there is no leaf, hung to the root, or $n - 2 \cdot k - 1$ if there is a leaf, hung to the root. Why is it so? Initially, there are $n - k - 1$ leaves (total amount of nodes — the amount of buds — root). If there is a leaf, hung to the root, then we can hang a bud to it, then hang a bud to the previous bud's leaf, and keep doing so until we use all $k$ buds. Then there are $k$ re-hangs, each of them decreases the answer by $1$. So the final answer is $n - k - 1 - k = n - 2 \cdot k - 1$. If there is no leaves hung to the root, then we can hang a bud to another bud's leaf, then a bud to the previous bud's leaf, and so on until we use $k - 1$ buds. The final answer in this case is $n - k - 1 - (k - 1) = n - 2 \cdot k$. It is not possible to make the answer less, because each re-hang decreases the answer by \le 1 and each re-hang we make decreases it exactly by 1 and we use all re-hangs.
    473 
    474 **Implementation (C++, shishin)**
    475 
    476 ```
    477 #include <bits/stdc++.h>
    478 using namespace std;
    479 
    480 vector<vector<int>> g;
    481 vector<int> type; // -1  -- default, 0 -- root, 1 -- leaf, 2 -- bud
    482 
    483 void dfs(int v, int p) {
    484     bool leaves = false;
    485     for (auto to : g[v]) {
    486         if (to == p) continue;
    487         dfs(to, v);
    488         if (type[to] == 1) leaves = true;
    489     }
    490     if (v != p) {
    491         if (!leaves) type[v] = 1;
    492         else type[v] = 2;
    493     }
    494 }
    495 
    496 int main() {
    497     ios_base::sync_with_stdio(false);
    498     cout.tie(0);
    499     cin.tie(0);
    500     int T;
    501     cin >> T;
    502     while (T --> 0) {
    503         int n;
    504         cin >> n;
    505         g.assign(n, vector<int>());
    506         type.assign(n, -1);
    507         for (int i = 0; i < n - 1; ++i) {
    508             int x, y;
    509             cin >> x >> y;
    510             --x; --y;
    511             g[x].emplace_back(y);
    512             g[y].emplace_back(x);
    513         }
    514         type[0] = 0;
    515         dfs(0, 0);
    516         bool root_leaf = false;
    517         for (auto v : g[0]) {
    518             if (type[v] == 1) {
    519                 root_leaf = true;
    520             }
    521         }
    522         int k = 0;
    523         for (int i = 0; i < n; ++i) {
    524             k += (type[i] == 2);
    525         }
    526         cout << n - 2 * k - root_leaf << '\n';
    527     }
    528     return 0;
    529 }
    530 ```
    531 
    532 **F: Points Movement**
    533 
    534 [1566F - Points Movement](/contest/1566/problem/F "Codeforces Global Round 16")
    535 
    536 **Hint 1**
    537 
    538 If a segment already contains a point then it can be thrown out of the consideration.
    539 
    540 **Hint 2**
    541 
    542 If there is a segment that contains some segment, we can save only the smaller one.
    543 
    544 **Hint 3**
    545 
    546 If you already know which segments will be visited by some point, how you should calculate the answer for this point?
    547 
    548 **Hint 4**
    549 
    550 For some segment, which points should visit it?
    551 
    552 **Editorial**
    553 
    554 Firstly, if a point has initially visited some segment, then we can throw it out of consideration. It means that all segments that cover at least one point can be thrown out. This can be done using the binary search for each segment separately.
    555 
    556 Secondly, if a segment $A$ is contained in a segment $B$ (i.e. $l_B \le l_A \le r_A \le r_B$), then a point that visited $A$ will visit $B$, too. It means that we should save only those segments that do not contain any other segments.
    557 
    558 This can be done using a Fenwick tree. Initially, all values in the tree are zeroes. We will consider the segments in decreasing order of $l$. Let's assume we are considering segment $i$. If there is an already considered segment $j$ $(r_j \le r_i)$, then segment $j$ is in segment $i$. It is so because $l_i \le l_j$ because of the considering order, so $l_i \le l_j \le r_j \le r_i$. To find the amount of such $j$ it is enough to find the amount of $1$ on a prefix until $r_i$ in the Fenwick tree. Now when we considered the segment $i$ we set $1$ in the Fenwick tree on position $r_i$.
    559 
    560 After that there are only segments that do not contain any other segments and they are not initially visited by any point. We will consider only these segments.
    561 
    562 Let's say that a segment is assigned to a point if that point visits this segment. Let's find out how to calculate the answer for one point if we already know the set of segments that are assigned to it. Let's consider the segments that are on the left to the point and say that the maximal distance from the point to these segments is $a$. In the same way let $b$ be the maximal distance from the point to the segments on the right. Then the answer for the point is $2\cdot min(a, b)+max(a, b)$.
    563 
    564 Now if a segment is between two neighbouring points, then it should be assigned to one of these points. (If a segment is to the left from the leftmost point or to the right from the rightmost point then it should be assigned to the leftmost point or to the rightmost point respectively). Now let's consider the segments between two neighbouring points. These segments are ordered by the left ends and by the right ends at the same time. Some prefix of these segments should be assigned to the left point, other segments (suffix) should be assigned to the right point.
    565 
    566 Now let's solve the problem using the dynamic programming. Let $dp[i][j]$ be the answer if we assigned the segments for first $i$ points and there are $j$ segments assigned to the $i$-th point that are to the right from it. There is a linear amount of dp states. Let's learn to calculate the dp. We will consider the dp states in increasing order of $i$ and, after that, $j$. Let $b$ be the distance from $i$-th point to $j$ segment after it. Then $dp[i][j]=\displaystyle\min_{0 \le k \le x} \Big(dp[i-1][k]+2\cdot min(b, a_{i, k})+max(b, a_{i, k})\Big)$, where $a_{i, k}$ — is the distance from $i$-th point to $(k+1)$-th segment after $(i-1)$-th point and $x$ is the amount of segments between points $i$ and $(i+1)$. But this is a quadratic dp. Now we can find out that for some prefix of segments after $(i-1)$-th point $a_{i, k}$ is greater than $b$ and for some suffix it is less than $b$. The length of that prefix may be found using the binary search or two pointers. For $k$ on that prefix the dp will be $dp[i-1][k] + x_i - r_{k+1}+2\cdot b$, and for $k$ on the suffix — $dp[i-1][k] + 2\cdot(x_i - r_{k+1})+b$. In these formulas everything except $b$ depends on $i$ and $k$. It means that we can calculate dp quickly using prefix and suffix minimums.
    567 
    568 The answer is $dp[n][x]$, where $x$ is the amount of segments to the right of the rightmost point.
    569 
    570 **Implementation (C++, Artyom123)**
    571 
    572 ```
    573 #include <bits/stdc++.h>
    574 
    575 using namespace std;
    576 
    577 #define pb emplace_back
    578 #define all(x) (x).begin(), (x).end()
    579 #define fi first
    580 #define se second
    581 #define pii pair<int, int>
    582 #define ll long long 
    583 
    584 const long long INFLL = 1e18;
    585 const int INF = 1e9 + 1;
    586 
    587 struct segment_tree {
    588     vector<int> t;
    589 
    590     segment_tree(int n) {
    591         t.assign(4 * n, INF);
    592     }
    593 
    594     void mod(int v, int vl, int vr, int id, int val) {
    595         if (vr - vl == 1) {
    596             t[v] = min(t[v], val);
    597             return;
    598         }
    599         int vm = (vl + vr) / 2;
    600         if (id < vm) mod(2 * v + 1, vl, vm, id, val);
    601         else mod(2 * v + 2, vm, vr, id, val);
    602         t[v] = min(t[v], val);
    603     }
    604 
    605     int get(int v, int vl, int vr, int l, int r) {
    606         if (vl >= l && vr <= r) return t[v];
    607         if (r <= vl || l >= vr) return INF;
    608         int vm = (vl + vr) / 2;
    609         return min(get(2 * v + 1, vl, vm, l, r), get(2 * v + 2, vm, vr, l, r));
    610     }
    611 };
    612 
    613 bool cmp(const pii &a, const pii &b) {
    614     return a.se - a.fi < b.se - b.fi;
    615 }
    616 
    617 int main() {
    618     ios_base::sync_with_stdio(0);
    619     cin.tie(0);
    620     cout.tie(0);
    621     int t;
    622     cin >> t;
    623     while (t--) {
    624         int n, m;
    625         cin >> n >> m;
    626         vector<ll> a(n);
    627         for (auto &c : a) cin >> c;
    628         sort(all(a));
    629         vector<pii> seg1(m);
    630         vector<int> dl;
    631         for (auto &c : seg1) {
    632             cin >> c.fi >> c.se;
    633             dl.pb(c.fi);
    634         }
    635         sort(all(dl));
    636         dl.resize(unique(all(dl)) - dl.begin());
    637         sort(all(seg1), cmp);
    638         map<int, int> ma;
    639         for (int i = 0; i < (int)dl.size(); i++) ma[dl[i]] = i;
    640         segment_tree tr((int)dl.size());
    641         vector<pii> seg;
    642         for (auto &c : seg1) {
    643             int id = lower_bound(all(a), c.fi) - a.begin();
    644             if (id < (int)a.size() && a[id] <= c.se) continue;
    645             if (tr.get(0, 0, dl.size(), ma[c.fi], dl.size()) <= c.se) continue;
    646             tr.mod(0, 0, dl.size(), ma[c.fi], c.se);
    647             seg.pb(c.fi, c.se);
    648         }
    649         m = seg.size();
    650         sort(all(seg));
    651         vector<vector<pii>> g(n + 1);
    652         int L = -1, R = m;
    653         while (R - L > 1) {
    654             int M = (L + R) / 2;
    655             if (seg[M].se < a[0]) L = M;
    656             else R = M;
    657         }
    658         for (int i = 0; i <= L; i++) g[0].pb(seg[i]);
    659         for (int i = 0; i < n; i++) {
    660             int RIGHT = INF;
    661             if (i + 1 < n) RIGHT = a[i + 1];
    662             int id = upper_bound(all(seg), make_pair((int)a[i], (int)a[i])) - seg.begin();
    663             if (id == m) continue;
    664             int L = id - 1, R = m;
    665             while (R - L > 1) {
    666                 int M = (L + R) / 2;
    667                 if (seg[M].se < RIGHT) L = M;
    668                 else R = M;
    669             }
    670             for (int j = id; j <= L; j++) g[i + 1].pb(seg[j]);
    671         }
    672         vector<vector<ll>> dp(n), pr(n), suff(n);
    673         for (int i = 0; i < n; i++) {
    674             dp[i].resize(g[i + 1].size() + 1, INFLL);
    675             pr[i].resize(g[i + 1].size() + 1, INFLL);
    676             suff[i].resize(g[i + 1].size() + 1, INFLL);
    677         }
    678         for (int j = 0; j <= (int)g[1].size(); j++) {
    679             ll x = 0;
    680             if (g[0].size()) x = a[0] - g[0][0].se;
    681             ll y = 0;
    682             if (j) y = g[1][j - 1].fi - a[0];
    683             dp[0][j] = 2 * min(x, y) + max(x, y);
    684         }
    685         for (int i = 1; i < n; i++) {
    686             for (int j = 0; j <= (int)g[i].size(); j++) {
    687                 if (j > 0) pr[i - 1][j] = pr[i - 1][j - 1];
    688                 pr[i - 1][j] = min(pr[i - 1][j], dp[i - 1][j] - (j == (int)g[i].size() ? a[i] : g[i][j].se));
    689             }
    690             for (int j = (int)g[i].size(); j >= 0; j--) {
    691                 if (j + 1 <= (int)g[i].size()) suff[i - 1][j] = suff[i - 1][j + 1];
    692                 suff[i - 1][j] = min(suff[i - 1][j], dp[i - 1][j] - 2 * (j == (int)g[i].size() ? a[i] : g[i][j].se));
    693             }
    694             int L = (int)g[i].size();
    695             for (int j = 0; j <= (int)g[i + 1].size(); j++) {
    696                 ll y = 0;
    697                 if (j) y = g[i + 1][j - 1].fi - a[i];
    698                 while (L > 0 && a[i] - g[i][L - 1].se <= y) L--;
    699                 if (L > 0) dp[i][j] = min(dp[i][j], 2 * y + a[i] + pr[i - 1][L - 1]);
    700                 dp[i][j] = min(dp[i][j], y + 2 * a[i] + suff[i - 1][L]);
    701             }
    702         }
    703         cout << dp[n - 1].back() << "\n";
    704     }
    705     return 0;
    706 }
    707 ```
    708 
    709 **G: Four Vertices**
    710 
    711 [1566G - Four Vertices](/contest/1566/problem/G "Codeforces Global Round 16")
    712 
    713 **Hint 1**
    714 
    715 The answer always consists either of three edges with common end or of two edges that don't have any common ends.
    716 
    717 **Hint 2**
    718 
    719 To find the answer of the second type you can leave in the graph only those edges that are in the list of three smallest edges for both ends.
    720 
    721 **Hint 3**
    722 
    723 Let's consider those cases when the minimal edge is in the answer or not in the answer.
    724 
    725 **Editorial**
    726 
    727 Observation: the answer always consists either of three edges that have one common end or of two edges that do not have any common ends.
    728 
    729 To find the answer of the first type it is enough to maintain three minimal edges for each vertex.
    730 
    731 To find the answer of the second type we will use this observation: we can leave in the graph only those edges that are in the set of three minimal edges for each their end. Let's prove that. Let's assume that the answer consists of two edges $(a, b)$ and $(c, d)$ and there are at least three edges $(a, a_1)$, $(a, a_2)$, $(a, a_3)$ less than $(a, b)$. Then the edge $(a, b)$ can be swapped by one of these edges because at least one of te integers $a_1$, $a_2$, $a_3$ is not equal to $c$ and $d$. Then we will maintain the set of all these edges.
    732 
    733 Now let's consider two cases. Let $(a, b)$ be the minimal edge. If it is in the answer then we need to find the minimal edge, that does not have any common vertices with $(a, b)$. In this case there are at most $6$ ``bad'' edges because the degrees of each vertex in the graph that consists only of remaining edges do not exceed $3$. It means that we have to consider $O(1)$ variants. If $(a, b)$ is not in the answer, then there are two edges in the answer that have vertices $a$ and $b$ as one of their ends. But there are at most $9$ such pairs of edges, so we have to consider only $O(1)$ variants.
    734 
    735 So the final answer is the minimum of answers of both types.
    736 
    737 **Implementation (C++, Kirill22)**
    738 
    739 ```
    740 #include<bits/stdc++.h>
    741 
    742 using namespace std;
    743 
    744 #define sz(a) (int) (a).size()
    745 
    746 const int N = 1e5;
    747 vector<pair<int, int>> g[N];
    748 map<pair<int, int>, int> cost;
    749 set<pair<int, int>> a[N], b[N];
    750 multiset<long long> dp;
    751 set<pair<int, pair<int, int>>> dp2;
    752 
    753 void solve() {
    754     auto minr = *dp2.begin();
    755     long long ans = 1e18;
    756     if (sz(dp)) {
    757         ans = min(ans, *dp.begin());
    758     }
    759     int v = minr.second.first, u = minr.second.second;
    760     auto it = dp2.begin();
    761     for (int i = 0; i < 6 && it != dp2.end(); i++, it = next(it)) {
    762         auto res = *it;
    763         int v2 = res.second.first, u2 = res.second.second;
    764         if (v2 != v && v2 != u && u2 != v && u2 != u) {
    765             ans = min(ans, (long long) res.first + minr.first);
    766         }
    767     }
    768     for (auto [w, v2] : a[v]) {
    769         for (auto [w2, u2] : a[u]) {
    770             if (v2 != u2 && v2 != u && u2 != v) {
    771                 ans = min(ans, (long long) w + w2);
    772             }
    773         }
    774     }
    775     cout << ans << '\n';
    776 }
    777 
    778 void del(int v) {
    779     if (sz(a[v]) >= 3) {
    780         long long res = 0;
    781         for (auto [w, to] : a[v]) {
    782             res += w;
    783         }
    784         dp.erase(dp.find(res));
    785     }
    786     for (auto [w, to] : a[v]) {
    787         if (dp2.find({w, {min(v, to), max(v, to)}}) != dp2.end()) {
    788             dp2.erase({w, {min(v, to), max(v, to)}});   
    789         }
    790     }
    791 }
    792 
    793 void upd(int v) {
    794     if (sz(a[v]) >= 3) {
    795         long long res = 0;
    796         for (auto [w, to] : a[v]) {
    797             res += w;
    798         }
    799         dp.insert(res);
    800     }
    801     for (auto [w, to] : a[v]) {
    802         if (a[to].find({w, v}) != a[to].end()) {
    803             dp2.insert({w, {min(v, to), max(v, to)}});  
    804         } 
    805     }
    806 }
    807 
    808 void relax(int v) {
    809     while (sz(a[v]) && sz(b[v])) {
    810         auto A = *a[v].rbegin(), B = *b[v].begin();
    811         if (A.first <= B.first) break;
    812         a[v].erase(A);
    813         b[v].erase(B);
    814         a[v].insert(B);
    815         b[v].insert(A);
    816     }
    817     while (sz(a[v]) < 3 && sz(b[v])) {
    818         auto B = *b[v].begin();
    819         b[v].erase(B);
    820         a[v].insert(B);
    821     }
    822 }
    823 
    824 void erase(int v, int u, int w) {
    825     del(v);
    826     del(u);
    827     if (a[v].find({w, u}) != a[v].end()) {
    828         a[v].erase({w, u});
    829     }
    830     else {
    831         b[v].erase({w, u});
    832     }
    833     if (a[u].find({w, v}) != a[u].end()) {
    834         a[u].erase({w, v});
    835     }
    836     else {
    837         b[u].erase({w, v});
    838     }
    839     relax(v);
    840     relax(u);
    841     upd(v);
    842     upd(u);
    843 }
    844 
    845 void add(int v, int u, int w) {
    846     del(v);
    847     del(u);
    848     b[v].insert({w, u});
    849     b[u].insert({w, v});
    850     relax(v);
    851     relax(u);
    852     upd(v);
    853     upd(u);
    854 }
    855 
    856 signed main() {
    857     ios_base::sync_with_stdio(0);
    858     cin.tie(0);
    859     cout.tie(0);
    860     int n, m;
    861     cin >> n >> m;
    862     for (int i = 0; i < m; i++) {
    863         int x, y, w;
    864         cin >> x >> y >> w;
    865         x--, y--;
    866         if (x > y) swap(x, y);
    867         cost[{x, y}] = w;
    868         g[x].push_back({w, y});
    869         g[y].push_back({w, x});
    870     }
    871     for (int i = 0; i < n; i++) {
    872         sort(g[i].begin(), g[i].end());
    873         for (int j = 0; j < sz(g[i]); j++) {
    874             if (j <= 2) {
    875                 a[i].insert(g[i][j]);
    876             }
    877             else {
    878                 b[i].insert(g[i][j]);
    879             }
    880         }
    881         if (sz(a[i]) >= 3) {
    882             long long res = 0;
    883             for (auto [w, to] : a[i]) {
    884                 res += w;
    885             }
    886             dp.insert(res);
    887         }
    888     }
    889     for (int i = 0; i < n; i++) {
    890         for (int j = 0; j < sz(g[i]); j++) {
    891             int v = g[i][j].second;
    892             if (j <= 2) {
    893                 if (a[v].find({g[i][j].first, i}) != a[v].end()) {
    894                     dp2.insert({g[i][j].first, {min(i, v), max(i, v)}});
    895                 }
    896             }
    897         }
    898     }
    899     int q;
    900     cin >> q;
    901     solve();
    902     while (q--) {
    903         int t, v, u;
    904         cin >> t >> v >> u;
    905         v--, u--;
    906         if (v > u) swap(v, u);
    907         if (t == 0) {
    908             int w = cost[{v, u}];
    909             erase(v, u, w);
    910         }
    911         else {
    912             int w;
    913             cin >> w;
    914             cost[{v, u}] = w;
    915             add(v, u, w);
    916         }
    917         solve();
    918     }
    919 }
    920 ```
    921 
    922 **H: Xor-quiz**
    923 
    924 [1566H - Xor-quiz](/contest/1566/problem/H "Codeforces Global Round 16")
    925 
    926 **Hint 1**
    927 
    928 Numbers with the same set of prime divisors may be considered as the same numbers.
    929 
    930 **Hint 2**
    931 
    932 The amount of distinct sets of prime divisors which multiplication does not exceed $C$ for such constraints does not exceed $\lceil 0.65 \cdot C \rceil$.
    933 
    934 **Hint 3**
    935 
    936 How you should find the $xor$ of all numbers that have the same set of prime divisors?
    937 
    938 **Hint 4**
    939 
    940 If you know the $xor$ of all numbers with the same set of prime divisors you can recover these numbers randomly.
    941 
    942 **Editorial**
    943 
    944 Let $f(x)$ be the multiplication of all prime divisors of $x$. Then let's make queries for all such $y$ that there is at least one such $x$, $1 \le x \le C$ and $f(x) = y$. For such constraints there will be at most $\lceil 0.65 \cdot C \rceil$ queries.
    945 
    946 Let's group all numbers by $f(x)$. All numbers in one group in any query will be considered together. Let $ans(x)$ be the answer for the query with number $x$ and $g(x)$ be the $xor$ of all number that are not coprime with $x$. Then $g(x)=ans(x) \oplus ans(1)$. Now let's find out how to calculate the $xor$ of all such $x$ that $f(x)$ is divisible by an arbitrary $y$. Let's take $xor$ of all $g(k)$ where $k$ is a divisor of $y$ greater than $1$. Let's prove that by doing that we will get the needed value. If $f(x)$ is divisible by $y$ then such $x$ will be considered $2^l - 1$ times, where $l$ is the amount of prime divisors of $y$. It means that $x$ will be contained in the final value. Now let's prove that there will be no unintended $x$ values. Let $f(x)$ be not divisible by $y$. It means that there is suche prime $p$ that $y$ is divisible by $p$ and $x$ is not divisible by $p$. Then for each divisor $a$ of $y$ that is divisible by $p$ we will assign $b=a/p$. Then such $x$ will be considered either for both $a$ and $b$ or for none of them. It means that it will be considered an even amount of times. Now to find the $xor$ of all numbers with an arbitrary $f(x)$ we need to consider all $x$ from $C$ to $1$ and make $f(x) = f(x) \oplus f(2x) \oplus f(3x) \oplus \ldots$.
    947 
    948 Now we only need to find $n$ distinct numbers from $1$ to $C$ such that $xor$ of numbers in each group is equal to a specific number. For each group of numbers with given $f(x)$ we will start the Gaussian elimination. Let $k$ be the size of a group and after the Gaussian elimination there are $b$ non-zero numbers. Then if $b=k$ there is a single way to obtain the needed $xor$. Else there are $2^{k-b}$ ways to obtain the needed $xor$. Now let's take some random sets of numbers with the needed $xor$ and calculate dp on these numbers to get take exactly $n$ numbers. If there are several ways we can choose any of them.
    949 
    950 **Implementation (C++, Artyom123)**
    951 
    952 ```
    953 #include <bits/stdc++.h>
    954 
    955 using namespace std;
    956 
    957 #define pb emplace_back
    958 #define all(x) (x).begin(), (x).end()
    959 #define fi first
    960 #define se second
    961 #define pii pair<int, int>
    962 #define ll long long 
    963 #define ld long double
    964 
    965 const long long INFLL = 1e18;
    966 const int INF = 1e9 + 1;
    967 const int MAXC = 1e6;
    968 mt19937 gen(time(0));
    969 
    970 vector<int> e(MAXC + 5);
    971 
    972 void precalc() {
    973     vector<int> p;
    974     for (int i = 2; i <= MAXC; i++) {
    975         if (e[i] == 0) {
    976             e[i] = i;
    977             p.pb(i);
    978         }
    979         for (int j = 0; j < (int)p.size() && p[j] * i <= MAXC && p[j] <= e[i]; j++) {
    980             e[p[j] * i] = p[j];
    981         }
    982     }
    983 }
    984 
    985 int f(int x) {
    986     int ans = 1;
    987     vector<int> p;
    988     while (x > 1) {
    989         p.pb(e[x]);
    990         x /= e[x];
    991     }
    992     for (int i = 0; i < (int)p.size(); i++) {
    993         if (i + 1 == (int)p.size() || p[i + 1] != p[i]) ans *= p[i];
    994     }
    995     return ans;
    996 }
    997 
    998 void gauss(int need, vector<int> &lst, vector<int> &ans, vector<vector<int>> &sz, vector<vector<vector<int>>> &v) {
    999     int n = lst.size();
   1000     vector<bitset<20>> a(n);
   1001     for (int i = 0; i < n; i++) a[i] = lst[i];
   1002     bitset<20> b = need;
   1003     vector<bitset<260>> l(n);
   1004     for (int i = 0; i < n; i++) l[i][i] = 1;
   1005     int i = 0;
   1006     vector<int> col(20, -1);
   1007     int bas_sz = 0;
   1008     for (int j = 0; j < 20 && i < n; j++) {
   1009         int i1 = i;
   1010         while (i1 < n && a[i1][j] == 0) i1++;
   1011         if (i1 == n) continue;
   1012         swap(a[i], a[i1]);
   1013         swap(l[i], l[i1]);
   1014         bas_sz++;
   1015         col[j] = i;
   1016         for (int i2 = i + 1; i2 < n; i2++) {
   1017             if (a[i2][j]) {
   1018                 a[i2] ^= a[i];
   1019                 l[i2] ^= l[i];
   1020             }
   1021         }
   1022         i++;
   1023     }
   1024     bitset<20> res;
   1025     bitset<260> path;
   1026     for (int j = 0; j < 20; j++) {
   1027         if (res[j] != b[j] && col[j] == -1) {
   1028             exit(0);
   1029         }
   1030         if (res[j] == b[j]) continue;
   1031         res ^= a[col[j]];
   1032         path ^= l[col[j]];
   1033     }
   1034     if (a.back().count() != 0) {
   1035         for (int i = 0; i < n; i++) {
   1036             if (path[i]) ans.pb(lst[i]);
   1037         }
   1038         return;
   1039     } 
   1040     vector<int> diff_sz(300);
   1041     sz.pb();
   1042     v.pb();
   1043     for (int it = 0; it < 100; it++) {
   1044         bitset<260> now = path;
   1045         for (int i = 0; i < n - bas_sz; i++) {
   1046             if (gen() % 2) now ^= l[bas_sz + i];
   1047         }
   1048         int now_sz = now.count();
   1049         if (diff_sz[now_sz]) continue;
   1050         v.back().pb();
   1051         for (int i = 0; i < n; i++) {
   1052             if (now[i]) v.back().back().pb(lst[i]);
   1053         }
   1054         diff_sz[now_sz] = 1;
   1055         sz.back().pb(now_sz);
   1056     }
   1057 }
   1058 
   1059 vector<int> mem(2 * MAXC + 5, -1);
   1060 
   1061 int query(int x) {
   1062     return mem[x];
   1063 }
   1064 
   1065 void solve(int n, int c) {
   1066     vector<int> calc(c + 1);
   1067     vector<vector<int>> total(c + 1);
   1068     for (int x = 1; x <= c; x++) total[f(x)].pb(x);
   1069     vector<int> need;
   1070     for (int x = 1; x <= c; x++) {
   1071         if (total[x].size()) need.pb(x);
   1072     }
   1073     cout << need.size() << " ";
   1074     for (auto &c : need) cout << c << " ";
   1075     cout << endl;
   1076     for (auto &c : need) {
   1077         int x;
   1078         cin >> x;
   1079         mem[c] = x;
   1080     }
   1081     int total_xor = query(1);
   1082     for (int x = 1; x <= c; x++) {
   1083         if (total[x].empty()) continue;
   1084         for (int y = x; y <= c; y += x) calc[y] ^= (query(x) ^ total_xor);
   1085     }
   1086     calc[1] = total_xor;
   1087     for (int x = c; x >= 1; x--) {
   1088         if (total[x].empty()) continue;
   1089         for (int y = 2 * x; y <= c; y += x) {
   1090             if (total[y].size()) calc[x] ^= calc[y];
   1091         }
   1092     }
   1093     vector<int> ans;
   1094     vector<vector<int>> sz;
   1095     vector<vector<vector<int>>> v;
   1096     for (int x = 1; x <= c; x++) {
   1097         if (total[x].empty()) continue;
   1098         gauss(calc[x], total[x], ans, sz, v);
   1099     }
   1100     vector<bitset<40000>> bag(sz.size() + 1);
   1101     bag[0][0] = 1;
   1102     for (int i = 1; i <= (int)sz.size(); i++) {
   1103         for (auto &x : sz[i - 1]) {
   1104             bag[i] |= (bag[i - 1] << x);
   1105         }
   1106     }
   1107     int now = n - ans.size();
   1108     for (int i = (int)sz.size(); i >= 1; i--) {
   1109         for (int j = 0; j < (int)sz[i - 1].size(); j++) {
   1110             int x = sz[i - 1][j];
   1111             if (now - x >= 0 && bag[i - 1][now - x]) {
   1112                 now -= x;
   1113                 for (auto &y : v[i - 1][j]) ans.pb(y);
   1114                 break;
   1115             }
   1116         }
   1117     }
   1118     sort(all(ans));
   1119     for (auto &c : ans) cout << c << " ";
   1120     cout << endl;
   1121 }
   1122 
   1123 int main() {
   1124     precalc();
   1125     int c, n;
   1126     cin >> c >> n;
   1127     solve(n, c);
   1128     return 0;
   1129 }
   1130 ```
   1131 
   1132 **Who did what?**
   1133 
   1134 * Problem A
   1135   + Idea: [shishyando](/profile/shishyando "Expert shishyando")
   1136   + Polygon: [shishyando](/profile/shishyando "Expert shishyando")
   1137   + Editorial: [shishyando](/profile/shishyando "Expert shishyando")
   1138 * Problem B
   1139   + Idea: [shishyando](/profile/shishyando "Expert shishyando")
   1140   + Polygon: [shishyando](/profile/shishyando "Expert shishyando")
   1141   + Editorial: [shishyando](/profile/shishyando "Expert shishyando")
   1142 * Problem C
   1143   + Idea: [shishyando](/profile/shishyando "Expert shishyando")
   1144   + Polygon: [shishyando](/profile/shishyando "Expert shishyando")
   1145   + Editorial: [shishyando](/profile/shishyando "Expert shishyando")
   1146 * Problem D
   1147   + Idea: [Artyom123](/profile/Artyom123 "International Master Artyom123")
   1148   + Polygon: [Artyom123](/profile/Artyom123 "International Master Artyom123")
   1149   + Editorial: [Artyom123](/profile/Artyom123 "International Master Artyom123")
   1150 * Problem E
   1151   + Idea: [shishyando](/profile/shishyando "Expert shishyando")
   1152   + Polygon: [shishyando](/profile/shishyando "Expert shishyando")
   1153   + Editorial: [shishyando](/profile/shishyando "Expert shishyando")
   1154 * Problem F
   1155   + Idea: [Artyom123](/profile/Artyom123 "International Master Artyom123")
   1156   + Polygon: [shishyando](/profile/shishyando "Expert shishyando")
   1157   + Editorial: [shishyando](/profile/shishyando "Expert shishyando") + [Artyom123](/profile/Artyom123 "International Master Artyom123")
   1158 * Problem G
   1159   + Idea: [Artyom123](/profile/Artyom123 "International Master Artyom123") + [isaf27](/profile/isaf27 "International Grandmaster isaf27")
   1160   + Polygon: tests: [Artyom123](/profile/Artyom123 "International Master Artyom123") + other: [shishyando](/profile/shishyando "Expert shishyando")
   1161   + Editorial: [Artyom123](/profile/Artyom123 "International Master Artyom123")
   1162 * Problem H
   1163   + Idea: [Artyom123](/profile/Artyom123 "International Master Artyom123") + [isaf27](/profile/isaf27 "International Grandmaster isaf27")
   1164   + Polygon: [shishyando](/profile/shishyando "Expert shishyando") + [Artyom123](/profile/Artyom123 "International Master Artyom123")
   1165   + Editorial: [Artyom123](/profile/Artyom123 "International Master Artyom123")
   1166 * English translation: [shishyando](/profile/shishyando "Expert shishyando")
   1167 * Edits on Polygon, common enhancements: [KAN](/profile/KAN "Legendary Grandmaster KAN"), [isaf27](/profile/isaf27 "International Grandmaster isaf27"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")