codeforces-scrape

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

1467.md (6889B)


      1 Source: https://codeforces.com/blog/entry/86566
      2 
      3 Many thanks to [infinitepro](/profile/infinitepro "Expert infinitepro"), [BledDest](/profile/BledDest "International Grandmaster BledDest") and [alimq](/profile/alimq "Candidate Master alimq") for helping me write the editorials.
      4 
      5 Tutorial is loading...
      6 
      7 **Solution**
      8 
      9 ```
     10 #include <bits/stdc++.h>
     11 using namespace std;
     12 #define int long long
     13 
     14 int solveTestCase() {
     15     int n;
     16     cin >> n;
     17 
     18     string s = "989";
     19     if (n <= 3)
     20         return cout << s.substr(0, n) << "\n", 0;
     21 
     22     cout << s;
     23     for (int i = 3; i < n; i++)
     24         cout << (i - 3) % 10;
     25     cout << "\n";
     26 }
     27 
     28 signed main() {
     29     ios::sync_with_stdio(false);
     30     cin.tie(nullptr);
     31     cout.tie(nullptr);
     32 
     33     int t = 1;
     34     cin >> t;
     35     while (t--)
     36         solveTestCase();
     37 
     38 }
     39 ```
     40 
     41 Tutorial is loading...
     42 
     43 **Solution**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47 using namespace std;
     48 #define int long long
     49 
     50 const int N = 3e5;
     51 int a[N], n;
     52 
     53 int isValley(int i) {
     54     return (i > 0 && i < n - 1 && a[i] < a[i - 1] && a[i] < a[i + 1]);
     55 }
     56 
     57 int isHill(int i) {
     58     return (i > 0 && i < n - 1 && a[i] > a[i - 1] && a[i] > a[i + 1]);
     59 }
     60 
     61 int solveTestCase() {
     62     cin >> n;
     63     for (int i = 0; i < n; i++)
     64         cin >> a[i];
     65 
     66     int is[n] = {};
     67     int s = 0;
     68     for (int i = 1; i < n - 1; i++) {
     69         if (isHill(i) || isValley(i))
     70             is[i] = 1, s++;
     71     }
     72 
     73     int ans = s;
     74     for (int i = 1; i < n - 1; i++) {
     75         int temp = a[i];
     76         a[i] = a[i - 1];
     77         ans = min(ans, s - is[i - 1] - is[i] - is[i + 1] + isHill(i - 1) + isValley(i - 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1));
     78         a[i] = a[i + 1];
     79         ans = min(ans, s - is[i - 1] - is[i] - is[i + 1] + isHill(i - 1) + isValley(i - 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1));
     80         a[i] = temp;
     81     }
     82 
     83     cout << ans << "\n";
     84 }
     85 
     86 signed main() {
     87     ios::sync_with_stdio(false);
     88     cin.tie(nullptr);
     89     cout.tie(nullptr);
     90 
     91     int t = 1;
     92     cin >> t;
     93     while (t--)
     94         solveTestCase();
     95 }
     96 ```
     97 
     98 Tutorial is loading...
     99 
    100 **Solution**
    101 
    102 ```
    103 #include <bits/stdc++.h>
    104 using namespace std;
    105 #define int long long
    106 
    107 const int N = 3e5;
    108 vector<vector<int>> a(3, vector<int>());
    109 vector<int> n(3, 0);
    110 
    111 int calc() {
    112     int ans = 0, m1 = a[1][0], m2 = a[2][0], s1 = 0, s2 = 0;
    113     for (int i : a[0]) ans += i;
    114     for (int i = 1; i < n[1]; i++) s1 += a[1][i];
    115     for (int i = 1; i < n[2]; i++) s2 += a[2][i];
    116 
    117     ans += max({s2 - m1 + s1 - m2, m2 + s2 - m1 - s1, m1 + s1 - m2 - s2});
    118     return ans;
    119 }
    120 
    121 int solveTestCase() {
    122     cin >> n[0] >> n[1] >> n[2];
    123     a[0].resize(n[0]);
    124     a[1].resize(n[1]);
    125     a[2].resize(n[2]);
    126 
    127     for (int i = 0; i < 3; i++) {
    128         for (int j = 0; j < n[i]; j++)
    129             cin >> a[i][j];
    130         sort(a[i].begin(), a[i].end());
    131     }
    132 
    133     int ans = -1e18;
    134     ans = max(ans, calc());
    135 
    136     swap(a[0], a[1]), swap(n[0], n[1]);
    137     ans = max(ans, calc());
    138 
    139     swap(a[0], a[2]), swap(n[0], n[2]);
    140     ans = max(ans, calc());
    141 
    142     cout << ans;
    143 }
    144 
    145 signed main() {
    146     ios::sync_with_stdio(false);
    147     cin.tie(nullptr);
    148     cout.tie(nullptr);
    149 
    150     int t = 1;
    151     //cin >> t;
    152     while (t--)
    153         solveTestCase();
    154 }
    155 ```
    156 
    157 Tutorial is loading...
    158 
    159 **Solution**
    160 
    161 ```
    162 #include <bits/stdc++.h>
    163 using namespace std;
    164 #define int long long
    165 
    166 const int N = 5005, mod = 1e9 + 7;
    167 int dp[N][N], cnt[N], a[N], q, n, k;
    168 
    169 void pre() {
    170     for (int i = 0; i < n; i++)
    171         dp[i][0] = 1;
    172         
    173     for (int j = 1; j < N; j++) {
    174         dp[0][j] = dp[1][j - 1];
    175         for (int i = 1; i < n - 1; i++)
    176             dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1]) % mod;
    177         dp[n - 1][j] = dp[n - 2][j - 1];
    178     }
    179     
    180     for (int i = 0; i < n; i++) {
    181         for (int j = 0; j <= k; j++)
    182             cnt[i] += dp[i][j] * dp[i][k - j], cnt[i] %= mod;
    183     }
    184 }
    185 
    186 void solveTestCase() {
    187     int ans = 0;
    188     for (int i = 0; i < n; i++)
    189         cin >> a[i], ans += a[i] * cnt[i], ans %= mod;
    190     
    191     while (q--) {
    192         int i, x;
    193         cin >> i >> x;
    194         i--;
    195         
    196         ans -= (a[i] * cnt[i]) % mod, ans += mod, ans %= mod;
    197         
    198         a[i] = x;
    199         ans += (a[i] * cnt[i]), ans %= mod;
    200         cout << ans << "\n";
    201     }
    202 }
    203 
    204 signed main() {
    205     ios::sync_with_stdio(false);
    206     cin.tie(nullptr);
    207     cout.tie(nullptr);
    208     
    209     cin >> n >> k >> q;
    210     pre();
    211     
    212     int t = 1;
    213     //cin >> t;
    214     while (t--)
    215         solveTestCase();
    216 }
    217 ```
    218 
    219 Tutorial is loading...
    220 
    221 **Solution**
    222 
    223 ```
    224 #include <bits/stdc++.h>
    225 using namespace std;
    226 #define int long long
    227 
    228 const int N = 5e5;
    229 vector<int> adj[N];
    230 int a[N], par[N], n;
    231 
    232 map<int, vector<int>> v, times;
    233 int euler[N * 2 - 1], tin[N], tout[N], c = 0;
    234 
    235 set<pair<int, int>> g;
    236 int dp[N], ans;
    237 
    238 void dfs(int v, int p = -1) {
    239     par[v] = p;
    240     tin[v] = c;
    241     euler[c++] = v;
    242 
    243     for (int i : adj[v]) {
    244         if (i == p)
    245             continue;
    246         dfs(i, v);
    247         euler[c++] = v;
    248     }
    249 
    250     tout[v] = c - 1;
    251 }
    252 
    253 void examine(int v) {
    254     int sum = 0;
    255 
    256     for (int i : adj[v]) {
    257         if (i == par[v])
    258             continue;
    259 
    260         int count = upper_bound(times[a[v]].begin(), times[a[v]].end(), tout[i]) - lower_bound(times[a[v]].begin(), times[a[v]].end(), tin[i]);
    261         if (count > 0)
    262             g.insert({v, i});
    263         sum += count;
    264     }
    265 
    266     sum = times[a[v]].size() - sum - 1;
    267     if (sum)
    268         g.insert({v, par[v]});
    269 }
    270 
    271 int setup(int v) {
    272     for (int i : adj[v]) {
    273         if (i != par[v])
    274             dp[v] += setup(i);
    275     }
    276     return dp[v] + g.count({v, par[v]});
    277 }
    278 
    279 void reroot(int v) {
    280     if (dp[v] == g.size())
    281         ans++;
    282 
    283     for (int i : adj[v]) {
    284         if (i == par[v])
    285             continue;
    286 
    287         dp[v] -= dp[i];
    288         dp[v] -= g.count({i, v});
    289         dp[i] += dp[v];
    290         dp[i] += g.count({v, i});
    291 
    292         reroot(i);
    293 
    294         dp[i] -= g.count({v, i});
    295         dp[i] -= dp[v];
    296         dp[v] += g.count({i, v});
    297         dp[v] += dp[i];
    298     }
    299 }
    300 
    301 int solveTestCase() {
    302     cin >> n;
    303     for (int i = 0; i < n; i++)
    304         cin >> a[i];
    305 
    306     for (int i = 0; i < n - 1; i++) {
    307         int u, v;
    308         cin >> u >> v;
    309         u--, v--;
    310         adj[u].push_back(v);
    311         adj[v].push_back(u);
    312     }
    313 
    314     dfs(0);
    315     for (int i = 0; i < n; i++)
    316         v[a[i]].push_back(i);
    317 
    318     for (auto i : v) {
    319         if (i.second.size() == 1)
    320             continue;
    321 
    322         for (int j : i.second)
    323             times[i.first].push_back(tin[j]);
    324         sort(times[i.first].begin(), times[i.first].end());
    325         for (int j : i.second)
    326             examine(j);
    327     }
    328 
    329     setup(0);
    330     reroot(0);
    331 
    332     cout << ans;
    333 }
    334 
    335 signed main() {
    336     ios::sync_with_stdio(false);
    337     cin.tie(nullptr);
    338     cout.tie(nullptr);
    339 
    340     int t = 1;
    341     //cin >> t;
    342     while (t--)
    343         solveTestCase();
    344 }
    345 ```
    346 
    347 UPD: Also, have a look at [this](https://codeforces.com/blog/entry/86566?#comment-746573) comment for an explanation of the sample test case of C.