codeforces-scrape

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

1969.md (9140B)


      1 Source: https://codeforces.com/blog/entry/129022
      2 
      3 [1969A - Two Friends](/contest/1969/problem/A "Educational Codeforces Round 165 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15     n = int(input())
     16     p = [int(x) - 1 for x in input().split()]
     17     ans = 3
     18     for i in range(n):
     19         if p[p[i]] == i:
     20             ans = 2
     21     print(ans)
     22 ```
     23 
     24 [1969B - Shifts and Sorting](/contest/1969/problem/B "Educational Codeforces Round 165 (Rated for Div. 2)")
     25 
     26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution (adedalic)**
     33 
     34 ```
     35 fun main() {
     36     repeat(readln().toInt()) {
     37         val s = readln().map { it.code - '0'.code }
     38         val zeroes = s.count { it == 0 }
     39         val cnt = intArrayOf(0, 0)
     40         var ans = 0L
     41         for (c in s) {
     42             cnt[c]++
     43             if (c == 0)
     44                 ans += if (cnt[1] > 0) 1 else 0
     45             else
     46                 ans += (zeroes - cnt[0])
     47         }
     48         println(ans)
     49     }
     50 }
     51 ```
     52 
     53 [1969C - Minimizing the Sum](/contest/1969/problem/C "Educational Codeforces Round 165 (Rated for Div. 2)")
     54 
     55 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     56 
     57 **Tutorial**
     58 
     59 Tutorial is loading...
     60 
     61 **Solution (Neon)**
     62 
     63 ```
     64 #include <bits/stdc++.h>
     65  
     66 using namespace std;
     67 
     68 using li = long long;
     69 const li INF = 1e18;
     70 
     71 int main() {
     72   int t;
     73   cin >> t;
     74   while (t--) {
     75     int n, k;
     76     cin >> n >> k;
     77     vector<li> a(n);
     78     for (auto& x : a) cin >> x;
     79     vector<vector<li>> dp(n + 1, vector<li>(k + 1, INF));
     80     dp[0][0] = 0;
     81     for (int i = 0; i < n; ++i) {
     82       for (int j = 0; j <= k; ++j) {
     83         li mn = INF;
     84         for (int d = 0; j + d <= k && i + d < n; ++d) {
     85           mn = min(mn, a[i + d]);
     86           dp[i + d + 1][j + d] = min(dp[i + d + 1][j + d], dp[i][j] + (d + 1) * mn);
     87         }
     88       }
     89     }
     90     cout << *min_element(dp[n].begin(), dp[n].end()) << '\n';
     91   }
     92 }
     93 ```
     94 
     95 [1969D - Shop Game](/contest/1969/problem/D "Educational Codeforces Round 165 (Rated for Div. 2)")
     96 
     97 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     98 
     99 **Tutorial**
    100 
    101 Tutorial is loading...
    102 
    103 **Solution (Neon)**
    104 
    105 ```
    106 #include <bits/stdc++.h>
    107  
    108 using namespace std;
    109 
    110 #define sz(a) int((a).size())
    111 using li = long long;
    112 
    113 int main() {
    114   int t;
    115   cin >> t;
    116   while (t--) {
    117     int n, k;
    118     cin >> n >> k;
    119     vector<int> a(n), b(n);
    120     for (auto& x : a) cin >> x;
    121     for (auto& x : b) cin >> x;
    122     vector<int> ord(n);
    123     iota(ord.begin(), ord.end(), 0);
    124     sort(ord.begin(), ord.end(), [&](int i, int j) {
    125       return b[i] > b[j];
    126     });
    127     li f = 0, p = 0;
    128     for (int i : ord) p += max(0, b[i] - a[i]);
    129     li ans = 0;
    130     multiset<int> s;
    131     if (sz(s) == k) ans = max(ans, p - f);
    132     for (int i : ord) {
    133       p -= max(0, b[i] - a[i]);
    134       s.insert(a[i]);
    135       f += a[i];
    136       if (sz(s) > k) {
    137         f -= *s.rbegin();
    138         s.erase(--s.end());
    139       }
    140       if (sz(s) == k) ans = max(ans, p - f);
    141     }
    142     cout << ans << '\n';
    143   }
    144 }
    145 ```
    146 
    147 [1969E - Unique Array](/contest/1969/problem/E "Educational Codeforces Round 165 (Rated for Div. 2)")
    148 
    149 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    150 
    151 **Tutorial**
    152 
    153 Tutorial is loading...
    154 
    155 **Solution (Neon)**
    156 
    157 ```
    158 #include <bits/stdc++.h>
    159  
    160 using namespace std;
    161 
    162 #define sz(a) int((a).size())
    163 
    164 vector<int> t, p;
    165 
    166 void push(int v) {
    167   if (v * 2 + 2 >= sz(t)) return;
    168   t[v * 2 + 1] += p[v]; p[v * 2 + 1] += p[v];
    169   t[v * 2 + 2] += p[v]; p[v * 2 + 2] += p[v];
    170   p[v] = 0;
    171 }
    172 
    173 void upd(int v, int l, int r, int L, int R, int x) {
    174   if (L >= R) return;
    175   if (l == L && r == R) {
    176     t[v] += x; p[v] += x;
    177     return;
    178   }
    179   int m = (l + r) / 2;
    180   push(v);
    181   upd(v * 2 + 1, l, m, l, min(m, R), x);
    182   upd(v * 2 + 2, m, r, max(m, L), R, x);
    183   t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
    184 }
    185 
    186 int get(int v, int l, int r, int L, int R) {
    187   if (L >= R) return 1e9;
    188   if (l == L && r == R) return t[v];
    189   int m = (l + r) / 2;
    190   push(v);
    191   return min(
    192     get(v * 2 + 1, l, m, l, min(m, R)),
    193     get(v * 2 + 2, m, r, max(m, L), R)
    194   );
    195 }
    196 
    197 void solve() {
    198   int n;
    199   cin >> n;
    200   vector<int> a(n);
    201   for (auto& x : a) cin >> x, --x;
    202   t = p = vector<int>(4 * n);
    203   vector<vector<int>> pos(n);
    204   int ans = 0, st = 0;
    205   for (int i = 0; i < n; ++i) {
    206     int x = a[i];
    207     pos[x].push_back(i);
    208     int k = sz(pos[x]);
    209     if (k > 0) upd(0, 0, n, st, pos[x][k - 1] + 1, +1);
    210     if (k > 1) upd(0, 0, n, st, pos[x][k - 2] + 1, -2);
    211     if (k > 2) upd(0, 0, n, st, pos[x][k - 3] + 1, +1);
    212     if (get(0, 0, n, st, i + 1) == 0) {
    213       ans += 1;
    214       st = i + 1;
    215     }
    216   }
    217   cout << ans << '\n';
    218 }
    219 
    220 int main() {
    221   int t;
    222   cin >> t;
    223   while (t--) solve();
    224 }
    225 ```
    226 
    227 [1969F - Card Pairing](/contest/1969/problem/F "Educational Codeforces Round 165 (Rated for Div. 2)")
    228 
    229 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    230 
    231 **Tutorial**
    232 
    233 Tutorial is loading...
    234 
    235 **Solution (BledDest)**
    236 
    237 ```
    238 #include<bits/stdc++.h>
    239 
    240 using namespace std;
    241 
    242 mt19937_64 rnd(12341234);
    243 
    244 int n, k;
    245 vector<int> deck;
    246 vector<int> dp;
    247 vector<vector<bool>> odd;
    248 vector<bool> full_odd;
    249 vector<long long> val;
    250 vector<long long> hs;      
    251 
    252 bool bad(const vector<bool>& v)
    253 {
    254     for(int i = 0; i < k; i++)
    255         if(!v[i])
    256             return false;
    257     return true;
    258 }
    259 
    260 vector<bool> inv(const vector<bool>& v)
    261 {
    262     vector<bool> res(k);
    263     for(int i = 0; i < k; i++)
    264         res[i] = !v[i];
    265     return res;
    266 }
    267 
    268 vector<bool> get_suffix(int l)
    269 {
    270     vector<bool> v(k);                     
    271     for(int i = l; i < n; i++) v[deck[i]] = !v[deck[i]];
    272     return v;
    273 }
    274 
    275 int get_next(long long cur, int x)
    276 {
    277     for(int i = x; i <= n; i += 2)
    278         if(hs[i] == cur)
    279             return i;
    280     return -1;
    281 }                
    282 
    283 int main()
    284 {
    285     cin >> n >> k;
    286     deck.resize(n);
    287     for(int i = 0; i < n; i++) cin >> deck[i];
    288     for(int i = 0; i < n; i++) --deck[i];
    289     val.resize(k);
    290     for(int i = 0; i < k; i++)
    291         while(val[i] == 0)
    292             val[i] = rnd();
    293 
    294     int max_score = 0;
    295     dp.resize(n + 1);
    296     full_odd.resize(k);
    297     odd.resize(n + 1, vector<bool>(k));
    298     hs.resize(n + 1);
    299     long long cur_hash = 0;
    300     for(int i = 0; i < n; i++)
    301     {
    302         cur_hash ^= val[deck[i]];
    303         if(full_odd[deck[i]]) max_score++;
    304         full_odd[deck[i]] = !full_odd[deck[i]];
    305         odd[i + 1] = full_odd;
    306         hs[i + 1] = cur_hash;
    307     }   
    308 
    309     for(int i = k; i <= n; i++)
    310         dp[i] = 1e9;                          
    311     long long start = 0ll;
    312     for(int i = 0; i < k; i++) start ^= val[i];
    313     int pos = get_next(start, k);
    314     if(pos == -1)
    315     {
    316         cout << max_score << endl;  
    317     }
    318     else
    319     {
    320         dp[pos] = 0;
    321         int ans = 1e9;
    322         for(int p = k; p <= n; p += 2)
    323         {
    324             if(dp[p] > 1e8) continue;   
    325             vector<bool> suff = get_suffix(p);
    326             vector<int> o, e;
    327             for(int j = 0; j < k; j++)
    328                 if(suff[j])
    329                     e.push_back(j);
    330                 else
    331                     o.push_back(j);
    332             int es = e.size();
    333             int os = o.size();
    334             bool flag = true;
    335             for(int i = 0; i < os && flag; i++)
    336                 for(int j = 0; j < i && flag; j++)
    337                 {
    338                     int x = o[i];
    339                     int y = o[j];
    340                     int add = 0;         
    341                     long long h = hs[p] ^ val[x] ^ val[y];
    342                     int pos = get_next(h, p);
    343                     if(pos == -1)                  
    344                     {
    345                         flag = false;
    346                         ans = min(ans, dp[p] + add);
    347                     }
    348                     else
    349                         dp[pos] = min(dp[pos], dp[p] + add);
    350                 }
    351 
    352             for(int i = 0; i < os && flag; i++)
    353                 for(int j = 0; j < es && flag; j++)
    354                 {
    355                     int x = o[i];
    356                     int y = e[j];
    357                     int add = 1;         
    358                     long long h = hs[p] ^ val[x] ^ val[y];
    359                     int pos = get_next(h, p);    
    360                     if(pos == -1)
    361                     {
    362                         flag = false;
    363                         ans = min(ans, dp[p] + add);
    364                     }
    365                     else
    366                         dp[pos] = min(dp[pos], dp[p] + add);
    367                 }
    368 
    369             for(int i = 0; i < es && flag; i++)
    370                 for(int j = 0; j < i && flag; j++)
    371                 {
    372                     int x = e[i];
    373                     int y = e[j];
    374                     int add = 2;                             
    375                     long long h = hs[p] ^ val[x] ^ val[y];
    376                     int pos = get_next(h, p);
    377                     if(pos == -1)
    378                     {
    379                         flag = false;
    380                         ans = min(ans, dp[p] + add);
    381                     }
    382                     else
    383                         dp[pos] = min(dp[pos], dp[p] + add);
    384                 }
    385         }
    386         cout << max_score - ans << endl;
    387     }       
    388 }
    389 ```