codeforces-scrape

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

1393.md (8738B)


      1 Source: https://codeforces.com/blog/entry/81161
      2 
      3 [1393A - Rainbow Dash, Fluttershy and Chess Coloring](/contest/1393/problem/A "Codeforces Round 662 (Div. 2)")
      4 
      5 Idea: [AlFlen](/profile/AlFlen "Master AlFlen")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (74TrAkToR)**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 main() {
     19     ios_base::sync_with_stdio(0);
     20     cin.tie(0);
     21     cout.tie(0);
     22     int t, n;
     23     cin >> t;
     24     while (t--) {
     25         cin >> n;
     26         cout << n / 2 + 1 << '\n';
     27     }
     28     return 0;
     29 }
     30 ```
     31 
     32 [1393B - Applejack and Storages](/contest/1393/problem/B "Codeforces Round 662 (Div. 2)")
     33 
     34 Idea: [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR")
     35 
     36 **Tutorial**
     37 
     38 Tutorial is loading...
     39 
     40 **Solution (74TrAkToR)**
     41 
     42 ```
     43 #include<bits/stdc++.h>
     44 
     45 using namespace std;
     46 
     47 int const MAXN = 1e5 + 5;
     48 int cnt[MAXN];
     49 
     50 main() {
     51     ios_base::sync_with_stdio(0);
     52     cin.tie(0);
     53     cout.tie(0);
     54     
     55     int n, q, x, cnt2 = 0, cnt4 = 0;
     56     char type;
     57     cin >> n;
     58 
     59     for (int i = 1; i <= n; ++i) {
     60         cin >> x;
     61         
     62         cnt2 -= cnt[x] / 2;
     63         cnt4 -= cnt[x] / 4;
     64         cnt[x]++;
     65         cnt2 += cnt[x] / 2;
     66         cnt4 += cnt[x] / 4;
     67     }
     68 
     69     cin >> q;
     70 
     71     for (int i = 1; i <= q; ++i) {
     72         cin >> type >> x;
     73         cnt2 -= cnt[x] / 2;
     74         cnt4 -= cnt[x] / 4;
     75         
     76         if (type == '+') cnt[x]++;
     77         else cnt[x]--;
     78         
     79         cnt2 += cnt[x] / 2;
     80         cnt4 += cnt[x] / 4;
     81         
     82         if (cnt4 >= 1 && cnt2 >= 4) cout << "YES" << '\n';
     83         else cout << "NO" << '\n';
     84     }
     85     
     86     return 0;
     87 }
     88 ```
     89 
     90 [1393C - Pinkie Pie Eats Patty-cakes](/contest/1393/problem/C "Codeforces Round 662 (Div. 2)")
     91 
     92 Idea: [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR") и [lapochka_queen](/profile/lapochka_queen "Unrated, lapochka_queen")
     93 
     94 **Tutorial**
     95 
     96 Tutorial is loading...
     97 
     98 **Solution (AlFlen)**
     99 
    100 ```
    101 #include <bits/stdc++.h>
    102 
    103 using namespace std;
    104 
    105 const int MAXN = 100009;
    106 int cnt[MAXN];
    107 vector<int> a;
    108 int n;
    109 
    110 bool check(int x) {
    111     for (int i = 1; i <= n; i ++) cnt[i] = 0;
    112     for (int i = 0; i < n; i ++) cnt[a[i]]++;
    113 
    114     set<pair<int, int>, greater<pair<int, int>>> ss; //use greater comparator to sort set in descending order
    115     for (int i = 1; i <= n; i ++) {
    116         if (cnt[i] > 0) ss.insert({cnt[i], i});
    117     }
    118 
    119     vector<int> b;
    120     for (int i = 0; i < n; i ++) {
    121         if (i >= x && cnt[b[i - x]]) {
    122             ss.insert({cnt[b[i - x]], b[i - x]});
    123         }
    124 
    125         if (ss.empty()) return 0;
    126         b.push_back(ss.begin()->second);
    127         ss.erase(ss.begin());
    128         cnt[b.back()]--;
    129     }
    130 
    131     return 1;
    132 }
    133 
    134 signed main() {
    135 	ios :: sync_with_stdio(0);
    136 	cin.tie(0);
    137 
    138 	int ttt;
    139 	cin >> ttt;
    140 
    141 	while (ttt--) {
    142         cin >> n;
    143 
    144         a.resize(n);
    145         for (int i = 0; i < n; i ++) {
    146             cin >> a[i];
    147         }
    148 
    149         int l = 0, r = n;
    150         while (r - l > 1) {
    151             int m = (r + l) / 2;
    152             if (check(m)) {
    153                 l = m;
    154             }
    155 
    156             else {
    157                 r = m;
    158             }
    159         }
    160 
    161         cout << l - 1 << "\n";
    162 	}
    163 
    164 	return 0;
    165 }
    166 ```
    167 
    168 [1393D - Rarity and New Dress](/contest/1393/problem/D "Codeforces Round 662 (Div. 2)")
    169 
    170 Idea: [74TrAkToR](/profile/74TrAkToR "Master 74TrAkToR")
    171 
    172 **Tutorial**
    173 
    174 Tutorial is loading...
    175 
    176 **Solution (74TrAkToR)**
    177 
    178 ```
    179 #include<bits/stdc++.h>
    180 
    181 using namespace std;
    182 
    183 typedef long long ll;
    184 int const maxn = 2005;
    185 char a[maxn][maxn];
    186 int cnt_up[maxn][maxn], cnt_down[maxn][maxn], L[maxn], R[maxn];
    187 
    188 main() {
    189     ios_base::sync_with_stdio(0);
    190     cin.tie(0);
    191     cout.tie(0);
    192     int n, m;
    193     cin >> n >> m;
    194     for (int i = 1; i <= n; ++i) {
    195         for (int j = 1; j <= m; ++j) cin >> a[i][j];
    196     }
    197     ll ans = 0;
    198     for (int i = 1; i <= n; ++i) {
    199         for (int j = 1; j <= m; ++j) {
    200             if (i != 1 && a[i][j] == a[i - 1][j]) cnt_up[i][j] = cnt_up[i - 1][j] + 1;
    201             else cnt_up[i][j] = 0;
    202         }
    203     }
    204     for (int i = n; i >= 1; --i) {
    205         for (int j = 1; j <= m; ++j) {
    206             if (i != n && a[i][j] == a[i + 1][j]) cnt_down[i][j] = cnt_down[i + 1][j] + 1;
    207             else cnt_down[i][j] = 0;
    208         }
    209     }
    210     for (int i = 1; i <= n; ++i) {
    211         for (int j = 1; j <= m; ++j) {
    212             int go = j;
    213             while (go <= m && a[i][j] == a[i][go]) go++;
    214             go--;
    215             for (int pos = j; pos <= go; ++pos) {
    216                 if (pos == j) L[pos] = pos;
    217                 else {
    218                     L[pos] = max(L[pos - 1], pos - min(cnt_up[i][pos], cnt_down[i][pos]));
    219                 }
    220             }
    221             j = go;
    222         }
    223         for (int j = m; j >= 1; --j) {
    224             int go = j;
    225             while (go >= 1 && a[i][j] == a[i][go]) go--;
    226             go++;
    227             for (int pos = j; pos >= go; --pos) {
    228                 if (pos == j) R[pos] = pos;
    229                 else {
    230                     R[pos] = min(R[pos + 1], pos + min(cnt_up[i][pos], cnt_down[i][pos]));
    231                 }
    232             }
    233             j = go;
    234         }
    235         for (int j = 1; j <= m; ++j) {
    236             ans += (ll)min(j - L[j] + 1, R[j] - j + 1);
    237         }
    238     }
    239     cout << ans << '\n';
    240     return 0;
    241 }
    242 ```
    243 
    244 [1393E2 - Twilight and Ancient Scroll (harder version)](/contest/1393/problem/E2 "Codeforces Round 662 (Div. 2)")
    245 
    246 Idea: [AlFlen](/profile/AlFlen "Master AlFlen")
    247 
    248 **Tutorial**
    249 
    250 Tutorial is loading...
    251 
    252 **Solution (74TrAkToR)**
    253 
    254 ```
    255 #include<bits/stdc++.h>
    256 
    257 using namespace std;
    258 
    259 typedef long long ll;
    260 int const maxn = 1e5 + 5, maxc = 1e6 + 5;
    261 ll mod[2], P[2], p[2][maxc], rev_P[2];
    262 vector < ll > h[2][maxn];
    263 vector < int > sorted[maxn];
    264 string s[maxn];
    265 int nxt[maxc];
    266 int a[maxc], dp[2][maxc], inf = 1e9 + 7;
    267 int MOD = 1e9 + 7;
    268 
    269 ll st(ll x, int y, int ok) {
    270     if (y == 0) return 1;
    271     if (y % 2 == 0) {
    272         ll d = st(x, y / 2, ok);
    273         return d * d % mod[ok];
    274     }
    275     return x * st(x, y - 1, ok) % mod[ok];
    276 }
    277 
    278 inline char get_c(int i, int x, int numb) {
    279     if (numb < x) return s[i][numb];
    280     if (numb + 1 < (int)s[i].size()) return s[i][numb + 1];
    281     return ' ';
    282 }
    283 
    284 inline ll get_hash(int t, int i, int x, int len) {
    285     if (len < x) return h[t][i][len];
    286     return (h[t][i][x] + (h[t][i][len + 1] - h[t][i][x + 1] + mod[t]) * rev_P[t]) % mod[t];
    287 }
    288 
    289 inline pair < ll, ll > get_h(int i, int x, int len) {
    290     return {get_hash(0, i, x, len), get_hash(1, i, x, len)};
    291 }
    292 
    293 inline int check(int i, int x, int j, int y) {
    294     int len1 = (int)s[i].size(), len2 = (int)s[j].size();
    295     if (x != len1) len1--;
    296     if (y != len2) len2--;
    297     int lef = 0, righ = min(len1, len2) + 1;
    298     while (righ - lef > 1) {
    299         int mid = (righ + lef) / 2;
    300         if (get_h(i, x, mid) == get_h(j, y, mid)) lef = mid;
    301         else righ = mid;
    302     }
    303     return get_c(i, x, lef) >= get_c(j, y, lef);
    304 }
    305 
    306 main() {
    307     ios_base::sync_with_stdio(0);
    308     cin.tie(0);
    309     cout.tie(0);
    310     mod[0] = 1e9 + 7, mod[1] = 1e9 + 9, P[0] = 29, P[1] = 31, rev_P[0] = st(P[0], mod[0] - 2, 0), rev_P[1] = st(P[1], mod[1] - 2, 1);
    311     p[0][0] = 1, p[1][0] = 1;
    312     for (int i = 1; i < maxc; ++i) {
    313         for (int j = 0; j <= 1; ++j) p[j][i] = p[j][i - 1] * P[j] % mod[j];
    314     }
    315     int n;
    316     cin >> n;
    317     for (int i = 1; i <= n; ++i) {
    318         cin >> s[i];
    319         for (int j = 0; j <= 1; ++j) {
    320             h[j][i].push_back(0);
    321             for (int pos = 0; pos < (int)s[i].size(); ++pos) {
    322                 h[j][i].push_back((h[j][i][pos] + p[j][pos] * (s[i][pos] - 'a' + 1)) % mod[j]);
    323             }
    324         }
    325         nxt[(int)s[i].size() - 1] = (int)s[i].size() - 1;
    326         for (int pos = (int)s[i].size() - 2; pos >= 0; --pos) {
    327             if (s[i][pos] != s[i][pos + 1]) nxt[pos] = pos + 1;
    328             else nxt[pos] = nxt[pos + 1];
    329         }
    330         int l = 0, r = (int)s[i].size() - 1;
    331         for (int j = 0; j < (int)s[i].size(); ++j) {
    332             if (s[i][nxt[j]] <= s[i][j]) a[l++] = j;
    333             else a[r--] = j;
    334         }
    335         for (int j = 0; j < (int)s[i].size(); ++j) {
    336             sorted[i].push_back(a[j]);
    337             if (a[j] == (int)s[i].size() - 1) sorted[i].push_back((int)s[i].size());
    338         }
    339     }
    340     for (int i = 0; i <= (int)s[1].size(); ++i) {
    341         dp[0][i] = 1;
    342     }
    343     for (int i = 2; i <= n; ++i) {
    344         int oks = (i - 1) % 2, ptr = 0, sum = 0, cur = -1;
    345         for (auto key : sorted[i]) {
    346             cur++;
    347             while (ptr < (int)sorted[i - 1].size() && check(i, key, i - 1, sorted[i - 1][ptr])) {
    348                 sum += dp[(1^oks)][ptr];
    349                 if (sum >= MOD) sum -= MOD;
    350                 ptr++;
    351             }
    352             dp[oks][cur] = sum;
    353         }
    354     }
    355     int ans = 0;
    356     for (int i = 0; i <= (int)s[n].size(); ++i) {
    357         ans += dp[(n - 1) % 2][i];
    358         if (ans >= MOD) ans -= MOD;
    359     }
    360     cout << ans << '\n';
    361     return 0;
    362 }
    363 ```