codeforces-scrape

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

2140.md (15515B)


      1 Source: https://codeforces.com/blog/entry/146218
      2 
      3 [2140A - Shift Sort](/contest/2140/problem/A "Codeforces Round 1049 (Div. 2)")
      4 
      5 Idea: [shorya1835](/profile/shorya1835 "Master shorya1835") Preparation: [wakanda-forever](/profile/wakanda-forever "Expert wakanda-forever")
      6 
      7 **Solution**
      8 
      9 Tutorial is loading...
     10 
     11 **Code**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 using namespace std;
     16 using ll = long long;
     17  
     18 int main(){
     19  
     20     int tt;
     21     cin >> tt;
     22  
     23     while(tt--){
     24  
     25         int n;
     26         string s;
     27         cin >> n >> s;
     28  
     29         int ans = 0;
     30  
     31         string p = s;
     32         sort(p.begin(), p.end());
     33  
     34         for(int i = 0; i < n; i++) if(s[i] != p[i]) ans++;
     35  
     36         cout << ans / 2 << '\n';
     37  
     38     }
     39     return 0;
     40 }
     41 ```
     42 
     43 [2140B - Another Divisibility Problem](/contest/2140/problem/B "Codeforces Round 1049 (Div. 2)")
     44 
     45 Idea: [wakanda-forever](/profile/wakanda-forever "Expert wakanda-forever") Preparation: [wakanda-forever](/profile/wakanda-forever "Expert wakanda-forever")
     46 
     47 **Solution**
     48 
     49 Tutorial is loading...
     50 
     51 **Code**
     52 
     53 ```
     54 #include<bits/stdc++.h>
     55 using namespace std;
     56  
     57 int main(){
     58     int t;
     59     cin >> t;
     60     while(t--){
     61         int x;
     62         cin >> x;
     63         cout << 2*x<< '\n';
     64     }
     65     return 0;
     66 }
     67 ```
     68 
     69 [2140C - Ultimate Value](/contest/2140/problem/C "Codeforces Round 1049 (Div. 2)")
     70 
     71 Idea: [shorya1835](/profile/shorya1835 "Master shorya1835") Preparation: [wakanda-forever](/profile/wakanda-forever "Expert wakanda-forever")
     72 
     73 **Solution**
     74 
     75 Tutorial is loading...
     76 
     77 **Code**
     78 
     79 ```
     80 #include <bits/stdc++.h>
     81 using namespace std;
     82 using ll = long long;
     83  
     84 int main(){
     85  
     86     int tt;
     87     cin >> tt;
     88  
     89     while(tt--){
     90  
     91         int n;
     92         cin >> n;
     93  
     94         vector<long long> a(n);
     95         for(int i = 0; i < n; i++){
     96             cin >> a[i];
     97         }
     98  
     99         ll ans = 0;
    100         for(int i = 0; i < n; i++){
    101             if(i % 2) ans -= a[i];
    102             else ans += a[i];
    103         }
    104  
    105         ll init = ans;
    106  
    107         for(int i = 0; i < n; i++) ans = max(ans, init + i - (i % 2));
    108  
    109         ll min_even = LLONG_MAX / 2, min_odd = LLONG_MAX / 2;
    110         for(int i = 0; i < n; i++){
    111             if(i % 2){
    112                 ans = max(init + i + a[i] + a[i] - min_even, ans);
    113                 min_odd = min(min_odd, i - a[i] - a[i]);
    114             }
    115             else{
    116                 ans = max(init + i - a[i] - a[i] - min_odd, ans);
    117                 min_even = min(min_even, i + a[i] + a[i]);
    118             }
    119         }
    120  
    121         cout << ans << '\n';
    122  
    123     }
    124  
    125     return 0;
    126 }
    127 ```
    128 
    129 [2140D - A Cruel Segment's Thesis](/contest/2140/problem/D "Codeforces Round 1049 (Div. 2)")
    130 
    131 Idea: [shorya1835](/profile/shorya1835 "Master shorya1835") Preparation: [shorya1835](/profile/shorya1835 "Master shorya1835")
    132 
    133 **Solution**
    134 
    135 Tutorial is loading...
    136 
    137 **Code**
    138 
    139 ```
    140 #include<bits/stdc++.h>
    141 using namespace std;
    142  
    143 typedef long long ll;
    144 typedef vector<int> vi;
    145 typedef vector<ll> vl;
    146 typedef set<int> si;
    147 typedef pair<int, int> pi;
    148 typedef pair<ll, ll> pl;
    149 
    150 #define fo(i, a, b) for (ll i = a; i < b; i++)
    151 #define F first
    152 #define S second
    153 #define pb push_back
    154 #define mp make_pair
    155  
    156 int main() {
    157     cin.tie(0)->sync_with_stdio(0);
    158     cin.exceptions(cin.failbit);
    159     ll T, n;
    160     cin >> T;
    161     while (T--) {
    162         cin >> n;
    163         vector<pl> a(n);
    164         fo(i, 0, n)cin >> a[i].first >> a[i].second;
    165         ll ans = 0;
    166         fo(i, 0, n)ans += a[i].second - a[i].first + 1;
    167         ans += n / 2;
    168         vector<pair<ll, pl>> b(n);
    169         fo(i, 0, n) {
    170             b[i].second = a[i];
    171             b[i].first = a[i].first + a[i].second;
    172         }
    173         sort(b.begin(), b.end());
    174         if (n % 2 == 0) {
    175             fo(i, 0, n) {
    176                 ans += a[i].second;
    177             }
    178             fo(i, 0, n / 2) {
    179                 ans -= b[i].first;
    180             }
    181             cout << ans - n - n / 2 << "\n";
    182         }
    183         else {
    184             ll k = 0, w = 0;
    185             fo(i, 0, n) {
    186                 w += a[i].second;
    187             }
    188             fo(i, 0, n / 2+1) {
    189                 w-= b[i].first;
    190             }
    191             fo(i, 0, n / 2 + 1) {
    192                 k = max(k, w + b[i].S.F);
    193             }
    194             w += b[n / 2].first;
    195             fo(i, n / 2 + 1, n) {
    196                 k = max(k, w - b[i].S.S);
    197             }
    198             cout << ans + k  - n - n / 2 << "\n";
    199         }
    200     }
    201 }
    202 ```
    203 
    204 [2140E1 - Prime Gaming (Easy Version)](/contest/2140/problem/E1 "Codeforces Round 1049 (Div. 2)")
    205 
    206 Idea: [Divine_Spark](/profile/Divine_Spark "Master Divine_Spark") Preparation: [shorya1835](/profile/shorya1835 "Master shorya1835")
    207 
    208 **Solution**
    209 
    210 Tutorial is loading...
    211 
    212 **Code**
    213 
    214 ```
    215 #include <bits/stdc++.h>
    216 using namespace std;
    217  
    218 typedef long long ll;
    219 int removebit(int n, int bit)
    220 {
    221     int msk = (1 << 22);
    222     int filtermask = msk - (1 << bit);
    223     return ((n >> 1) & filtermask) | (n & ((1 << bit) - 1));
    224 }
    225 const ll MOD = 1e9+7;
    226 class mint
    227 {
    228 public:
    229     ll val;
    230     static ll mod_exp(ll a, ll b)
    231     {
    232         ll res = 1;
    233         a = a % MOD;
    234         while (b > 0)
    235         {
    236             if (b % 2 == 1)
    237                 res = (res * a) % MOD;
    238             b /= 2;
    239             a = (a * a) % MOD;
    240         }
    241         return res;
    242     }
    243     static ll gcdExtended(ll a, ll b, ll *x, ll *y)
    244     {
    245         if (a == 0)
    246         {
    247             *x = 0, *y = 1;
    248             return b;
    249         }
    250         ll x1, y1;
    251         ll gcd = gcdExtended(b % a, a, &x1, &y1);
    252         *x = y1 - (b / a) * x1;
    253         *y = x1;
    254         return gcd;
    255     }
    256     static ll modInverse(ll a)
    257     {
    258         ll x, y;
    259         ll g = gcdExtended(a, MOD, &x, &y);
    260         g++;
    261         ll res = (x % MOD);
    262         if (res < 0)
    263             res += MOD;
    264         return res;
    265     }
    266     mint() { val = 0; }
    267     mint(ll x)
    268     {
    269         val = x % MOD;
    270         if (val < 0)
    271             val += MOD;
    272     }
    273     mint &operator+=(const mint &other)
    274     {
    275         val += other.val;
    276         if (val >= MOD)
    277             val -= MOD;
    278         return (*this);
    279     }
    280     mint &operator-=(const mint &other)
    281     {
    282         val -= other.val;
    283         if (val < 0)
    284             val += MOD;
    285         return (*this);
    286     }
    287     mint &operator*=(const mint &other)
    288     {
    289         val = (val * other.val) % MOD;
    290         return (*this);
    291     }
    292     mint &operator/=(const mint &other)
    293     {
    294         val = (val * modInverse(other.val)) % MOD;
    295         return (*this);
    296     }
    297     mint &operator=(const mint &other)
    298     {
    299         val = other.val;
    300         return (*this);
    301     }
    302     mint operator+(const mint &other) const { return mint(*this) += other; }
    303     mint operator-(const mint &other) const { return mint(*this) -= other; }
    304     mint operator*(const mint &other) const { return mint(*this) *= other; }
    305     mint operator/(const mint &other) const { return mint(*this) /= other; }
    306     bool operator==(const mint &other) const { return val == other.val; }
    307  
    308     mint operator++()
    309     {
    310         ++val;
    311         if (val == MOD)
    312             val = 0;
    313         return (*this);
    314     }
    315     mint operator++(int)
    316     {
    317         val++;
    318         if (val == MOD)
    319             val = 0;
    320         return mint(val - 1);
    321     }
    322     mint operator--()
    323     {
    324         --val;
    325         if (val == -1)
    326             val = MOD - 1;
    327         return (*this);
    328     }
    329     mint operator--(int)
    330     {
    331         val--;
    332         if (val == -1)
    333             val = MOD - 1;
    334         return mint(val + 1);
    335     }
    336  
    337     // ^ has very low precedence, careful!!
    338  
    339     template <typename T>
    340     mint &operator^=(const T &other)
    341     {
    342         val = mod_exp(val, other);
    343         return (*this);
    344     }
    345     template <typename T>
    346     mint operator^(const T &other) const { return mint(*this) ^= other; }
    347  
    348     mint &operator^=(const mint &other)
    349     {
    350         val = mod_exp(val, other.val);
    351         return (*this);
    352     }
    353     mint operator^(const mint &other) const { return mint(*this) ^= other; }
    354  
    355     template <typename T>
    356     explicit operator T() { return (T)val; }
    357     template <typename T>
    358     friend mint operator+(T other, const mint &M) { return mint(other) + M; }
    359     template <typename T>
    360     friend mint operator-(T other, const mint &M) { return mint(other) - M; }
    361     template <typename T>
    362     friend mint operator*(T other, const mint &M) { return mint(other) * M; }
    363     template <typename T>
    364     friend mint operator/(T other, const mint &M) { return mint(other) / M; }
    365     template <typename T>
    366     friend mint operator^(T other, const mint &M) { return mint(other) ^ M; }
    367  
    368     friend std::ostream &operator<<(std::ostream &output, const mint &M) { return output << M.val; }
    369     friend std::istream &operator>>(std::istream &input, mint &M)
    370     {
    371         input >> M.val;
    372         M.val %= MOD;
    373         return input;
    374     }
    375 };
    376  
    377 const int maxn = 20;
    378 const int maxm = 30;
    379  
    380 ll modpow(ll a , ll b ) {
    381     ll res = 1 ;
    382     a %= MOD;
    383     while( b > 0 ) {
    384         if( b&1 ) res = ( res*a ) % MOD;
    385         a = ( a*a ) % MOD;
    386         b >>= 1 ;
    387     }
    388     return res ;
    389 }
    390  
    391 int main()
    392 {   int t;
    393     cin >> t;
    394     while(t--){
    395         bool pl = 1;
    396         int n, m;
    397         cin >> n >> m;
    398         int k,x;
    399         cin >> k;
    400         vector<int> good;
    401         for(int i=0;i<k;i++){
    402             cin >> x;
    403             good.push_back(x);
    404         }
    405         if(m==1){
    406             cout << 1<< "\n";
    407             continue;
    408         }
    409         vector<vector<vector<bool>>> dp(2, vector<vector<bool>>(n + 1));
    410         int cntt = 0;
    411         for (int i = 1; i <= n; i++)
    412         {
    413     
    414             dp[0][i].resize(1 << i);
    415             dp[1][i].resize(1 << i);
    416             if (i == 1)
    417             {
    418                 for (int j = 0; j <= 1; j++)
    419                 {
    420                     for (int k = 0; k <= 1; k++)
    421                     {
    422                         dp[j][i][k] = k;
    423                     }
    424                 }
    425             }
    426             else
    427             {
    428                 for (int msk = 0; msk < (1 << i); msk++)
    429                 {
    430                     bool ans0 = 1;
    431                     bool ans1 = 0;
    432                     for (auto x :good)
    433                     {
    434                         if (x <= i)
    435                         {
    436                             cntt++;
    437                             int finmsk = removebit(msk, x - 1);
    438                             ans0 &= dp[1][i - 1][finmsk];
    439                             ans1 |= dp[0][i - 1][finmsk];
    440                         }
    441                         else
    442                         {
    443                             break;
    444                         }
    445                     }
    446                     dp[0][i][msk] = ans0;
    447                     dp[1][i][msk] = ans1;
    448                 }
    449             }
    450         }
    451         mint finans = 0;
    452         for (int r = 0; r < (1<<n); r++)
    453         {   
    454             finans += 1+dp[pl][n][r];
    455             
    456         }
    457         cout << finans << endl;
    458     }
    459 }
    460 ```
    461 
    462 [2140E2 - Prime Gaming (Hard Version)](/contest/2140/problem/E2 "Codeforces Round 1049 (Div. 2)")
    463 
    464 Idea: [Divine_Spark](/profile/Divine_Spark "Master Divine_Spark") Preparation:[wakanda-forever](/profile/wakanda-forever "Expert wakanda-forever"), [shorya1835](/profile/shorya1835 "Master shorya1835")
    465 
    466 **Solution**
    467 
    468 Tutorial is loading...
    469 
    470 **Code**
    471 
    472 ```
    473 #include <bits/stdc++.h>
    474 using namespace std;
    475 typedef long long ll;
    476 const ll MOD = 1000000007;
    477 int removebit(int n, int bit)
    478 {
    479     int msk = (1 << 22);
    480     int filtermask = msk - (1 << bit);
    481     return ((n >> 1) & filtermask) | (n & ((1 << bit) - 1));
    482 }
    483 
    484 const int maxn = 20;
    485 const int maxm = 30;
    486  
    487 ll binpow(ll a,ll b,ll m = MOD){
    488     ll res = 1;
    489     while (b){
    490         if (b&1) res = (res*a)%m;
    491         a = (a*a)%m;
    492         b>>=1;
    493     }
    494     return res;
    495 }
    496 int main()
    497 {   int t;
    498     cin >> t;
    499     while(t--){
    500         bool pl = 1;
    501         int n, m;
    502         cin >> n >> m;
    503         int k,x;
    504         cin >> k;
    505         vector<int> good;
    506         for(int i=0;i<k;i++){
    507             cin >> x;
    508             good.push_back(x);
    509         }
    510         vector<vector<vector<bool>>> dp(2, vector<vector<bool>>(n + 1));
    511         vector<vector<vector<int>>> cnt(2, (n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1))));
    512         int cntt = 0;
    513         for (int i = 1; i <= n; i++)
    514         {
    515     
    516             dp[0][i].resize(1 << i);
    517             dp[1][i].resize(1 << i);
    518             if (i == 1)
    519             {
    520                 for (int j = 0; j <= 1; j++)
    521                 {
    522                     for (int k = 0; k <= 1; k++)
    523                     {
    524                         dp[j][i][k] = k;
    525                     }
    526                     cnt[j][1][1]++;
    527                 }
    528             }
    529             else
    530             {
    531                 for (int msk = 0; msk < (1 << i); msk++)
    532                 {
    533                     bool ans0 = 1;
    534                     bool ans1 = 0;
    535                     for (auto x :good)
    536                     {
    537                         if (x <= i)
    538                         {
    539                             cntt++;
    540                             int finmsk = removebit(msk, x - 1);
    541                             ans0 &= dp[1][i - 1][finmsk];
    542                             ans1 |= dp[0][i - 1][finmsk];
    543                         }
    544                         else
    545                         {
    546                             break;
    547                         }
    548                     }
    549                     dp[0][i][msk] = ans0;
    550                     dp[1][i][msk] = ans1;
    551                     cnt[0][i][__popcount(msk)] += ans0;
    552                     cnt[1][i][__popcount(msk)] += ans1;
    553                 }
    554             }
    555         }
    556         ll finans = 0;
    557         for (int r = 1; r <= n; r++)
    558         {   
    559             for(int k=1;k<=m;k++){
    560                 finans += (((binpow(k-1,n-r)*binpow(m-k+1,r))%MOD) * (cnt[pl][n][r]))%MOD;
    561             }
    562         }
    563         cout << finans%MOD << endl;
    564     }
    565 }
    566 ```
    567 
    568 **Bonus**
    569 
    570 Solve the problem when piles must have distinct stones, $m \le 10^9$ and there is no constraint on sum of $m$.
    571 
    572 [2140F - Sum Minimisation](/contest/2140/problem/F "Codeforces Round 1049 (Div. 2)")
    573 
    574 Idea: [shorya1835](/profile/shorya1835 "Master shorya1835") Preparation: [wakanda-forever](/profile/wakanda-forever "Expert wakanda-forever"), [shorya1835](/profile/shorya1835 "Master shorya1835")
    575 
    576 **Solution**
    577 
    578 Tutorial is loading...
    579 
    580 **Code**
    581 
    582 ```
    583 #include<bits/stdc++.h>
    584 using namespace std;
    585 typedef long long ll;
    586 typedef vector<int> vi;
    587 typedef vector<ll> vl;
    588 typedef set<int> si;
    589 typedef pair<ll, ll> pl;
    590 #define fo(i, a, b) for (ll i = a; i < b; i++)
    591 #define pb push_back
    592 
    593 ll gcd(ll a,ll b){
    594     if(a==0)return b;
    595     else return gcd(b%a,a);
    596 }
    597 vl a;
    598 ll lc, s, n;
    599 bool good(){
    600     bool v=1;
    601     if(n>23){
    602         fo(i,0,n){
    603             if(a[i]!=a[0]){
    604                 v=0;
    605                 break;
    606             }
    607         }
    608     }
    609     else{
    610         fo(i,2,n){
    611             fo(j,0,n){
    612                 if((a[j]%i)!=(a[0]%i)){
    613                     v=0;
    614                     break;
    615                 }
    616             }
    617         }
    618     }
    619     v&=(s%n==0);
    620     return v;
    621 }
    622 int main() {
    623     cin.tie(0)->sync_with_stdio(0);
    624     cin.exceptions(cin.failbit);
    625     ll T;
    626     cin >> T;
    627     while (T--) {
    628         cin >> n;
    629         a.clear();
    630         a.resize(n);
    631         s=0;
    632         fo(i,0,n){
    633             cin >> a[i];
    634             s+=a[i];
    635         }
    636         sort(a.begin(),a.end());
    637         lc=1;
    638         if(n>23){
    639             lc=1e10;
    640         }
    641         else{
    642             fo(i,2,n+1){
    643                 lc=(lc*i)/gcd(lc,i);
    644             }
    645         }
    646         if(good()){
    647             cout << s<< "\n";
    648             continue;
    649         }
    650         a[0]--;
    651         s--;
    652         if(good()){
    653             cout << s<< "\n";
    654             continue;
    655         }
    656         cout << -1 << "\n";
    657 
    658     }
    659 }
    660 ```
    661 
    662 Thanks to [satyam343](/profile/satyam343 "Master satyam343") for his help throughout the round.