codeforces-scrape

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

1281.md (12057B)


      1 Source: https://codeforces.com/blog/entry/72212
      2 
      3 I hope you enjoyed the problems! Thanks to the onsite teams and coaches who gave feedback; I'm glad the reception was positive.
      4 
      5 Interestingly, in the onsite ICPC round, while "Kirchhoff" got several accepted solutions, "Miss Punyverse" got no accepted submissions at all! It is the reverse here. (Kirchhoff even has a trickier output format in the onsite round compared to the version presented in Codeforces.) It seems the ICPC scoreboard really affects the results greatly; what the top few teams are working on influences what everyone else will be working on.
      6 
      7 I am planning on releasing the full, untouched ICPC Manila 2019 problem set in the gym sometime in the future, so you can see which problems you missed. The Intergalactic Sliding Puzzle is *not* the hardest problem in the round!
      8 
      9 [1281A - Suffix Three](/contest/1281/problem/A "Codeforces Round 607 (Div. 2)")
     10 
     11 **Solution Sketch**
     12 
     13 Tutorial is loading...
     14 
     15 **Accepted Code**
     16 
     17 ```
     18 for cas in range(int(input())): print({'o': "FILIPINO", 'a': "KOREAN", 'u': "JAPANESE"}[input()[-1]])
     19 ```
     20 
     21 Accepted Submission: [67015948](/contest/1281/submission/67015948 "Submission 67015948 by kevinsogo")
     22 
     23 [1281B - Azamon Web Services](/contest/1281/problem/B "Codeforces Round 607 (Div. 2)")
     24 
     25 **Solution Sketch**
     26 
     27 Tutorial is loading...
     28 
     29 **Accepted Code**
     30 
     31 ```
     32 def solve(s, t):
     33     mns = list(s)
     34     for i in range(len(s)-2,-1,-1): mns[i] = min(mns[i], mns[i + 1])
     35     for i in range(len(s)):
     36         if s[i] != mns[i]:
     37             j = max(j for j, v in enumerate(s[i:], i) if v == mns[i])
     38             s = s[:i] + s[j] + s[i+1:j] + s[i] + s[j+1:]
     39             break
     40     return s if s < t else '---'
     41 
     42 for cas in range(int(input())):
     43     print(solve(*input().split()))
     44 ```
     45 
     46 Accepted Submission: [67049609](/contest/1281/submission/67049609 "Submission 67049609 by kevinsogo")
     47 
     48 [1281C - Cut and Paste](/contest/1281/problem/C "Codeforces Round 607 (Div. 2)")
     49 
     50 **Solution Sketch**
     51 
     52 Tutorial is loading...
     53 
     54 **Accepted Code**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58 using namespace std;
     59 using ll = long long;
     60 constexpr ll mod = 1'000'000'007; //'
     61 constexpr int N = 1111;
     62 
     63 char _s[N];
     64 ll solve() {
     65     int x;
     66     scanf("%d%s", &x, _s);
     67     ll ls = strlen(_s);
     68     vector<char> s(_s, _s + ls);
     69     for (int i = 1; i <= x; i++) {
     70         int v = s[i - 1] - '1';
     71         if (s.size() < x) {
     72             vector<char> sub(s.begin() + i, s.end());
     73             for (int it = 0; it < v; it++) s.insert(s.end(), sub.begin(), sub.end());
     74         }
     75         ls = (ls + (ls - i) * v) % mod;
     76     }
     77     return ls;
     78 }
     79 
     80 int main() {
     81     int z;
     82     for (scanf("%d", &z); z--; printf("%lld\n", (solve() % mod + mod) % mod));
     83 }
     84 ```
     85 
     86 Accepted Submission: [67016113](/contest/1280/submission/67016113 "Submission 67016113 by kevinsogo")
     87 
     88 [1281D - Beingawesomeism](/contest/1281/problem/D "Codeforces Round 607 (Div. 2)")
     89 
     90 **Solution Sketch**
     91 
     92 Tutorial is loading...
     93 
     94 **Accepted Code**
     95 
     96 ```
     97 #include <bits/stdc++.h>
     98 using namespace std;
     99 
    100 int solve(int r, int c, vector<string> grid) {
    101     vector<int> rows(r), cols(c);
    102     int total = 0;
    103     for (int i = 0; i < r; i++) {
    104         for (int j = 0; j < c; j++) {
    105             if (grid[i][j] == 'A') rows[i]++, cols[j]++, total++;
    106         }
    107     }
    108     if (total == r * c) return 0;
    109     if (total == 0) return -1;
    110 
    111     if (rows[0] == c || rows.back() == c || cols[0] == r || cols.back() == r) return 1;
    112     if (grid[0][0] == 'A' || grid[0].back() == 'A' || grid.back()[0] == 'A' || grid.back().back() == 'A') return 2;
    113     if (*max_element(rows.begin(), rows.end()) == c || *max_element(cols.begin(), cols.end()) == r) return 2;
    114     if (rows[0] || rows.back() || cols[0] || cols.back()) return 3;
    115     return 4;
    116 }
    117 
    118 int main() {
    119     int z;
    120     for (cin >> z; z--;) {
    121         int r, c;
    122         cin >> r >> c;
    123         vector<string> grid(r);
    124         for (int i = 0; i < r; i++) cin >> grid[i];
    125         int res = solve(r, c, grid);
    126         (~res ? cout << res : cout << "MORTAL") << '\n';
    127     }
    128 }
    129 ```
    130 
    131 Accepted Submission: [67016167](/contest/1280/submission/67016167 "Submission 67016167 by kevinsogo")
    132 
    133 [1281E - Jeremy Bearimy](/contest/1281/problem/E "Codeforces Round 607 (Div. 2)")
    134 
    135 **Solution Sketch**
    136 
    137 Tutorial is loading...
    138 
    139 **Accepted Code**
    140 
    141 ```
    142 #include <bits/stdc++.h>
    143 using namespace std;
    144 using ll = long long;
    145 
    146 void solve() {
    147     int n;
    148     cin >> n;
    149     n <<= 1;
    150     vector<vector<pair<int,ll>>> adj(n);
    151     for (int i = 0; i < n - 1; i++) {
    152         int a, b; ll c;
    153         cin >> a >> b >> c;
    154         a--, b--;
    155         adj[a].emplace_back(b, c);
    156         adj[b].emplace_back(a, c);
    157     }
    158 
    159     vector<int> parent(n, -1), que(1, 0);
    160     vector<ll> parent_cost(n);
    161     parent[0] = 0;
    162     for (int f = 0; f < que.size(); f++) {
    163         int i = que[f];
    164         for (auto [j, c]: adj[i]) {
    165             if (parent[j] == -1) {
    166                 parent[j] = i;
    167                 parent_cost[j] = c;
    168                 que.push_back(j);
    169             }
    170         }
    171     }
    172     vector<int> size(n, 1);
    173     ll mn = 0, mx = 0;
    174     reverse(que.begin(), que.end());
    175     for (int i : que) {
    176         size[parent[i]] += size[i];
    177         mx += parent_cost[i] * min(size[i], n - size[i]);
    178         mn += parent_cost[i] * (size[i] & 1);
    179     }
    180     cout << mn << " " << mx << '\n';
    181 }
    182 
    183 int main() {
    184     ios_base::sync_with_stdio(false);
    185     cin.tie(NULL);
    186     int z;
    187     for (cin >> z; z--; solve());
    188 }
    189 ```
    190 
    191 Accepted Submission: [67020743](/contest/1280/submission/67020743 "Submission 67020743 by kevinsogo")
    192 
    193 [1281F - Miss Punyverse](/contest/1281/problem/F "Codeforces Round 607 (Div. 2)")
    194 
    195 **Solution Sketch**
    196 
    197 Tutorial is loading...
    198 
    199 **Accepted Code**
    200 
    201 ```
    202 #include <bits/stdc++.h>
    203 using namespace std;
    204 using ll = long long;
    205 
    206 struct Group {
    207     int win; ll adv;
    208     Group(int win = -1, ll adv = 0): win(win), adv(adv) {}
    209     Group operator+(const Group& o) const {
    210         return Group(win + o.win, adv + o.adv);
    211     }
    212     Group operator+() const {
    213         return Group(win + (adv > 0));
    214     }
    215     bool operator<(const Group& o) const {
    216         return win < o.win || win == o.win && adv < o.adv;
    217     }
    218 };
    219 
    220 vector<Group> convolve(const vector<Group>& fa, const vector<Group>& fb) {
    221     vector<Group> fi(fa.size() + fb.size());
    222     for (int a = 0; a < fa.size(); a++) {
    223         for (int b = 0; b < fb.size(); b++) {
    224             fi[a + b    ] = max(fi[a + b    ], fa[a] +  fb[b]);
    225             fi[a + b + 1] = max(fi[a + b + 1], fa[a] + +fb[b]);
    226         }
    227     }
    228     return fi;
    229 }
    230 
    231 vector<vector<Group>> f;
    232 vector<vector<int>> adj;
    233 void convolve_tree(int i, int p = -1) {
    234     for (int j : adj[i]) {
    235         if (j == p) continue;
    236         convolve_tree(j, i);
    237         f[i] = convolve(f[i], f[j]);
    238     }
    239 }
    240 
    241 int solve() {
    242     int n, m;
    243     scanf("%d%d", &n, &m);
    244     f = vector<vector<Group>>(n, vector<Group>(1, Group(0)));
    245     for (int i = 0, b; i < n; i++) {
    246         scanf("%d", &b);
    247         f[i][0].adv -= b;
    248     }
    249     for (int i = 0, w; i < n; i++) {
    250         scanf("%d", &w);
    251         f[i][0].adv += w;
    252     }
    253     adj = vector<vector<int>>(n);
    254     for (int i = 1; i < n; i++) {
    255         int x, y;
    256         scanf("%d%d", &x, &y);
    257         x--, y--;
    258         adj[x].push_back(y);
    259         adj[y].push_back(x);
    260     }
    261     convolve_tree(0);
    262     return (+f[0][m - 1]).win;
    263 }
    264 
    265 int main() {
    266     int z;
    267     for (scanf("%d", &z); z--; printf("%d\n", solve()));
    268 }
    269 ```
    270 
    271 Accepted Submission: [67016189](/contest/1280/submission/67016189 "Submission 67016189 by kevinsogo")
    272 
    273 [1280E - Kirchhoff's Current Loss](/contest/1280/problem/E "Codeforces Round 607 (Div. 1)")
    274 
    275 **Solution Sketch**
    276 
    277 Tutorial is loading...
    278 
    279 **Accepted Code**
    280 
    281 ```
    282 #include <bits/stdc++.h>
    283 using namespace std;
    284 using ll = long long;
    285 const ll INF = 1LL << 60;
    286 
    287 class Circuit {
    288 public:
    289     ll w = -1;
    290     ll width() {
    291         if (w == -1) compute_width();
    292         return w;
    293     }
    294     virtual void compute_width() {}
    295     virtual void assign(ll value) {}
    296     virtual ostream& write_to(ostream& os) const { return os; }
    297     void assign_minimal(ll value) { assign(value * width()); }
    298     friend ostream& operator<<(ostream& os, const Circuit& circuit);
    299 };
    300 
    301 ostream& operator<<(ostream& os, const Circuit& circuit) {
    302     return circuit.write_to(os);
    303 }
    304 
    305 class Resistor: public Circuit {
    306 public:
    307     ll value = -1;
    308     Resistor() {}
    309     void compute_width() override {
    310         w = 1;
    311     }
    312     void assign(ll value) override {
    313         this->value = value;
    314     }
    315     ostream& write_to(ostream& os) const override {
    316         return os << ' ' << value;
    317     }
    318 };
    319 
    320 class Join: public Circuit {
    321 public:
    322     char typ;
    323     vector<Circuit*> children;
    324     Join() {}
    325     void compute_width() override {
    326         w = typ == 'S' ? INF : 0;
    327         for (auto child: children) {
    328             ll ww = child->width();
    329             w = typ == 'S' ? min(w, ww) : w + ww;
    330         }
    331     }
    332     void assign(ll value) override {
    333         for (auto child: children) {
    334             if (typ == 'S') {
    335                 if (child->width() == width()) {
    336                     child->assign(value);
    337                     value = 0;
    338                 } else {
    339                     child->assign(0);
    340                 }
    341             } else {
    342                 child->assign(value);
    343             }
    344         }
    345     }
    346     ostream& write_to(ostream& os) const override {
    347         for (auto child: children) os << *child;
    348         return os;
    349     }
    350 };
    351 
    352 class CircuitParser {
    353     const string& s;
    354     int i = 0;
    355     CircuitParser(const string& s): s(s) {}
    356     Circuit *parse() {
    357         if (s[i++] == '(') {
    358             Join *j = new Join();
    359             while (true) {
    360                 j->children.push_back(parse());
    361                 if (s[i++] == ')') break;
    362                 j->typ = s[i++];
    363                 i++;
    364             }
    365             return j;
    366         } else {
    367             return new Resistor();
    368         }
    369     }
    370 public:
    371     static Circuit *parse(const string& s) {
    372         return CircuitParser(s).parse();
    373     }
    374 };
    375 
    376 void solve(ll a, const string& s) {
    377     Circuit *c = CircuitParser::parse(s);
    378     c->assign_minimal(a);
    379     cout << "REVOLTING" << *c << '\n';
    380 }
    381 
    382 int main() {
    383     ios_base::sync_with_stdio(false);
    384     cin.tie(NULL);
    385     int z;
    386     for (cin >> z; z--;) {
    387         ll a;
    388         string s;
    389         cin >> a;
    390         getline(cin, s);
    391         assert(s[0] == ' ');
    392         solve(a, s.substr(1));
    393     }
    394 }
    395 ```
    396 
    397 Accepted Submission: [67016199](/contest/1280/submission/67016199 "Submission 67016199 by kevinsogo")
    398 
    399 [1280F - Intergalactic Sliding Puzzle](/contest/1280/problem/F "Codeforces Round 607 (Div. 1)")
    400 
    401 **Solution Sketch**
    402 
    403 Tutorial is loading...
    404 
    405 **Accepted Code**
    406 
    407 ```
    408 def solve(k, grid):
    409     seek = *range(2*k + 2), *range(4*k + 1, 2*k + 1, -1)
    410     flat = [seek[v] for v in grid[0] + grid[1][::-1] if v]
    411 
    412     m = {
    413         'L': 'l'*2*k + 'u' + 'r'*2*k + 'd',
    414         'R': 'u' + 'l'*2*k + 'd' + 'r'*2*k,
    415         'C': 'l'*k + 'u' + 'r'*k + 'd',
    416         'D': 'CC' + 'R'*(2*k + 1) + 'CC' + 'R'*(2*k + 2),
    417         'F': 'R'*(k - 1) + 'DD' + 'R'*(2*k + 1) + 'D' + 'L'*2*k + 'DD' + 'L'*k,
    418         'G': 'FF',
    419     }
    420 
    421     [(i, j)] = [(i, j) for i in range(2) for j in range(2*k + 1) if grid[i][j] == 0]
    422     st = 'r'*(2*k - j) + 'd'*(1 - i)
    423 
    424     for v in range(2, 4*k + 2):
    425         ct = flat.index(v)
    426 
    427         if ct >= 2:
    428             st += 'L'*(ct - 2) + 'GR'*(ct - 2) + 'G'
    429             flat = flat[ct - 1: ct + 1] + flat[:ct - 1] + flat[ct + 1:]
    430 
    431         if ct >= 1:
    432             st += 'G'
    433             flat = flat[1:3] + flat[:1] + flat[3:]
    434 
    435         st += 'L'
    436         flat = flat[1:] + flat[:1]
    437         
    438     if flat[0] == 1: return st, m
    439 
    440 def main():
    441     def get_line():
    442         return [0 if x == 'E' else int(x) for x in input().split()]
    443 
    444     for cas in range(int(input())):
    445         res = solve(int(input()), [get_line() for i in range(2)])
    446         if res is None:
    447             print('SURGERY FAILED')
    448         else:
    449             print('SURGERY COMPLETE')
    450             st, m = res
    451             print(st)
    452             for shortcut in m.items(): print(*shortcut)
    453             print('DONE')
    454 
    455 main()
    456 ```
    457 
    458 Accepted Submission: [67026155](/contest/1280/submission/67026155 "Submission 67026155 by kevinsogo")