codeforces-scrape

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

1979.md (14731B)


      1 Source: https://codeforces.com/blog/entry/130213
      2 
      3 Thank you for participating!
      4 
      5 ## [1979A - Guess the Maximum](/contest/1979/problem/A "Codeforces Round 951 (Div. 2)")
      6 
      7 **Solution**
      8 
      9 Let $m$ be the maximum among the numbers $a_i, a_{i + 1},\ldots, a_j$. Notice that there always exists such $k$ that $i \le k \lt j$ and $a_k = m$ or $a_{k + 1} = m$. Therefore, we can assume that Bob always chooses the pair of numbers $p$ and $p + 1$ ($1 \le p \lt n$) as $i$ and $j$.
     10 
     11 Therefore you need to consider the maximums in pairs of adjacent elements and take the minimum among them. Let $min$ be the found minimum, then it is obvious that the answer is equal to $min - 1$.
     12 
     13 **Code**
     14 
     15 ```
     16 #include <iostream>
     17 using namespace std;
     18 
     19 int main() {
     20     int t;
     21     cin >> t;
     22     while (t--) {
     23         int n;
     24         cin >> n;
     25         int a[n];
     26         for (int& i : a) {
     27             cin >> i;
     28         }
     29         int mini = max(a[0], a[1]);
     30         for (int i = 1; i < n - 1; i++) {
     31             mini = min(mini, max(a[i], a[i + 1]));
     32         }
     33         cout << mini - 1 << "\n";
     34     }
     35 }
     36 ```
     37 
     38 ## [1979B - XOR Sequences](/contest/1979/problem/B "Codeforces Round 951 (Div. 2)")
     39 
     40 **Hint**
     41 
     42 Look at samples.
     43 
     44 **Solution**
     45 
     46 Consider two numbers $v$ and $u$ such that $x \oplus v = y \oplus u$. Then consider the numbers $x \oplus (v + 1)$ and $y \oplus (u + 1)$. Let's look at the last bit of $v$ and $u$. Possible scenarios:
     47 
     48 * Both bits are equal to $0$ — adding one will change the bits at the same positions, therefore $x \oplus (v + 1) = y \oplus (u + 1)$;
     49 * Both bits are equal to $1$ — adding one will change the bits at the same positions and also add one to the next bit, therefore we can similarly consider the next bit;
     50 * Bits are different — adding one to the zero bit will only change one bit, while the subsequent bit of the other number will be changed. This means that $x \oplus (v + 1) \neq y \oplus (u + 1)$.
     51 
     52 It is clear that we need to maximize the number of zeros in the maximum matching suffix of $u$ and $v$. Obviously, this number is equal to the maximum matching suffix of $x$ and $y$. Let $k$ be the length of the maximum matching suffix of $x$ and $y$, then the answer is $2^k$.
     53 
     54 This can be calculated in $O(\log C)$ time for one test case, where $C$ is the limit on $x$ and $y$.
     55 
     56 **Code**
     57 
     58 ```
     59 #include <bits/stdc++.h>
     60 using namespace std;
     61 
     62 int main() {
     63     int t;
     64     cin >> t;
     65     while (t--) {
     66         int a, b;
     67         cin >> a >> b;
     68         
     69         for (int i = 0; i < 30; i++) {
     70             if ((a & (1 << i)) != (b & (1 << i))) {
     71                 cout << (1ll << i) << "\n";
     72                 break;
     73             }
     74         }
     75     }
     76 }
     77 ```
     78 
     79 ## [1979C - Earning on Bets](/contest/1979/problem/C "Codeforces Round 951 (Div. 2)")
     80 
     81 **Hint**
     82 
     83 Try to come up with a condition for the existence of an answer.
     84 
     85 **Solution**
     86 
     87 Let $S$ be the total amount of coins placed on all possible outcomes. Then, if the coefficient for winning is $k_i$, we have to place **more** than $\frac{S}{k_i}$ on this outcome.
     88 
     89 We can obtain the following inequality:
     90 
     91 $\sum_{i = 1}^n \frac{S}{k_i} \lt S.$
     92 
     93 Dividing both sides by $S$, we obtain the necessary and sufficient condition for the existence of an answer:
     94 
     95 $\sum_{i = 1}^n \frac{1}{k_i} \lt 1.$
     96 
     97 This check can be performed by reducing all fractions to a common denominator. Notice that the numerators of the reduced fractions correspond to the required bets on the outcomes.
     98 
     99 **Code**
    100 
    101 ```
    102 #include <bits/stdc++.h>
    103 using namespace std;
    104 
    105 #define int long long
    106 
    107 int gcd(int a, int b) {
    108     while (b != 0) {
    109         int tmp = a % b;
    110         a = b;
    111         b = tmp;
    112     }
    113     return a;
    114 }
    115 int lcm(int a, int b) {
    116     return a * b / gcd(a, b);
    117 }
    118 
    119 void solve() {
    120     int n;
    121     cin >> n;
    122     
    123     vector <int> k(n);
    124     for (int i = 0; i < n; i++) {
    125         cin >> k[i];
    126     }
    127     
    128     int z = 1;
    129     for (int i = 0; i < n; i++) {
    130         z = lcm(z, k[i]);
    131     }
    132     
    133     int suma = 0;
    134     for (int i = 0; i < n; i++) {
    135         suma += z / k[i];
    136     }
    137     
    138     if (suma < z) {
    139         for (int i = 0; i < n; i++) {
    140             cout << z / k[i] << " ";
    141         }
    142         cout << "\n";
    143     } else {
    144         cout << -1 << "\n";
    145     }
    146 }
    147 
    148 signed main() {
    149     int t;
    150     cin >> t;
    151     while (t--) {
    152         solve();
    153     }
    154 }
    155 ```
    156 
    157 ## [1979D - Fixing a Binary String](/contest/1979/problem/D "Codeforces Round 951 (Div. 2)")
    158 
    159 **Solution**
    160 
    161 Let's consider the block of characters at the end. Notice that their quantity cannot decrease. Let $x$ be the number of identical characters at the end; there are three possible cases:
    162 
    163 * $x = k$ — it is enough to find any block of length greater than $k$ and separate a block of length $k$ from it;
    164 * $x \gt k$ — obviously, there is no solution;
    165 * $x \lt k$ — find a block of length $k - x$ or $2k - x$ and separate a block of length $k - x$ from it.
    166 
    167 This solution works in $O(n)$, but it is not the only correct one. Your solution may differ significantly from the one proposed.
    168 
    169 **Code**
    170 
    171 ```
    172 #include <bits/stdc++.h>
    173 using namespace std;
    174 
    175 int main() {
    176     int t;
    177     cin >> t;
    178     while (t--) {
    179         int n, k;
    180         cin >> n >> k;
    181         
    182         string s;
    183         cin >> s;
    184         
    185         int x = 0;
    186         for (int i = n - 1; i >= 0; i--) {
    187             if (s[i] == s[n - 1]) {
    188                 x++;
    189             } else {
    190                 break;
    191             }
    192         }
    193         
    194         auto check = [&]() {
    195             for (int i = 0; i < k; i++) {
    196                 if (s[i] != s[0]) return false;
    197             }
    198             for (int i = 0; i + k < n; i++) {
    199                 if (s[i] == s[i + k]) return false;
    200             }
    201             return true;
    202         };
    203         
    204         auto operation = [&](int p) {
    205             reverse(s.begin(), s.begin() + p);
    206             s = s.substr(p, (int)s.size() - p) + s.substr(0, p);
    207             if (check()) {
    208                 cout << p << "\n";
    209             } else {
    210                 cout << -1 << "\n";
    211             }
    212         };
    213         
    214         if (x == k) {
    215             int p = n;
    216             for (int i = n - 1 - k; i >= 0; i--) {
    217                 if (s[i] == s[i + k]) {
    218                     p = i + 1;
    219                     break;
    220                 }
    221             }
    222             operation(p);
    223         } else if (x > k) {
    224             cout << -1 << "\n";
    225         } else {
    226             bool was = false;
    227             for (int i = 0; i < n; i++) {
    228                 if (s[i] != s.back()) continue;
    229                 int j = i;
    230                 while (j + 1 < n && s[i] == s[j + 1]) {
    231                     j++;
    232                 }
    233                 if (j - i + 1 + x == k) {
    234                     operation(j + 1);
    235                     was = true;
    236                     break;
    237                 } else if (j - i + 1 - k + x == k) {
    238                     operation(i + k - x);
    239                     was = true;
    240                     break;
    241                 }
    242                 i = j;
    243             }
    244             if (!was) {
    245                 operation(n);
    246             }
    247         }
    248     }
    249 }
    250 ```
    251 
    252 ## [1979E - Manhattan Triangle](/contest/1979/problem/E "Codeforces Round 951 (Div. 2)")
    253 
    254 **Hint**
    255 
    256 In every Manhattan triangle there are two points such that $|x_1 - x_2| = |y_1 - y_2|$.
    257 
    258 **Solution**
    259 
    260 Note this fact: in every Manhattan triangle there are two points such that $|x_1 - x_2| = |y_1 - y_2|$.
    261 
    262 Let's start with distributing all points with their $(x + y)$ value.
    263 
    264 For each point $(x; y)$ find point $(x + d / 2; y - d / 2)$ using lower bound method in corresponding set. Then we have to find the third point: it can be in either $(x + y + d)$ or $(x + y - d)$ diagonal. Borders at $x$ coordinate for them are $[x + d / 2; x + d]$ and $[x - d / 2; x]$ — it can be found using the same lower bound method.
    265 
    266 Then, distribute all points with $(x - y)$ value and do the same algorithm.
    267 
    268 Total time complexity is $O(n \log n)$.
    269 
    270 **Code**
    271 
    272 ```
    273 #include <bits/stdc++.h>
    274 using namespace std;
    275 
    276 const int MAXC = 1e5;
    277 const int MAXD = 4e5 + 10;
    278 
    279 set <pair <int, int>> diag[MAXD];
    280 
    281 void solve() {
    282     int n, d;
    283     cin >> n >> d;
    284     
    285     vector <int> x(n), y(n);
    286     for (int i = 0; i < n; i++) {
    287         cin >> x[i] >> y[i];
    288         x[i] += MAXC;
    289         y[i] += MAXC;
    290     }
    291     
    292     bool found = false;
    293     {
    294         for (int i = 0; i < n; i++) {
    295             diag[x[i] + y[i]].insert({x[i], i});
    296         }
    297         for (int i = 0; i < n; i++) {
    298             auto it1 = diag[x[i] + y[i]].lower_bound({x[i] + d / 2, -1});
    299             if (it1 == diag[x[i] + y[i]].end() || it1->first != x[i] + d / 2) continue;
    300             if (x[i] + y[i] + d < MAXD) {
    301                 auto it2 = diag[x[i] + y[i] + d].lower_bound({x[i] + d / 2, -1});
    302                 if (it2 != diag[x[i] + y[i] + d].end() && it2->first <= it1->first + d / 2) {
    303                     cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n";
    304                     found = true;
    305                     break;
    306                 }
    307             }
    308             if (x[i] + y[i] - d >= 0) {
    309                 auto it2 = diag[x[i] + y[i] - d].lower_bound({x[i] - d / 2, -1});
    310                 if (it2 != diag[x[i] + y[i] - d].end() && it2->first <= it1->first - d / 2) {
    311                     cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n";
    312                     found = true;
    313                     break;
    314                 }
    315             }
    316         }
    317         for (int i = 0; i < n; i++) {
    318             diag[x[i] + y[i]].erase({x[i], i});
    319         }
    320     }
    321     if (!found) {
    322         for (int i = 0; i < n; i++) {
    323             y[i] -= 2 * MAXC;
    324             diag[x[i] - y[i]].insert({x[i], i});
    325         }
    326         for (int i = 0; i < n; i++) {
    327             auto it1 = diag[x[i] - y[i]].lower_bound({x[i] + d / 2, -1});
    328             if (it1 == diag[x[i] - y[i]].end() || it1->first != x[i] + d / 2) continue;
    329             if (x[i] - y[i] + d < MAXD) {
    330                 auto it2 = diag[x[i] - y[i] + d].lower_bound({x[i] + d / 2, -1});
    331                 if (it2 != diag[x[i] - y[i] + d].end() && it2->first <= it1->first + d / 2) {
    332                     cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n";
    333                     found = true;
    334                     break;
    335                 }
    336             }
    337             if (x[i] - y[i] - d >= 0) {
    338                 auto it2 = diag[x[i] - y[i] - d].lower_bound({x[i] - d / 2, -1});
    339                 if (it2 != diag[x[i] - y[i] - d].end() && it2->first <= it1->first - d / 2) {
    340                     cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n";
    341                     found = true;
    342                     break;
    343                 }
    344             }
    345         }
    346         for (int i = 0; i < n; i++) {
    347             diag[x[i] - y[i]].erase({x[i], i});
    348         }
    349     }
    350     if (!found) {
    351         cout << "0 0 0\n";
    352     }
    353 }
    354 
    355 int main() {
    356     int t;
    357     cin >> t;
    358     while (t--) {
    359         solve();
    360     }
    361 }
    362 ```
    363 
    364 ## [1979F - Kostyanych's Theorem](/contest/1979/problem/F "Codeforces Round 951 (Div. 2)")
    365 
    366 **Solution**
    367 
    368 Let's consider the following recursive algorithm. We will store the Hamiltonian path as a double-ended queue, maintaining the start and end.
    369 
    370 In case there are only $1$ or $2$ vertices left in the graph, the problem is solved trivially.
    371 
    372 Suppose we know that the current graph has $n$ vertices, and there are **at most** $(n - 2)$ edges missing. Then the total number of edges in such a graph is at least
    373 
    374 $\frac{n(n - 1)}{2} - (n - 2) = \frac{n^2 - 3n + 4}{2}.$
    375 
    376 Let all vertices in the graph have a degree of at most $(n - 3)$, then the total number of edges does not exceed
    377 
    378 $\frac{n(n-3)}{2} = \frac{n^2 - 3n}{2},$
    379 
    380 which is less than the stated value. Hence, we conclude that there is **at least one** vertex with a degree greater than $(n - 3)$.
    381 
    382 If there exists a vertex $v$ with a degree of $(n - 2)$, then it is sufficient to run our recursive algorithm for the remaining graph. Since $v$ is only not connected by an edge to one vertex, $v$ is connected either to the start or the end of the maintained path in the remaining graph. Thus, we can insert the vertex $v$ either at the beginning or at the end of the path.
    383 
    384 Otherwise, let $u$ be the vertex with a degree of $(n - 1)$. There is at least one vertex $w$ with a degree not exceeding $(n - 3)$. Remove $u$ and $w$ from the graph. Notice that the number of edges in such a graph does not exceed
    385 
    386 $\frac{n^2 - 3n + 4}{2} - (n - 1) - (n - 3) + 1 = \frac{n^2 - 7n + 14}{2}$ $\frac{n^2 - 7n + 14}{2} = \frac{n^2 - 5n + 6}{2} - \frac{2n - 8}{2}$ $\frac{n^2 - 5n + 6}{2} - \frac{2n - 8}{2} = \frac{(n - 2)(n - 3)}{2} - (n - 4)$ $\frac{(n - 2)(n - 3)}{2} - (n - 4) = \frac{(n - 2)((n - 2) - 1)}{2} - ((n - 2) - 2).$
    387 
    388 The invariant is preserved, so we can run the algorithm for the remaining graph. Then, we can arrange the vertices in the following order: $w$ — $u$ — $s$ — ..., where $s$ — the start of the Hamiltonian path in the remaining graph.
    389 
    390 It remains to understand how to use queries.
    391 
    392 Make a query $d = (n - 2)$. Let $u$ be the second number in the response to our query. If $u \neq 0$, the degree of vertex $v$ is $(n - 2)$. Run our recursive algorithm, and then compare the start and end of the obtained path with $u$.
    393 
    394 Otherwise, if $u = 0$, it means the degree of vertex $v$ is $(n - 1)$. In this case, ask about any vertex with a low degree (this can be done with a query $d = 0$). Then simply arrange the vertices in the order mentioned above.
    395 
    396 We will make no more than $n$ queries, and the final asymptotic will be $O(n)$.
    397 
    398 **Code**
    399 
    400 ```
    401 #include <bits/stdc++.h>
    402 using namespace std;
    403 
    404 pair <int, int> ask(int d) {
    405     cout << "? " << d << endl;
    406     int v, u;
    407     cin >> v >> u;
    408     return {v, u};
    409 }
    410  
    411 pair <int, int> get(int n, vector <int>& nxt) {
    412     if (n == 1) {
    413         int v = ask(0).first;
    414         return {v, v};
    415     }
    416     if (n == 2) {
    417         int u = ask(0).first;
    418         int v = ask(0).first;
    419         nxt[u] = v;
    420         return {u, v};
    421     }
    422     pair <int, int> t = ask(n - 2);
    423     int v = t.first;
    424     int ban = t.second;
    425     if (ban != 0) {
    426         pair <int, int> res = get(n - 1, nxt);
    427         if (ban != res.first) {
    428             nxt[v] = res.first;
    429             return {v, res.second};
    430         } else {
    431             nxt[res.second] = v;
    432             return {res.first, v};
    433         }
    434     } else {
    435         int u = ask(0).first;
    436         nxt[u] = v;
    437         pair <int, int> res = get(n - 2, nxt);
    438         nxt[v] = res.first;
    439         return {u, res.second};
    440     }
    441 }
    442  
    443 void solve() {
    444     int n;
    445     cin >> n;
    446     
    447     vector <int> nxt(n + 1, -1);
    448     pair <int, int> ans = get(n, nxt);
    449     
    450     int v = ans.first;
    451     cout << "! ";
    452     do {
    453         cout << v << " ";
    454         v = nxt[v];
    455     } while (v != -1);
    456     cout << endl;
    457 }
    458 
    459 int main() {
    460     int t;
    461     cin >> t;
    462     while (t--) {
    463         solve();
    464     }
    465 }
    466 ```