codeforces-scrape

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

1554.md (7762B)


      1 Source: https://codeforces.com/blog/entry/93321
      2 
      3 The problem names are based on my favorite characters out there. Yes, [1554E - You](/contest/1554/problem/E "Codeforces Round 735 (Div. 2)") are my most favorite character UwU.
      4 
      5 I have tried to make the editorials as interactive as possible. Enjoy.
      6 
      7 Tutorial is loading...
      8 
      9 **Code(C++)**
     10 
     11 ```
     12 #include<bits/stdc++.h>
     13 using namespace std;
     14 
     15 int32_t main() {
     16   ios_base::sync_with_stdio(0);
     17   cin.tie(0);
     18   int t; cin >> t;
     19   while (t--) {
     20     int n; cin >> n;
     21     vector<int> a(n);
     22     for (auto &x: a) {
     23       cin >> x;
     24     }
     25     long long ans = 0;
     26     for (int i = 1; i < n; i++) {
     27       ans = max(ans, 1LL * a[i] * a[i - 1]);
     28     }
     29     cout << ans << '\n';
     30   }
     31   return 0;
     32 }
     33 ```
     34 
     35 **Code(Python)**
     36 
     37 ```
     38 import sys
     39 input = sys.stdin.buffer.readline
     40 t = int(input())
     41 for _ in range(t):
     42   n = int(input())
     43   a = list(map(int, input().split()))
     44   ans = 0
     45   for i in range(n - 1):
     46     ans = max(ans, a[i] * a[i + 1])
     47   print(ans)
     48 ```
     49 
     50 Tutorial is loading...
     51 
     52 **Code(C++)**
     53 
     54 ```
     55 #include<bits/stdc++.h>
     56 using namespace std;
     57 
     58 int32_t main() {
     59   ios_base::sync_with_stdio(0);
     60   cin.tie(0);
     61   int t; cin >> t;
     62   while (t--) {
     63     int n, k; cin >> n >> k;
     64     vector<int> a(n + 1);
     65     for (int i = 1; i <= n; i++) {
     66       cin >> a[i];
     67     }
     68     long long ans = -1e12;
     69     int l = max(1, n - 2 * k);
     70     for (int i = l; i <= n; i++) {
     71       for (int j = i + 1; j <= n; j++) {
     72         ans = max(ans, 1LL * i * j - 1LL * k * (a[i] | a[j]));
     73       }
     74     }
     75     cout << ans << '\n';
     76   }
     77   return 0;
     78 }
     79 ```
     80 
     81 **Code(Python)**
     82 
     83 ```
     84 import sys
     85 input = sys.stdin.buffer.readline
     86 t = int(input())
     87 for _ in range(t):
     88   n, k = map(int, input().split())
     89   a = list(map(int, input().split()))
     90   l = max(0, n - 2 * k - 1)
     91   ans = -1e12
     92   for i in range(l, n):
     93     for j in range(i + 1, n):
     94       ans = max(ans, (i + 1) * (j + 1) - k * (a[i] | a[j]))
     95   print(ans)
     96 ```
     97 
     98 Tutorial is loading...
     99 
    100 **Code(C++)**
    101 
    102 ```
    103 #include<bits/stdc++.h>
    104 using namespace std;
    105 
    106 int32_t main() {
    107   ios_base::sync_with_stdio(0);
    108   cin.tie(0);
    109   int t; cin >> t;
    110   while (t--) {
    111     int n, m; cin >> n >> m;
    112     ++m;
    113     int ans = 0;
    114     for (int k = 30; k >= 0 and n < m; k--) {
    115       if ((n >> k & 1) == (m >> k & 1)) continue;
    116       if (m >> k & 1) ans |= 1 << k, n |= 1 << k;
    117     }
    118     cout << ans << '\n';
    119   }
    120   return 0;
    121 }
    122 ```
    123 
    124 **Code(Python)**
    125 
    126 ```
    127 import sys
    128 input = sys.stdin.buffer.readline
    129 t = int(input())
    130 for _ in range(t):
    131   n, m = map(int, input().split())
    132   m += 1
    133   ans = 0
    134   for k in range(30, -1, -1):
    135     if (n >= m): break
    136     if ((n >> k & 1) == (m >> k & 1)): continue
    137     if (m >> k & 1):
    138       ans |= 1 << k
    139       n |= 1 << k
    140   print(ans)
    141 ```
    142 
    143 Tutorial is loading...
    144 
    145 **Code(C++)**
    146 
    147 ```
    148 #include<bits/stdc++.h>
    149 using namespace std;
    150 
    151 int32_t main() {
    152   ios_base::sync_with_stdio(0);
    153   cin.tie(0);
    154   int t; cin >> t;
    155   while (t--) {
    156     int n; cin >> n;
    157     if (n == 1) {
    158       cout << "a\n";
    159     }
    160     else {
    161       cout << string(n / 2, 'a') + (n & 1 ? "bc" : "b") + string(n / 2 - 1, 'a') << '\n';
    162     }
    163   }
    164   return 0;
    165 }
    166 ```
    167 
    168 **Code(Python)**
    169 
    170 ```
    171 t = int(input())
    172 for _ in range(t):
    173   n = int(input())
    174   if (n == 1):
    175     print('a')
    176   else:
    177     s = 'a' * (n // 2)
    178     if (n & 1):
    179       s += 'bc'
    180     else:
    181       s += 'b'
    182     s += 'a' * (n // 2 - 1)
    183     print(s)
    184 ```
    185 
    186 If you are wondering(as you always do 。^‿^。) about the checker:
    187 
    188 **Checker**
    189 
    190 Write a suffix automata and check if every node occurs an odd number of times.
    191 
    192 **Code**
    193 
    194 ```
    195 #include<bits/stdc++.h>
    196 #include "testlib.h"
    197 using namespace std;
    198 
    199 // len -> largest string length of the corresponding endpos-equivalent class
    200 // link -> longest suffix that is another endpos-equivalent class.
    201 // firstpos -> 1 indexed end position of the first occurrence of the largest string of that node
    202 // minlen(v) -> smallest string of node v = len(link(v)) + 1
    203 // terminal nodes -> store the suffixes
    204 struct SuffixAutomaton {
    205   struct node {
    206     int len, link, firstpos;
    207     map<char, int> nxt;
    208   };
    209   int sz, last;
    210   vector<node> t;
    211   vector<int> terminal;
    212   vector<int> dp;
    213   vector<vector<int>> g;
    214   SuffixAutomaton() {}
    215   SuffixAutomaton(int n) {
    216     t.resize(2 * n); terminal.resize(2 * n, 0);
    217     dp.resize(2 * n, -1); sz = 1; last = 0;
    218     g.resize(2 * n);
    219     t[0].len = 0; t[0].link = -1; t[0].firstpos = 0;
    220   }
    221   void extend(char c) {
    222     int p = last;
    223     int cur = sz++;
    224     t[cur].len = t[last].len + 1;
    225     t[cur].firstpos = t[cur].len;
    226     p = last;
    227     while (p != -1 && !t[p].nxt.count(c)) {
    228       t[p].nxt[c] = cur;
    229       p = t[p].link;
    230     }
    231     if (p == -1) t[cur].link = 0;
    232     else {
    233       int q = t[p].nxt[c];
    234       if (t[p].len + 1 == t[q].len) t[cur].link = q;
    235       else {
    236         int clone = sz++;
    237         t[clone] = t[q];
    238         t[clone].len = t[p].len + 1;
    239         while (p != -1 && t[p].nxt[c] == q) {
    240           t[p].nxt[c] = clone;
    241           p = t[p].link;
    242         }
    243         t[q].link = t[cur].link = clone;
    244       }
    245     }
    246     last = cur;
    247   }
    248   void build_tree() {
    249     for (int i = 1; i < sz; i++) g[t[i].link].push_back(i);
    250   }
    251   void build(string &s) {
    252     for (auto x: s) {
    253       extend(x);
    254       terminal[last] = 1;
    255     }
    256     build_tree();
    257   }
    258   int cnt(int i) { // number of times i-th node occurs in the string
    259     if (dp[i] != -1) return dp[i];
    260     int ret = terminal[i];
    261     for (auto &x: g[i]) ret += cnt(x);
    262     return dp[i] = ret;
    263   }
    264 };
    265 pair<int, int> ok(string s) {
    266   int n = s.size();
    267   SuffixAutomaton sa(n);
    268   sa.build(s);
    269   for (int i = 1; i < sa.sz; i++) {
    270     if (sa.cnt(i) % 2 == 0) {
    271       return {sa.t[i].firstpos - sa.t[i].len, sa.t[i].firstpos - 1};
    272     }
    273   }
    274   return {-1, -1};
    275 }
    276 int main(int argc, char* argv[]) {
    277   registerTestlibCmd(argc, argv);
    278   int t = inf.readInt();
    279   inf.readEoln();
    280   for (int test = 1; test <= t; test++) {
    281     setTestCase(test);
    282     int n = inf.readInt();
    283     inf.readEoln();
    284     string s = ouf.readToken();
    285     if (s.size() != n) {
    286       quitf(_wa, "the length of s should be exactly %d", n);
    287     }
    288     for (int i = 0; i < n; i++) {
    289       if (!(s[i] >= 'a' and s[i] <= 'z')) {
    290         quitf(_wa, "s contains %c which is not an English lowercase character", s[i]);
    291       }
    292     }
    293     auto p = ok(s);
    294     if (p.first != -1) {
    295       quitf(_wa, "the substring s[%d, %d] (0-indexed) occurs even number of times in s :\"(", p.first, p.second);
    296     }
    297   }
    298   quitf(_ok, "you are the best problem solver ever UwU");
    299   return 0;
    300 }
    301 ```
    302 
    303 Tutorial is loading...
    304 
    305 **Code(C++)**
    306 
    307 ```
    308 #include<bits/stdc++.h>
    309 using namespace std;
    310 
    311 const int N = 1e5 + 9, mod = 998244353;
    312 
    313 vector<int> g[N];
    314 int dp[N], d, ok, ans[N];
    315 void dfs(int u, int p = 0) {
    316   if (!ok) return;
    317   for (auto v: g[u]) {
    318     if (v ^ p) {
    319       dfs(v, u);
    320     }
    321   }
    322   if (dp[u] % d != 0) {
    323     if (p) {
    324       dp[u]++;
    325     }
    326     if (dp[u] % d != 0) {
    327       ok = 0;
    328       return;
    329     }
    330   }
    331   else {
    332     dp[p]++;
    333   }
    334 }
    335 int32_t main() {
    336   ios_base::sync_with_stdio(0);
    337   cin.tie(0);
    338   int t; cin >> t;
    339   while (t--) {
    340     int n; cin >> n;
    341     for (int i = 1; i < n; i++) {
    342       int u, v; cin >> u >> v;
    343       g[u].push_back(v);
    344       g[v].push_back(u);
    345     }
    346     for (int i = 1; i <= n; i++) {
    347       ans[i] = 0;
    348     }
    349     ans[1] = 1;
    350     for (int k = 1; k <= n - 1; k++) {
    351       ans[1] = (ans[1] + ans[1]) % mod;
    352     }
    353     for (d = 2; d <= n - 1; d++) {
    354       if ((n - 1) % d == 0) {
    355         ok = 1;
    356         dfs(1);
    357         ans[d] = ok;
    358         for (int i = 0; i <= n; i++) {
    359           dp[i] = 0;
    360         }
    361       }
    362     }
    363     for (int i = n; i >= 1; i--) {
    364       for (int j = i + i; j <= n; j += i) {
    365         ans[i] = (ans[i] - ans[j] + mod) % mod;
    366       }
    367     }
    368     for (int i = 1; i <= n; i++) {
    369       if (i > 1) cout << ' ';
    370       cout << ans[i];
    371     }
    372     cout << '\n';
    373     for (int i = 1; i <= n; i++) {
    374       g[i].clear();
    375     }
    376   }
    377   return 0;
    378 }
    379 ```