codeforces-scrape

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

1473.md (13951B)


      1 Source: https://codeforces.com/blog/entry/86827
      2 
      3 [1473A - Replacing Elements](/contest/1473/problem/A "Educational Codeforces Round 102 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), [adedalic](/profile/adedalic "International Master adedalic")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19   int tc;
     20   cin >> tc;
     21   while (tc--) {
     22     int n, d;
     23     cin >> n >> d;
     24     vector<int> a(n);
     25     for (int& x : a) cin >> x;
     26     sort(a.begin(), a.end());
     27     cout << (a.back() <= d || a[0] + a[1] <= d ? "YES" : "NO") << endl;
     28   }
     29 }
     30 ```
     31 
     32 [1473B - String LCM](/contest/1473/problem/B "Educational Codeforces Round 102 (Rated for Div. 2)")
     33 
     34 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     35 
     36 **Tutorial**
     37 
     38 Tutorial is loading...
     39 
     40 **Solution (Neon)**
     41 
     42 ```
     43 #include <bits/stdc++.h>
     44 
     45 using namespace std;
     46 
     47 int main() {
     48   auto mul = [](string s, int k) -> string {
     49     string res = "";
     50     while (k--) res += s;
     51     return res;
     52   };
     53   
     54   int tc;
     55   cin >> tc;
     56   while (tc--) {
     57     string s, t;
     58     cin >> s >> t;
     59     int n = s.length(), m = t.length();
     60     int g = __gcd(n, m);
     61     if (mul(s, m / g) == mul(t, n / g))
     62       cout << mul(s, m / g) << endl;
     63     else
     64       cout << "-1" << endl;
     65   }
     66 }
     67 ```
     68 
     69 [1473C - No More Inversions](/contest/1473/problem/C "Educational Codeforces Round 102 (Rated for Div. 2)")
     70 
     71 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     72 
     73 **Tutorial**
     74 
     75 Tutorial is loading...
     76 
     77 **Solution (adedalic)**
     78 
     79 ```
     80 fun main() {
     81     repeat(readLine()!!.toInt()) {
     82         val (n, k) = readLine()!!.split(' ').map { it.toInt() }
     83 
     84         for (i in 1 until (k - (n - k)))
     85             print("$i ")
     86         for (i in k downTo (k - (n - k)))
     87             print("$i ")
     88         println("")
     89     }
     90 }
     91 ```
     92 
     93 [1473D - Program](/contest/1473/problem/D "Educational Codeforces Round 102 (Rated for Div. 2)")
     94 
     95 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     96 
     97 **Tutorial**
     98 
     99 Tutorial is loading...
    100 
    101 **Solution (awoo)**
    102 
    103 ```
    104 #include <bits/stdc++.h>
    105 
    106 #define forn(i, n) for (int i = 0; i < int(n); i++)
    107 
    108 using namespace std;
    109 
    110 int main() {
    111 	cin.tie(0);
    112 	ios_base::sync_with_stdio(0);
    113 	int t;
    114 	cin >> t;
    115 	forn(_, t){
    116 		int n, m;
    117 		string s;
    118 		cin >> n >> m;
    119 		cin >> s;
    120 		vector<int> sul(1, 0), sur(1, 0);
    121 		for (int i = n - 1; i >= 0; --i){
    122 			int d = s[i] == '+' ? 1 : -1;
    123 			sul.push_back(min(0, sul.back() + d));
    124 			sur.push_back(max(0, sur.back() + d));
    125 		}
    126 		reverse(sul.begin(), sul.end());
    127 		reverse(sur.begin(), sur.end());
    128 		vector<int> prl(1, 0), prr(1, 0), pr(1, 0);
    129 		forn(i, n){
    130 			int d = s[i] == '+' ? 1 : -1;
    131 			pr.push_back(pr.back() + d);
    132 			prl.push_back(min(prl.back(), pr.back()));
    133 			prr.push_back(max(prr.back(), pr.back()));
    134 		}
    135 		forn(i, m){
    136 			int l, r;
    137 			cin >> l >> r;
    138 			--l;
    139 			int l1 = prl[l], r1 = prr[l];
    140 			int l2 = sul[r] + pr[l], r2 = sur[r] + pr[l];
    141 			printf("%d\n", max(r1, r2) - min(l1, l2) + 1);
    142 		}
    143 	}
    144 	return 0;
    145 }
    146 ```
    147 
    148 [1473E - Minimum Path](/contest/1473/problem/E "Educational Codeforces Round 102 (Rated for Div. 2)")
    149 
    150 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    151 
    152 **Tutorial**
    153 
    154 Tutorial is loading...
    155 
    156 **Solution (Neon)**
    157 
    158 ```
    159 #include <bits/stdc++.h>
    160 
    161 using namespace std;
    162 
    163 const int N = 200 * 1000 + 13;
    164 
    165 int n, m;
    166 vector<pair<int, int>> g[N];
    167 long long d[N][2][2];
    168 
    169 int main() {
    170   scanf("%d%d", &n, &m);
    171   for (int i = 0; i < m; i++) {
    172     int v, u, w;
    173     scanf("%d%d%d", &v, &u, &w);
    174     --v; --u;
    175     g[v].emplace_back(u, w);
    176     g[u].emplace_back(v, w);
    177   }
    178   
    179   for (int i = 0; i < n; i++)
    180     for (int j = 0; j < 2; j++)
    181       for (int k = 0; k < 2; k++)
    182         d[i][j][k] = (long long)1e18;
    183 
    184   d[0][0][0] = 0;
    185   set<pair<long long, array<int, 3>>> q;
    186   q.insert({0, {0, 0, 0}});
    187 
    188   while (!q.empty()) {
    189     auto [v, mx, mn] = q.begin()->second;
    190     q.erase(q.begin());
    191     for (auto [u, w] : g[v]) {
    192       for (int i = 0; i <= 1 - mx; i++) {
    193         for (int j = 0; j <= 1 - mn; j++) {
    194           if (d[u][mx | i][mn | j] > d[v][mx][mn] + (1 - i + j) * w) {
    195             auto it = q.find({d[u][mx | i][mn | j], {u, mx | i, mn | j}});
    196             if (it != q.end())
    197               q.erase(it);
    198             d[u][mx | i][mn | j] = d[v][mx][mn] + (1 - i + j) * w;
    199             q.insert({d[u][mx | i][mn | j], {u, mx | i, mn | j}});
    200           }
    201         }
    202       }
    203     }
    204   }
    205 
    206   for (int i = 1; i < n; i++) {
    207     printf("%lld ", d[i][1][1]);
    208   }
    209   puts("");
    210 }
    211 ```
    212 
    213 [1473F - Strange Set](/contest/1473/problem/F "Educational Codeforces Round 102 (Rated for Div. 2)")
    214 
    215 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    216 
    217 **Tutorial**
    218 
    219 Tutorial is loading...
    220 
    221 **Solution (BledDest)**
    222 
    223 ```
    224 #include<bits/stdc++.h>
    225 
    226 using namespace std;
    227 
    228 template<typename T>
    229 struct dinic {
    230     struct edge {
    231         int u, rev;
    232         T cap, flow;
    233     };
    234     
    235     int n, s, t;
    236     T flow;
    237     vector<int> lst;
    238     vector<int> d;
    239     vector<vector<edge>> g;
    240     
    241     T scaling_lim;
    242     bool scaling;
    243     
    244     dinic() {}
    245     
    246     dinic(int n, int s, int t, bool scaling = false) : n(n), s(s), t(t), scaling(scaling) {
    247         g.resize(n);
    248         d.resize(n);
    249         lst.resize(n);
    250         flow = 0;
    251     }
    252 
    253     void add_edge(int v, int u, T cap, bool directed = true) {
    254         g[v].push_back({u, g[u].size(), cap, 0});
    255         g[u].push_back({v, int(g[v].size()) - 1, directed ? 0 : cap, 0});
    256     }
    257 
    258     T dfs(int v, T flow) {
    259         if (v == t)
    260             return flow;
    261         if (flow == 0)
    262             return 0;
    263         T result = 0;
    264         for (; lst[v] < g[v].size(); ++lst[v]) {
    265             edge& e = g[v][lst[v]];
    266             if (d[e.u] != d[v] + 1)
    267                 continue;
    268             T add = dfs(e.u, min(flow, e.cap - e.flow));
    269             if (add > 0) {
    270                 result += add;
    271                 flow -= add;
    272                 e.flow += add;
    273                 g[e.u][e.rev].flow -= add;
    274             }
    275             if (flow == 0)
    276                 break;
    277         }
    278         return result;
    279     }
    280 
    281     bool bfs() {
    282         fill(d.begin(), d.end(), -1);
    283         queue<int> q({s});
    284         d[s] = 0;
    285         while (!q.empty() && d[t] == -1) {
    286             int v = q.front(); q.pop();
    287             for (auto& e : g[v]) {
    288                 if (d[e.u] == -1 && e.cap - e.flow >= scaling_lim) {
    289                     q.push(e.u);
    290                     d[e.u] = d[v] + 1;
    291                 }
    292             }
    293         }
    294         return d[t] != -1;
    295     }
    296 
    297     T calc() {
    298         T max_lim = numeric_limits<T>::max() / 2 + 1;
    299         for (scaling_lim = scaling ? max_lim : 1; scaling_lim > 0; scaling_lim >>= 1) {
    300             while (bfs()) {
    301                 fill(lst.begin(), lst.end(), 0);
    302                 T add;
    303                 while((add = dfs(s, numeric_limits<T>::max())) > 0)
    304                 flow += add;
    305             }
    306         }   
    307         return flow;
    308     }
    309     
    310     vector<bool> min_cut() {
    311         vector<bool> res(n);
    312         for(int i = 0; i < n; i++) 
    313             res[i] = (d[i] != -1);
    314         return res;
    315     }
    316 };
    317 
    318 int main() {
    319     int n;
    320     cin >> n;
    321     vector<int> a(n), b(n);
    322     for(int i = 0; i < n; i++)
    323         cin >> a[i];
    324     for(int i = 0; i < n; i++)
    325         cin >> b[i];
    326     int s = n;
    327     int t = n + 1;
    328     dinic<int> d(n + 2, s, t, true);
    329     vector<int> last(101, -1);
    330     for(int i = 0; i < n; i++){
    331         if(b[i] > 0)
    332             d.add_edge(s, i, b[i]);
    333         if(b[i] < 0)
    334             d.add_edge(i, t, -b[i]);
    335         for(int k = 1; k <= 100; k++)
    336             if(last[k] != -1 && a[i] % k == 0)
    337                 d.add_edge(i, last[k], int(1e9));
    338         last[a[i]] = i;    
    339     }   
    340     int sum = 0;
    341     for(int i = 0; i < n; i++)
    342         sum += max(0, b[i]);
    343     cout << sum - d.calc() << endl;
    344 }
    345 ```
    346 
    347 [1473G - Tiles](/contest/1473/problem/G "Educational Codeforces Round 102 (Rated for Div. 2)")
    348 
    349 Idea: [Neon](/profile/Neon "Candidate Master Neon"), [adedalic](/profile/adedalic "International Master adedalic")
    350 
    351 **Tutorial**
    352 
    353 Tutorial is loading...
    354 
    355 **Solution (Neon)**
    356 
    357 ```
    358 #include <bits/stdc++.h>
    359 
    360 using namespace std;
    361 
    362 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    363 #define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
    364 #define sz(a) int((a).size())
    365 
    366 template<const int &MOD>
    367 struct _m_int {
    368   int val;
    369  
    370   _m_int(int64_t v = 0) {
    371     if (v < 0) v = v % MOD + MOD;
    372     if (v >= MOD) v %= MOD;
    373     val = int(v);
    374   }
    375  
    376   _m_int(uint64_t v) {
    377     if (v >= MOD) v %= MOD;
    378     val = int(v);
    379   }
    380  
    381   _m_int(int v) : _m_int(int64_t(v)) {}
    382   _m_int(unsigned v) : _m_int(uint64_t(v)) {}
    383  
    384   static int inv_mod(int a, int m = MOD) {
    385     int g = m, r = a, x = 0, y = 1;
    386  
    387     while (r != 0) {
    388       int q = g / r;
    389       g %= r; swap(g, r);
    390       x -= q * y; swap(x, y);
    391     }
    392  
    393     return x < 0 ? x + m : x;
    394   }
    395  
    396   explicit operator int() const { return val; }
    397   explicit operator unsigned() const { return val; }
    398   explicit operator int64_t() const { return val; }
    399   explicit operator uint64_t() const { return val; }
    400   explicit operator double() const { return val; }
    401   explicit operator long double() const { return val; }
    402  
    403   _m_int& operator+=(const _m_int &other) {
    404     val -= MOD - other.val;
    405     if (val < 0) val += MOD;
    406     return *this;
    407   }
    408  
    409   _m_int& operator-=(const _m_int &other) {
    410     val -= other.val;
    411     if (val < 0) val += MOD;
    412     return *this;
    413   }
    414  
    415   static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
    416 #if !defined(_WIN32) || defined(_WIN64)
    417     return unsigned(x % m);
    418 #endif
    419     // Optimized mod for Codeforces 32-bit machines.
    420     // x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int.
    421     unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
    422     unsigned quot, rem;
    423     asm("divl %4\n"
    424       : "=a" (quot), "=d" (rem)
    425       : "d" (x_high), "a" (x_low), "r" (m));
    426     return rem;
    427   }
    428  
    429   _m_int& operator*=(const _m_int &other) {
    430     val = fast_mod(uint64_t(val) * other.val);
    431     return *this;
    432   }
    433  
    434   _m_int& operator/=(const _m_int &other) {
    435     return *this *= other.inv();
    436   }
    437  
    438   friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
    439   friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
    440   friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
    441   friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }
    442  
    443   _m_int& operator++() {
    444     val = val == MOD - 1 ? 0 : val + 1;
    445     return *this;
    446   }
    447  
    448   _m_int& operator--() {
    449     val = val == 0 ? MOD - 1 : val - 1;
    450     return *this;
    451   }
    452  
    453   _m_int operator++(int) { _m_int before = *this; ++*this; return before; }
    454   _m_int operator--(int) { _m_int before = *this; --*this; return before; }
    455  
    456   _m_int operator-() const {
    457     return val == 0 ? 0 : MOD - val;
    458   }
    459  
    460   friend bool operator==(const _m_int &a, const _m_int &b) { return a.val == b.val; }
    461   friend bool operator!=(const _m_int &a, const _m_int &b) { return a.val != b.val; }
    462   friend bool operator<(const _m_int &a, const _m_int &b) { return a.val < b.val; }
    463   friend bool operator>(const _m_int &a, const _m_int &b) { return a.val > b.val; }
    464   friend bool operator<=(const _m_int &a, const _m_int &b) { return a.val <= b.val; }
    465   friend bool operator>=(const _m_int &a, const _m_int &b) { return a.val >= b.val; }
    466  
    467   _m_int inv() const {
    468     return inv_mod(val);
    469   }
    470  
    471   _m_int pow(int64_t p) const {
    472     if (p < 0)
    473       return inv().pow(-p);
    474  
    475     _m_int a = *this, result = 1;
    476  
    477     while (p > 0) {
    478       if (p & 1)
    479         result *= a;
    480       a *= a;
    481       p >>= 1;
    482     }
    483  
    484     return result;
    485   }
    486   
    487   friend string to_string(_m_int<MOD> x) {
    488     return to_string(x.val);
    489   }
    490  
    491   friend ostream& operator<<(ostream &os, const _m_int &m) {
    492     return os << m.val;
    493   }
    494 };
    495 
    496 extern const int MOD = 998244353;
    497 using Mint = _m_int<MOD>;
    498 
    499 const int g = 3;
    500 const int LOGN = 15;
    501 
    502 vector<Mint> w[LOGN];
    503 vector<int> rv[LOGN];
    504 
    505 void prepare() {
    506   Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN));
    507   forn(st, LOGN - 1) {
    508     w[st].assign(1 << st, 1);
    509     Mint bw = wb.pow(1 << (LOGN - st - 1));
    510     Mint cw = 1;
    511     forn(k, 1 << st) {
    512       w[st][k] = cw;
    513       cw *= bw;
    514     }
    515   }
    516   forn(st, LOGN) {
    517     rv[st].assign(1 << st, 0);
    518     if (st == 0) {
    519       rv[st][0] = 0;
    520       continue;
    521     }
    522     int h = (1 << (st - 1));
    523     forn(k, 1 << st)
    524       rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    525   }
    526 }
    527 
    528 void ntt(vector<Mint> &a, bool inv) {
    529   int n = sz(a);
    530   int ln = __builtin_ctz(n);
    531   forn(i, n) {
    532     int ni = rv[ln][i];
    533     if (i < ni) swap(a[i], a[ni]);
    534   }
    535   forn(st, ln) {
    536     int len = 1 << st;
    537     for (int k = 0; k < n; k += (len << 1)) {
    538       fore(pos, k, k + len){
    539         Mint l = a[pos];
    540         Mint r = a[pos + len] * w[st][pos - k];
    541         a[pos] = l + r;
    542         a[pos + len] = l - r;
    543       }
    544     }
    545   }
    546   if (inv) {
    547     Mint rn = Mint(n).inv();
    548     forn(i, n) a[i] *= rn;
    549     reverse(a.begin() + 1, a.end());
    550   }
    551 }
    552 
    553 vector<Mint> mul(vector<Mint> a, vector<Mint> b) {
    554   int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1));
    555   a.resize(cnt);
    556   b.resize(cnt);
    557   ntt(a, false);
    558   ntt(b, false);
    559   vector<Mint> c(cnt);
    560   forn(i, cnt) c[i] = a[i] * b[i];
    561   ntt(c, true);
    562   return c;
    563 }
    564 
    565 int main() {
    566   prepare();
    567   
    568   vector<Mint> fact(1, 1), ifact(1, 1);
    569   auto C = [&](int n, int k) -> Mint {
    570     if (k < 0 || k > n) return 0;
    571     while (sz(fact) <= n) {
    572       fact.push_back(fact.back() * sz(fact));
    573       ifact.push_back(fact.back().inv());
    574     }
    575     return fact[n] * ifact[k] * ifact[n - k];
    576   };
    577   
    578   int n;
    579   cin >> n;
    580   vector<int> a(n), b(n);
    581   forn(i, n) cin >> a[i] >> b[i];
    582   
    583   vector<Mint> ans(1, 1);
    584   forn(i, n) {
    585     vector<Mint> Cs;
    586     for (int j = b[i] - sz(ans) + 1; j < sz(ans) + a[i]; ++j)
    587       Cs.push_back(C(a[i] + b[i], j));
    588     auto res = mul(ans, Cs);
    589     int cnt = sz(ans);
    590     ans.resize(cnt + a[i] - b[i]);
    591     forn(j, sz(ans)) ans[j] = res[cnt + j - 1];
    592   }
    593   
    594   cout << accumulate(ans.begin(), ans.end(), Mint(0)) << endl;
    595 }
    596 ```