codeforces-scrape

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

2169.md (10400B)


      1 Source: https://codeforces.com/blog/entry/148390
      2 
      3 [2169A - Alice and Bob](/contest/2169/problem/A "Educational Codeforces Round 184 (Rated for Div. 2)")
      4 
      5 Idea: [Roms](/profile/Roms "Master Roms")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Roms)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17  
     18 int t;
     19  
     20 int main() {
     21     cin >> t;
     22     for (int tc = 0; tc < t; ++tc) {
     23         int n, a;
     24         cin >> n >> a;
     25         vector <int> v(n);
     26         int l = 0, r = 0;
     27         for (int i = 0; i < n; ++i) {
     28             cin >> v[i];
     29             if (a > v[i]) ++l;
     30             if (a < v[i]) ++r;
     31         }
     32         
     33         cout << (l > r ? a - 1 : a + 1) << endl;
     34     }
     35     return 0;
     36 }
     37 ```
     38 
     39 [2169B - Drifting Away](/contest/2169/problem/B "Educational Codeforces Round 184 (Rated for Div. 2)")
     40 
     41 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     42 
     43 **Tutorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Solution (awoo)**
     48 
     49 ```
     50 for _ in range(int(input())):
     51     s = input()
     52     for i in range(len(s) - 1):
     53         if s[i] != '<' and s[i + 1] != '>':
     54             print(-1)
     55             break
     56     else:
     57         print(len(s) - min(s.count('<'), s.count('>')))
     58 ```
     59 
     60 [2169C - Range Operation](/contest/2169/problem/C "Educational Codeforces Round 184 (Rated for Div. 2)")
     61 
     62 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     63 
     64 **Tutorial**
     65 
     66 Tutorial is loading...
     67 
     68 **Solution (Neon)**
     69 
     70 ```
     71 #include <bits/stdc++.h>
     72  
     73 using namespace std;
     74  
     75 using li = long long;
     76  
     77 int main() {
     78   int t;
     79   cin >> t;
     80   while (t--) {
     81     int n;
     82     cin >> n;
     83     li s = 0, mn = 0, bst = 0;
     84     for (int i = 0; i < n; ++i) {
     85       int x;
     86       cin >> x;
     87       s += x;
     88       li cur = (i + 1) * li(i + 2) - s;
     89       mn = min(mn, cur);
     90       bst = max(bst, cur - mn);
     91     }
     92     cout << s + bst << '\n';
     93   }
     94 }
     95 ```
     96 
     97 [2169D1 - Removal of a Sequence (Easy Version)](/contest/2169/problem/D1 "Educational Codeforces Round 184 (Rated for Div. 2)")
     98 
     99 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
    100 
    101 **Tutorial**
    102 
    103 Tutorial is loading...
    104 
    105 **Solution (FelixArg)**
    106 
    107 ```
    108 #include <bits/stdc++.h>
    109  
    110 using namespace std;
    111  
    112 const long long INF = 1000000000000LL + 1;
    113 
    114 void solve(){
    115     int x;
    116     long long y, k;
    117  
    118     cin >> x >> y >> k;
    119  
    120     long long l = 1, r = INF;
    121     long long m;
    122  
    123     while(l <= r){
    124         m = l + (r - l) / 2;
    125         long long ost = (m - 1);
    126         for (int i = 0; i < x; i++){
    127             ost -= ost / y;
    128         }
    129         if (ost + 1 > k){
    130             r = m - 1;
    131         }
    132         else{
    133             l = m + 1;
    134         }
    135     }
    136  
    137     if (r == INF){
    138         cout << -1 << '\n';
    139     }
    140     else{
    141         cout << r << '\n';
    142     }
    143 }
    144  
    145 signed main()
    146 {
    147 #ifdef FELIX
    148   auto _clock_start = chrono::high_resolution_clock::now();
    149 #endif
    150   ios_base::sync_with_stdio(false);
    151   cin.tie(0);
    152   cout.tie(0);
    153  
    154   int t = 1;
    155   cin >> t;
    156   while(t--){
    157     solve();
    158   }
    159  
    160 #ifdef FELIX
    161   cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    162     chrono::high_resolution_clock::now()
    163       - _clock_start).count() << "ms." << endl;
    164 #endif
    165   return 0;
    166 }
    167 ```
    168 
    169 [2169D2 - Removal of a Sequence (Hard Version)](/contest/2169/problem/D2 "Educational Codeforces Round 184 (Rated for Div. 2)")
    170 
    171 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
    172 
    173 **Tutorial**
    174 
    175 Tutorial is loading...
    176 
    177 **Solution (FelixArg)**
    178 
    179 ```
    180 #include <bits/stdc++.h>
    181  
    182 using namespace std;
    183  
    184 #define int long long
    185  
    186 const int INF = 1'000'000'000'000LL;
    187  
    188 void solve(){
    189   int x, y, k;
    190   cin >> x >> y >> k;
    191  
    192   if (y == 1){
    193     cout << -1 << '\n';
    194     return;
    195   }
    196  
    197   for (int i = 0; i < x; ){
    198     int cur = (k - 1) / (y - 1);
    199     if (cur == 0){
    200       break;
    201     }
    202     int fk = (cur + 1) * (y - 1) + 1;
    203     int cnt = (fk - k + cur - 1) / cur;
    204     cnt = min(x - i, cnt);
    205     k += cnt * cur;
    206     if (k > INF){
    207       cout << -1 << '\n';
    208       return;
    209     } 
    210     i += cnt;
    211   }
    212  
    213   cout << k << '\n';
    214 }
    215  
    216 signed main()
    217 {
    218 #ifdef FELIX
    219     auto _clock_start = chrono::high_resolution_clock::now();
    220 #endif
    221     ios_base::sync_with_stdio(false);
    222     cin.tie(0);
    223     cout.tie(0);
    224  
    225     int t = 1;
    226     cin >> t;
    227     while(t--){
    228         solve();
    229     }
    230  
    231 #ifdef FELIX
    232     cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    233         chrono::high_resolution_clock::now()
    234             - _clock_start).count() << "ms." << endl;
    235 #endif
    236     return 0;
    237 }
    238 ```
    239 
    240 [2169E - Points Selection](/contest/2169/problem/E "Educational Codeforces Round 184 (Rated for Div. 2)")
    241 
    242 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    243 
    244 **Tutorial**
    245 
    246 Tutorial is loading...
    247 
    248 **Solution (BledDest)**
    249 
    250 ```
    251 #include<bits/stdc++.h>
    252  
    253 using namespace std;
    254  
    255 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    256 #define sz(a) int((a).size())
    257  
    258 typedef long long li;
    259  
    260 const int INF = int(1e9);
    261 const li INF64 = li(1e18);
    262  
    263 int n;
    264 vector<li> x[3];
    265  
    266 bool read() {
    267     if(!(cin >> n))
    268         return false;
    269     fore (k, 0, 3) {
    270         x[k].resize(n);
    271         fore (i, 0, n)
    272             cin >> x[k][i];
    273     }
    274     return true;
    275 }
    276  
    277 void solve() {
    278     vector< vector<li> > w(n, vector<li>(1 << 4, 0));
    279     fore (i, 0, n) {
    280         fore (mask, 0, 1 << 4) {
    281             fore (k, 0, 4) if ((mask >> k) & 1)
    282                 w[i][mask] += x[k & 1][i] * (k < 2 ? -1 : 1);
    283         }
    284     }
    285  
    286     vector< vector<li> > d(n + 1, vector<li>(1 << 4, -INF64));
    287     d[0][0] = 0;
    288     fore (i, 0, n) fore (mask, 0, 1 << 4) {
    289         if (d[i][mask] < -INF64 / 2)
    290             continue;
    291         
    292         d[i + 1][mask] = max(d[i + 1][mask], d[i][mask] + x[2][i]);
    293  
    294         int filter = ((1 << 4) - 1) ^ mask;
    295         for (int cmask = filter; cmask > 0; cmask = (cmask - 1) & filter)
    296             d[i + 1][mask | cmask] = max(d[i + 1][mask | cmask], d[i][mask] + 2ll * w[i][cmask]);
    297     }
    298     cout << d[n][(1 << 4) - 1] << endl;
    299 }
    300  
    301 int main() {
    302 #ifdef _DEBUG
    303     freopen("input.txt", "r", stdin);
    304     int tt = clock();
    305 #endif
    306     ios_base::sync_with_stdio(false);
    307  
    308     int t; cin >> t;
    309     while (t--) {
    310         read();
    311         solve();
    312         
    313 #ifdef _DEBUG
    314         cerr << "TIME = " << clock() - tt << endl;
    315         tt = clock();
    316 #endif
    317     }
    318     return 0;
    319 }
    320 ```
    321 
    322 [2169F - Subsequence Problem](/contest/2169/problem/F "Educational Codeforces Round 184 (Rated for Div. 2)")
    323 
    324 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    325 
    326 **Tutorial**
    327 
    328 Tutorial is loading...
    329 
    330 **Solution (BledDest)**
    331 
    332 ```
    333 #include<bits/stdc++.h>
    334  
    335 using namespace std;
    336  
    337 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    338 #define sz(a) int((a).size())
    339  
    340 const int LOGN = 19;
    341 const int MOD = 998244353;
    342 int g = 3;
    343  
    344 int mul(int a, int b) {
    345     return int(a * 1ll * b % MOD);
    346 }
    347 int norm(int a) {
    348     while(a >= MOD) a -= MOD;
    349     while(a < 0) a += MOD;
    350     return a;
    351 }
    352 int binPow (int a, int k) {
    353     int ans = 1;
    354     for (; k > 0; k >>= 1) {
    355         if (k & 1)
    356             ans = mul(ans, a);
    357         a = mul(a, a);
    358     }
    359     return ans;
    360 }
    361 int inv(int a) {
    362     return binPow(a, MOD - 2);
    363 }
    364  
    365 vector<int> w[LOGN], rv;
    366 bool precalced = false;
    367  
    368 void precalc() {
    369     if(precalced)
    370         return;
    371     precalced = true;
    372     
    373     int wb = binPow(g, (MOD - 1) / (1 << LOGN));
    374     fore(st, 0, LOGN) {
    375         w[st].assign(1 << st, 1);
    376  
    377         int bw = binPow(wb, 1 << (LOGN - st - 1));
    378         int cw = 1;
    379  
    380         fore(k, 0, (1 << st)) {
    381             w[st][k] = cw;
    382             cw = mul(cw, bw);
    383         }
    384     }
    385     
    386     rv.assign(1 << LOGN, 0);
    387     fore(i, 1, sz(rv))
    388         rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1));
    389 }
    390  
    391 const int MX = (1 << LOGN) + 3;
    392  
    393 inline void fft(int a[MX], int n, bool inverse) {
    394     precalc();
    395     
    396     int ln = __builtin_ctz(n);
    397     assert((1 << ln) < MX);
    398     assert((1 << ln) == n);
    399  
    400     fore(i, 0, n) {
    401         int ni = rv[i] >> (LOGN - ln);
    402         if(i < ni) swap(a[i], a[ni]);
    403     }
    404  
    405     for(int st = 0; (1 << st) < n; st++) {
    406         int len = (1 << st);
    407         for(int k = 0; k < n; k += (len << 1)) {
    408             fore(pos, k, k + len) {
    409                 int l = a[pos];
    410                 int r = mul(a[pos + len], w[st][pos - k]);
    411  
    412                 a[pos] = norm(l + r);
    413                 a[pos + len] = norm(l - r);
    414             }
    415         }
    416     }
    417     
    418     if(inverse) {
    419         int in = inv(n);
    420         fore(i, 0, n)
    421             a[i] = mul(a[i], in);
    422         reverse(a + 1, a + n);
    423     }
    424 }
    425  
    426 int aa[MX], bb[MX], cc[MX];
    427  
    428 vector<int> multiply(const vector<int> &a, const vector<int> &b, int cutoff) {
    429     int ln = 1;
    430     while(ln < (sz(a) + sz(b)))
    431         ln <<= 1;
    432     
    433     fore(i, 0, ln)
    434         aa[i] = (i < sz(a) ? a[i] : 0);
    435     fore(i, 0, ln)
    436         bb[i] = (i < sz(b) ? b[i] : 0);
    437         
    438     fft(aa, ln, false);
    439     fft(bb, ln, false);
    440     
    441     fore(i, 0, ln)
    442         cc[i] = mul(aa[i], bb[i]);
    443     fft(cc, ln, true);
    444     
    445     vector<int> ans(cc, cc + ln);
    446     while((ans.size() > 0 && ans.back() == 0) || ans.size() > cutoff)
    447         ans.pop_back();
    448     return ans;
    449 }
    450  
    451 vector<int> fact, ifact;
    452  
    453 void precalc_factorials(int s) {
    454     fact.resize(s);
    455     fact[0] = 1;
    456     for(int i = 1; i < s; i++)
    457         fact[i] = mul(fact[i - 1], i);
    458     ifact.resize(s);
    459     for(int i = 0; i < s; i++)
    460         ifact[i] = inv(fact[i]);
    461 }
    462  
    463 int choose(int n, int k) {
    464     if(n < 0 || n < k || k < 0) return 0;
    465     return mul(fact[n], mul(ifact[n - k], ifact[k]));
    466 }
    467  
    468 int main() {
    469     ios_base::sync_with_stdio(0);
    470     cin.tie(0);
    471     int n, m, k;
    472     cin >> n >> m >> k;
    473     vector<int> lens(k);
    474     for(int i = 0; i < k; i++) cin >> lens[i];
    475  
    476     int cutoff = n + 1;
    477     precalc_factorials(1 << LOGN);
    478     vector<int> segments(6);
    479     segments[0] = 1;
    480     for(auto len : lens)
    481         for(int i = 1; i <= len; i++)
    482             segments[i]++;
    483     vector<vector<int>> poly(6);
    484     for(int i = 0; i < 6; i++) {
    485         if(segments[i] == 0)
    486             poly[i] = { 1 };
    487         else {
    488             int choices = norm(m - i);
    489             int p = 1;
    490             poly[i].resize(cutoff);
    491             for(int k = 0; k < cutoff; k++) {
    492                 int cur = mul(p, choose(k + segments[i] - 1, k));
    493                 poly[i][k] = cur;
    494                 p = mul(p, choices);
    495             }
    496         }
    497     }
    498     vector<int> ans = { 1 };
    499     for(int i = 0; i < 6; i++)
    500         ans = multiply(ans, poly[i], cutoff);
    501  
    502     int used = 0;
    503     int coef = 1;
    504     for(auto len : lens) {
    505         coef = mul(coef, fact[len]);
    506         used += len;
    507     }
    508     int res = mul(coef, ans[n - used]);
    509     cout << res << endl;
    510 }
    511 ```