codeforces-scrape

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

2040.md (16470B)


      1 Source: https://codeforces.com/blog/entry/137074
      2 
      3 [2040A - Game of Division](/contest/2040/problem/A "Codeforces Round 992 (Div. 2)")
      4 
      5 **Editorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution C++**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13  
     14 using namespace std;
     15  
     16 int main() {
     17     int tt;
     18     cin >> tt;
     19     while (tt--) {
     20         int n, k;
     21         cin >> n >> k;
     22         vector < vector <int> > b(k);
     23         for (int i = 1; i <= n; i++) {
     24             int x;
     25             cin >> x;
     26             b[x % k].push_back(i);
     27         }
     28         int res = -1;
     29         for (int i = 0; i < k; i++) {
     30             if ((int)b[i].size() == 1) {
     31                 res = b[i][0];
     32                 break;
     33             }
     34         }
     35         if (res == -1) {
     36             cout << "NO" << endl;
     37         }
     38         else {
     39             cout << "YES" << endl << res << endl;
     40         }
     41     }
     42     
     43     return 0;
     44 }
     45 ```
     46 
     47 **Solution Python**
     48 
     49 ```
     50 for _ in range(int(input())):
     51     n, k = map(int, input().split())
     52     a = list(map(int, input().split()))
     53     b = [[] for _ in range(k)]
     54     for i in range(0, n):
     55         x = a[i]
     56         b[x % k].append(i + 1)
     57     res = -1
     58     for i in range(k):
     59         if len(b[i]) == 1:
     60             res = b[i][0]
     61             break
     62     if res == -1:
     63         print("NO")
     64     else:
     65         print("YES\n" + str(res))
     66 ```
     67 
     68 [2040B - Paint a Strip](/contest/2040/problem/B "Codeforces Round 992 (Div. 2)")
     69 
     70 **Editorial**
     71 
     72 Tutorial is loading...
     73 
     74 **Solution C++**
     75 
     76 ```
     77 #include <bits/stdc++.h>
     78  
     79 using namespace std;
     80  
     81 int main() {
     82     int tt;
     83     cin >> tt;
     84     while (tt--) {
     85         int n;
     86         cin >> n;
     87         for (int ans = 1, cur = 1; ; ans++, cur = cur * 2 + 2) {
     88             if (cur >= n) {
     89                 cout << ans << '\n';
     90                 break;
     91             }
     92         }
     93     }
     94     
     95     return 0;
     96 }
     97 ```
     98 
     99 **Solution Python**
    100 
    101 ```
    102 tt = int(input())
    103 for _ in range(tt):
    104     n = int(input())
    105     ans = 1
    106     cur = 1
    107     while True:
    108         if cur >= n:
    109             print(ans)
    110             break
    111         ans += 1
    112         cur = cur * 2 + 2
    113 ```
    114 
    115 **Notes**
    116 
    117 At some point in the development of this problem, the following alternative statement appeared: we need to minimize the total number of operations of both types. How to solve this problem?
    118 
    119 [2040C - Ordered Permutations](/contest/2040/problem/C "Codeforces Round 992 (Div. 2)")
    120 
    121 **Editorial**
    122 
    123 Tutorial is loading...
    124 
    125 **Solution C++**
    126 
    127 ```
    128 #include <bits/stdc++.h>
    129  
    130 using namespace std;
    131  
    132 int main() {
    133     int tt;
    134     cin >> tt;
    135     while (tt--) {
    136         int n;
    137         long long k;
    138         cin >> n >> k;
    139         vector <int> a, b;
    140         
    141         if (n <= 60 && (1ll << (n - 1)) < k) {
    142             cout << -1 << endl;
    143             continue;
    144         }
    145         k--;
    146         vector <int> d;
    147         while (k) {
    148             d.push_back(k % 2);
    149             k /= 2;
    150         }
    151         while (d.size() < n - 1) d.push_back(0);
    152         
    153         for (int i = n - 2, j = 1; i >= 0; i--, j++) {
    154             if (d[i] == 0) a.push_back(j);
    155             else b.push_back(j);
    156         }
    157         
    158         reverse(b.begin(), b.end());
    159         for (int i : a) cout << i << ' ';
    160         cout << n << ' ';
    161         for (int i : b) cout << i << ' ';
    162         cout << endl;
    163     }
    164  
    165     return 0;
    166 }
    167 ```
    168 
    169 **Solution Python**
    170 
    171 ```
    172 tt = int(input())
    173 for _ in range(tt):
    174     n, k = map(int, input().split())
    175     a, b = [], []
    176  
    177     if n <= 60 and (1 << (n - 1)) < k:
    178         print(-1)
    179         continue
    180     k -= 1
    181     d = []
    182     while k:
    183         d.append(k % 2)
    184         k //= 2
    185     while len(d) < n - 1:
    186         d.append(0)
    187  
    188     a, b = [], []
    189     j = 1
    190     for i in range(n - 2, -1, -1):
    191         if d[i] == 0:
    192             a.append(j)
    193         else:
    194             b.append(j)
    195         j += 1
    196  
    197     b.reverse()
    198     print(*a, n, *b)
    199 ```
    200 
    201 [2040D - Non Prime Tree](/contest/2040/problem/D "Codeforces Round 992 (Div. 2)")
    202 
    203 **Editorial**
    204 
    205 Tutorial is loading...
    206 
    207 **Solution 1**
    208 
    209 ```
    210 #include <bits/stdc++.h>
    211  
    212 using namespace std;
    213  
    214 int main() {
    215     int tt;
    216     cin >> tt;
    217     while (tt--) {
    218         int n;
    219         cin >> n;
    220         vector < vector <int> > g(n);
    221         for (int i = 0; i < n - 1; i++) {
    222             int a, b;
    223             cin >> a >> b;
    224             a--, b--;
    225             g[a].push_back(b);
    226             g[b].push_back(a);
    227         }
    228         
    229         vector <int> res(n);
    230         int lst = 1;
    231         res[0] = lst;
    232         
    233         function <void(int, int)> dfs = [&](int v, int p) {
    234             for (int to : g[v]) {
    235                 if (to == p) continue;
    236                 res[to] = lst + 1;
    237                 while (res[to] != res[v] + 1 && 
    238                       (res[to] % 2 != res[v] % 2 || res[to] - res[v] == 2)) {
    239                     res[to]++;   
    240                 }
    241                 lst = res[to];
    242                 dfs(to, v);
    243             }
    244         };
    245         
    246         dfs(0, 0);
    247         for (int i : res) cout << i << ' ';
    248         cout << endl;
    249     }
    250     
    251     return 0;
    252 }
    253 ```
    254 
    255 **Solution 2 (zap4eg)**
    256 
    257 ```
    258 #include <bits/stdc++.h>
    259 using namespace std;
    260  
    261 using ll = long long;
    262  
    263 void dfs(int v, vector<vector<int>>& g, vector<int>& h, int p) {
    264     h[v] = h[p] + 1;
    265     for (int u : g[v]) {
    266         if (u == p)
    267             continue;
    268         dfs(u, g, h, v);
    269     }
    270 }
    271  
    272 int main() {
    273     ios::sync_with_stdio(0);
    274     cin.tie(0);
    275     cout.tie(0);
    276     
    277     int tt;
    278     cin >> tt;
    279     while (tt--) {
    280         int n;
    281         cin >> n;
    282         vector<vector<int>> g(n);
    283         for (int i = 0; i < n - 1; i++) {
    284             int u, v;
    285             cin >> u >> v;
    286             u--, v--;
    287             g[u].push_back(v);
    288             g[v].push_back(u);
    289         }
    290         vector<int> h(n);
    291         dfs(0, g, h, 0);
    292         vector<vector<int>> hs(n + 1);
    293         for (int i = 0; i < n; i++)
    294             hs[h[i]].push_back(i);
    295         int l = 2, r = 2 * n;
    296         int cur = 0;
    297         vector<int> ans(n);
    298         for (int i = 1; i <= n; i++) {
    299            if (cur) {
    300                for (int v : hs[i]) {
    301                     ans[v] = r;
    302                     r -= 2;
    303                }
    304            } 
    305            else {
    306                for (int v : hs[i]) {
    307                     ans[v] = l;
    308                     l += 2;
    309                }
    310            }
    311            cur ^= 1;
    312         }
    313         bool found = false;
    314         for (int i = 0; i < n; i++) {
    315             for (int v : g[i]) {
    316                 if (h[v] < h[i])
    317                     continue;
    318                 if (abs(ans[v] - ans[i]) == 2) {
    319                     ans[v] = ans[i] - 1;
    320                     found = true;
    321                     break;
    322                 }
    323             }
    324             if (found)
    325                 break;
    326         }
    327         for (int i = 0; i < n; i++)
    328             cout << ans[i] << ' ';
    329         cout << '\n';
    330     }
    331     
    332     return 0;
    333 }
    334 ```
    335 
    336 **Notes**
    337 
    338 There are many possible solutions to this problem, and almost all testers have implemented a unique solution. There are solutions that we could not prove correct, but we could not hack them either.
    339 
    340 [2040E - Control of Randomness](/contest/2040/problem/E "Codeforces Round 992 (Div. 2)")
    341 
    342 **Editorial**
    343 
    344 Tutorial is loading...
    345 
    346 **Solution**
    347 
    348 ```
    349 #include <bits/stdc++.h>
    350  
    351 using namespace std;
    352  
    353 void solve() {
    354     int n, q;
    355     cin >> n >> q;
    356     
    357     vector < vector <int> > g(n);
    358     for (int i = 0; i < n - 1; i++) {
    359         int u, v;
    360         cin >> u >> v;
    361         u--, v--;
    362         g[u].push_back(v);
    363         g[v].push_back(u);
    364     }
    365     
    366     vector <int> depth(n);
    367     vector <int> d(n);
    368     vector <int> par(n);
    369  
    370     function <void(int, int)> dfs = [&](int v, int p) {
    371         if (depth[v] == 1) d[v] = 1;
    372         if (depth[v] > 1) d[v] = d[par[p]] + 2 * (int)g[p].size();
    373         par[v] = p;
    374         for(int to : g[v]) {
    375             if (to == p) continue;
    376             depth[to] = depth[v] + 1;
    377             dfs(to, v);
    378         }
    379     };
    380     
    381     dfs(0, 0);
    382     
    383     while (q--) {
    384         int v, p;
    385         cin >> v >> p;
    386         v--;
    387         int res = d[v];
    388         vector <int> cnt;
    389         while (v != 0 && par[v] != 0) {
    390             cnt.push_back((int)g[par[v]].size());
    391             v = par[par[v]];
    392         }
    393         sort(cnt.rbegin(), cnt.rend());
    394         for (int i = 0; i < min(p, (int)cnt.size()); i++) {
    395             res -= 2 * (cnt[i] - 1);
    396         }
    397         cout << res << '\n';
    398     }
    399 }
    400  
    401 int main() {
    402     int tt;
    403     cin >> tt;
    404     while (tt--) {
    405         solve();
    406     }
    407  
    408     return 0;
    409 }
    410 ```
    411 
    412 **Solution (Notes)**
    413 
    414 ```
    415 #include <bits/stdc++.h>
    416  
    417 using namespace std;
    418  
    419 void solve() {
    420     int n, q;
    421     cin >> n >> q;
    422     
    423     vector < vector <int> > g(n);
    424     for (int i = 0; i < n - 1; i++) {
    425         int u, v;
    426         cin >> u >> v;
    427         u--, v--;
    428         g[u].push_back(v);
    429         g[v].push_back(u);
    430     }
    431     
    432     vector <int> depth(n);
    433     vector <int> d(n);
    434     vector < vector < pair <int,int> > > qrs(n); // <p, idx>
    435     vector <int> res(q);
    436     
    437     for (int i = 0; i < q; i++) {
    438         int v, p;
    439         cin >> v >> p;
    440         v--;
    441         qrs[v].push_back({p, i});
    442     }
    443     
    444     multiset <int> st[2]; // store negative number to be able to use usual foreach loop
    445     
    446     function <void(int, int, int)> dfs = [&](int v, int p, int pp) {
    447         if (depth[v] == 1) d[v] = 1;
    448         if (depth[v] > 1) d[v] = d[pp] + 2 * (int)g[p].size();
    449         
    450         for (pair <int, int> qr : qrs[v]) {
    451             int p = qr.first, idx = qr.second;
    452             int ans = d[v];
    453             for (int i : st[1 - depth[v] % 2]) {
    454                 if (p == 0) break;
    455                 ans -= (-i - 1) * 2;
    456                 p--;
    457             }
    458             res[idx] = ans;
    459         }
    460         
    461         if (depth[v] != 0) st[depth[v] % 2].insert(-(int)g[v].size());
    462         
    463         for (int to : g[v]) {
    464             if (to == p) continue;
    465             depth[to] = depth[v] + 1;
    466             dfs(to, v, p);
    467         }
    468         
    469         if (depth[v] != 0) st[depth[v] % 2].erase(st[depth[v] % 2].find(-(int)g[v].size()));
    470     };
    471     
    472     dfs(0, 0, 0);
    473     
    474     for (int i = 0; i < q; i++)
    475         cout << res[i] << '\n';
    476 }
    477  
    478 int main() {
    479     int tt;
    480     cin >> tt;
    481     while (tt--) {
    482         solve();
    483     }
    484  
    485     return 0;
    486 }
    487 ```
    488 
    489 **Notes**
    490 
    491 This problem originally had the following constraints:
    492 
    493 1. $1 \le n, q \le 2 \cdot 10^5$
    494 2. The sum of $p$ in all queries is not greater than $2 \cdot 10^5$
    495 
    496 How to solve this problem?
    497 
    498 Could you solve this problem without the second constraint?
    499 
    500 **Hint**
    501 
    502 However, it is not hard thanks to a recent [blog](https://codeforces.com/blog/entry/136858).
    503 
    504 [2040F - Number of Cubes](/contest/2040/problem/F "Codeforces Round 992 (Div. 2)")
    505 
    506 **Editorial**
    507 
    508 Tutorial is loading...
    509 
    510 **Solution Phi**
    511 
    512 ```
    513 #include <bits/stdc++.h>
    514 #define int long long
    515  
    516 using namespace std;
    517  
    518 const int N = 3000010;
    519 const int mod = 998244353;
    520 int fact[N], ifact[N], phi[N];
    521  
    522 int powmod(int a, int n) {
    523     int res = 1;
    524     while (n) {
    525         if (n % 2 == 0) {
    526             a = (a * a) % mod;
    527             n /= 2;
    528         }
    529         else {
    530             res = (res * a) % mod;
    531             n--;
    532         }
    533     }
    534     return res;
    535 }
    536  
    537 int inv(int a) {
    538     return powmod(a, mod - 2);
    539 }
    540  
    541 void prepare() {
    542     fact[0] = 1;
    543     for (int i = 1; i < N; i++) {
    544         fact[i] = (fact[i - 1] * i) % mod;
    545     }
    546     ifact[N - 1] = inv(fact[N - 1]);
    547     for (int i = N - 2; i >= 0; i--) {
    548         ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
    549     }
    550  
    551     phi[0] = 0;
    552     phi[1] = 1;
    553     for (int i = 2; i < N; i++) {
    554         phi[i] = i - 1;
    555     }
    556     for (int i = 2; i < N; i++) {
    557         for (int j = i * 2; j < N; j += i) {
    558             phi[j] -= phi[i];
    559         }
    560     }
    561 }
    562  
    563 int C(int n, int k) {
    564     return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod;
    565 }
    566  
    567 int MC(vector <int> &a) {
    568     int sum=0;
    569     for (int i : a) sum += i;
    570     int res = fact[sum];
    571     for (int i : a) {
    572         res = (res * ifact[i]) % mod;
    573     }
    574     return res;
    575 }
    576  
    577 int lcm(int a, int b) {
    578     return a / __gcd(a, b) * b;
    579 }
    580  
    581 vector <int> all_divs(int x) {
    582     vector <int> d;
    583     for (int i = 1; i * i <= x; i++) {
    584         if (x % i == 0) {
    585             d.push_back(i);
    586             if (i * i != x) {
    587                 d.push_back(x / i);
    588             }
    589         }
    590     }
    591     return d;
    592 }
    593  
    594 void solve() {
    595     int a, b, c, k;
    596     cin >> a >> b >> c >> k;
    597     vector <int> v(k);
    598     for (int &i : v) cin >> i;
    599  
    600     int g = v[0];
    601     for (int i : v) g = __gcd(g, i);
    602  
    603     map <int, int> mp;
    604     for (int i : all_divs(a)) {
    605         for (int j : all_divs(b)) {
    606             for (int l : all_divs(c)) {
    607                 int N = lcm(i, lcm(j, l));
    608                 if (g % N == 0) {
    609                     mp[N] += phi[i] * phi[j] * phi[l];
    610                 }
    611             }
    612         }
    613     }
    614  
    615     int sum = 0;
    616     for (pair <int, int> pr : mp) {
    617         int N = pr.first, cnt = pr.second;
    618         vector <int> u;
    619         for (int t : v) u.push_back(t / N);
    620         sum = (sum + (MC(u) * cnt) % mod) % mod;
    621     }
    622  
    623     sum = (sum * inv(a * b * c)) % mod;
    624  
    625     cout << sum << endl;
    626 }
    627  
    628 int32_t main() {
    629     prepare();
    630  
    631     int tt;
    632     cin >> tt;
    633     while (tt--) {
    634         solve();
    635     }
    636  
    637     return 0;
    638 }
    639 ```
    640 
    641 **Solution DP**
    642 
    643 ```
    644 #include <bits/stdc++.h>
    645 #define int long long
    646  
    647 using namespace std;
    648  
    649 const int N = 3000010;
    650 const int mod = 998244353;
    651 int fact[N], ifact[N];
    652 int pos[N];
    653  
    654 int powmod(int a, int n) {
    655     int res = 1;
    656     while (n) {
    657         if (n % 2 == 0) {
    658             a = (a * a) % mod;
    659             n /= 2;
    660         }
    661         else {
    662             res = (res * a) % mod;
    663             n--;
    664         }
    665     }
    666     return res;
    667 }
    668  
    669 int inv(int a) {
    670     return powmod(a, mod - 2);
    671 }
    672  
    673 void prepare() {
    674     fact[0] = 1;
    675     for (int i = 1;i < N; i++) {
    676         fact[i] = (fact[i - 1] * i) % mod;
    677     }
    678     ifact[N - 1] = inv(fact[N - 1]);
    679     for (int i = N - 2; i >= 0; i--) {
    680         ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
    681     }
    682 }
    683  
    684 int C(int n, int k) {
    685     return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod;
    686 }
    687  
    688 int MC(vector <int> &a) {
    689     int sum=0;
    690     for (int i : a) sum += i;
    691     int res = fact[sum];
    692     for (int i : a) {
    693         res = (res * ifact[i]) % mod;
    694     }
    695     return res;
    696 }
    697  
    698 int lcm(int a, int b) {
    699     return a / __gcd(a, b) * b;
    700 }
    701  
    702 vector <int> all_divs(int x) {
    703     vector <int> d1, d2;
    704     for (int i = 1; i * i <= x; i++) {
    705         if (x % i == 0) {
    706             d1.push_back(i);
    707             if (i * i != x) {
    708                 d2.push_back(x / i);
    709             }
    710         }
    711     }
    712     reverse(d2.begin(), d2.end());
    713     for (int i : d2) d1.push_back(i);
    714     return d1;
    715 }
    716  
    717 void solve() {
    718     int a, b, c, k;
    719     cin >> a >> b >> c >> k;
    720     vector <int> v(k);
    721     for (int &i : v) cin >> i;
    722  
    723     int g = v[0];
    724     for (int i : v) g = __gcd(g, i);
    725     vector <int> divs_g = all_divs(g);
    726  
    727     set <int> divs;
    728     for (int i : all_divs(a)) divs.insert(i);
    729     for (int i : all_divs(b)) divs.insert(i);
    730     for (int i : all_divs(c)) divs.insert(i);
    731     for (int i : all_divs(g)) divs.insert(i);
    732     int D = divs.size();
    733     int i = 0;
    734     for (int j : divs) {
    735         pos[j] = i;
    736         i++;
    737     }
    738  
    739     int n = max({a, b, c}) + 1;
    740     vector < vector <int> > tmp(3, vector <int> (D));
    741     vector < vector <int> > cnt(3, vector <int> (D));
    742     for (int t = 0; t < 3; t++) {
    743         int x;
    744         if (t == 0) x = a;
    745         if (t == 1) x = b;
    746         if (t == 2) x = c;
    747         vector <int> divs_x = all_divs(x);
    748  
    749         for (int i = (int)divs_x.size() - 1; i >= 0; i--) {
    750             tmp[t][pos[divs_x[i]]] += x / divs_x[i];
    751             for (int j = 0; j < i; j++) {
    752                 if (divs_x[i] % divs_x[j] == 0) {
    753                     tmp[t][pos[divs_x[j]]] -= tmp[t][pos[divs_x[i]]];
    754                 }
    755             }
    756             cnt[t][pos[x / divs_x[i]]] = tmp[t][pos[divs_x[i]]];
    757         }
    758     }
    759         
    760     vector < vector <int> > dp(4, vector <int> (D));
    761     dp[0][0] = 1;
    762     for(int i = 0; i < 3; i++) {
    763         for (int t1 : divs_g) {
    764             for (int t2 : divs_g) {
    765                 int new_pos = lcm(t1, t2);
    766                 if (t2 < n) {
    767                     dp[i + 1][pos[new_pos]] = (dp[i + 1][pos[new_pos]] + dp[i][pos[t1]] * cnt[i][pos[t2]]) % mod;
    768                 }
    769             }
    770         }
    771     }
    772  
    773     int sum = 0;
    774     i = 0;
    775     for (int j : divs) {
    776         if (g % j != 0) continue;
    777         int N = j, cnt = dp[3][pos[j]];
    778         vector <int> u;
    779         for (int t : v) u.push_back(t / N);
    780         sum = (sum + (MC(u) * cnt) % mod) % mod;
    781     }
    782  
    783     sum = (sum * inv(a * b * c)) % mod;
    784  
    785     cout << sum << endl;
    786 }
    787  
    788 int32_t main() {
    789     prepare();
    790  
    791     int tt;
    792     cin >> tt;
    793     while (tt--) {
    794         solve();
    795     }
    796  
    797     return 0;
    798 }
    799 ```