codeforces-scrape

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

1680.md (7502B)


      1 Source: https://codeforces.com/blog/entry/102852
      2 
      3 [1680A - Minimums and Maximums](/contest/1680/problem/A "Educational Codeforces Round 128 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     l1, r1, l2, r2 = map(int, input().split())
     17     if max(l1, l2) <= min(r1, r2):
     18         print(max(l1, l2))
     19     else:
     20         print(l1 + l2)
     21 ```
     22 
     23 [1680B - Robots](/contest/1680/problem/B "Educational Codeforces Round 128 (Rated for Div. 2)")
     24 
     25 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 **Solution (BledDest)**
     32 
     33 ```
     34 t = int(input())
     35 for i in range(t):
     36     n, m = map(int, input().split())
     37     s = []
     38     for j in range(n):
     39         s.append(input())
     40     minx = 10 ** 9
     41     miny = 10 ** 9
     42     for x in range(n):
     43         for y in range(m):
     44             if s[x][y] == 'R':
     45                 minx = min(minx, x)
     46                 miny = min(miny, y)
     47     print('YES' if s[minx][miny] == 'R' else 'NO')
     48 ```
     49 
     50 [1680C - Binary String](/contest/1680/problem/C "Educational Codeforces Round 128 (Rated for Div. 2)")
     51 
     52 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     53 
     54 **Tutorial**
     55 
     56 Tutorial is loading...
     57 
     58 **Solution (BledDest)**
     59 
     60 ```
     61 def can(pos, m):
     62     k = len(pos) 
     63     x = k - m
     64     for i in range(m + 1):
     65         l = pos[i]
     66         r = pos[i + x - 1]
     67         if r - l + 1 - x <= m:
     68             return True
     69     return False    
     70 
     71 t = int(input())
     72 for i in range(t):
     73     s = input()
     74     pos = []
     75     n = len(s)
     76     for i in range(n):
     77         if s[i] == '1':
     78             pos.append(i)
     79     lf = 0
     80     rg = len(pos)
     81     while rg - lf > 1:
     82         mid = (lf + rg) // 2
     83         if can(pos, mid):
     84             rg = mid
     85         else:
     86             lf = mid
     87     if len(pos) == 0 or pos[-1] - pos[0] == len(pos) - 1:
     88         print(0)
     89     else:
     90         print(rg)
     91 ```
     92 
     93 [1680D - Dog Walking](/contest/1680/problem/D "Educational Codeforces Round 128 (Rated for Div. 2)")
     94 
     95 Idea: [vovuh](/profile/vovuh "Master vovuh") and [BledDest](/profile/BledDest "International Grandmaster BledDest")
     96 
     97 **Tutorial**
     98 
     99 Tutorial is loading...
    100 
    101 **Solution (vovuh)**
    102 
    103 ```
    104 #include <bits/stdc++.h>
    105 
    106 using namespace std;
    107 
    108 int main() {
    109 #ifdef _DEBUG
    110     freopen("input.txt", "r", stdin);
    111 //  freopen("output.txt", "w", stdout);
    112 #endif
    113     
    114     int n;
    115     long long k;
    116     cin >> n >> k;
    117     vector<long long> a(n);
    118     for (auto &it : a) {
    119         cin >> it;
    120     }
    121     
    122     long long ans = 0;
    123     for (int it = 0; it < n; ++it) {
    124         vector<int> cnt(n);
    125         for (int i = n - 1; i >= 0; --i) {
    126             cnt[i] = (a[i] == 0);
    127             if (i + 1 < n) {
    128                 cnt[i] += cnt[i + 1];
    129             }
    130         }
    131         vector<long long> b = a;
    132         long long s = accumulate(b.begin(), b.end(), 0ll);
    133         bool ok = true;
    134         for (int i = 0; i < n; ++i) {
    135             if (b[i] == 0) {
    136                 long long x = (i + 1 < n ? cnt[i + 1] : 0);
    137                 b[i] = min(k, x * k - s);
    138                 if (b[i] < -k) {
    139                     ok = false;
    140                 }
    141                 s += b[i];
    142             }
    143         }
    144         if (ok) {
    145             long long pos = 0, mn = 0, mx = 0;
    146             for (int i = 0; i < n; ++i) {
    147                 pos += b[i];
    148                 mn = min(mn, pos);
    149                 mx = max(mx, pos);
    150             }
    151             if (pos == 0) {
    152                 ans = max(ans, mx - mn + 1);
    153             }
    154         }
    155         rotate(a.begin(), a.begin() + 1, a.end());
    156     }
    157     
    158     if (ans == 0) {
    159         ans = -1;
    160     }
    161     
    162     cout << ans << endl;
    163     
    164     return 0;
    165 }
    166 ```
    167 
    168 [1680E - Moving Chips](/contest/1680/problem/E "Educational Codeforces Round 128 (Rated for Div. 2)")
    169 
    170 Idea: [vovuh](/profile/vovuh "Master vovuh")
    171 
    172 **Tutorial**
    173 
    174 Tutorial is loading...
    175 
    176 **Solution (vovuh)**
    177 
    178 ```
    179 #include <bits/stdc++.h>
    180 
    181 using namespace std;
    182 
    183 const int INF = 1e9;
    184 
    185 int main() {
    186 #ifdef _DEBUG
    187     freopen("input.txt", "r", stdin);
    188 //  freopen("output.txt", "w", stdout);
    189 #endif
    190     
    191     int tc;
    192     cin >> tc;
    193     while (tc--) {
    194         int n;
    195         string s[2];
    196         cin >> n >> s[0] >> s[1];
    197         
    198         for (int it = 0; it < 2; ++it) {
    199             while (s[0].back() == '.' && s[1].back() == '.') {
    200                 s[0].pop_back();
    201                 s[1].pop_back();
    202             }
    203             reverse(s[0].begin(), s[0].end());
    204             reverse(s[1].begin(), s[1].end());
    205         }
    206         n = s[0].size();
    207         
    208         vector<vector<int>> cost(n, vector<int>(2));
    209         for (int i = 0; i < n; ++i) {
    210             for (int j = 0; j < 2; ++j) {
    211                 cost[i][j] = (s[j][i] == '*');
    212             }
    213         }
    214         
    215         vector<vector<int>> dp(n, vector<int>(2, INF));
    216         dp[0][0] = cost[0][1];
    217         dp[0][1] = cost[0][0];
    218         for (int i = 0; i + 1 < n; ++i) {
    219             dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + 1 + cost[i + 1][1]);
    220             dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + 2);
    221             dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1 + cost[i + 1][0]);
    222             dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + 2);
    223         }
    224         
    225         cout << min(dp[n - 1][0], dp[n - 1][1]) << endl;
    226     }
    227         
    228     return 0;
    229 }
    230 ```
    231 
    232 [1680F - Lenient Vertex Cover](/contest/1680/problem/F "Educational Codeforces Round 128 (Rated for Div. 2)")
    233 
    234 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    235 
    236 **Tutorial**
    237 
    238 Tutorial is loading...
    239 
    240 **Solution (awoo)**
    241 
    242 ```
    243 #include <bits/stdc++.h>
    244 
    245 #define forn(i, n) for (int i = 0; i < int(n); i++)
    246 
    247 using namespace std;
    248 
    249 vector<vector<int>> g, h;
    250 vector<int> tin, tout, clr;
    251 vector<vector<int>> sum(2);
    252 int T;
    253 
    254 int flip;
    255 int cnt;
    256 
    257 bool isp(int v, int u){
    258     return tin[v] <= tin[u] && tout[v] >= tout[u];
    259 }
    260 
    261 void init(int v){
    262     tin[v] = T++;
    263     for (int u : g[v]){
    264         if (clr[u] == -1){
    265             clr[u] = clr[v] ^ 1;
    266             h[v].push_back(u);
    267             init(u);
    268         }
    269         else if (tin[u] < tin[v]){
    270             int dif = clr[v] ^ clr[u];
    271             if (!dif){
    272                 flip = clr[v] ^ 1;
    273                 ++cnt;
    274             }
    275             --sum[dif][u];
    276             ++sum[dif][v]; 
    277         }
    278     }
    279     tout[v] = T;
    280 }
    281 
    282 int sv;
    283 
    284 void dfs(int v){
    285     for (int u : h[v]){
    286         dfs(u);
    287         if (sum[0][u] == cnt && sum[1][u] == 1){
    288             sv = u;
    289             flip = clr[v] ^ 1;
    290         }
    291         forn(i, 2) sum[i][v] += sum[i][u];
    292     }
    293 }
    294 
    295 int main() {
    296     cin.tie(0);
    297     iostream::sync_with_stdio(false);
    298     int t;
    299     cin >> t;
    300     forn(_, t){
    301         int n, m;
    302         cin >> n >> m;
    303         g.assign(n, vector<int>());
    304         h.assign(n, vector<int>());
    305         forn(i, m){
    306             int v, u;
    307             cin >> v >> u;
    308             --v, --u;
    309             g[v].push_back(u);
    310             g[u].push_back(v);
    311         }
    312         tin.resize(n);
    313         tout.resize(n);
    314         forn(i, 2) sum[i].assign(n, 0);
    315         clr.assign(n, -1);
    316         cnt = 0;
    317         T = 0;
    318         clr[0] = 0;
    319         init(0);
    320         if (cnt <= 1){
    321             cout << "YES\n";
    322             forn(v, n) cout << (clr[v] ^ flip);
    323             cout << "\n";
    324             continue;
    325         }
    326         sv = -1;
    327         dfs(0);
    328         if (sv == -1){
    329             cout << "NO\n";
    330         }
    331         else{
    332             cout << "YES\n";
    333             forn(v, n) cout << (clr[v] ^ isp(sv, v) ^ flip);
    334             cout << "\n";
    335         }
    336     }
    337     return 0;
    338 }
    339 ```