codeforces-scrape

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

743.md (3855B)


      1 Source: https://codeforces.com/blog/entry/49049
      2 
      3 Tutorial is loading...
      4 
      5 **Setter's code**
      6 
      7 ```
      8 int n, a, b;
      9 string s;
     10 cin >> n >> a >> b >> s;
     11 
     12 a--, b--;
     13 
     14 cout << ((s[a] - '0') ^ (s[b] - '0'));
     15 ```
     16 
     17 Tutorial is loading...
     18 
     19 **Setter's code**
     20 
     21 ```
     22 int go(ll l, ll r, ll need, int alphSize)
     23 {
     24     ll m = l + (r - l) / 2LL;
     25     if (need < m)
     26         return go(l, m - 1, need, alphSize - 1);
     27     else if (need > m)
     28         return go(m + 1, r, need, alphSize - 1);
     29     else
     30         return alphSize;
     31 }
     32 
     33 void solveABig()
     34 {
     35     int n;
     36     ll k;
     37 
     38     cin >> n >> k;
     39     ll sz = 1;
     40     for (int i = 1; i < n; i++)
     41         sz = sz * 2LL + 1LL;
     42     
     43     cout << go(1, sz, k, n);
     44 }
     45 ```
     46 
     47 Tutorial is loading...
     48 
     49 **Setter's code**
     50 
     51 ```
     52 int n;
     53 cin >> n;
     54 if (n == 1)
     55 	cout << -1 << endl;
     56 else
     57 	cout << n << ' ' << n + 1 << ' ' << n * (n + 1) << endl;
     58 ```
     59 
     60 Tutorial is loading...
     61 
     62 **Setter's code**
     63 
     64 ```
     65 int a[maxn];
     66 vector<int> g[maxn];
     67 
     68 ll sum_subTree[maxn], mx_subTree[maxn];
     69 
     70 void dfs1(int v, int p) {
     71     sum_subTree[v] = a[v];
     72     mx_subTree[v] = -llinf;
     73     for (int i = 0; i < g[v].size(); i++) {
     74         int to = g[v][i];
     75         if (to == p)
     76             continue;
     77         dfs1(to, v);
     78         sum_subTree[v] += sum_subTree[to];
     79         mx_subTree[v] = max(mx_subTree[v], mx_subTree[to]);
     80     }
     81     mx_subTree[v] = max(mx_subTree[v], sum_subTree[v]);
     82 }
     83 
     84 ll ans = -llinf;
     85 
     86 void dfs2(int v, int p, ll out) {
     87     if (out != -llinf)
     88     ans = max(ans, sum_subTree[v] + out);
     89 
     90     vector<pair<ll, int> > miniset;
     91     for (int i = 0; i < g[v].size(); i++) {
     92         int to = g[v][i];
     93         if (to == p)
     94             continue;
     95         miniset.pb(mp(mx_subTree[to], to));
     96         sort(miniset.rbegin(), miniset.rend());
     97         if (miniset.size() == 3)
     98             miniset.pop_back();
     99     }
    100     miniset.pb(mp(-llinf, -1));
    101     for (int i = 0; i < g[v].size(); i++) {
    102         int to = g[v][i];
    103         if (to == p)
    104             continue;
    105         ll cur = miniset[0].s == to ? miniset[1].f : miniset[0].f;
    106         dfs2(to, v, max(out, cur));
    107     }
    108 }
    109 
    110 int main() {
    111     for (int i = 0; i + 1 < n; i++) {
    112         int u, v;
    113         read(u, v);
    114         u--, v--;
    115         g[u].pb(v);
    116         g[v].pb(u);
    117     }
    118 
    119     dfs1(0, -1);
    120     dfs2(0, -1, -llinf);
    121     cout << ((ans == -llinf) ? ("Impossible") : to_string(ans));
    122     return 0;
    123 }
    124 ```
    125 
    126 Tutorial is loading...
    127 
    128 **Setter's code**
    129 
    130 ```
    131 int can(int len) {
    132     for (int i = 0; i < 8; i++)
    133         cur[i] = 0;
    134     for (int i = 0; i <= n; i++)
    135         for (int j = 0; j < (1 << 8); j++)
    136             dp[i][j] = -inf;
    137     dp[0][0] = 0;
    138     for (int i = 0; i < n; i++) {
    139         for (int j = 0; j < (1 << 8); j++) {
    140             if (dp[i][j] == -inf)
    141                 continue;
    142             for (int k = 0; k < 8; k++) {
    143                 if (j & (1 << k))
    144                     continue;
    145                 int it = cur[k] + len - 1;
    146                 if (it >= in[k].size())
    147                     continue;
    148                 amax(dp[in[k][it] + 1][j | (1 << k)], dp[i][j]);
    149                     
    150                 it++;
    151                 if (it >= in[k].size())
    152                     continue;
    153                 amax(dp[in[k][it] + 1][j | (1 << k)], dp[i][j] + 1);
    154             }
    155         }
    156         cur[a[i]]++;
    157     }
    158 
    159     int ans = -inf;
    160     for (int i = 0; i <= n; i++)
    161         ans = max(ans, dp[i][(1 << 8) - 1]);
    162     if (ans == -inf)
    163         return -1;
    164 
    165     return ans * (len + 1) + (8 - ans) * len;
    166 }
    167 
    168 int main() {
    169     for (int i = 0; i < n; i++) {
    170         in[a[i]].push_back(i);
    171     }
    172 
    173     int l = 1, r = n / 8;
    174     while (r - l > 1) {
    175         int m = (l + r) >> 1;
    176         if (can(m) != -1)
    177             l = m;
    178         else
    179             r = m;
    180     }
    181     int ans = max(can(l), can(r));
    182     if (ans == -1) {
    183         ans = 0;
    184         for (int i = 0; i < 8; i++)
    185             if (!in[i].empty())
    186                 ans++;
    187     }
    188     cout << ans;
    189     return 0;
    190 }
    191 ```