codeforces-scrape

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

1795.md (8867B)


      1 Source: https://codeforces.com/blog/entry/112963
      2 
      3 [1795A - Two Towers](/contest/1795/problem/A "Educational Codeforces Round 143 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon) 1**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19   auto ok = [](string s) {
     20     for (int i = 1; i < (int)s.size(); ++i)
     21       if (s[i - 1] == s[i]) return false;
     22     return true;    
     23   };
     24   
     25   int t;
     26   cin >> t;
     27   while (t--) {
     28     int n, m;
     29     string s, t;
     30     cin >> n >> m >> s >> t;
     31     bool f = false;
     32     for (int x = 0; x < 2; ++x) {
     33       string cs = s, ct = t;
     34       for (int i = 0; i < n; ++i) {
     35         f |= ok(cs) && ok(ct);
     36         ct.push_back(cs.back());
     37         cs.pop_back();
     38       }
     39       swap(n, m);
     40       swap(s, t);   
     41     }
     42     cout << (f ? "YES\n" : "NO\n");
     43   }
     44 }
     45 ```
     46 
     47 **Solution (Neon) 2**
     48 
     49 ```
     50 #include <bits/stdc++.h>
     51 
     52 using namespace std;
     53 
     54 int main() {
     55   int t;
     56   cin >> t;
     57   while (t--) {
     58     int n, m;
     59     string s, t;
     60     cin >> n >> m >> s >> t;
     61     reverse(t.begin(), t.end());
     62     s += t;
     63     int cnt = 0;
     64     for (int i = 1; i < n + m; ++i) cnt += s[i - 1] == s[i];
     65     cout << (cnt <= 1 ? "YES\n" : "NO\n");
     66   }
     67 }
     68 ```
     69 
     70 [1795B - Ideal Point](/contest/1795/problem/B "Educational Codeforces Round 143 (Rated for Div. 2)")
     71 
     72 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     73 
     74 **Tutorial**
     75 
     76 Tutorial is loading...
     77 
     78 **Solution (Neon)**
     79 
     80 ```
     81 #include <bits/stdc++.h>
     82 
     83 using namespace std;
     84 
     85 int main() {
     86   int t;
     87   cin >> t;
     88   while (t--) {
     89     int n, k;
     90     cin >> n >> k;
     91     int L = 0, R = 55;
     92     while (n--) {
     93       int l, r;
     94       cin >> l >> r;
     95       if (l <= k && k <= r)
     96         L = max(L, l), R = min(R, r);
     97     }
     98     cout << (L == R ? "YES\n" : "NO\n");
     99   }
    100 }
    101 ```
    102 
    103 [1795C - Tea Tasting](/contest/1795/problem/C "Educational Codeforces Round 143 (Rated for Div. 2)")
    104 
    105 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    106 
    107 **Tutorial**
    108 
    109 Tutorial is loading...
    110 
    111 **Solution (Neon)**
    112 
    113 ```
    114 #include <bits/stdc++.h>
    115 
    116 using namespace std;
    117 
    118 using li = long long;
    119 
    120 int main() {
    121   ios::sync_with_stdio(false); cin.tie(0);
    122   int t;
    123   cin >> t;
    124   while (t--) {
    125     int n;
    126     cin >> n;
    127     vector<li> a(n), b(n);
    128     for (auto& x : a) cin >> x;
    129     for (auto& x : b) cin >> x;
    130     vector<li> sum(n + 1);
    131     for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + b[i];
    132     vector<li> cnt(n + 1), add(n + 1);
    133     for (int i = 0; i < n; ++i) {
    134       int j = upper_bound(sum.begin(), sum.end(), a[i] + sum[i]) - sum.begin() - 1;
    135       cnt[i] += 1;
    136       cnt[j] -= 1;
    137       add[j] += a[i] - sum[j] + sum[i];
    138     }
    139     for (int i = 0; i < n; ++i) {
    140       cout << cnt[i] * b[i] + add[i] << ' ';
    141       cnt[i + 1] += cnt[i];   
    142     }
    143     cout << '\n';
    144   }
    145 }
    146 ```
    147 
    148 [1795D - Triangle Coloring](/contest/1795/problem/D "Educational Codeforces Round 143 (Rated for Div. 2)")
    149 
    150 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    151 
    152 **Tutorial**
    153 
    154 Tutorial is loading...
    155 
    156 **Solution (BledDest)**
    157 
    158 ```
    159 #include <bits/stdc++.h>
    160  
    161 using namespace std;
    162 
    163 const int MOD = 998244353;
    164 
    165 int add(int x, int y)
    166 {
    167     return ((x + y) % MOD + MOD) % MOD;
    168 }
    169 
    170 int mul(int x, int y)
    171 {
    172     return x * 1ll * y % MOD;   
    173 }
    174 
    175 int binpow(int x, int y)
    176 {
    177     int z = 1;
    178     while(y)
    179     {
    180         if(y % 2 == 1) z = mul(z, x);
    181         x = mul(x, x);
    182         y /= 2;
    183     }
    184     return z;
    185 }
    186 
    187 int inv(int x)
    188 {
    189     return binpow(x, MOD - 2);    
    190 }
    191 
    192 int divide(int x, int y)
    193 {
    194     return mul(x, inv(y));
    195 }
    196 
    197 int main()
    198 {
    199     int n;
    200     cin >> n;
    201     int ans = 1;
    202     for(int i = 1; i <= n / 6; i++)
    203         ans = mul(ans, divide(i + n / 6, i));
    204     for(int i = 0; i < n / 3; i++)
    205     {
    206         vector<int> a(3);
    207         for(int j = 0; j < 3; j++)
    208             cin >> a[j];
    209         int mn = *min_element(a.begin(), a.end());
    210         int cnt_min = count(a.begin(), a.end(), mn);
    211         ans = mul(ans, cnt_min);
    212     }
    213     cout << ans << endl;
    214 }
    215 ```
    216 
    217 [1795E - Explosions?](/contest/1795/problem/E "Educational Codeforces Round 143 (Rated for Div. 2)")
    218 
    219 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    220 
    221 **Tutorial**
    222 
    223 Tutorial is loading...
    224 
    225 **Solution (adedalic)**
    226 
    227 ```
    228 import java.util.*
    229 
    230 fun main() {
    231     repeat(readln().toInt()) {
    232         val n = readln().toInt()
    233         var h = readln().split(' ').map { it.toInt() }
    234 
    235         val d = Array(2) { LongArray(n) { 0 } }
    236         for (tp in 0..1) {
    237             val s = Stack<Pair<Int, Int>>()
    238 
    239             for (i in h.indices) {
    240                 while (s.isNotEmpty() && s.peek().first > h[i] - i)
    241                     s.pop()
    242                 var j = maxOf(-1, i - h[i])
    243                 if (s.isNotEmpty())
    244                     j = maxOf(j, s.peek().second)
    245 
    246                 val len = (i - j).toLong()
    247                 d[tp][i] = len * h[i] - len * (len - 1) / 2
    248                 if (j >= 0 && len < h[i])
    249                     d[tp][i] += d[tp][j]
    250 
    251                 s.push(Pair(h[i] - i, i))
    252             }
    253             h = h.reversed()
    254         }
    255         d[1] = d[1].reversedArray()
    256 
    257         var ans = 1e18.toLong()
    258         val sum = h.fold(0L) { total, it -> total + it }
    259         for (i in h.indices) {
    260             val cur = sum - d[0][i] - d[1][i] + 2 * h[i]
    261             ans = minOf(ans, cur)
    262         }
    263         println(ans)
    264     }
    265 }
    266 ```
    267 
    268 [1795F - Blocking Chips](/contest/1795/problem/F "Educational Codeforces Round 143 (Rated for Div. 2)")
    269 
    270 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    271 
    272 **Tutorial**
    273 
    274 Tutorial is loading...
    275 
    276 **Solution (awoo)**
    277 
    278 ```
    279 #include <bits/stdc++.h>
    280  
    281 using namespace std;
    282  
    283 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    284 
    285 vector<vector<int>> g;
    286 vector<int> req;
    287 vector<char> used;
    288 
    289 vector<int> d;
    290 
    291 bool dfs(int v, int p = -1){
    292     d[v] = 0;
    293     for (int u : g[v]) if (u != p){
    294         if (!dfs(u, v)) return false;
    295         if (!used[u]) d[v] = max(d[v], d[u] + 1);
    296     }
    297     if (req[v] == 0 || d[v] >= req[v]) return true;
    298     if (p == -1 || used[p]) return false;
    299     used[p] = true;
    300     req[p] = req[v] - 1;
    301     return true;
    302 }
    303 
    304 int main(){
    305     int t;
    306     scanf("%d", &t);
    307     while (t--){
    308         int n;
    309         scanf("%d", &n);
    310         g.assign(n, {});
    311         d.resize(n);
    312         forn(i, n - 1){
    313             int v, u;
    314             scanf("%d%d", &v, &u);
    315             --v, --u;
    316             g[v].push_back(u);
    317             g[u].push_back(v);
    318         }
    319         int k;
    320         scanf("%d", &k);
    321         vector<int> a(k);
    322         forn(i, k){
    323             scanf("%d", &a[i]);
    324             --a[i];
    325         }
    326         int l = 1, r = n;
    327         int res = 0;
    328         while (l <= r){
    329             int m = (l + r) / 2;
    330             used.assign(n, 0);
    331             req.assign(n, 0);
    332             forn(i, k){
    333                 used[a[i]] = true;
    334                 req[a[i]] = m / k + (i < m % k);
    335             }
    336             if (dfs(0)){
    337                 res = m;
    338                 l = m + 1;
    339             }
    340             else{
    341                 r = m - 1;
    342             }
    343         }
    344         printf("%d\n", res);
    345     }
    346 }
    347 ```
    348 
    349 [1795G - Removal Sequences](/contest/1795/problem/G "Educational Codeforces Round 143 (Rated for Div. 2)")
    350 
    351 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    352 
    353 **Tutorial**
    354 
    355 Tutorial is loading...
    356 
    357 **Solution (awoo)**
    358 
    359 ```
    360 #include <bits/stdc++.h>
    361  
    362 using namespace std;
    363  
    364 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    365 
    366 typedef unsigned long long uli;
    367 
    368 int main(){
    369     int t;
    370     scanf("%d", &t);
    371     while (t--){
    372         int n, m;
    373         scanf("%d%d", &n, &m);
    374         vector<int> a(n);
    375         forn(i, n) scanf("%d", &a[i]);
    376         vector<vector<int>> g(n);
    377         forn(i, m){
    378             int v, u;
    379             scanf("%d%d", &v, &u);
    380             --v, --u;
    381             g[v].push_back(u);
    382             g[u].push_back(v);
    383         }
    384         vector<char> rem(n);
    385         vector<int> d(n);
    386         forn(i, n) d[i] = g[i].size();
    387         queue<int> q;
    388         forn(i, n) if (a[i] == d[i]) q.push(i);
    389         vector<pair<int, int>> ord;
    390         while (!q.empty()){
    391             int v = q.front();
    392             q.pop();
    393             rem[v] = true;
    394             for (int u : g[v]) if (!rem[u]){
    395                 --d[u];
    396                 ord.push_back({v, u});
    397                 if (d[u] == a[u])
    398                     q.push(u);
    399             }
    400         }
    401         reverse(ord.begin(), ord.end());
    402         vector<uli> mask(n);
    403         long long ans = n * 1ll * (n + 1) / 2;
    404         for (int l = 0; l < n; l += 64){
    405             int r = min(n, l + 64);
    406             for (int i = l; i < r; ++i)
    407                 mask[i] = 1ull << (i - l);
    408             for (const pair<int, int> &it : ord)
    409                 mask[it.first] |= mask[it.second];
    410             forn(i, n){
    411                 ans -= __builtin_popcountll(mask[i]);
    412                 mask[i] = 0;
    413             }
    414         }
    415         printf("%lld\n", ans);
    416     }
    417 }
    418 ```