codeforces-scrape

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

1817.md (17613B)


      1 Source: https://codeforces.com/blog/entry/115586
      2 
      3 [1818A - Политика](/contest/1818/problem/A "Codeforces Round 869 (Div. 2)")
      4 
      5 Problem idea: [adamant](/profile/adamant "Мастер adamant")   
      6  Preparation: [adamant](/profile/adamant "Мастер adamant")
      7 
      8 **Editorial**
      9 
     10 Tutorial is loading...
     11 
     12 **Solution**
     13 
     14 ```
     15 void solve() {
     16     int n, k;
     17     cin >> n >> k;
     18     string t[n];
     19     int ans = n;
     20     for(int i = 0; i < n; i++) {
     21         cin >> t[i];
     22         if(t[i] != t[0]) {
     23             ans--;
     24         }
     25     }
     26     cout << ans << "\n";
     27 }
     28 ```
     29 
     30 [1818B - Неделимые отрезки](/contest/1818/problem/B "Codeforces Round 869 (Div. 2)")
     31 
     32 Problem idea: [adamant](/profile/adamant "Мастер adamant")   
     33  Preparation: [adamant](/profile/adamant "Мастер adamant")
     34 
     35 **Editorial**
     36 
     37 Tutorial is loading...
     38 
     39 **Solution**
     40 
     41 ```
     42 void solve() {
     43     int n;
     44     cin >> n;
     45     if(n == 1) {
     46         cout << 1 << "\n";
     47     } else if(n % 2) {
     48         cout << -1 << "\n";
     49     } else {
     50         int a[n];
     51         iota(a, a + n, 1);
     52         for(int i = 0; i < n; i += 2) {
     53             swap(a[i], a[i + 1]);
     54         }
     55         for(auto it: a) {
     56             cout << it << ' ';
     57         }
     58         cout << "\n";
     59     }
     60 }
     61 ```
     62 
     63 [1817A - Почти возрастающая подпоследовательность](/contest/1817/problem/A "Codeforces Round 869 (Div. 1)")
     64 
     65 Problem idea: [dario2994](/profile/dario2994 "Международный гроссмейстер dario2994")   
     66  Preparation: [jeroenodb](/profile/jeroenodb "Гроссмейстер jeroenodb")
     67 
     68 **Editorial**
     69 
     70 Tutorial is loading...
     71 
     72 **Solution**
     73 
     74 ```
     75 #include "bits/stdc++.h"
     76 using namespace std;
     77 typedef vector<int> vi;
     78 
     79 int main() {
     80     ios_base::sync_with_stdio(false);
     81     cin.tie(NULL);
     82     int n,q; cin >> n >> q;
     83     vi a(n);
     84     for(int& i : a) cin >> i;
     85     vi p(n-1);
     86     for(int i=1;i<n-1;++i) {
     87         int downhill = a[i-1]>=a[i] and a[i]>=a[i+1];
     88         p[i] = p[i-1] + downhill;
     89     }
     90     while(q--) {
     91         int l,r; cin >> l >> r;
     92         --l,--r;
     93         if(l==r) {
     94             cout << "1\n";
     95         } else {
     96             int ans = (r-l+1) - p[r-1] + p[l];
     97             cout << ans << '\n';
     98         }
     99     }
    100 }
    101 ```
    102 
    103 [1817B - Граф-рыба](/contest/1817/problem/B "Codeforces Round 869 (Div. 1)")
    104 
    105 Problem idea: [jeroenodb](/profile/jeroenodb "Гроссмейстер jeroenodb")   
    106  Preparation: [jeroenodb](/profile/jeroenodb "Гроссмейстер jeroenodb")
    107 
    108 **Hint 1**
    109 
    110 Can you find a necessary condition for whether a Fish Subgraph exists?
    111 
    112 **Hint 2**
    113 
    114 For the Fish Subgraph to exist, the graph must have a cycle with one node in the cycle having degree at least 4.
    115 
    116 **Hint 3**
    117 
    118 When the necessary condition is satisfied, actually, you can always find a Fish Subgraph. Try to prove this, and see if your proof can be turned into an algorithm.
    119 
    120 **Editorial**
    121 
    122 Tutorial is loading...
    123 
    124 **Solution**
    125 
    126 ```
    127 #include "bits/stdc++.h"
    128 using namespace std;
    129 #define all(x) begin(x),end(x)
    130 typedef vector<int> vi;
    131 typedef vector<vi> vvi;
    132 typedef pair<int,int> pi;
    133 
    134 void solve() {
    135     int n,m; cin >> n >> m;
    136     vvi adj(n);
    137     while(m--) {
    138         int u,v; cin >> u >> v;
    139         --u,--v;
    140         adj[u].push_back(v);
    141         adj[v].push_back(u);
    142     }
    143     // find cycle and node with big degree.
    144     for(int u=0;u<n;++u) if(adj[u].size()>=4) for(int v : adj[u]) {
    145         // find path from u to v, without edge (u,v)
    146         vi cur;
    147         vi p;
    148         vector<bool> vis(n);
    149         auto dfs = [&](auto&& self, int at) -> void {
    150             vis[at]=1;
    151             cur.push_back(at);
    152             if(at==v) {
    153                 p=cur;
    154                 return;
    155             }
    156             for(int to : adj[at]) if(!vis[to]) {
    157                 if(at==u and to==v) continue;
    158                 self(self,to);
    159                 if(!p.empty()) return;
    160             }
    161             cur.pop_back();
    162         };
    163         dfs(dfs,u);
    164         if(p.empty()) continue;
    165         // found cycle, with a node with degree >=4
    166         vi extra = adj[u];
    167         extra.resize(4);
    168         int mn = p.size();
    169         for(auto i : extra) {
    170             auto it = find(all(p),i);
    171             if(it!=p.begin()+1) {
    172                 mn = min(mn,int(it-p.begin())+1);
    173             }
    174         }
    175         p.resize(mn);
    176         partition(all(extra),[&](int i) {return count(all(p),i)==0;});
    177         extra.resize(2);
    178 
    179         cout << "YES\n";
    180         cout << p.size()+2 << '\n';
    181         auto out = [&](int a, int b) {cout << a+1 << ' ' << b+1 << '\n';};
    182         int prv=p.back();
    183         for(auto i : p) {
    184             out(i,prv);
    185             prv=i;
    186         }
    187         out(u,extra[0]);
    188         out(u,extra[1]);
    189         return;
    190     }
    191 
    192     cout << "NO\n";
    193 }
    194 
    195 int main() {
    196     ios_base::sync_with_stdio(false);
    197     cin.tie(NULL);
    198     int t; cin >> t;
    199     while(t--) solve();
    200 }
    201 ```
    202 
    203 [1817C - Подобные многочлены](/contest/1817/problem/C "Codeforces Round 869 (Div. 1)")
    204 
    205 Problem idea: [adamant](/profile/adamant "Мастер adamant")   
    206  Preparation: [adamant](/profile/adamant "Мастер adamant")
    207 
    208 **Editorial**
    209 
    210 Tutorial is loading...
    211 
    212 **Solution**
    213 
    214 ```
    215 const int mod = 1e9 + 7;
    216 
    217 namespace algebra {
    218     const int maxn = 3e6 + 42;
    219     mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
    220 
    221     template<typename T>
    222     T bpow(T x, size_t n) {
    223         if(n == 0) {
    224             return T(1);
    225         } else {
    226             auto t = bpow(x, n / 2);
    227             t = t * t;
    228             return n % 2 ? x * t : t;
    229         }
    230     }
    231 
    232     const int m = mod;
    233     struct modular {
    234         int r;
    235         constexpr modular(): r(0) {}
    236         constexpr modular(int64_t rr): r(rr % m) {if(r < 0) r += m;}
    237         modular inv() const {return bpow(*this, m - 2);}
    238         modular operator - () const {return r ? m - r : 0;}
    239         modular operator * (const modular &t) const {return (int64_t)r * t.r % m;}
    240         modular operator / (const modular &t) const {return *this * t.inv();}
    241         modular operator += (const modular &t) {r += t.r; if(r >= m) r -= m; return *this;}
    242         modular operator -= (const modular &t) {r -= t.r; if(r < 0) r += m; return *this;}
    243         modular operator + (const modular &t) const {return modular(*this) += t;}
    244         modular operator - (const modular &t) const {return modular(*this) -= t;}
    245         modular operator *= (const modular &t) {return *this = *this * t;}
    246         modular operator /= (const modular &t) {return *this = *this / t;}
    247         
    248         bool operator == (const modular &t) const {return r == t.r;}
    249         bool operator != (const modular &t) const {return r != t.r;}
    250         bool operator < (const modular &t) const {return r < t.r;}
    251         
    252         explicit operator int() const {return r;}
    253         int64_t rem() const {return 2 * r > m ? r - m : r;}
    254     };
    255     
    256     istream& operator >> (istream &in, modular &x) {
    257         return in >> x.r;
    258     }
    259     
    260     ostream& operator << (ostream &out, modular const& x) {
    261         return out << x.r;
    262     }
    263     
    264     vector<modular> F(maxn), RF(maxn);
    265     
    266     template<typename T>
    267     T fact(int n) {
    268         static bool init = false;
    269         if(!init) {
    270             F[0] = T(1);
    271             for(int i = 1; i < maxn; i++) {
    272                 F[i] = F[i - 1] * T(i);
    273             }
    274             init = true;
    275         }
    276         return F[n];
    277     }
    278     
    279     template<typename T>
    280     T rfact(int n) {
    281         static bool init = false;
    282         if(!init) {
    283             RF[maxn - 1] = T(1) / fact<T>(maxn - 1);
    284             for(int i = maxn - 2; i >= 0; i--) {
    285                 RF[i] = RF[i + 1] * T(i + 1);
    286             }
    287             init = true;
    288         }
    289         return RF[n];
    290     }
    291 }
    292 
    293 using namespace algebra;
    294 
    295 using base = modular;
    296 
    297 void solve() {
    298     int d;
    299     cin >> d;
    300     vector<base> A(d + 1), B(d + 1);
    301     copy_n(istream_iterator<base>(cin), d + 1, begin(A));
    302     copy_n(istream_iterator<base>(cin), d + 1, begin(B));
    303     base s = 0, k2 = 0;
    304     auto coef = [&](int i) {
    305         return base((d - i) % 2 ? -1 : 1) * rfact<base>(i) * rfact<base>(d - i);
    306     };
    307     for(int i = 0; i <= d; i++) {
    308         s += (A[i] - B[i]) * coef(i) * (d * (d + 1) / 2 - i);
    309         k2 += (A[i] + B[i]) * coef(i);
    310     }
    311     s *= base(2) / (k2 * d);
    312     cout << s << "\n";
    313 }
    314 ```
    315 
    316 [1817D - Автомат с игрушками](/contest/1817/problem/D "Codeforces Round 869 (Div. 1)")
    317 
    318 Problem idea: [adamant](/profile/adamant "Мастер adamant")   
    319  Preparation: [jeroenodb](/profile/jeroenodb "Гроссмейстер jeroenodb")
    320 
    321 **Editorial**
    322 
    323 Instead of caring about the positions of all the toys, we only need to care about the position of the special toy with index $k$. The other toys can be treated as undistinguishable.
    324 
    325 The intended way of solving this problem is playing the game in the webpage, trying to come up with some simple combinations of operations that make the special toy move to another position in a predictable way. Using these building blocks in a smart way, finding a way to move the special toy to the topleft.
    326 
    327 As the size of the grid can be up to $100\,000$ and we can make $1\,000\,000$ moves, we will be aiming for a solution which does a linear number of moves.
    328 
    329 There are lots of potential solutions which use a linear number of moves, here is a relatively painless one:
    330 
    331 Do casework on $k$:
    332 
    333 * Case $1$: If $1 \leq k \lt \frac{n-1}{2}$, we initally make one $\texttt{R}$ button press to align the toys with the right boundary. After this, there is an easy pattern to expose all the toys in the left halve, one by one: $\texttt{DRURDRUR...}$ repeated. When the special toy is exposed, the repeating pattern is stopped, and $\texttt{DL}$ are pressed. Toy $k$ will be moved to the topleft corner.
    334 
    335 **Visualization**
    336 
    337 ![ ](https://espresso.codeforces.com/e0c3dcd6552566c5140e50c822d846c4da69bc08.png) Left halve solution for $n=15$.
    338 
    339 * Case $2$: If $k = \frac{n-1}{2}$, the puzzle can be solved in two moves: $\texttt{DL}$.
    340 
    341 **Visualization**
    342 
    343 ![ ](https://espresso.codeforces.com/e5ca9bc17aa7ebb6a1e5ad69053b62ba3ee76ee8.png) Solution for middle toy and $n=15$.
    344 
    345 * Case $3$: If $\frac{n-1}{2} \lt k \leq n-2$, we try to reduce back to case $1$, by moving the special toy to the left halve, and ensuring that all other toys are in the top row. Using symmetry, we can apply case $1$ to $k^\prime = n-1 - k$, but mirror all horizontal moves, to move the toy to the topright corner. The other toys are no longer all in the top row. To fix this, the last pattern we need is again $\texttt{DRURDRUR...}$ repeated. After a while of repeating this, all toys will be in the right halve of the board, occupying the top and bottom row. To finish moving the special toy (which stayed in the topright corner), we do the buttons presses $\texttt{LDRU}$. All toys end up in the top row, and the special toy will be at position $k_\text{new} = \frac{n-1}{2} - 1$, so this successfully reduces to case $1$.
    346 
    347 **Visualization**
    348 
    349 ![ ](https://espresso.codeforces.com/9406f83399af41cee39133567e570a93ea65c63d.png) Full solution for right halve for $n=15$.
    350 
    351 How many moves does this take? In case $1$ the pattern $\texttt{DRUR}$ needs to be repeated at most $\approx \frac{n}{2}$ times. In case $3$, we need to use the first pattern $\frac{n}{2}$ times, and we use the second pattern $\frac{n}{2}$ times. We reduce down to case $1$, but luckily the special toy is already close to the correct position, so only a constant number of extra moves are done.
    352 
    353 So in total, this solution uses $O(1) + \max \left( 4\frac{n}{2}, 4 \cdot 2 \frac{n}{2} \right) = 4n + O(1)$ moves. So this solution fits well within the constraints, although it is pretty wasteful.
    354 
    355 Bonus: Can you prove that the optimal number of moves needed in the worstcase (over all $k$) for a width of $n$ is $\Omega(n)$? We only did some testing of small cases, with a bruteforce BFS solution, and found that the worstcase is around $n/2$ button presses.
    356 
    357 **Solution**
    358 
    359 ```
    360 #include "bits/stdc++.h"
    361 using namespace std;
    362 
    363 int main() {
    364     int n,k; cin >> n >> k;
    365     --k;
    366     int half = (n-3)/2;
    367     string res = "";
    368     if(k==half) {
    369         res = "DL";
    370     } else {
    371         while(true) {
    372             if(k<half) {
    373                 res+="R";
    374                 int need = half-1-k;
    375                 while(need--) {
    376                     res+="DRUR";
    377                 }
    378                 res+="DL";
    379                 break;
    380             } else {
    381                 int need = k-half-1;
    382                 while(need--) {
    383                     res+="LDLU";
    384                 }
    385                 res+="LDR";
    386                 for(int i=0;i<half+1;++i) {
    387                     res+="DRUR";
    388                 }
    389                 res+="LDRU"; 
    390                 k = half-1;
    391             }
    392         }
    393     }
    394     cout << res << '\n';
    395 }
    396 ```
    397 
    398 [1817E - Полусумма](/contest/1817/problem/E "Codeforces Round 869 (Div. 1)")
    399 
    400 Problem idea: [adamant](/profile/adamant "Мастер adamant")   
    401  Preparation: [adamant](/profile/adamant "Мастер adamant")
    402 
    403 **Editorial**
    404 
    405 Tutorial is loading...
    406 
    407 **Solution**
    408 
    409 ```
    410 // split into 1, ..., k and k+1, ..., n
    411 pair<int, istring> check_k(istring const& a, int k) {
    412     int n = size(a);
    413     istring A(n, 0), B(n, 0);
    414     for(int i = 0; i < n; i++) {
    415         if(i <= k) {
    416             A[min(k, i + 1)] += a[i];
    417         } else {
    418             B[min(n - k - 2, n - i)] += a[i];
    419         }
    420     }
    421     // multiply by 2^(n - i - 1) instead of dividing by 2^i
    422     reverse(all(A));
    423     reverse(all(B));
    424     int carry = 0;
    425     // subtract A from B and normalize base 2
    426     for(int i = 0; i < n; i++) {
    427         B[i] -= A[i] - carry;
    428         carry = B[i] >> 1; // floor(B[i] / 2)
    429         B[i] &= 1;
    430     }
    431     if(carry < 0) {
    432         return {-1, {}}; // it's always possible to make it positive
    433     }
    434     while(carry) {
    435         B.push_back(carry & 1);
    436         carry >>= 1; 
    437     }
    438     while(!B.empty() && B.back() == 0) {
    439         B.pop_back();
    440     }
    441     reverse(all(B));
    442     return {(int)size(B) - n, B};
    443 }
    444 
    445 const int mod = 1e9 + 7;
    446 
    447 int bpow(int x, int n) {
    448     if(!n) {
    449         return 1;
    450     } else if(n % 2) {
    451         return int64_t(x) * bpow(x, n - 1) % mod;
    452     } else {
    453         return bpow(int64_t(x) * x % mod, n / 2);
    454     }
    455 }
    456 
    457 int inv(int x) {
    458     return bpow(x, mod - 2);
    459 }
    460 
    461 void solve() {
    462     int n;
    463     cin >> n;
    464     istring a(n, 0);
    465     for(int i = 0; i < n; i++) {
    466         cin >> a[i];
    467     }
    468     sort(all(a));
    469     auto cand = check_k(a, 0);
    470     int cnt = 0;
    471     for(int i = 1; i < n; i++) {
    472         if(a[i] != a[i - 1]) {
    473             cand = max(cand, check_k(a, i - 1));
    474             cnt++;
    475             if(cnt == 30) {
    476                 break;
    477             }
    478         }
    479     }
    480     cnt = 0;
    481     istring b = a;
    482     reverse(all(b));
    483     for(int i = 1; i < n; i++) {
    484         if(b[i] != b[i - 1]) {
    485             cand = max(cand, check_k(a, n - i - 1));
    486             cnt++;
    487             if(cnt == 30) {
    488                 break;
    489             }
    490         }
    491     }
    492     auto [sz, ansf] = cand;
    493     int ans = 0;
    494     for(size_t i = 0; i < size(ansf); i++) {
    495         ans = (ans + bpow(2, (mod - 1) + (sz - i)) * ansf[i]) % mod;
    496     }
    497     cout << ans << "\n";
    498 }
    499 ```
    500 
    501 [1817F - Запутанные строки](/contest/1817/problem/F "Codeforces Round 869 (Div. 1)")
    502 
    503 Problem idea: [adamant](/profile/adamant "Мастер adamant")   
    504  Preparation: [adamant](/profile/adamant "Мастер adamant")
    505 
    506 **Editorial**
    507 
    508 Tutorial is loading...
    509 
    510 **Solution**
    511 
    512 ```
    513 map<char, int> to[maxn];
    514 int len[maxn], link[maxn];
    515 int last, sz = 1;
    516 
    517 void add_letter(char c) {
    518     int p = last;
    519     last = sz++;
    520     len[last] = len[p] + 1;
    521     for(; to[p][c] == 0; p = link[p]) {
    522         to[p][c] = last;
    523     }
    524     int q = to[p][c];
    525     if(q != last) {
    526         if(len[q] == len[p] + 1) {
    527             link[last] = q;
    528         } else {
    529             int cl = sz++;
    530             len[cl] = len[p] + 1;
    531             link[cl] = link[q];
    532             to[cl] = to[q];
    533             link[last] = link[q] = cl;
    534             for(; to[p][c] == q; p = link[p]) {
    535                 to[p][c] = cl;
    536             }
    537         }
    538     }
    539 }
    540 
    541 int term[maxn];
    542 int used[maxn], comp[maxn], dist[maxn];
    543 vector<int> in_comp[maxn];
    544 
    545 void dfs(int v = 0) {
    546     comp[v] = v;
    547     dist[v] = 0;
    548     used[v] = 1;
    549     for(auto [c, u]: to[v]) {
    550         if(!used[u]) {
    551             dfs(u);
    552         }
    553         if(to[v].size() == 1 && !term[v]) {
    554             comp[v] = comp[u];
    555             dist[v] = dist[u] + 1;
    556         }
    557     }
    558     in_comp[comp[v]].push_back(v);
    559 }
    560 
    561 void solve() {
    562     string s;
    563     cin >> s;
    564     for(auto c: s) {
    565         add_letter(c);
    566     }
    567     for(int p = last; p; p = link[p]) {
    568         term[p] = 1;
    569     }
    570     term[0] = 1;
    571     dfs();
    572     int64_t ans = 0;
    573     for(int v = 0; v < sz; v++) {
    574         if(in_comp[v].size()) {
    575             int m = in_comp[v].size();
    576             sort(all(in_comp[v]), [&](int a, int b) {
    577                 return dist[a] > dist[b];
    578             });
    579             vector<int64_t> A(m), B(m);
    580             for(int i = 0; i < m; i++) {
    581                 int u = in_comp[v][i];
    582                 int L = dist[u];
    583                 int R = L + len[link[u]];
    584                 // L' must be larger than R
    585                 int cnt = len[u] - len[link[u]];
    586                 A[i] = (int64_t)cnt * L;
    587                 B[i] = cnt;
    588                 if(i > 0) {
    589                     A[i] += A[i - 1];
    590                     B[i] += B[i - 1];
    591                 }
    592                 auto it = upper_bound(all(in_comp[v]), R, [&](int R, int b) {
    593                     return R > dist[b];
    594                 }) - begin(in_comp[v]);
    595                 if(it) {
    596                     it--;
    597                     ans += A[it] - B[it] * R;
    598                 }
    599             }
    600         }
    601     }
    602     cout << ans << "\n";
    603 }
    604 ```