codeforces-scrape

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

1647.md (18796B)


      1 Source: https://codeforces.com/blog/entry/100780
      2 
      3 Task A. Idea [FairyWinx](/profile/FairyWinx "Master FairyWinx")
      4 
      5 **Hint 1**
      6 
      7 The optimal answer has the maximum number of digits, so you only need to use the digits $1,2$.
      8 
      9 **Hint 2**
     10 
     11 Alternate these numbers so that there are no adjacent identical numbers.
     12 
     13 **Solution**
     14 
     15 Since we want to maximize the number we need, we will first find the longest suitable number. Obviously, it is better to use only the numbers $1$ and $2$ for this. Therefore, the answer always looks like $2121\ldots$ or $1212\ldots$. The first option is optimal when $n$ has a remainder of $2$ or $0$ modulo $3$, otherwise the second option is optimal.
     16 
     17 Below is an example of a neat implementation.
     18 
     19 **Code**
     20 
     21 ```
     22 #include <bits/stdc++.h>
     23  
     24 using namespace std;
     25  
     26 void solve() {
     27     int n;
     28     cin >> n;
     29     int type;
     30     if (n % 3 == 1)
     31         type = 1;
     32     else
     33         type = 2;
     34     int sum = 0;
     35     while (sum != n) {
     36         cout << type;
     37         sum += type;
     38         type = 3 - type;
     39     }
     40     cout << '\n';
     41 }
     42  
     43 int main() {
     44     ios_base::sync_with_stdio(0);
     45     cin.tie(0);
     46  
     47     int t;
     48     cin >> t;
     49     while (t--)
     50         solve();
     51 }
     52 ```
     53 
     54 ---
     55 
     56 Задача B. Idea [FairyWinx](/profile/FairyWinx "Master FairyWinx")
     57 
     58 **Hint 1**
     59 
     60 What is a picture if the answer to the problem is "YES".
     61 
     62 **Hint 2**
     63 
     64 Think about a square of size $2\times 2$.
     65 
     66 **Solution**
     67 
     68 Note that the answer to the problem is "YES" if and only if the picture is a certain number of disjoint rectangles. Now, in this case, let's look at all squares of size $2\times 2$, note that there cannot be exactly $3$ filled cells in each of them.
     69 
     70 It is also clear that if there are $3$ such cells, then there will be two intersecting rectangles. Therefore, you just need to check if there is a $2\times 2$ square in which there are exactly $3$ colored cells.
     71 
     72 **Code**
     73 
     74 ```
     75 #include <bits/stdc++.h>
     76  
     77 using namespace std;
     78  
     79 void solve() {
     80     int n, m;
     81     cin >> n >> m;
     82     vector<vector<int>> a(n, vector<int> (m));
     83     for (int i = 0; i < n; ++i) {
     84         string s;
     85         cin >> s;
     86         for (int j = 0; j < m; ++j) {
     87             a[i][j] = s[j] - '0';
     88         }
     89     }
     90     for (int i = 0; i < n - 1; ++i) {
     91         for (int j = 0; j < m - 1; ++j) {
     92             int sum = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
     93             if (sum == 3) {
     94                 cout << "NO\n";
     95                 return;
     96             }
     97         }
     98     }
     99     cout << "YES\n";
    100 }
    101  
    102 int main() {
    103     ios_base::sync_with_stdio(0);
    104     cin.tie(0);
    105  
    106     int t;
    107     cin >> t;
    108     while (t--)
    109         solve();
    110 }
    111 ```
    112 
    113 ---
    114 
    115 Задача C. Idea [FairyWinx](/profile/FairyWinx "Master FairyWinx")
    116 
    117 **Hint 1**
    118 
    119 There is always an answer when the upper right cell is painted white.
    120 
    121 **Hint 1**
    122 
    123 Imagine that you have only rectangles of size $1\times 2$.
    124 
    125 **Hint 2**
    126 
    127 Paint over the cells from the "end".
    128 
    129 **Solution**
    130 
    131 According to the condition, if the upper left cell is painted black, then we cannot paint it that way. Otherwise it is possible. Let's colour the cells in the following order: $(n,m), (n,m - 1), \ldots, (n, 1), (n - 1, m), \ldots (1, 1)$.
    132 
    133 Let the cell $(i, j)$ be colored black, then if $j \gt 1$, then just paint the rectangle $(i, j - 1)$, $(i, j)$. Otherwise, if $j = 1$, then we will color the rectangle $(i - 1, j)$.
    134 
    135 After such an operation, no cells that we painted before will be repainted, since they have one coordinate larger than ours, and the cell itself will be painted black.
    136 
    137 Thus, we are able to paint the table for a maximum of $n\cdot m - 1$ operations.
    138 
    139 **Code**
    140 
    141 ```
    142 #include <bits/stdc++.h>
    143  
    144 using namespace std;
    145  
    146 void solve() {
    147     int n, m;
    148     cin >> n >> m;
    149     vector<vector<int>> a(n, vector<int> (m));
    150     for (int i = 0; i < n; ++i) {
    151         string s;
    152         cin >> s;
    153         for (int j = 0; j < m; ++j)
    154             a[i][j] = s[j] - '0';
    155     }
    156     vector<array<int, 4>> ans;
    157     if (a[0][0] == 1) {
    158         cout << -1<< '\n';
    159         return;
    160     }
    161     
    162     for (int j = m - 1; j >= 0; --j) {
    163         for (int i = n - 1; i >= 0; --i) {
    164             if (a[i][j]) {
    165                 if (i != 0) {
    166                     ans.push_back({i, j + 1, i + 1, j + 1});
    167                 } else {
    168                     ans.push_back({i + 1, j, i + 1, j + 1});
    169                 }
    170             }
    171         }
    172     }
    173     cout << ans.size() << '\n';
    174     for (auto i : ans) {
    175         cout << i[0] << ' ' << i[1] << ' ' << i[2] << ' ' << i[3] << '\n';
    176     }
    177 }
    178  
    179 int main() {
    180     ios_base::sync_with_stdio(0);
    181     cin.tie(0);
    182  
    183     int t;
    184     cin >> t;
    185     while (t--)
    186         solve();
    187 }
    188 ```
    189 
    190 ---
    191 
    192 Задача D. Idea [FairyWinx](/profile/FairyWinx "Master FairyWinx")
    193 
    194 **An important fact**
    195 
    196 A number is beautiful only if it is a multiple of $d$, but not a multiple of $d^2$
    197 
    198 **Hint 1.1**
    199 
    200 Let's solve a more general problem: count the number of such partitions.
    201 
    202 **Hint 1.2**
    203 
    204 This problem is solved by dynamic programming.
    205 
    206 **Hint 1.3**
    207 
    208 Keep the remaining number in dynamics, as well as the last divisor.
    209 
    210 **Solution 1**
    211 
    212 Let's solve a more complex problem: calculate the number of partitions into such multipliers.
    213 
    214 This is easily solved by dynamic programming. Let $dp_{n, d}$ be the number of factorizations, if we have a number left to decompose the number $n$, and before that we divided by the number $d$. Let's go through all such beautiful numbers $i\geq d$ that divide $n$, then $dp_{n /i, i} += dp_{n, d}$.
    215 
    216 Note that in this case, we took into account each option exactly once, since we count the divisors in the order of their increase.
    217 
    218 Let $C$ be the number of divisors of the number $x$, and $V$ be the number of beautiful divisors of the number $x$. Then it works for $O(C\cdot V)$ or $O(C\cdot V^2\cdot log)$ depending on the implementation (since $n$ is always a divisor of the number $x$), but it all comes easily, since $V$ is no more $700$.
    219 
    220 **Code**
    221 
    222 ```
    223 #include <bits/stdc++.h>
    224  
    225 using namespace std;
    226  
    227 bool good(int i, int d) {
    228     return i % d == 0 && i % (1ll * d * d) != 0;
    229 }
    230  
    231 void solve() {
    232     int x, d;
    233     cin >> x >> d;
    234     map<pair<int, int>, int> dp;
    235     dp[{x, 1}] = 1;
    236     int res = 0;
    237     vector<int> del;
    238     for (int i = 1; i * i <= x; ++i) {
    239         if (x % i == 0) {
    240             if (good(i, d))
    241                 del.push_back(i);
    242             if (x != i * i && good(x / i, d))
    243                 del.push_back(x / i);
    244         }
    245     }
    246     while (dp.size()) {
    247         auto z = *dp.rbegin();
    248         if (z.first.first == 1) {
    249             res += z.second;
    250         }
    251         for (auto i : del) {
    252             if (z.first.first % i == 0 && i >= z.first.second) {
    253                 dp[{z.first.first / i, i}] = min(dp[{z.first.first / i, i}] + z.second, 2);
    254             }
    255         }
    256         dp.erase(z.first);
    257     }
    258     if (res == 1)
    259         cout << "NO\n";
    260     else
    261         cout << "YES\n";
    262 }
    263  
    264 int main() {
    265     ios_base::sync_with_stdio(0);
    266     cin.tie(0);
    267  
    268     int t;
    269     cin >> t;
    270     while (t--)
    271         solve();
    272 }
    273 ```
    274 
    275 **Hint 2.1**
    276 
    277 Consider the case ![dw_smiley](/predownloaded/9a/b5/9ab563b1a2afd666eecce1a2949cf939fbd1aba6.gif)
    278 
    279 **Solution 2 (which almost everyone wrote)**
    280 
    281 Let $x = d^a\cdot b$. Where $b$ is not a multiple of $d$.
    282 
    283 Then consider a few cases:
    284 
    285 * $a = 1$. Then $a$ is a beautiful number, since any number multiple of $d^2$ can be decomposed into $d\cdot(a/d)$, each of which is colored, and a number multiple of only $d$, obviously, cannot be decomposed. So in this case there is exactly one option.
    286 * $b$ is composite, then obviously we can decompose in several ways if $a\neq 1$.
    287 * $d$ is simple. If $b$ is prime, then the statement — we have only one option to decompose the number. Since every beautiful multiplier of the form $d\cdot k$. But since $d$ is simple, there are no other ways to decompose it, except to add a multiplier from $b$, and since $b$ is simple, then all these options will be equal before the permutation.
    288 * $d$ is composite and is not a power of prime. If $a\leq 2$, then this case is no different from the past, since we still have to get two beautiful multipliers and they will all just be equal to $d$. Otherwise, let $d = p\cdot q$, where $gcd(p, q) = 1$. Then we can make the number $p\cdot q^{b - 1}$ and $p^{b - 1}\cdot q$. And also $q\cdot p, q\cdot p, \ldots , q\cdot p$, in this case we have a different number of divisors, so these options will be different, which means we have several options in this case.
    289 * $d$ is the power of a prime number. Then $d = p^k$. The statement, if $d = p^2$, and $x =p^7$, then it cannot be decomposed in several ways, otherwise, if $a \gt 2$ and $k \gt 1$, then let's look at the partition of $p^{2k - 1}, p^{k+1}, p^k, \ldots , p^k$, it is clear that if $k \gt 2$, then even if $b = p$, then the multiplier of $p^{k+ 2}$ will still be beautiful, so it does not differ from the composite $d$ in last case. Otherwise, if $k = 2$, then if $a = 3$ and $b = p$, then nothing can be added, otherwise we will have the opportunity to choose $3$ of the multiplier $p^k$, and somehow decompose the rest (since in this case $a \gt 3$, then at least one more multiplier will be) and add $b$ there. And we can decompose these 3 multipliers into $2$ or $3$ multipliers, as written above. Therefore, the only unique case when $d$ is the degree of a prime is $d = p^2, x = p^7$.
    290 
    291 **Реализация**
    292 
    293 ```
    294 #include <bits/stdc++.h>
    295  
    296 using namespace std;
    297  
    298 int prime(int x) {
    299     for (int i = 2; i * i <= x; ++i) {
    300         if (x % i == 0)
    301             return i;
    302     }
    303     return -1;
    304 }
    305  
    306 void solve() {
    307     int x, d;
    308     cin >> x >> d;
    309     int cnt = 0;
    310     while (x % d == 0) {
    311         ++cnt;
    312         x /= d;
    313     }
    314     if (cnt == 1) {
    315         cout << "NO\n";
    316         return;
    317     }
    318     if (prime(x) != -1) {
    319         cout << "YES\n";
    320         return;
    321     }
    322     if (prime(d) != -1 && d == prime(d) * prime(d)) {
    323         if (x == prime(d) && cnt == 3) {
    324             cout << "NO\n";
    325             return;
    326         }
    327     }
    328     if (cnt > 2 && prime(d) != -1) {
    329         cout << "YES\n";
    330         return;
    331     }
    332     cout << "NO\n";
    333 }
    334  
    335 int main() {
    336     ios_base::sync_with_stdio(0);
    337     cin.tie(0);
    338     
    339     int t;
    340     cin >> t;
    341     while (t--)
    342         solve();
    343 }
    344 ```
    345 
    346 ---
    347 
    348 Задача E. Idea [FairyWinx](/profile/FairyWinx "Master FairyWinx")
    349 
    350 **Hint 1**
    351 
    352 After each operation, the maximum number is always increased by a specific number.
    353 
    354 **Hint 2**
    355 
    356 Students with a number greater than $n$ are not interested in us.
    357 
    358 **Hint 3**
    359 
    360 Imagine that schoolchildren are not expelled, but at any given time we are just interested in a student with a minimum number. Obviously, the answer in this case will not change in any way.
    361 
    362 **Hint 4**
    363 
    364 Understand that every student will move to one particular desk after all the operations.
    365 
    366 **Hint 5**
    367 
    368 Write a greedy ![dw_smiley](/predownloaded/81/1f/811f0005ac46f06725274786a34a2080609f03ee.gif)
    369 
    370 **Solution**
    371 
    372 After each lesson, the person's number increases from the maximum number by the number of desks where no one goes. Therefore, it is easy to calculate how much time has passed since the very beginning, let it be the number $k$.
    373 
    374 Then let's imagine that schoolchildren are not expelled, but at any given time we are simply interested in a student with a minimum number. Obviously, the answer in this case will not change in any way.
    375 
    376 Let $to_i$ be the desk to which the student will move after $k$ transfers, who originally sat at $i$ desk. This is a standard problem that can be solved using binary lifts or not the most pleasant dfs with cycle allocation and the like. (but we do not recommend you to write the latter), we define the set $V_i$ as the set of all numbers $j$, where $to_j = i$.
    377 
    378 Let the starting placement of the student be a permutation of $b$, then we will understand that if someone is transferred to the $i$ desk after $k$ operations, then the value in it is the minimum value in $V_i$. And if no one changes seats for it, then a student with the same number will always sit in it, regardless of the initial seating arrangement. After that, it is not difficult to guess the optimal starting seating of schoolchildren.
    379 
    380 Let $s$ be a lot of schoolchildren for whom we have not yet chosen the desk at which they are sitting. We will iterate over $i$ from $1$ to $n$ in ascending order. Then you need to understand who should sit at the $i$ desk.
    381 
    382 If we know that there is a desk for which $min(V_i) = i$ must be performed, then we must put a student with the minimum number of $V_i$ at $i$, and we can put the remaining people at any desks with a number greater than $i$, so we will add all the other students to the set $s$. Otherwise, we just need to take a person from $s$ with the minimum number and put him in a place under the number $i$, and then just remove him from the set of $s$.
    383 
    384 **Реализация**
    385 
    386 ```
    387 #include <bits/stdc++.h>
    388  
    389 using namespace std;
    390  
    391 const int K = 30;
    392  
    393 int main() {
    394     ios_base::sync_with_stdio(0);
    395     cin.tie(0);
    396  
    397     int n;
    398     cin >> n;
    399     vector<int> cnt(n);
    400     vector<vector<int>> up(n, vector<int> (K));
    401     for (int i = 0; i < n; ++i) {
    402         int a;
    403         cin >> a;
    404         --a;
    405         ++cnt[a];
    406         up[i][0] = a;
    407     }
    408     for (int k = 1; k < K; ++k) {
    409         for (int i = 0; i < n; ++i) {
    410             up[i][k] = up[up[i][k - 1]][k - 1];
    411         }
    412     }
    413     vector<int> a(n);
    414     int cnt_bad = 0;
    415     for (int i = 0; i < n; ++i) {
    416         cin >> a[i];
    417         if (!cnt[i]) {
    418             ++cnt_bad;
    419         }
    420     }
    421     int k = (*max_element(a.begin(), a.end()) - n) / cnt_bad;
    422     vector<vector<int>> add(n);
    423  
    424     for (int i = 0; i < n; ++i) {
    425         int v = i, level = k;
    426         for (int j = K - 1; j >= 0; --j) {
    427             if (level >= (1 << j)) {
    428                 level -= (1 << j);
    429                 v = up[v][j];
    430             }
    431         }
    432         add[a[v] - 1].push_back(i);
    433     }
    434     set<int> now;
    435     vector<int> ans(n);
    436     for (int i = 0; i < n; ++i) {
    437         if (add[i].size()) {
    438             int res = *min_element(add[i].begin(), add[i].end());
    439             for (int j : add[i]) {
    440                 if (j != res) {
    441                     now.emplace(j);
    442                 }
    443             }
    444             ans[res] = i + 1;
    445         } else {
    446             ans[*now.begin()] = i + 1;
    447             now.erase(*now.begin());
    448         }
    449     }
    450     for (int i : ans)
    451         cout << i << ' ';
    452     cout << '\n';
    453 }
    454 ```
    455 
    456 ---
    457 
    458 Задача F. Idea [Igorbunov](/profile/Igorbunov "Grandmaster Igorbunov")
    459 
    460 **Hint 1**
    461 
    462 Realize that the maximum element is always an "inflection" of the first sequence.
    463 
    464 **Hint 2**
    465 
    466 It can be assumed that the "inflection" of the second subsequence will always be to the left of the maximum element (if anything, you can then simply expand the array).
    467 
    468 **Hint 3**
    469 
    470 In total, we have $3$ points in time — both subsequences increase, the first decreases, and the second increases, or both subsequences decrease.
    471 
    472 **Hint 4**
    473 
    474 The first and third cases are solved by obvious greed.
    475 
    476 **Hint 5**
    477 
    478 For the second one, you can simply write the dynamics.
    479 
    480 **Solution**
    481 
    482 The inflection of the sequence is the maximum number in the subsequence. Then note that in the first subsequence, the inflection will be the maximum number in our array, let its position in the array be $ind$.
    483 
    484 Then let's say for convenience that the inflection of the second subsequence will be to the right of the maximum element. (then expand the array and run the solution one more time).
    485 
    486 In this case, we will have $3$ states: both subsequences increase, the first decreases, and the second increases, or both subsequences decrease.
    487 
    488 Let's solve the first case first:
    489 
    490 Let $dp1_i$ be the minimum possible maximum element in a subsequence that does not contain an $i$ element. It is considered not difficult. If $dp1_{i - 1} \lt a_{i}$, then $dp1_{i} = min(dp1_{i}, a_{i - 1})$, since in this case we can add an $i$ element to a subsequence that does not contain an element of $i - 1$. Similarly, if $a_{i - 1} \lt a_{i}$, then $dp1_{i} = min(dp1_{i}, dp1_{i - 1})$.
    491 
    492 The third case is considered anologically, but only it needs to be counted from the end. (This array will be $dp3$)
    493 
    494 Now let's deal with the second case:
    495 
    496 Let $dp2_{i, 0}$ be the minimum possible last element in the second subsequence if the $i$ element belongs to the first subsequence. And $dp2_{i, 1}$ is the maximum possible last element in the first subsequence if the $i$ element belongs to the second subsequence. There are several options. If $i$ and $i - 1$ lie in the same and different subsequences. And we will count for $i\leq ind$, since before this section both sub-sequences increase, and this is another calculated case. And then it is not difficult to get the conversion formulas:
    497 
    498 * $dp2_{ind, 0} = dp1_{ind}$, by definition $dp2_{ind, 0}$
    499 * If $a_{i - 1} \gt a_i$, then $dp2_{i, 0} = min(dp2_{i, 0}, dp2_{i - 1, 0})$.
    500 * If $dp2_{i - 1, 1} \gt a_i$, then $dp2_{i, 0} = min(dp2_{i, 0}, a_{i - 1})$.
    501 * If $a_{i - 1} \lt a_{i}$, then $dp2_{i, 1} = max(dp2_{i, 1}, dp3_{i - 1, 1})$.
    502 * If $dp2_{i - 1, 0} \lt a_i$, then $dp2_{i, 1} = max(dp2_{i, 1}, a_{i - 1})$.
    503 
    504 Now let's understand that the element with the number $i$ can be an inflection of the second subsequence if $i \gt ind$, as well as $dp2_{i, 1} \gt dp3_{i}$. That is, we can move from the second state to the third.
    505 
    506 **Реализация**
    507 
    508 ```
    509 #include <bits/stdc++.h>
    510  
    511 using namespace std;
    512  
    513 const int inf = 1e9 + 228;
    514  
    515 int solve (int n, vector<int> a) {
    516     int ind = max_element(a.begin(), a.end()) - a.begin();
    517     vector<int> dp1(n, inf);
    518     dp1[0] = -1;
    519     for (int i = 1; i <= ind; ++i) {
    520         if (a[i] > dp1[i - 1])
    521             dp1[i] = min(dp1[i], a[i - 1]);
    522         if (a[i] > a[i - 1])
    523             dp1[i] = min(dp1[i], dp1[i - 1]);
    524     }
    525  
    526     vector<int> dp2(n, inf);
    527     dp2[n - 1] = -1;
    528     for (int i = n - 2; i >= ind; --i) {
    529         if (a[i] > dp2[i + 1])
    530             dp2[i] = min(dp2[i], a[i + 1]);
    531         if (a[i] > a[i + 1])
    532             dp2[i] = min(dp2[i], dp2[i + 1]);
    533     }
    534  
    535     vector<array<int, 2>> dp3(n, {inf, -inf});
    536     dp3[ind][0] = dp1[ind];
    537     int ans = 0;
    538     for (int i = ind + 1; i < n; ++i) {
    539         if (a[i - 1] > a[i])
    540             dp3[i][0] = min(dp3[i][0], dp3[i - 1][0]);
    541         if (dp3[i - 1][1] > a[i])
    542             dp3[i][0] = min(dp3[i][0], a[i - 1]);
    543         
    544         if (a[i - 1] < a[i])
    545             dp3[i][1] = max(dp3[i][1], dp3[i - 1][1]);
    546         if (dp3[i - 1][0] < a[i])
    547             dp3[i][1] = max(dp3[i][1], a[i - 1]);
    548         
    549         if (dp3[i][1] > dp2[i])
    550             ++ans;
    551     }
    552     return ans;
    553 }
    554  
    555 signed main() {
    556     ios_base::sync_with_stdio(0);
    557     cin.tie(0);
    558  
    559     int n;
    560     cin >> n;
    561     vector<int> a(n);
    562     for (int i = 0; i < n; ++i)
    563         cin >> a[i];
    564     int ans = solve(n, a);
    565     reverse(a.begin(), a.end());
    566     cout << ans + solve(n, a) << '\n';
    567 }
    568 ```