codeforces-scrape

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

1607.md (11230B)


      1 Source: https://codeforces.com/blog/entry/96604
      2 
      3 ### Short information
      4 
      5 Sorry for another delayed editorial, I know I promised that it will come out sooner the previous time, but I wasn't feeling well today, so the work was slower than usual.
      6 
      7 **About problem F:**
      8 
      9 I am once again sorry for the inconveniences caused by tight ML in this problem. It was not the intended behavior since we relied too much on the main solution and didn't assume most of the solutions using DFS will fail. In this editorial I attach the code of the main solution that we expected from the beginning, it uses ~75MB of memory.
     10 
     11 I guess, Div. 3 Rounds are not only for participants to learn but also can serve as educational for authors as well. I'll try not to repeat the same mistakes the next time :) Thanks to everyone for participating and hope to see you again!
     12 
     13 ### The editorial
     14 
     15 [1607A - Linear Keyboard](/contest/1607/problem/A "Codeforces Round 753 (Div. 3)")
     16 
     17 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     18 
     19 **Tutorial**
     20 
     21 Tutorial is loading...
     22 
     23 **Solution**
     24 
     25 ```
     26 t = int(input())
     27 for _ in range(t):
     28     k, s = input(), input()
     29     res = 0
     30     for i in range(1, len(s)):
     31         res += abs(k.index(s[i]) - k.index(s[i - 1]))
     32     print(res)
     33 ```
     34 
     35 [1607B - Odd Grasshopper](/contest/1607/problem/B "Codeforces Round 753 (Div. 3)")
     36 
     37 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution**
     44 
     45 ```
     46 t = int(input())
     47 maps = [
     48     lambda x: 0,
     49     lambda x: x,
     50     lambda x: -1,
     51     lambda x: -x - 1
     52 ]
     53 
     54 for _ in range(t):
     55     x0, n = map(int, input().split())
     56     d = maps[n % 4](n)
     57     print(x0 - d if x0 % 2 == 0 else x0 + d)
     58 ```
     59 
     60 [1607C - Minimum Extraction](/contest/1607/problem/C "Codeforces Round 753 (Div. 3)")
     61 
     62 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov")
     63 
     64 **Tutorial**
     65 
     66 Tutorial is loading...
     67 
     68 **Solution**
     69 
     70 ```
     71 t = int(input())
     72 
     73 for _ in range(t):
     74     n = int(input())
     75     a = sorted(list(map(int, input().split())))
     76     res = a[0]
     77     for i in range(n - 1):
     78         res = max(res, a[i + 1] - a[i])
     79     print(res)
     80 ```
     81 
     82 [1607D - Blue-Red Permutation](/contest/1607/problem/D "Codeforces Round 753 (Div. 3)")
     83 
     84 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     85 
     86 **Tutorial**
     87 
     88 Tutorial is loading...
     89 
     90 **Solution**
     91 
     92 ```
     93 #include <bits/stdc++.h>
     94 
     95 using namespace std;
     96 
     97 #define forn(i, n) for (int i = 0; i < int(n); i++)
     98 
     99 int main() {
    100     int t;
    101     cin >> t;
    102     forn(tt, t) {
    103         int n;
    104         cin >> n;
    105         vector<int> a(n);
    106         forn(i, n)
    107             cin >> a[i];
    108 
    109         string c;
    110         cin >> c;
    111 
    112         vector<int> l, r;
    113         forn(i, n)
    114             (c[i] == 'B' ? l : r).push_back(a[i]);
    115         sort(l.begin(), l.end());
    116         sort(r.begin(), r.end(), greater<int>());
    117 
    118         bool ok = true;
    119         forn(i, l.size())
    120             if (l[i] < i + 1)
    121                 ok = false;
    122         forn(i, r.size())
    123             if (r[i] > n - i)
    124                 ok = false;
    125 
    126         cout << (ok ? "YES" : "NO") << '\n';
    127     }
    128 }
    129 ```
    130 
    131 [1607E - Robot on the Board 1](/contest/1607/problem/E "Codeforces Round 753 (Div. 3)")
    132 
    133 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    134 
    135 **Tutorial**
    136 
    137 Tutorial is loading...
    138 
    139 **Solution**
    140 
    141 ```
    142 #include <bits/stdc++.h>
    143 
    144 using namespace std;
    145 
    146 int main() {
    147     int t;
    148     cin >> t;
    149     while (t--) {
    150         int n, m;
    151         cin >> n >> m;
    152         string s;
    153         cin >> s;
    154 
    155         int bx = 0, by = 0;
    156         int min_bx = 0, max_bx = 0, min_by = 0, max_by = 0;
    157         for (char c: s) {
    158             if      (c == 'L') min_by = min(min_by, --by);
    159             else if (c == 'R') max_by = max(max_by, ++by);
    160             else if (c == 'U') min_bx = min(min_bx, --bx);
    161             else               max_bx = max(max_bx, ++bx);
    162 
    163             if (max_bx - min_bx >= n) {
    164                 if (bx == min_bx) min_bx++;
    165                 break;
    166             }
    167             if (max_by - min_by >= m) {
    168                 if (by == min_by) min_by++;
    169                 break;
    170             }
    171         }
    172 
    173         cout << 1 - min_bx << ' ' << 1 - min_by << '\n';
    174     }
    175 }
    176 ```
    177 
    178 [1607F - Robot on the Board 2](/contest/1607/problem/F "Codeforces Round 753 (Div. 3)")
    179 
    180 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov")
    181 
    182 **Tutorial**
    183 
    184 Tutorial is loading...
    185 
    186 **Solution**
    187 
    188 ```
    189 #include <bits/stdc++.h>
    190 
    191 using namespace std;
    192 
    193 typedef vector<int> vi;
    194 typedef pair<int, int> pii;
    195 
    196 int main() {
    197     int t;
    198     cin >> t;
    199     while (t--) {
    200         int n, m;
    201         cin >> n >> m;
    202         vector<string> dir(n);
    203         for (int i = 0; i < n; i++)
    204             cin >> dir[i];
    205 
    206         vector<vi> res(n, vi(m, 0));
    207         int opt = 0, optr = 0, optc = 0;
    208         for (int r = 0; r < n; r++) {
    209             for (int c = 0; c < m; c++) {
    210                 if (res[r][c] > 0)
    211                     continue;
    212 
    213                 int nr = r, nc = c;
    214                 int depth = 0;
    215                 vector<pii> path;
    216                 auto ok = [&n, &m](int row, int col) {
    217                     return row > -1 && row < n && col > -1 && col < m;
    218                 };
    219 
    220                 do {
    221                     res[nr][nc] = --depth;
    222                     path.emplace_back(nr, nc);
    223                     if (dir[nr][nc] == 'L')
    224                         nc--;
    225                     else if (dir[nr][nc] == 'R')
    226                         nc++;
    227                     else if (dir[nr][nc] == 'U')
    228                         nr--;
    229                     else
    230                         nr++;
    231                 } while (ok(nr, nc) && res[nr][nc] == 0);
    232 
    233                 int start = 1;
    234                 if (ok(nr, nc)) {
    235                     if (res[nr][nc] < 0) {
    236                         int cycle = res[nr][nc] - depth + 1;
    237                         for (int i = 0; i < cycle; i++) {
    238                             auto p = path.back();
    239                             path.pop_back();
    240                             res[p.first][p.second] = cycle;
    241                         }
    242                     }
    243                     start = res[nr][nc] + 1;
    244                 }
    245                 while (!path.empty()) {
    246                     auto p = path.back();
    247                     path.pop_back();
    248                     res[p.first][p.second] = start++;
    249                 }
    250 
    251                 if (res[r][c] > opt) {
    252                     opt = res[r][c];
    253                     optr = r;
    254                     optc = c;
    255                 }
    256             }
    257         }
    258 
    259         cout << optr + 1 << ' ' << optc + 1 << ' ' << opt << '\n';
    260     }
    261 }
    262 ```
    263 
    264 [1607G - Banquet Preparations 1](/contest/1607/problem/G "Codeforces Round 753 (Div. 3)")
    265 
    266 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov")
    267 
    268 **Tutorial**
    269 
    270 Tutorial is loading...
    271 
    272 **Solution**
    273 
    274 ```
    275 #include <bits/stdc++.h>
    276 
    277 using namespace std;
    278 
    279 typedef pair<int, int> pii;
    280 typedef long long ll;
    281 
    282 int main() {
    283     int t;
    284     cin >> t;
    285     while (t--) {
    286         int n, m;
    287         cin >> n >> m;
    288         vector<pii> dishes(n);
    289         ll balance = 0;
    290         ll max_a = 0, max_b = 0;
    291         ll total_eat = static_cast<long long>(n) * m;
    292 
    293         for (int i = 0; i < n; i++) {
    294             cin >> dishes[i].first >> dishes[i].second;
    295             balance += dishes[i].first - dishes[i].second;
    296             max_a += min(m, dishes[i].first);
    297             max_b += min(m, dishes[i].second);
    298         }
    299         ll max_delta = 2 * max_a - total_eat, min_delta = total_eat - 2 * max_b;
    300         ll min_a = total_eat - max_b;
    301 
    302         ll eat_a;
    303         if (balance < 0) {
    304             eat_a = min_a;
    305             if (balance - min_delta >= 0)
    306                 eat_a = min(max_a, (total_eat + balance + 1) / 2);
    307         } else {
    308             eat_a = max_a;
    309             if (balance - max_delta <= 0)
    310                 eat_a = min(max_a, (total_eat + balance + 1) / 2);
    311         }
    312         ll ans = abs(balance - 2 * eat_a + total_eat);
    313 
    314         cout << ans << '\n';
    315         ll rest_a = eat_a - min_a;
    316         for (int i = 0; i < n; i++) {
    317             ll cur_a = 0;
    318             if (dishes[i].second < m)
    319                 cur_a += m - dishes[i].second;
    320             ll add = min(rest_a, min(m - cur_a, dishes[i].first - cur_a));
    321             cur_a += add;
    322             rest_a -= add;
    323             cout << cur_a << ' ' << m - cur_a << '\n';
    324         }
    325     }
    326 }
    327 ```
    328 
    329 [1607H - Banquet Preparations 2](/contest/1607/problem/H "Codeforces Round 753 (Div. 3)")
    330 
    331 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    332 
    333 **Tutorial**
    334 
    335 Tutorial is loading...
    336 
    337 **Solution**
    338 
    339 ```
    340 #include <bits/stdc++.h>
    341 
    342 using namespace std;
    343 
    344 #define forn(i, n) for (int i = 0; i < int(n); i++)
    345 
    346 struct seg {
    347     int a, b, m;
    348     int index;
    349 };
    350 
    351 int n, ans;
    352 vector<seg> segments;
    353 map<int, vector<seg>> diags;
    354 
    355 void erase(multiset<pair<pair<int,int>, int>>& lr, int l, int r, int index) {
    356     pair<pair<int,int>,int> plr = make_pair(make_pair(l, r), index);
    357     auto i = lr.find(plr);
    358     assert(i != lr.end());
    359     lr.erase(i);
    360 }
    361 
    362 void erase(multiset<pair<pair<int,int>, int>>& lr, multiset<pair<pair<int,int>, int>>& rl, int l, int r, int index) {
    363     erase(lr, l, r, index);
    364     erase(rl, r, l, index);
    365 }
    366 
    367 map<int, pair<int,int>> dd;
    368 
    369 void setup_dd(int index, int value) {
    370     assert(dd.count(index) == 0);
    371     int x = segments[index].a - value;
    372     int y = segments[index].m - x;
    373     assert(segments[index].a - x >= 0);
    374     assert(segments[index].b - y >= 0);
    375     assert(x + y == segments[index].m);
    376     dd[index] = make_pair(x, y);
    377 }
    378 
    379 int solve(vector<seg> s) {
    380     int n = s.size();
    381     multiset<pair<pair<int,int>, int>> lr;
    382     multiset<pair<pair<int,int>, int>> rl;
    383     forn(i, n) {
    384         int min_d = max(s[i].m - s[i].b, 0);
    385         int max_d = min(s[i].a, s[i].m);
    386         lr.insert(make_pair(make_pair(s[i].a - max_d, s[i].a - min_d), s[i].index));
    387         rl.insert(make_pair(make_pair(s[i].a - min_d, s[i].a - max_d), s[i].index));
    388     }
    389 
    390     int result = 0;
    391     while (!rl.empty()) {
    392         result++;
    393         auto min_r_iterator = rl.begin();
    394         int r = min_r_iterator->first.first;
    395         int l = min_r_iterator->first.second;
    396         int index = min_r_iterator->second;
    397         erase(lr, rl, l, r, index);
    398         setup_dd(index, r);
    399 
    400         while (!lr.empty()) {
    401             auto min_l_iterator = lr.begin();
    402             int ll = min_l_iterator->first.first;
    403             int rr = min_l_iterator->first.second;
    404             int ii = min_l_iterator->second;
    405             if (ll <= r) {
    406                 erase(lr, rl, ll, rr, ii);
    407                 setup_dd(ii, r);
    408             } else
    409                 break;
    410         }
    411     }
    412 
    413     return result;
    414 }
    415 
    416 int main() {
    417     int t;
    418     cin >> t;
    419     forn(tt, t) {
    420         cin >> n;
    421         diags.clear();
    422         dd.clear();
    423         segments = vector<seg>(n);
    424         forn(i, n) {
    425             seg s;
    426             s.index = i;
    427             cin >> s.a >> s.b >> s.m;
    428             diags[s.a + s.b - s.m].push_back(s);
    429             segments[i] = s;
    430         }
    431         int sum = 0;
    432         for (auto p: diags)
    433             sum += solve(p.second);
    434         cout << sum << '\n';
    435         forn(i, n)
    436             cout << dd[i].first << " " << dd[i].second << '\n';
    437     }
    438 }
    439 ```