codeforces-scrape

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

1494.md (9195B)


      1 Source: https://codeforces.com/blog/entry/88344
      2 
      3 [1494A - ABC String](/contest/1494/problem/A "Educational Codeforces Round 105 (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)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 bool solve() {
     19   string s;
     20   cin >> s;
     21   vector<int> d(3);
     22   int x = s[0] - 'A';
     23   int y = s.back() - 'A';
     24   if (x == y)
     25     return false;
     26   d[x] = 1; d[y] = -1;
     27   if (count(s.begin(), s.end(), 'A' + x) == s.length() / 2)
     28     d[3 ^ x ^ y] = -1;
     29   else
     30     d[3 ^ x ^ y] = 1;
     31   int bal = 0;
     32   for (char c : s) {
     33     bal += d[c - 'A'];
     34     if (bal < 0) return false;
     35   }
     36   return bal == 0;
     37 }
     38 
     39 int main() {
     40   int t; cin >> t;
     41   while (t--) {
     42     cout << (solve() ? "YES\n" : "NO\n");
     43   }
     44 }
     45 ```
     46 
     47 [1494B - Berland Crossword](/contest/1494/problem/B "Educational Codeforces Round 105 (Rated for Div. 2)")
     48 
     49 Idea: [Neon](/profile/Neon "Candidate Master Neon")
     50 
     51 **Tutorial**
     52 
     53 Tutorial is loading...
     54 
     55 **Solution (awoo)**
     56 
     57 ```
     58 for _ in range(int(input())):
     59     n, U, R, D, L = map(int, input().split())
     60     for mask in range(16):
     61         rU, rR, rD, rL = U, R, D, L
     62         if mask & 1:
     63             rU -= 1
     64             rL -= 1
     65         if mask & 2:
     66             rL -= 1
     67             rD -= 1
     68         if mask & 4:
     69             rD -= 1
     70             rR -= 1
     71         if mask & 8:
     72             rR -= 1
     73             rU -= 1
     74         if min(rU, rR, rD, rL) >= 0 and max(rU, rR, rD, rL) <= n - 2:
     75             print("YES")
     76             break
     77     else:
     78         print("NO")
     79 ```
     80 
     81 [1494C - 1D Sokoban](/contest/1494/problem/C "Educational Codeforces Round 105 (Rated for Div. 2)")
     82 
     83 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     84 
     85 **Tutorial**
     86 
     87 Tutorial is loading...
     88 
     89 **Solution (awoo)**
     90 
     91 ```
     92 #include <bits/stdc++.h>
     93 
     94 #define forn(i, n) for (int i = 0; i < int(n); i++)
     95 
     96 using namespace std;
     97 
     98 int calc(const vector<int> &a, const vector<int> &b){
     99     int n = a.size();
    100     int m = b.size();
    101     vector<int> su(n + 1);
    102     int r = m - 1;
    103     for (int i = n - 1; i >= 0; --i){
    104         su[i] = su[i + 1];
    105         while (r >= 0 && b[r] > a[i]) --r;
    106         if (r >= 0 && b[r] == a[i]) ++su[i];
    107     }
    108     int ans = 0;
    109     int j = 0;
    110     r = 0;
    111     forn(l, m){
    112         while (j < n && a[j] <= b[l] + j) ++j;
    113         while (r < m && b[r] - b[l] < j) ++r;
    114         ans = max(ans, r - l + su[j]);
    115     }
    116     return ans;
    117 }
    118 
    119 int main() {
    120     int t;
    121     scanf("%d", &t);
    122     forn(_, t){
    123         int n, m;
    124         scanf("%d%d", &n, &m);
    125         vector<int> a(n), b(m);
    126         forn(i, n) scanf("%d", &a[i]);
    127         forn(i, m) scanf("%d", &b[i]);
    128         vector<int> al, bl, ar, br;
    129         forn(i, n){
    130             if (a[i] < 0) al.push_back(-a[i]);
    131             else ar.push_back(a[i]);
    132         }
    133         forn(i, m){
    134             if (b[i] < 0) bl.push_back(-b[i]);
    135             else br.push_back(b[i]);
    136         }
    137         reverse(al.begin(), al.end());
    138         reverse(bl.begin(), bl.end());
    139         printf("%d\n", calc(al, bl) + calc(ar, br));
    140     }
    141     return 0;
    142 }
    143 ```
    144 
    145 [1494D - Dogeforces](/contest/1494/problem/D "Educational Codeforces Round 105 (Rated for Div. 2)")
    146 
    147 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    148 
    149 **Tutorial**
    150 
    151 Tutorial is loading...
    152 
    153 **Solution (Neon)**
    154 
    155 ```
    156 #include <bits/stdc++.h>
    157 
    158 using namespace std;
    159 
    160 #define sz(a) int((a).size())
    161 
    162 const int N = 505;
    163 
    164 int n;
    165 int a[N][N];
    166 int c[2 * N];
    167 vector<pair<int, int>> e;
    168 
    169 int calc(vector<int> ls) {
    170   if (sz(ls) == 1)
    171     return ls[0];
    172   
    173   int res = -1;
    174   for (int u : ls)
    175     res = max(res, a[ls[0]][u]);
    176   
    177   vector<vector<int>> ch;
    178   ch.push_back({ls[0]});
    179   for (int i = 1; i < sz(ls); ++i) {
    180     int v = ls[i];
    181     int group = -1;
    182     for (int j = 0; j < sz(ch); ++j) {
    183       if (a[v][ch[j][0]] != res) {
    184         group = j;
    185         break;
    186       }
    187     }
    188     if (group == -1) {
    189       group = sz(ch);
    190       ch.push_back({});
    191     }
    192     ch[group].push_back(v);
    193   }
    194   
    195   int v = n++;
    196   c[v] = res;
    197   for (int i = 0; i < sz(ch); ++i) {
    198     int u = calc(ch[i]);
    199     e.emplace_back(u, v);
    200   }
    201   return v;
    202 }
    203 
    204 int main() {
    205   cin >> n;
    206   for (int i = 0; i < n; ++i)
    207     for (int j = 0; j < n; ++j)
    208       cin >> a[i][j];
    209   for (int i = 0; i < n; ++i)
    210     c[i] = a[i][i];
    211   vector<int> ls(n);
    212   iota(ls.begin(), ls.end(), 0);
    213   int root = calc(ls);
    214   cout << n << '\n';
    215   for (int i = 0; i < n; ++i)
    216     cout << c[i] << ' ';
    217   cout << '\n' << root + 1 << '\n';
    218   for (auto it : e)
    219     cout << it.first + 1 << ' ' << it.second + 1 << '\n';
    220 }
    221 ```
    222 
    223 [1494E - A-Z Graph](/contest/1494/problem/E "Educational Codeforces Round 105 (Rated for Div. 2)")
    224 
    225 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    226 
    227 **Tutorial**
    228 
    229 Tutorial is loading...
    230 
    231 **Solution (adedalic)**
    232 
    233 ```
    234 #include<bits/stdc++.h>
    235 
    236 using namespace std;
    237 
    238 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    239 #define sz(a) int((a).size())
    240 
    241 #define x first
    242 #define y second
    243 
    244 typedef pair<int, int> pt;
    245 
    246 int main() {
    247     ios_base::sync_with_stdio(false);
    248     cin.tie(NULL);
    249     
    250     int n, m;
    251     cin >> n >> m;
    252     
    253     map<pt, int> allEdges;
    254     set<pt> difPairs, eqPairs;
    255     
    256     fore (q, 0, m) {
    257         char tp; cin >> tp;
    258         if (tp == '+') {
    259             int u, v;
    260             char c;
    261             cin >> u >> v >> c;
    262             
    263             if (allEdges.count({v, u})) {
    264                 if (allEdges[{v, u}] == c)
    265                     eqPairs.emplace(min(u, v), max(u, v));
    266                 else
    267                     difPairs.emplace(min(u, v), max(u, v));
    268             }
    269             allEdges[{u, v}] = c;
    270             
    271         } else if (tp == '-') {
    272             int u, v;
    273             cin >> u >> v;
    274             if (eqPairs.count({min(u, v), max(u, v)}))
    275                 eqPairs.erase({min(u, v), max(u, v)});
    276             if (difPairs.count({min(u, v), max(u, v)}))
    277                 difPairs.erase({min(u, v), max(u, v)});
    278             
    279             allEdges.erase({u, v});
    280         } else {
    281             int k;
    282             cin >> k;
    283             
    284             bool hasAns = !eqPairs.empty();
    285             if (k & 1)
    286                 hasAns |= !difPairs.empty();
    287             cout << (hasAns ? "YES" : "NO") << '\n';
    288         }
    289     }
    290     
    291     return 0;
    292 }
    293 ```
    294 
    295 [1494F - Delete The Edges](/contest/1494/problem/F "Educational Codeforces Round 105 (Rated for Div. 2)")
    296 
    297 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    298 
    299 **Tutorial**
    300 
    301 Tutorial is loading...
    302 
    303 **Solution (BledDest)**
    304 
    305 ```
    306 #include <bits/stdc++.h>
    307 
    308 using namespace std;
    309 
    310 const int N = 300043;
    311 
    312 int n, m;
    313 set<int> g[N];
    314 set<int> g2[N];
    315 
    316 vector<int> res;
    317 
    318 void euler(int x)
    319 {
    320     while(!g2[x].empty())
    321     {
    322         int y = *g2[x].begin();
    323         g2[x].erase(y);
    324         g2[y].erase(x);
    325         euler(y);
    326     }
    327     res.push_back(x);
    328 }
    329 
    330 bool check(int c)
    331 {
    332     for(int i = 1; i <= n; i++)
    333         g2[i] = g[i];
    334     res = vector<int>();
    335     euler(c);
    336     int curm = 0;
    337     for(int i = 1; i <= n; i++)
    338         curm += g[i].size();
    339     for(int i = 1; i <= n; i++)
    340         g2[i] = g[i];
    341     for(int i = 1; i < res.size(); i++)
    342     {
    343         int x = res[i - 1];
    344         int y = res[i];
    345         if(g2[x].count(y) != 1)
    346             return false;
    347         g2[x].erase(y);
    348         g2[y].erase(x);
    349     }
    350     return curm / 2 + 1 == res.size();    
    351 }
    352 
    353 int main()
    354 {
    355     scanf("%d %d", &n, &m);
    356     for(int i = 0; i < m; i++)
    357     {
    358         int x, y;
    359         scanf("%d %d", &x, &y);
    360         g[x].insert(y);
    361         g[y].insert(x);
    362     }
    363     for(int i = 1; i <= n; i++)
    364     {
    365         set<int> pr = g[i];
    366         set<int> diff;
    367         for(auto x : pr)
    368             if(g[x].size() % 2 == 1)
    369             {
    370                 g[i].erase(x);
    371                 g[x].erase(i);
    372                 diff.insert(x);
    373             }
    374         if(check(i))
    375         {
    376             res.push_back(-1);
    377             for(auto x : diff)
    378             {
    379                 res.push_back(x);
    380                 res.push_back(i);
    381             }
    382             printf("%d\n", res.size());
    383             for(auto x : res) printf("%d ", x);
    384             puts("");
    385             exit(0);
    386         }
    387         for(auto x : pr)
    388         {
    389             if(g[i].count(x))
    390             {
    391                 g[i].erase(x);
    392                 g[x].erase(i);
    393                 diff.insert(x);
    394             }
    395             else
    396             {
    397                 g[i].insert(x);
    398                 g[x].insert(i);
    399                 diff.erase(x);
    400             }
    401             if(check(i))
    402             {
    403                 res.push_back(-1);
    404                 for(auto x : diff)
    405                 {
    406                     res.push_back(x);
    407                     res.push_back(i);
    408                 }
    409                 printf("%d\n", res.size());
    410                 for(auto x : res) printf("%d ", x);
    411                 puts("");
    412                 exit(0);
    413             }
    414             if(g[i].count(x))
    415             {
    416                 g[i].erase(x);
    417                 g[x].erase(i);
    418                 diff.insert(x);
    419             }
    420             else
    421             {
    422                 g[i].insert(x);
    423                 g[x].insert(i);
    424                 diff.erase(x);
    425             }
    426         }
    427         for(auto x : diff)
    428         {
    429             g[i].insert(x);
    430             g[x].insert(i);
    431         }
    432     }
    433     puts("0");
    434 }
    435 ```