codeforces-scrape

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

1918.md (33215B)


      1 Source: https://codeforces.com/blog/entry/125300
      2 
      3 Hello, everyone!
      4 
      5 We hope you like our problems!
      6 
      7 Thank you for participation!
      8 
      9 [1918A — Brick Wall](https://codeforces.com/contest/1918/problem/A)
     10 
     11 Author: [ooaa](/profile/ooaa "Master ooaa")
     12 
     13 **Tutorial**
     14 
     15 The stability of the wall is the number of horizontal bricks minus the number of vertical bricks. Since a horizontal brick has a length of at least $2$, no more than $\lfloor\frac{m}{2}\rfloor$ horizontal bricks can be placed in one row. Therefore, the answer does not exceed $n \cdot \lfloor\frac{m}{2}\rfloor$. On the other hand, if horizontal bricks of length $2$ are placed in a row, and when $m$ is odd, the last brick has a length of $3$, then in each row there will be exactly $\lfloor\frac{m}{2}\rfloor$ horizontal bricks, and there will be no vertical bricks in the wall at all. This achieves the maximum stability of $n \cdot \lfloor\frac{m}{2}\rfloor$. The solution is one formula, so it works in $O(1)$ time.
     16 
     17 **Solution**
     18 
     19 ```
     20 #include <bits/stdc++.h>
     21 
     22 using namespace std;
     23 
     24 int main()
     25 {
     26     ios_base::sync_with_stdio(false);
     27     cin.tie(0);
     28     int t;
     29     cin >> t;
     30     while(t--)
     31     {
     32         int64_t n,m;
     33         cin >> n >> m;
     34         cout << n*(m/2) << '\n';
     35     }
     36     return 0;
     37 }
     38 ```
     39 
     40 [1918B — Minimize Inversions](https://codeforces.com/contest/1918/problem/B)
     41 
     42 Author: [ace5](/profile/ace5 "International Grandmaster ace5")
     43 
     44 **Tutorial**
     45 
     46 Notice that by performing operations of the form: swap $a_i$ with $a_j$ and $b_i$ with $b_j$ simultaneously, we can rearrange the array $a$ how we want, but the same $a_i$ will correspond to the same $b_i$ (because we are changing both $a_i$ and $b_i$ at the same time). Let's sort the array $a$ using these operations. Then the sum of the number of inversions in $a$ and $b$ will be the number of inversions in $b$, since $a$ is sorted. It is claimed that this is the minimum sum that can be achieved.
     47 
     48 Proof: Consider two pairs of elements $a_i$ with $a_j$ and $b_i$ with $b_j$ ($i$ < $j$). In each of these pairs, there can be either $0$ or $1$ inversions, so among the two pairs, there can be $0$, $1$, or $2$ inversions. If there were $0$ inversions before the operation, then there will be $2$ after the operation; if there was $1$, then there will still be $1$; if there were $2$, then it will become $0$. If the permutation $a_i$ is sorted, then in each pair of indices $i$ and $j$ there will be a maximum of 1 inversion, so any pair of indices will give no more inversions than if they were swapped. Since the number of inversions in each pair is the minimum possible, the total number of inversions is also the minimum possible.
     49 
     50 Time complexity: $O(n \log n)$ per test case.
     51 
     52 **Solution**
     53 
     54 ```
     55 #include <bits/stdc++.h>
     56 
     57 using namespace std;
     58 
     59 int main()
     60 {
     61     ios_base::sync_with_stdio(false);
     62     cin.tie(0);
     63     int t;
     64     cin >> t;
     65     while(t--)
     66     {
     67         int n;
     68         cin >> n;
     69         pair<int,int> ab[n];
     70         for(int i = 0;i < n;++i)
     71         {
     72             cin >> ab[i].first;
     73         }
     74         for(int i = 0;i < n;++i)
     75         {
     76             cin >> ab[i].second;
     77         }
     78         sort(ab,ab+n);
     79         for(int i = 0;i < n;++i)
     80         {
     81             cout << ab[i].first << ' ';
     82         }
     83         cout << "\n";
     84         for(int i = 0;i < n;++i)
     85         {
     86             cout << ab[i].second << ' ';
     87         }
     88         cout << "\n";
     89     }
     90 }
     91 ```
     92 
     93 [1918C — XOR-distance](https://codeforces.com/contest/1918/problem/C)
     94 
     95 Author: [ace5](/profile/ace5 "International Grandmaster ace5")
     96 
     97 **Tutorial**
     98 
     99 Let's consider the bitwise representation of numbers $a$, $b$, $x$. Let's look at any $2$ bits at the same position in $a$ and $b$, if they are the same, then regardless of what is in $x$ on this position, the number $|({a \oplus x}) - ({b \oplus x})|$ will have a $0$ at this position. Therefore, it is advantageous to set $0$ at all such positions in $x$ (since we want $x \leq r$, and the answer does not depend on the bit). If the bits in $a$ and $b$ at the same position are different, then at this position there will be a $1$ either in $a \oplus x$ or in $b \oplus x$ depending on what is at this position in $x$.
    100 
    101 Let $a$ < $b$, if not, then we will swap them. Then at the highest position, where the bits differ, there is a $0$ in $a$ and a $1$ in $b$. There are $2$ options, either to set a $1$ at this position in $x$ (and then there will be a $1$ in $a \oplus x$), or to set a $0$ in $x$ (and then there will be a $0$ in $a \oplus x$).
    102 
    103 Suppose we set $0$ in $x$, then $a \oplus x$ will definitely be less than $b \oplus x$ (because in the highest differing bit, $a \oplus x$ has $0$, and $b \oplus x$ has $1$). Therefore, it is advantageous to set $1$ in $a \oplus x$ on all next positions, as this will make their difference smaller. Therefore, we can go through the positions in descending order, and if the position is differing, then we will set a $1$ in $a \oplus x$ at this position if possible (if after this $x$ does not exceed $r$).
    104 
    105 The second case (when we set $1$ in $x$ at the position of the first differing bit) is analyzed similarly, but in fact it is not needed, because the answer will not be smaller, and $x$ will become larger.
    106 
    107 Time complexity: $O(\log 10^{18})$ per test case.
    108 
    109 **Solution**
    110 
    111 ```
    112 #include <bits/stdc++.h>
    113 
    114 using namespace std;
    115 
    116 const int maxb = 60;
    117 
    118 bool get_bit(int64_t a,int i)
    119 {
    120     return a&(1ll<<i);
    121 }
    122 
    123 int main()
    124 {
    125     ios_base::sync_with_stdio(false);
    126     cin.tie(0);
    127     int t;
    128     cin >> t;
    129     while(t--)
    130     {
    131         int64_t a,b,r;
    132         cin >> a >> b >> r;
    133         int64_t x = 0;
    134         bool first_bit = 1;
    135         if(a > b)
    136             swap(a,b);
    137         for(int i = maxb-1;i >= 0;--i)
    138         {
    139             bool bit_a = get_bit(a,i);
    140             bool bit_b = get_bit(b,i);
    141             if(bit_a != bit_b)
    142             {
    143                 if(first_bit)
    144                 {
    145                     first_bit = 0;
    146                 }
    147                 else
    148                 {
    149                     if(!bit_a && x+(1ll<<i) <= r)
    150                     {
    151                         x += (1ll<<i);
    152                         a ^= (1ll<<i);
    153                         b ^= (1ll<<i);
    154                     }
    155                 }
    156             }
    157         }
    158         cout << b-a << "\n";
    159     }
    160 }
    161 ```
    162 
    163 [1918D — Blocking Elements](https://codeforces.com/contest/1918/problem/D)
    164 
    165 Author: [ace5](/profile/ace5 "International Grandmaster ace5")
    166 
    167 **Tutorial**
    168 
    169 Let's do a binary search. Suppose we know that the minimum possible cost is at least $l$ and not greater than $r$. Let's choose $m = (l+r)/2$. We need to learn how to check if the answer is less than or equal to $m$. We will calculate $dp_i$–the minimum sum of blocked elements in the prefix up to $i$ if position $i$ is blocked, and on each of the subsegments without blocked elements, the sum of elements is less than or equal to $m$. Then $dp_i = a_i + \min(dp_j)$ for all $j$ such that the sum on the subsegment from $j+1$ to $i-1$ is less than or equal to $m$. Such $j$ form a segment, since $a_j$ is positive. We will maintain the boundaries of this segment. We will also maintain all $dp_j$ for $j$ inside this subsegment in the set. When moving from $i$ to $i+1$, we will move the left boundary of the subsegment until the sum on it becomes less than or equal to $m$, and remove $dp_j$ from the set, and also add $dp_i$ to the set. The minimum sum of blocked elements under the condition that the sum on all subsegments without blocked elements is less than or equal to $m$ can be found as the minimum among all $dp_i$ such that the sum from $i$ to $n$ is less than or equal to $m$. If this answer is less than or equal to $m$, then the answer to the problem is less than or equal to $m$, otherwise the answer is greater than $m$.
    170 
    171 Time complexity: $O(n \log n \log 10^9)$ per test case.
    172 
    173 **Solution**
    174 
    175 ```
    176 #include <bits/stdc++.h>
    177 
    178 using namespace std;
    179 
    180 int main()
    181 {
    182     ios_base::sync_with_stdio(false);
    183     cin.tie(0);
    184     int t;
    185     cin >> t;
    186     while(t--)
    187     {
    188         int n;
    189         cin >> n;
    190         int64_t a[n+1];
    191         for(int i = 0;i < n;++i)
    192         {
    193             cin >> a[i];
    194         }
    195         int64_t l = 0,r = int64_t(1e9)*n;
    196         while(l < r)
    197         {
    198             int64_t m = (l+r)/2;
    199             set<pair<int64_t,int>> pos;
    200             int64_t dp[n+1];
    201             int p2 = n;
    202             dp[n] = 0;
    203             pos.insert({dp[n],n});
    204             int64_t sum = 0;
    205             for(int j = n-1;j >= 0;--j)
    206             {
    207                 while(sum > m)
    208                 {
    209                     sum -= a[p2-1];
    210                     pos.erase({dp[p2],p2});
    211                     p2--;
    212                 }
    213                 dp[j] = pos.begin()->first + a[j];
    214                 pos.insert({dp[j],j});
    215                 sum += a[j];
    216             }
    217             sum = 0;
    218             int yes = 0;
    219             for(int j =0;j < n;++j)
    220             {
    221                 if(sum <= m && dp[j] <= m)
    222                     yes = 1;
    223                 sum += a[j];
    224             }
    225             if(yes)
    226                 r = m;
    227             else
    228                 l = m+1;
    229         }
    230         cout << l << "\n";
    231     }
    232 }
    233 ```
    234 
    235 [1918E — ace5 and Task Order](https://codeforces.com/contest/1918/problem/E)
    236 
    237 Author: [ace5](/profile/ace5 "International Grandmaster ace5")
    238 
    239 **Tutorial**
    240 
    241 **Randomized solution:** We will use the quicksort algorithm. We will choose a random element from the array, let its index be $i$, and we will perform $?$ $i$ until we get the answer $=$ (i.e., $x = a_i$). Now we will ask about all the other elements, thereby finding out whether they are greater than or less than $a_i$ (don't forget to return $x = a_i$, i.e., perform $?$ $i$ after each query about the element). After this, we will divide all the elements into two parts, where $a_i \gt x$ and $a_i \lt x$. We will recursively run the algorithm on each part. The parts will become smaller and smaller, and in the end, we will sort our permutation, allowing us to guess it.
    242 
    243 **Non-randomized solution:** We will find the element $1$ in the array in $3n$ queries. To do this, we will go through the array, asking about each element each time. If the answer is $ \lt $, we will continue asking until the answer becomes $=$, and if the answer is $=$ or $ \gt $, we will move on to the next element. Then the last element on which the answer was $ \lt $ is the element $1$. $x$ will increase by a maximum of $n$ in the process (a maximum of $1$ from each element), so it will decrease by a maximum of $2n$, i.e., a maximum of $3n$ queries. Similarly, we will find the element $n$. Now we will run an algorithm similar to the randomized solution, but now we can set $x = n/2$ instead of taking $x$ as a random element.
    244 
    245 Both solutions comfortably fit within the limit of $40n$ queries.
    246 
    247 **Randomized solution**
    248 
    249 ```
    250 #include <bits/stdc++.h>
    251 
    252 using namespace std;
    253 
    254 mt19937 rnd(593);
    255 
    256 char query(int i)
    257 {
    258     cout << "? " << i+1 << endl;
    259     char c;
    260     cin >> c;
    261     return c;
    262 }
    263 
    264 void quicksort(vector<int> &a,vector<int> &ord)
    265 {
    266     if(a.size() == 0)
    267         return ;
    268     int mid = rnd()%a.size();
    269     while(query(a[mid]) != '=')
    270         ;
    271     vector<int> l,r;
    272     for(int i = 0;i < a.size();++i)
    273     {
    274         if(i == mid)
    275             continue;
    276         if(query(a[i]) == '<')
    277         {
    278             l.push_back(a[i]);
    279         }
    280         else
    281         {
    282             r.push_back(a[i]);
    283         }
    284         query(a[mid]);
    285     }
    286     vector<int> l_ord;
    287     vector<int> r_ord;
    288     quicksort(l,l_ord);
    289     quicksort(r,r_ord);
    290     for(int i = 0;i < l_ord.size();++i)
    291     {
    292         ord.push_back(l_ord[i]);
    293     }
    294     ord.push_back(a[mid]);
    295     for(int i = 0;i < r_ord.size();++i)
    296     {
    297         ord.push_back(r_ord[i]);
    298     }
    299     return ;
    300 }
    301 
    302 int main()
    303 {
    304     int t;
    305     cin >> t;
    306     while(t--)
    307     {
    308         int n;
    309         cin >> n;
    310         vector<int> a;
    311         vector<int> ord;
    312         for(int i = 0;i < n;++i)
    313         {
    314             a.push_back(i);
    315         }
    316         quicksort(a,ord);
    317         cout << "! ";
    318         vector<int> ans(n);
    319         for(int i = 0;i < n;++i)
    320         {
    321             ans[ord[i]] = i;
    322         }
    323         for(int i = 0;i < n;++i)
    324         {
    325             cout << ans[i]+1 << ' ';
    326         }
    327         cout << endl;
    328     }
    329 }
    330 ```
    331 
    332 **Non-randomized solution**
    333 
    334 ```
    335 #include <bits/stdc++.h>
    336 
    337 using namespace std;
    338 
    339 char query(int pos)
    340 {
    341     cout << "? " << pos << endl;
    342     char ans;
    343     cin >> ans;
    344     return ans;
    345 }
    346 
    347 void dnq(int l,int r,vector<int> pos,vector<int> & res,int pos1,int posn)
    348 {
    349     int m = (l+r)/2;
    350     vector<int> lh;
    351     vector<int> rh;
    352     for(int i = 0;i < pos.size();++i)
    353     {
    354         char x = query(pos[i]);
    355         if(x == '>')
    356         {
    357             rh.push_back(pos[i]);
    358             query(pos1);
    359         }
    360         else if(x == '<')
    361         {
    362             lh.push_back(pos[i]);
    363             query(posn);
    364         }
    365         else
    366         {
    367             res[pos[i]] = m;
    368         }
    369     }
    370     if(lh.size() != 0)
    371     {
    372         int m2 = (l+m-1)/2;
    373         for(int j = 0;j < m-m2;++j)
    374             query(pos1);
    375         dnq(l,m-1,lh,res,pos1,posn);
    376         query(posn);
    377     }
    378     if(rh.size() != 0)
    379     {
    380         int m2 = (m+1+r)/2;
    381         for(int j = 0;j < m2-m;++j)
    382             query(posn);
    383         dnq(m+1,r,rh,res,pos1,posn);
    384     }
    385     return ;
    386 }
    387 
    388 int main()
    389 {
    390     int t;
    391     cin >> t;
    392     while(t--)
    393     {
    394         int n;
    395         cin >> n;
    396         int pos1 = -1;
    397         for(int i = 1;i <= n;++i)
    398         {
    399             char ans = query(i);
    400             if(ans == '<')
    401             {
    402                 i--;
    403             }
    404             else if(ans == '=')
    405             {
    406                 pos1 = i;
    407             }
    408             else
    409             {
    410                 if(pos1 != -1)
    411                 {
    412                     query(pos1);
    413                 }
    414             }
    415         }
    416         int posn = -1;
    417         for(int i = 1;i <= n;++i)
    418         {
    419             char ans = query(i);
    420             if(ans == '>')
    421             {
    422                 i--;
    423             }
    424             else if(ans == '=')
    425             {
    426                 posn = i;
    427             }
    428             else
    429             {
    430                 if(posn != -1)
    431                 {
    432                     query(posn);
    433                 }
    434             }
    435         }
    436         vector<int> res(n+1);
    437         vector<int> pos(n);
    438         for(int j = 0;j < n;++j)
    439             pos[j] = j+1;
    440         int m = (1+n)/2;
    441         for(int k = 0;k < n-m;++k)
    442         {
    443             query(pos1);
    444         }
    445         dnq(1,n,pos,res,pos1,posn);
    446         cout << "! ";
    447         for(int j = 1;j <= n;++j)
    448             cout << res[j] << ' ';
    449         cout << endl;
    450     }
    451 }
    452 ```
    453 
    454 [1918F — Caterpillar on a Tree](https://codeforces.com/contest/1918/problem/F)
    455 
    456 Author: [ooaa](/profile/ooaa "Master ooaa")
    457 
    458 **Tutorial**
    459 
    460 First, it can be noticed that it is enough to visit all the leaves of the tree. After all, if the caterpillar skips some internal node, then it will not be able to reach the subtree of this node and visit the leaves in it. Therefore, it makes no sense to teleport to the root from a non-leaf (otherwise it would be more profitable to move to the root earlier, and all the leaves would remain visited).
    461 
    462 The optimal path of the caterpillar on the tree can be divided into movements from the root to a leaf, movements from one leaf to another, and teleportations from a leaf to the root. Let the order of visiting the leaves in the optimal path be fixed. Then it makes no sense to teleport from the last leaf, as all the leaves have already been visited. In addition, it is not profitable to move not along the shortest path in the sections of transition from the root to a leaf without visiting other leaves, or in movements from one leaf to another without visiting other leaves. If the leaf $v$ is visited after the leaf $u$, then teleporting from $u$ saves time of transition from $u$ to $v$ minus the time of moving to $v$ from the root. It is possible to choose $k$ leaves, without the last visited leaf, which give the maximum savings (if there are fewer leaves in the tree, or the savings become negative, then take fewer than $k$ leaves), and teleport from them. Thus, if the order of visiting the leaves is known, the optimal time can be found.
    463 
    464 It turns out that if you take the tree and sort the children of each node in ascending (not descending) order of the depth of the subtree, and then write down all the leaves from left to right (in depth-first order), then this will be one of the optimal leaf orders. This order of sorting the tree and its leaves will be called the order of sorting by the subtree depth.
    465 
    466 The tree can be sorted in this way in one depth-first traversal. For each leaf, it is possible to calculate how much time teleporting from it saves. To do this, it is enough to move from this leaf to the root until the first node, for which the previous node is not the rightmost child. Then the savings are the length of the path traveled minus the remaining distance to the root. Such paths for different leaves do not intersect along the edges, and the remaining distance to the root can be precalculated in a depth-first search for all nodes at once. Therefore, the algorithm works in $O(n \log n)$ time, where the logarithm arises from sorting the children of each node by the depth of the subtree.
    467 
    468 **Theorem.**
    469 
    470 There exists a shortest route for the caterpillar, in which the leaves are visited in the order of sorting the children of each node by the depth of the subtree.
    471 
    472 **Proof**
    473 
    474 Let $u_1, \ldots, u_m$ be all the leaves of the tree in the order that will result if the children of each node are sorted in ascending order of the depth of the subtree. Consider the shortest route of the caterpillar visiting all the nodes of the tree. Let $v_1, \ldots, v_m$ be the leaves of the tree, in the order of visiting in this route. Consider the maximum prefix of leaves that coincides with the order of sorting by the depth of the subtree: $v_1 = u_1,\ldots, v_i = u_i$. If $i = m$, then the theorem is proven. Now, let's assume that the next leaf is the incorrect leaf $v_{i+1} \neq u_{i+1}$.
    475 
    476 The goal is to change the route in such a way that the time of traversing the tree does not increase, so that the first $i$ visited leaves do not change and remain in the same order, and so that the leaf $u_{i+1}$ is encountered earlier in the route than before the change. Then it is possible to move the leaf $u_{i+1}$ to its $(i+1)$s place, while maintaining the order of the first $i$ visited leaves. Then, in the same way, one can put all the leaves $u_{i+1}, \ldots, u_m$ in their places one by one and get the shortest route of the caterpillar with the desired order of visiting leaves.
    477 
    478 ![ ](/predownloaded/bf/44/bf44334522a72073b32f04d44ca712c2a348abcc.jpg)
    479 
    480 **Lemma.**
    481 
    482 Let the node $w$ be the ancestor of the node $u$. Let the caterpillar in the shortest route on the tree crawl from $u$ to $w$. Then the caterpillar enters the subtree of the node $u$ only once, traverses this subtree depth-first, and returns to $w$.
    483 
    484 Proof of the lemma.
    485 
    486 If the caterpillar crawls from $w$ to $u$ only once, then it cannot leave the subtree of $u$ until all the nodes in this subtree are visited, and it cannot jump on a trampoline, as it still needs to move from $u$ to $w$. All this cannot be done faster than the number of steps equal to twice the number of nodes in the subtree of $u$, because the caterpillar needs to reach each node via an edge from the ancestor and to return to the ancestor. And any route without teleportations, which uses each edge twice, is one of the depth-first traversals.
    487 
    488 If the caterpillar crawls from $w$ to $u$ two or more times, then the route can be shortened, as shown in figure.
    489 
    490 The lemma is proven.
    491 
    492 At the moment, the leaf $v_{i+1}$ lies in the order of visiting the leaves in the optimal route of the caterpillar in the place of the leaf $u_{i+1}$. The goal is to move the leaf $u_{i+1}$ closer to the beginning of the route, without changing the first $i$ visited leaves: $u_1, \ldots, u_i$.
    493 
    494 ![ ](/predownloaded/9c/87/9c876527b0877a6696f2608d6161ad42c357bb95.jpg)
    495 
    496 Let $w$ be the least common ancestor of the leaves $u_{i+1}$ and $v_{i+1}$, let $u$ be the child of $w$, in the subtree of which the node $u_{i+1}$ is located, and $v$ be the child of $w$, in the subtree of which the node $v_{i+1}$ is located, as shown in figure. To move the leaf $u_{i+1}$ closer to the beginning of the route, let us consider cases.
    497 
    498 **Case 1:** The caterpillar in the current version of the optimal route crawls from $u$ to $w$.
    499 
    500 In this case, according to the lemma, the caterpillar enters the subtree of vertex $u$ only once, and traverses it in the depth-first manner before returning to $w$. There are no leaves $u_1, \ldots, u_i$ in the subtree of $u$, because all the leaves of the subtree of $u$ are visited consecutively during the depth-first traversal, and the leaf $v_{i+1}$ not from the subtree of $u$ is visited after $u_1, \ldots, u_i$, but before $u_{i+1}$. Then the route can be changed as follows: the cycle $w \to \text{ (traversal of the subtree of } u\text{) } \to w$ is cut out from where it is located, and inserted at the moment of the first visit to $w$ after the visit to the leaf $u_i$. The leaf $u_i$ is not in the subtree of the node $v$, because the subtree of $u$ has a smaller depth ($u_{i+1}$ is earlier in the desired leaf order than $v_{i+1}$), and there are still unvisited leaves in it. Then, before entering $v_{i+1}$, the caterpillar will have to come from the leaf $u_i$ to the node $w$, and at that moment a depth-first traversal of the subtree of $u$ with the visit to the leaf $u_{i+1}$ will occur. This traversal was moved to an earlier time, before visiting $v_{i+1}$, which means that in the order of visiting the leaves in the caterpillar's route, the leaf $u_{i+1}$ has been moved closer to the beginning.
    501 
    502 **Case 2:** The caterpillar in the current version of the optimal route does not crawl from $u$ to $w$, but crawls from $v$ to $w$.
    503 
    504 Then the entire subtree of $v$ is traversed in a depth-first traversal. Since the leaf $u_{i+1}$ is earlier in the desired order than $v_{i+1}$, the subtree of $v$ is deeper than the subtree of $u$, and in the desired order all the leaves of $v$ come after $u_{i+1}$. Moreover, since the caterpillar does not crawl from $u$ to $w$, it is impossible to leave the subtree of $u$ except by teleporting to the root. The last jump on the trampoline from the subtree of the node $u$ is considered (or stopping at the end of the route). At this moment, all the leaves of the subtree of $u$ are visited. The route can be changed as follows: cut out the depth-first traversal of the subtree of $v$, cancel the last jump or stop in the subtree of $u$, descend from there to $w$, perform a depth-first traversal of the subtree of $v$ in such a way that the deepest node of this subtree is visited last, and teleport to the root (or stop at the end of the route). This will not be longer, because a section of transition from a leaf in the subtree of $u$ to $w$ has been added, and a section of movement from the deepest leaf in the subtree of $v$ to $w$ has disappeared, here it is important that the subtree of $v$ is deeper than the subtree of $u$. And the node $u_{i+1}$ has become closer to the beginning of the list of visited leaves, because all the leaves of the subtree of $v$, including $v_{i+1}$, have moved somewhere after all the leaves of the subtree of $u$.
    505 
    506 **Case 3:** The caterpillar in the current version of the optimal route does not crawl either from $u$ to $w$, nor from $v$ to $w$.
    507 
    508 Then all the sections of the route that move into the subtrees of the nodes $u$ and $v$ do not leave these subtrees and end with teleportation to the root or stopping at the end of the route. Among them, there is a section that starts with a step from $w$ to $u$, in which the leaf $u_{i+1}$ is visited, and a section that starts with a step from $w$ to $v$, in which the leaf $v_{i+1}$ is visited. In the current route, the section with $v_{i+1}$ comes earlier. The route can be changed very simply: swap the section visiting the leaf $u_{i+1}$ and the section visiting the leaf $v_{i+1}$. If both sections end with teleportations, then a correct caterpillar route will result. If the caterpillar stopped at the end of the section visiting $u_{i+1}$, and teleported to the root from the section with $v_{i+1}$, then now it will teleport after completing the section with $u_{i+1}$ and stop at the end of the section with $v_{i+1}$. The positions of the leaves $u_1, \ldots, u_i$ in the route will not change: they are not in the subtree of $v$, and they are not in the section with $u_{i+1}$, visited after $v_{i+1}$. And the leaf $u_{i+1}$ will get a place closer to the beginning in the order of visiting the leaves, because the section with its visit now occurs earlier in the route.
    509 
    510 In all cases, it was possible to move the leaf $u_{i+1}$ in the optimal route of the caterpillar closer to the beginning, while maintaining the order of the first $i$ visited leaves, which means that there exists an optimal route of the caterpillar in which the leaves are visited in the order of sorting the subtrees of the tree by depth. The theorem is proven.
    511 
    512 **Solution**
    513 
    514 ```
    515 #include <bits/stdc++.h>
    516 
    517 using namespace std;
    518 
    519 const int maxn = 200005;
    520 int d[maxn];
    521 int h[maxn];
    522 int p[maxn];
    523 vector<int> leaf_jump_gains;
    524 vector<vector<int> > children;
    525 
    526 bool comp_by_depth(int u,int v)
    527 {
    528     return d[u] < d[v];
    529 }
    530 
    531 void sort_subtrees_by_depth(int v)
    532 {
    533     d[v] = 0;
    534     if(v == 1)
    535         h[v] = 0;
    536     else
    537         h[v] = h[p[v]]+1;
    538     for(int i = 0; i < int(children[v].size()); ++i)
    539     {
    540         int u = children[v][i];
    541         sort_subtrees_by_depth(u);
    542         d[v] = max(d[v],d[u]+1);
    543     }
    544     sort(children[v].begin(),children[v].end(),comp_by_depth);
    545 }
    546 
    547 int main()
    548 {
    549     ios_base::sync_with_stdio(false);
    550     cin.tie(0);
    551     int n,k;
    552     cin >> n >> k;
    553     children.resize(n+1);
    554     for(int i = 2; i <= n; ++i)
    555     {
    556         cin >> p[i];
    557         children[p[i]].push_back(i);
    558     }
    559     sort_subtrees_by_depth(1);
    560     for(int i = 1; i <= n; ++i)
    561     {
    562         if(children[i].size() == 0)
    563         {
    564             int jump_gain = 0;
    565             int v = i;
    566             while(v != 1)
    567             {
    568                 int s = children[p[v]].size();
    569                 if(children[p[v]][s-1] == v)
    570                 {
    571                     v = p[v];
    572                     ++jump_gain;
    573                 }
    574                 else
    575                 {
    576                     jump_gain = jump_gain+1-h[p[v]];
    577                     break;
    578                 }
    579             }
    580             leaf_jump_gains.push_back(jump_gain);
    581         }
    582     }
    583     sort(leaf_jump_gains.begin(),leaf_jump_gains.end());
    584     int s = leaf_jump_gains.size();
    585     ++k; //non-returning from the last leaf is like one more jump
    586     int res = 2*(n-1);
    587     for(int i = s-1; i >= max(0,s-k); --i)
    588         res -= max(leaf_jump_gains[i],0);
    589     cout << res << '\n';
    590     return 0;
    591 }
    592 ```
    593 
    594 [1918G — Permutation of Given](https://codeforces.com/contest/1918/problem/G)
    595 
    596 Author: [ace5](/profile/ace5 "International Grandmaster ace5")
    597 
    598 **Tutorial**
    599 
    600 At first, you can manually find answers for small values of $n$. For $n = 2, 4, 6$, the answer will be "YES" and the arrays will be $[-1, 1]$, $[-1, -2, 2, 1]$, $[-1, -2, 2, 1, -1, 1]$. It is not difficult to prove by case analysis that the answer is "NO" for $3$ and $5$. It can be assumed that for all odd $n$, the answer is "NO", but if you try to prove the absence of an array or find an array for $n = 7$, it turns out that the array exists: $[-5, 8, 1, -3, -4, -2, 5]$. In fact, an array exists for all $n$ except $3$ and $5$.
    601 
    602 It would be easy if it were possible to make the number in each cell unchanged. But the presence of array edges and the prohibition of zeros make this impossible. Furthermore, it can be noticed that an infinite array in which the sequence of six numbers $1, -3, -4, -1, 3, 4$ is repeated, generates the same number in each cell as it was there. In general, any sequence of six numbers of the form $a, -b, -a-b, -a, b, a+b$ will have this property. Thus, it is possible to transform the internal cells of the array into cells with the same numbers, the question is what to do at the edges. In the author's solution, suitable edges (possibly consisting of several numbers) were manually selected for each remainder of division by $6$. And then the solution for each value of $n$ was created as follows: take the edges for $n \mod 6$ and insert into the middle as many sequences of six numbers that transition into themselves as needed.
    603 
    604 Solution by [green_gold_dog](/profile/green_gold_dog "Grandmaster green_gold_dog"):
    605 
    606 The idea is that any correct array can be extended by $2$ elements to remain correct. Let the array end with the numbers $a$ and $b$. Then it can be extended by two elements as follows: \begin{equation*} [\ldots,\;a,\;b] \to [\ldots, a,\; b,\; -b,\; a-b] \end{equation*} This array transitions into its permutation: the entire old array, except for $a$, is generated by the old array; the last three cells generate $a-b$, $a$, $-b$, i.e., two new elements, and the missing element $a$. It is also necessary for the new elements to be non-zero. If the last two elements of the old array were different, then the new elements are non-zero; moreover, the new elements cannot be the same, as $a$ and $b$ are non-zero, so this operation can be repeated many times.
    607 
    608 To start, two arrays are sufficient: $[1, 2]$ for $n = 2$ and $[1, 2, -3, 2, 4, -5, -2]$ for $n = 7$. Then these arrays can be extended by $2$ to obtain the answer for even or odd $n$.
    609 
    610 Both solutions print an array using simple rules and work in $O(n)$ time.
    611 
    612 **Solution by ooaa**
    613 
    614 ```
    615 #include <bits/stdc++.h>
    616 
    617 using namespace std;
    618 
    619 int main()
    620 {
    621     ios_base::sync_with_stdio(false);
    622     cin.tie(0);
    623     int n;
    624     cin >> n;
    625     if(n%6 == 0)
    626     {
    627         cout << "YES\n";
    628         cout << "2 1 -1 ";
    629         for(int j = 0;j < n/6-1;++j)
    630         {
    631             cout << "1 -1 -2 -1 1 2 ";
    632         }
    633         cout << "1 -1 -2" << "\n";
    634         return 0;
    635     }
    636     else if(n%6 == 1)
    637     {
    638         cout << "YES\n";
    639         cout << "-5 8 1 -3 -4 ";
    640         for(int j = 0;j < n/6-1;++j)
    641         {
    642             cout << "-1 3 4 1 -3 -4 ";
    643         }
    644         cout << "-2 5" << "\n";
    645         return 0;
    646     }
    647     else if(n%6 == 2)
    648     {
    649         cout << "YES\n";
    650         for(int j = 0;j < n/6;++j)
    651         {
    652             cout << "1 -1 -2 -1 1 2 ";
    653         }
    654         cout << "1 -1" << "\n";
    655         return 0;
    656     }
    657     else if(n%6 == 3)
    658     {
    659         if(n == 3)
    660             cout << "NO\n";
    661         else
    662         {
    663             cout << "YES\n";
    664             cout << "2 1 1 -3 -4 -1 3 ";
    665             for(int j = 0;j < n/6-1;++j)
    666             {
    667                 cout << "4 1 -3 -4 -1 3 ";
    668             }
    669             cout << "3 -2" << "\n";
    670             return 0;
    671         }
    672     }
    673     else if(n%6 == 4)
    674     {
    675         cout << "YES\n";
    676         for(int j = 0;j < n/6;++j)
    677         {
    678             cout << "1 -1 -2 -1 1 2 ";
    679         }
    680         cout << "1 -1 1 2" << "\n";
    681         return 0;
    682     }
    683     else if(n%6 == 5)
    684     {
    685         if(n == 5)
    686         {
    687             cout << "NO\n";
    688         }
    689         else
    690         {
    691             cout << "YES\n";
    692             cout << "-2 1 1 -3 -4 -1 3 ";
    693             for(int j = 0;j < n/6-1;++j)
    694             {
    695                 cout << "4 1 -3 -4 -1 3 ";
    696             }
    697             cout << "2 -1 2 4" << "\n";
    698             return 0;
    699         }
    700     }
    701 
    702 }
    703 ```
    704 
    705 **Solution by green_gold_dog**
    706 
    707 ```
    708 //#pragma GCC optimize("Ofast")
    709 //#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
    710 #include <bits/stdc++.h>
    711  
    712 using namespace std;
    713  
    714 typedef long long ll;
    715 typedef double db;
    716 typedef long double ldb;
    717 typedef complex<double> cd;
    718  
    719 constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
    720 constexpr db PI = acos(-1);
    721 constexpr bool IS_FILE = false, IS_TEST_CASES = false;
    722  
    723 random_device rd;
    724 mt19937 rnd32(rd());
    725 mt19937_64 rnd64(rd());
    726  
    727 template<typename T>
    728 bool assign_max(T& a, T b) {
    729 	if (b > a) {
    730 		a = b;
    731 		return true;
    732 	}
    733 	return false;
    734 }
    735  
    736 template<typename T>
    737 bool assign_min(T& a, T b) {
    738 	if (b < a) {
    739 		a = b;
    740 		return true;
    741 	}
    742 	return false;
    743 }
    744  
    745 template<typename T>
    746 T square(T a) {
    747 	return a * a;
    748 }
    749  
    750 template<>
    751 struct std::hash<pair<ll, ll>> {
    752 	ll operator() (pair<ll, ll> p) const {
    753 		return ((__int128)p.first * MOD + p.second) % INF64;
    754 	}
    755 };
    756  
    757 void solve() {
    758 	ll n;
    759 	cin >> n;
    760 	if (n == 5 || n == 3) {
    761 		cout << "NO\n";
    762 		return;
    763 	}
    764 	cout << "YES\n";
    765 	vector<ll> arr;
    766 	if (n % 2 == 0) {
    767 		arr.push_back(1);
    768 		arr.push_back(2);
    769 	} else {
    770 		arr.push_back(1);
    771 		arr.push_back(2);
    772 		arr.push_back(-3);
    773 		arr.push_back(2);
    774 		arr.push_back(4);
    775 		arr.push_back(-5);
    776 		arr.push_back(-2);
    777 	}
    778 	while (arr.size() != n) {
    779 		ll x = arr[arr.size() - 2];
    780 		ll y = x - arr.back();
    781 		ll z = y - x;
    782 		arr.push_back(z);
    783 		arr.push_back(y);
    784 	}
    785 	for (auto i : arr) {
    786 		cout << i << ' ';
    787 	}
    788 	cout << '\n';
    789 }
    790  
    791 int main() {
    792 	if (IS_FILE) {
    793 		freopen("", "r", stdin);
    794 		freopen("", "w", stdout);
    795 	}
    796     	ios_base::sync_with_stdio(false);
    797     	cin.tie(0);
    798     	cout.tie(0);
    799 	ll t = 1;
    800 	if (IS_TEST_CASES) {
    801 		cin >> t;
    802 	}
    803 	for (ll i = 0; i < t; i++) {
    804 		solve();
    805 	}
    806 }
    807 ```