codeforces-scrape

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

1634.md (11508B)


      1 Source: https://codeforces.com/blog/entry/99563
      2 
      3 Thank you for participating, we hope you enjoyed the problems! We kindly ask you to rate each of the round's problems in the corresponding spoiler in order to improve the quality of future contests.
      4 
      5 You can also check video editorials of problems B and C on [competitive__programmer](/profile/competitive__programmer "Specialist competitive__programmer") [Youtube channel](https://www.youtube.com/channel/UCnZ5rC2_JY0EuYMGMiAbISg).
      6 
      7 All problems were prepared by [Alexdat2000](/profile/Alexdat2000 "International Master Alexdat2000") with the help of coauthors.
      8 
      9 [Why didn't AI participate](https://codeforces.com/blog/entry/99579?#comment-884764)
     10 
     11 [1634A - Reverse and Concatenate](/contest/1634/problem/A "Codeforces Round 770 (Div. 2)")  
     12  Idea: [sevlll777](/profile/sevlll777 "International Master sevlll777")
     13 
     14 **Hint 1**
     15 
     16 What property will the string have after the first operation (regardless of the type of operation)?
     17 
     18 **Hint 2**
     19 
     20 What happens if you apply an operation to a palindrome?
     21 
     22 **Tutorial**
     23 
     24 Tutorial is loading...
     25 
     26 **Solution**
     27 
     28 [145468383](/contest/1634/submission/145468383 "Submission 145468383 by sevlll777")
     29 
     30 ```
     31 q = int(input())
     32 
     33 for _ in range(q):
     34     n, k = map(int, input().split())
     35     s = input()
     36     if s == s[::-1] or k == 0:
     37         print(1)
     38     else:
     39         print(2)
     40 ```
     41 
     42 **Rate the problem**
     43 
     44 * Didn't solve
     45 * Good problem
     46 * Average problem
     47 * Bad problem
     48 
     49 [1634B - Fortune Telling](/contest/1634/problem/B "Codeforces Round 770 (Div. 2)")  
     50  Idea: [crazyilian](/profile/crazyilian "Master crazyilian") and [antontrygubO_o](/profile/antontrygubO_o "International Grandmaster antontrygubO_o")
     51 
     52 **Hint 1**
     53 
     54 Can you figure out which of your friends can't get the number $y$ regardless of the order of operations? The answer to the problem would be the other person, since the jury guarantees that exactly one of your friends could get it.
     55 
     56 **Hint 2**
     57 
     58 What do the numbers $a \oplus b$ and $a + b$ have in common for any $a, b$?
     59 
     60 **Hint 3**
     61 
     62 What do all the numbers that can be obtained by all combinations of operations starting with $x$ have in common? Does the set of these numbers intersect with the set of numbers that can be obtained starting with $x + 3$?
     63 
     64 **Tutorial**
     65 
     66 Tutorial is loading...
     67 
     68 **Solution**
     69 
     70 [145468445](/contest/1634/submission/145468445 "Submission 145468445 by sevlll777")
     71 
     72 ```
     73 def main():
     74     n, x, y = map(int, input().split())
     75     a = list(map(int, input().split()))
     76     if (sum(a) + x + y) % 2 == 0:
     77         print('Alice')
     78     else:
     79         print('Bob')
     80 
     81 for _ in range(int(input())):
     82     main()
     83 ```
     84 
     85 **Rate the problem**
     86 
     87 * Didn't solve
     88 * Good problem
     89 * Average problem
     90 * Bad problem
     91 
     92 [1634C - OKEA](/contest/1634/problem/C "Codeforces Round 770 (Div. 2)")  
     93  Idea: [sevlll777](/profile/sevlll777 "International Master sevlll777")
     94 
     95 **Hint 1**
     96 
     97 If $k \gt 1$, for which $n$ is there no solution?
     98 
     99 **Hint 1.1**
    100 
    101 For which $n$ is there no solution when $k = 2$? Does the same rule of thumb hold for other $k \gt 1$?
    102 
    103 **Hint 2**
    104 
    105 Note that the array $[1, 3, 5, 7, 9, ...]$ satisfies the requirements (that is, the arithmetic mean of each subsegment is an integer) because the sum of the first $X$ elements of this array is $X^2$. Try to generalize this special case and find other arrays that satisfy the conditions.
    106 
    107 **Tutorial**
    108 
    109 Tutorial is loading...
    110 
    111 **Solution**
    112 
    113 [145468509](/contest/1634/submission/145468509 "Submission 145468509 by sevlll777")
    114 
    115 ```
    116 def solve():
    117     n, k = map(int, input().split())
    118     if k == 1:
    119         print("YES")
    120         for i in range(1, n + 1):
    121             print(i)
    122         return
    123 
    124     if n % 2 == 1:
    125         print("NO")
    126         return
    127 
    128     print("YES")
    129     for i in range(1, n + 1):
    130         print(*[i for i in range(i, n * k + 1, n)])
    131 
    132 for _ in range(int(input())):
    133     solve()
    134 ```
    135 
    136 **Rate the problem**
    137 
    138 * Didn't solve
    139 * Good problem
    140 * Average problem
    141 * Bad problem
    142 
    143 [1634D - Finding Zero](/contest/1634/problem/D "Codeforces Round 770 (Div. 2)")  
    144  Idea: [sevlll777](/profile/sevlll777 "International Master sevlll777")
    145 
    146 **Hint 1**
    147 
    148 The problem can be reworded as follows: find $n - 2$ indices that definitely can't contain a zero.
    149 
    150 **Hint 2**
    151 
    152 Solve the problem for $n = 4$.
    153 
    154 **Hint 2.1**
    155 
    156 For $n = 4$, denote by $\bar{i}$ the answer to the query for the three indices except $i$. Knowing $\bar{1}$, $\bar{2}$, $\bar{3}$, and $\bar{4}$, can you find two indexes that don't contain zero for certain? Use the fact that there is exactly one zero in the array.
    157 
    158 **Hint 3**
    159 
    160 Solve the problem for even $n$ using the solution for $n = 4$.
    161 
    162 **Tutorial**
    163 
    164 Tutorial is loading...
    165 
    166 **Solution**
    167 
    168 [145469065](/contest/1634/submission/145469065 "Submission 145469065 by sevlll777")
    169 
    170 ```
    171 #include <bits/stdc++.h>
    172  
    173 #define all(x) (x).begin(), (x).end()
    174 #define len(x) (int) (x).size()
    175  
    176 using namespace std;
    177  
    178  
    179 int get(const vector <int>& x) {
    180     cout << "? " << x[0] + 1 << " " << x[1] + 1 << " " << x[2] + 1 << endl;
    181     int ans;
    182     cin >> ans;
    183     return ans;
    184 }
    185  
    186  
    187 signed main() {
    188     ios_base::sync_with_stdio();
    189     cin.tie(nullptr);
    190     
    191     int t;
    192     cin >> t;
    193     
    194     while(t --> 0) {
    195         int n;
    196         cin >> n;
    197     
    198         pair <int, int> possible = {0, 1};
    199         for (int i = 2; i < n - 1; i += 2) {
    200             vector <pair <int, int>> ch(4);
    201             vector <int> now = {possible.first, possible.second, i, i + 1};
    202             for (int j = 0; j < 4; j++) {
    203                 vector <int> x = now;
    204                 x.erase(x.begin() + j);
    205                 ch[j] = {get(x), now[j]};
    206             }
    207             sort(all(ch));
    208             possible = {ch[0].second, ch[1].second};
    209         }
    210         if (n % 2 == 1) {
    211             int other = 0;
    212             while (possible.first == other || possible.second == other) {
    213                 other++;
    214             }
    215             vector <pair <int, int>> ch(4);
    216             vector <int> now = {possible.first, possible.second, n - 1, other};
    217             for (int j = 0; j < 4; j++) {
    218                 vector <int> x = now;
    219                 x.erase(x.begin() + j);
    220                 ch[j] = {get(x), now[j]};
    221             }
    222             sort(all(ch));
    223             possible = {ch[0].second, ch[1].second};
    224         }
    225         cout << "! " << possible.first + 1 << " " << possible.second + 1 << endl;
    226     }
    227  
    228     return 0;
    229 }
    230 ```
    231 
    232 **Rate the problem**
    233 
    234 * Didn't solve
    235 * Good problem
    236 * Average problem
    237 * Bad problem
    238 
    239 [1634E - Fair Share](/contest/1634/problem/E "Codeforces Round 770 (Div. 2)")  
    240  Idea: [sevlll777](/profile/sevlll777 "International Master sevlll777")
    241 
    242 **Hint 1**
    243 
    244 In what cases is the answer definitely NO?
    245 
    246 **Hint 2**
    247 
    248 The lengths of all arrays are even numbers, and each number appears an even number of times in total. There are suspiciously many even numbers...
    249 
    250 **Hint 3**
    251 
    252 An Euler circuit is a circuit that passes through all edges of a graph exactly once (or a union of several circuits if the graph is disconnected). It turns out that an Euler circuit exists if and only if the degree of each vertex is even.
    253 
    254 **Hint 4**
    255 
    256 Construct some graph such that the degree of each of its vertices is even, find a directed Eulerian circuit in it, and reconstruct the answer to the problem using this circuit. What do the edges of such graph correspond to?
    257 
    258 **Tutorial**
    259 
    260 Tutorial is loading...
    261 
    262 **Solution**
    263 
    264 [145468656](/contest/1634/submission/145468656 "Submission 145468656 by sevlll777")
    265 
    266 ```
    267 #include <bits/stdc++.h>
    268 
    269 #define len(x) (int) (x).size()
    270 #define all(x) (x).begin(), (x).end()
    271 #define endl "\n"
    272 
    273 using namespace std;
    274 
    275 const int N = 4e5 + 100, H = 2e5 + 50;
    276 vector <pair <int, int>> g[N];
    277 string ans[N];
    278 int pos[N];
    279 
    280 void dfs(int v) {
    281     if (pos[v] == 0) {
    282         ans[v] = string(len(g[v]), 'L');
    283     }
    284 
    285     while (pos[v] < len(g[v])) {
    286         auto [i, ind] = g[v][pos[v]];
    287         if (i == -1) {
    288             pos[v]++;
    289             continue;
    290         }
    291         g[i][ind].first = -1, g[v][pos[v]].first = -1;
    292         if (v < H) {
    293             ans[v][pos[v]] = 'R';
    294         }
    295         pos[v]++;
    296         dfs(i);
    297     }
    298 }
    299 
    300 signed main() {
    301     ios::sync_with_stdio(false);
    302     cin.tie(nullptr);
    303 
    304     int m;
    305     cin >> m;
    306     map <int, int> ind, cnt;
    307     int fre_ind = 0;
    308 
    309     vector <vector <int>> nums(m);
    310     for (int i = 0; i < m; i++) {
    311         int n;
    312         cin >> n;
    313         for (int _ = 0; _ < n; _++) {
    314             int x;
    315             cin >> x;
    316             if (!ind.count(x)) {
    317                 ind[x] = fre_ind++;
    318             }
    319             x = ind[x];
    320             cnt[x]++;
    321             nums[i].push_back(x);
    322             g[i].emplace_back(x + H, len(g[x + H]));
    323             g[x + H].emplace_back(i, len(g[i]) - 1);
    324         }
    325     }
    326 
    327     for (auto [num, cn] : cnt) {
    328         if (cn % 2 == 1) {
    329             cout << "NO" << endl;
    330             return 0;
    331         }
    332     }
    333 
    334     for (int i = 0; i < N; i++) {
    335         dfs(i);
    336     }
    337 
    338     cout << "YES" << endl;
    339     for (int i = 0; i < m; i++) {
    340         cout << ans[i] << endl;
    341     }
    342     return 0;
    343 }
    344 ```
    345 
    346 **Rate the problem**
    347 
    348 * Didn't solve
    349 * Good problem
    350 * Average problem
    351 * Bad problem
    352 
    353 [1634F - Fibonacci Additions](/contest/1634/problem/F "Codeforces Round 770 (Div. 2)")  
    354  Idea: [Mangooste](/profile/Mangooste "Grandmaster Mangooste")
    355 
    356 **Hint 1**
    357 
    358 Let $C_i = A_i - B_i$. Perform all operations on the array $C$.
    359 
    360 **Hint 2**
    361 
    362 Nevermind Fibonacci and suppose the operation was to increase the elements of a given subsegment by a given constant. Can you solve this problem without using heavy data structures like segment tree?
    363 
    364 **Hint 3**
    365 
    366 Generalize the idea from hint 2 using the characteristic property of Fibonacci numbers ($F_i = F_{i-1} + F_{i-2}$).
    367 
    368 **Tutorial**
    369 
    370 Tutorial is loading...
    371 
    372 **Solution**
    373 
    374 [145468716](/contest/1634/submission/145468716 "Submission 145468716 by sevlll777")
    375 
    376 ```
    377 #include <bits/stdc++.h>
    378 
    379 #define all(x) (x).begin(), (x).end()
    380 #define len(x) (int) (x).size()
    381 #define endl "\n"
    382 #define int long long
    383 
    384 using namespace std;
    385 
    386 const int N = 3e5 + 100;
    387 int MOD;
    388 int fib[N];
    389 
    390 vector <int> unfib;
    391 int notzero = 0;
    392 
    393 void upd(int ind, int delta) {
    394   notzero -= (unfib[ind] != 0);
    395   unfib[ind] += delta;
    396   if (unfib[ind] >= MOD) {
    397     unfib[ind] -= MOD;
    398   };
    399   notzero += (unfib[ind] != 0);
    400 }
    401 
    402 signed main() {
    403   ios_base::sync_with_stdio(false);
    404   cin.tie(nullptr);
    405   cout.tie(nullptr);
    406 
    407   int n, q;
    408   cin >> n >> q >> MOD;
    409 
    410   fib[0] = fib[1] = 1;
    411   for (int i = 2; i < N; i++) {
    412     fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
    413   }
    414 
    415   vector <int> delta(n);
    416   for (int& i : delta) {
    417     cin >> i;
    418   }
    419   for (int i = 0; i < n; i++) {
    420     int x;
    421     cin >> x;
    422     delta[i] = (delta[i] - x + MOD) % MOD;
    423   }
    424 
    425   unfib.resize(n);
    426   unfib[0] = delta[0];
    427   if (len(unfib) >= 2) {
    428     unfib[1] = (delta[1] - delta[0] + MOD) % MOD;
    429   }
    430   for (int i = 2; i < n; i++) {
    431     unfib[i] = ((long long) delta[i] - delta[i - 1] - delta[i - 2] + MOD * 2) % MOD;
    432   }
    433   for (int i = 0; i < n; i++) {
    434     notzero += (unfib[i] != 0);
    435   }
    436 
    437   while (q--) {
    438     char c;
    439     int l, r;
    440     cin >> c >> l >> r;
    441     if (c == 'A') {
    442       upd(l - 1, 1);
    443       if (r != n) {
    444         upd(r, MOD - fib[r - l + 1]);
    445       }
    446       if (r < n - 1) {
    447         upd(r + 1, MOD - fib[r - l]);
    448       }
    449     } else {
    450       upd(l - 1, MOD - 1);
    451       if (r != n) {
    452         upd(r, fib[r - l + 1]);
    453       }
    454       if (r < n - 1) {
    455         upd(r + 1, fib[r - l]);
    456       }
    457     }
    458     if (!notzero) {
    459       cout << "YES" << endl;
    460     } else {
    461       cout << "NO" << endl;
    462     }
    463   }
    464   return 0;
    465 }
    466 ```
    467 
    468 **Rate the problem**
    469 
    470 * Didn't solve
    471 * Good problem
    472 * Average problem
    473 * Bad problem