codeforces-scrape

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

807.md (13928B)


      1 Source: https://codeforces.com/blog/entry/51883
      2 
      3 Here is the tutorial of VK Cup 2017 Round 3 and Codeforces Round #412. Enjoy!
      4 
      5 **Is it rated?**
      6 
      7 Tutorial is loading...
      8 
      9 **Code**
     10 
     11 ```
     12 n = int(input())
     13 results = []
     14 for i in range(n):
     15     results.append(list(map(int, input().split())))
     16 
     17 for r in results:
     18     if r[0] != r[1]:
     19         print("rated")
     20         exit()
     21 
     22 for i in range(n):
     23     for j in range(i):
     24         if results[i][0] > results[j][0]:
     25             print("unrated")
     26             exit()
     27 
     28 print("maybe")
     29 ```
     30 
     31 **T-Shirt Hunt**
     32 
     33 Tutorial is loading...
     34 
     35 **More efficient code**
     36 
     37 ```
     38 #include <bits/stdc++.h>
     39 
     40 using namespace std;
     41 
     42 int main() {
     43   int p, x, y;
     44   cin >> p >> x >> y;
     45   for (int s = y; ; s++) {
     46     if (s % 50 != x % 50) {
     47       continue;
     48     }
     49     bool me = false;
     50     int i = s / 50 % 475;
     51     for (int j = 0; j < 25; j++) {
     52       i = (i * 96 + 42) % 475;
     53       if (i + 26 == p) {
     54         me = true;
     55         break;
     56       }
     57     }
     58     if (me) {
     59       printf("%d\n", (max(0, s - x) + 50) / 100);
     60       break;
     61     }
     62   }
     63   return 0;
     64 }
     65 ```
     66 
     67 **Less efficient code**
     68 
     69 ```
     70 p, x, y = map(int, input().split())
     71 
     72 def check(s):
     73     i = (s // 50) % 475
     74     for t in range(25):
     75         i = (i * 96 + 42) % 475
     76         if 26 + i == p:
     77             return True
     78     return False
     79 
     80 for up in range(500):
     81     for down in range(500):
     82         if x + 100 * up - 50 * down >= y and check(x + 100 * up - 50 * down):
     83             print(up)
     84             exit()
     85 
     86 assert(False)
     87 ```
     88 
     89 **Success Rate**
     90 
     91 Tutorial is loading...
     92 
     93 **Binary search solution code**
     94 
     95 ```
     96 #include <bits/stdc++.h>
     97 
     98 using namespace std;
     99 
    100 typedef long long ll;
    101 
    102 bool check(ll x, ll y, ll p, ll q, ll t) {
    103   return p * t >= x && q * t - p * t >= y - x;
    104 }
    105 
    106 void solve() {
    107   ll x, y, p, q;
    108   scanf("%lld%lld%lld%lld", &x, &y, &p, &q);
    109 
    110   ll l = -1;
    111   ll r = (ll) 1e9;
    112 
    113   if (!check(x, y, p, q, r)) {
    114     printf("-1\n");
    115     return;
    116   }
    117 
    118   while (r - l > 1) {
    119     ll m = (l + r) / 2;
    120     if (check(x, y, p, q, m)) {
    121       r = m;
    122     } else {
    123       l = m;
    124     }
    125   }
    126 
    127   printf("%lld\n", r * q - y);
    128 }
    129 
    130 int main() {
    131   int t;
    132   scanf("%d", &t);
    133 
    134   while (t--) {
    135     solve();
    136   }
    137 
    138   return 0;
    139 }
    140 ```
    141 
    142 **Formula solution code**
    143 
    144 ```
    145 #include <bits/stdc++.h>
    146 
    147 using namespace std;
    148 
    149 int main() {
    150   int tt;
    151   cin >> tt;
    152   while (tt--) {
    153     int x, y, p, q;
    154     cin >> x >> y >> p >> q;
    155     if (p == 0) {
    156       cout << (x == 0 ? 0 : -1) << endl;
    157       continue;
    158     }
    159     if (p == q) {
    160       cout << (x == y ? 0 : -1) << endl;
    161       continue;
    162     }
    163     int t1 = (x + p - 1) / p;
    164     int t2 = ((y - x) + (q - p) - 1) / (q - p);
    165     cout << (q * 1LL * max(t1, t2) - y) << endl;
    166   }
    167   return 0;
    168 }
    169 ```
    170 
    171 **Dynamic Problem Scoring**
    172 
    173 Tutorial is loading...
    174 
    175 **Code**
    176 
    177 ```
    178 #include <bits/stdc++.h>
    179 
    180 using namespace std;
    181 
    182 const int N = 123456;
    183 const int m = 5;
    184 const int k = 6;
    185 
    186 int a[N][m];
    187 int score[N];
    188 int cost[m];
    189 int solved[m];
    190 
    191 int main() {
    192   int n;
    193   scanf("%d", &n);
    194   for (int i = 0; i < n; i++) {
    195     for (int j = 0; j < m; j++) {
    196       scanf("%d", a[i] + j);
    197       if (a[i][j] != -1) {
    198         solved[j]++;
    199       }
    200     }
    201   }
    202   for (int bots = 0; bots <= ((1 << (k - 1)) - 1) * n; bots++) {
    203     for (int j = 0; j < m; j++) {
    204       int total = n + bots;
    205       int cur = solved[j];
    206       if (a[0][j] != -1 && a[1][j] != -1 && a[0][j] > a[1][j]) {
    207         cur += bots;
    208       }
    209       cost[j] = 500;
    210       while (cost[j] < 500 * k && 2 * cur <= total) {
    211         cur *= 2;
    212         cost[j] += 500;
    213       }
    214     }
    215     for (int i = 0; i < 2; i++) {
    216       score[i] = 0;
    217       for (int j = 0; j < m; j++) {
    218         if (a[i][j] != -1) {
    219           score[i] += cost[j] / 250 * (250 - a[i][j]);
    220         }
    221       }
    222     }
    223     if (score[0] > score[1]) {
    224       printf("%d\n", bots);
    225       return 0;
    226     }
    227   }
    228   printf("%d\n", -1);
    229   return 0;
    230 }
    231 ```
    232 
    233 **Prairie Partition**
    234 
    235 Tutorial is loading...
    236 
    237 **Code with the second optimization**
    238 
    239 ```
    240 n = int(input())
    241 a = sorted(list(map(int, input().split())))
    242 
    243 maxe = max(a)
    244 cnt = []
    245 cur = 1
    246 k = 0
    247 i = 0
    248 while i < n:
    249     cnt.append(0)
    250     while i < n and a[i] < cur:
    251         cnt[2 * k] += 1
    252         i += 1
    253     cnt.append(0)
    254     while i < n and a[i] == cur:
    255         cnt[2 * k + 1] += 1
    256         i += 1
    257     k += 1
    258     cur *= 2
    259 cnt.append(0)
    260 cnt.append(0)
    261 maxe = len(cnt) - 1
    262 
    263 maxk = cnt[1]
    264 was = False
    265 for l in range(maxk):
    266     cur = 1
    267     while cnt[cur] > 0:
    268         cnt[cur] -= 1
    269         cur += 2
    270     cnt[cur] -= 1
    271     cursum = 0
    272     ok = True
    273     for t in range(maxe, 0, -1):
    274         cursum += cnt[t]
    275         if cursum > 0:
    276             ok = False
    277             break
    278     if ok:
    279         print(l + 1, end=" ")
    280         was = True
    281 
    282 if not was:
    283     print(-1)
    284 ```
    285 
    286 **Code with both optimizations**
    287 
    288 ```
    289 #include <bits/stdc++.h>
    290 
    291 using namespace std;
    292 
    293 const int MAX = 66;
    294 
    295 int power[MAX + 10];
    296 int between[MAX + 10];
    297 int extra[MAX + 10];
    298 int ende[MAX + 10];
    299 
    300 int main() {
    301   int n;
    302   cin >> n;
    303   for (int i = 0; i < n; i++) {
    304     long long foo;
    305     cin >> foo;
    306     int cc = 0;
    307     bool good = true;
    308     while (foo > 1) {
    309       if (foo & 1) {
    310         good = false;
    311       }
    312       cc++;
    313       foo >>= 1;
    314     }
    315     if (good) {
    316       power[cc]++;
    317     } else {
    318       between[cc]++;
    319     }
    320   }
    321   int low = 1, high = power[0] + 1;
    322   while (low < high) {
    323     int mid = (low + high) >> 1;
    324     int cur = mid;
    325     for (int i = 0; i < MAX; i++) {
    326       extra[i] = power[i] - cur;
    327       int new_cur = min(cur, power[i + 1]);
    328       ende[i] = cur - new_cur;
    329       cur = new_cur;
    330     }
    331     bool fail = false;
    332     int open = 0;
    333     for (int i = MAX - 1; i >= 0; i--) {
    334       open += ende[i];
    335       open -= between[i];
    336       open -= extra[i + 1];
    337       if (open < 0) {
    338         fail = true;
    339         break;
    340       }
    341     }
    342     open -= extra[0];
    343     if (open < 0) {
    344       fail = true;
    345     }
    346     if (fail) {
    347       low = mid + 1;
    348     } else {
    349       high = mid;
    350     }
    351   }
    352   if (low > power[0]) {
    353     cout << -1 << endl;
    354     return 0;
    355   }
    356   for (int i = low; i <= power[0]; i++) {
    357     cout << i << " ";
    358   }
    359   cout << endl;
    360   return 0;
    361 }
    362 ```
    363 
    364 **Perishable Roads**
    365 
    366 Tutorial is loading...
    367 
    368 **Code**
    369 
    370 ```
    371 #include <bits/stdc++.h>
    372 
    373 using namespace std;
    374 
    375 const long long inf = (long long) 1e18;
    376 
    377 const int N = 2010;
    378 
    379 int a[N][N];
    380 long long d[N];
    381 bool used[N];
    382 
    383 int main() {
    384   // reading input data
    385   int n;
    386   scanf("%d", &n);
    387   for (int i = 0; i < n; i++) {
    388     a[i][i] = 0;
    389     for (int j = i + 1; j < n; j++) {
    390       scanf("%d", a[i] + j);
    391       a[j][i] = a[i][j];
    392     }
    393   }
    394   // finding minimum edge weight
    395   int min_edge = a[0][1];
    396   for (int i = 0; i < n; i++) {
    397     for (int j = 0; j < n; j++) {
    398       if (i != j) {
    399         min_edge = min(min_edge, a[i][j]);
    400       }
    401     }
    402   }
    403   // subtracting minimum edge weight from all edge weights
    404   for (int i = 0; i < n; i++) {
    405     for (int j = 0; j < n; j++) {
    406       if (i != j) {
    407         a[i][j] -= min_edge;
    408       }
    409     }
    410   }
    411   // initializing distance array
    412   for (int i = 0; i < n; i++) {
    413     d[i] = inf;
    414     for (int j = 0; j < n; j++) {
    415       if (i != j) {
    416         d[i] = min(d[i], 2LL * a[i][j]);
    417       }
    418     }
    419     used[i] = false;
    420   }
    421   // running Dijkstra
    422   for (int it = 0; it < n; it++) {
    423     long long min_d = inf;
    424     int ver = -1;
    425     for (int i = 0; i < n; i++) {
    426       if (!used[i] && d[i] < min_d) {
    427         min_d = d[i];
    428         ver = i;
    429       }
    430     }
    431     used[ver] = true;
    432     for (int i = 0; i < n; i++) {
    433       d[i] = min(d[i], d[ver] + a[ver][i]);
    434     }
    435   }
    436   // printing result
    437   for (int i = 0; i < n; i++) {
    438     cout << (d[i] + (long long) min_edge * (n - 1)) << endl;
    439   }
    440   return 0;
    441 }
    442 ```
    443 
    444 **Blog Post Rating**
    445 
    446 Tutorial is loading...
    447 
    448 **Code**
    449 
    450 ```
    451 #include <bits/stdc++.h>
    452 
    453 using namespace std;
    454 
    455 inline int signum(int x) {
    456   return (x < 0 ? -1 : (x > 0 ? 1 : 0));
    457 }
    458 
    459 const int inf = (int) 1e9;
    460 
    461 const int N = 500010;
    462 
    463 pair <int, int> a[N];
    464 int pos[N];
    465 
    466 pair <int, int> mn[4 * N];
    467 int add[4 * N];
    468 
    469 void push(int x) {
    470   add[x + x] += add[x];
    471   mn[x + x].first += add[x];
    472   add[x + x + 1] += add[x];
    473   mn[x + x + 1].first += add[x];
    474   add[x] = 0;
    475 }
    476 
    477 void pull(int x) {
    478   mn[x] = min(mn[x + x], mn[x + x + 1]);
    479 }
    480 
    481 void build(int x, int l, int r) {
    482   add[x] = 0;
    483   if (l == r) {
    484     mn[x] = make_pair(a[l].first, l);
    485     return;
    486   }
    487   int y = (l + r) >> 1;
    488   build(x + x, l, y);
    489   build(x + x + 1, y + 1, r);
    490   pull(x);
    491 }
    492 
    493 void modify(int x, int l, int r, int ll, int rr, int v) {
    494   if (ll <= l && r <= rr) {
    495     add[x] -= v;
    496     mn[x].first -= v;
    497     return;
    498   }
    499   push(x);
    500   int y = (l + r) >> 1;
    501   if (ll <= y) {
    502     modify(x + x, l, y, ll, rr, v);
    503   }
    504   if (rr > y) {
    505     modify(x + x + 1, y + 1, r, ll, rr, v);
    506   }
    507   pull(x);
    508 }
    509 
    510 pair <int, int> find_min(int x, int l, int r, int ll, int rr) {
    511   if (ll <= l && r <= rr) {
    512     return mn[x];
    513   }
    514   push(x);
    515   int y = (l + r) >> 1;
    516   pair <int, int> res = make_pair(inf, -1);
    517   if (ll <= y) {
    518     res = min(res, find_min(x + x, l, y, ll, rr));
    519   }
    520   if (rr > y) {
    521     res = min(res, find_min(x + x + 1, y + 1, r, ll, rr));
    522   }
    523   pull(x);
    524   return res;
    525 }
    526 
    527 int main() {
    528   int n;
    529   scanf("%d", &n);
    530   for (int i = 0; i < n; i++) {
    531     scanf("%d", &a[i].first);
    532     a[i].second = i;
    533   }
    534   sort(a, a + n);
    535   for (int i = 0; i < n; i++) {
    536     pos[a[i].second] = i;
    537   }
    538   build(1, 0, n - 1);
    539   set <int> minus, zero, plus;
    540   for (int id = 0; id < n; id++) {
    541     int i = pos[id];
    542     auto p = find_min(1, 0, n - 1, i, i);
    543     int vote = signum(p.first);
    544     if (vote == 0) {
    545       zero.insert(i);
    546     } else {
    547       if (vote == -1) {
    548         minus.insert(i);
    549         modify(1, 0, n - 1, i, n - 1, -1);
    550         int last_minus = *(--minus.end());
    551         if (a[last_minus].first == 1 - (int) minus.size()) {
    552           minus.erase(last_minus);
    553           modify(1, 0, n - 1, last_minus, n - 1, 1);
    554           zero.insert(last_minus);
    555         } else {
    556           if (!zero.empty()) {
    557             int first_zero = *(zero.begin());
    558             zero.erase(first_zero);
    559             plus.insert(first_zero);
    560             modify(1, 0, n - 1, first_zero, n - 1, 1);
    561           }
    562         }
    563       } else {
    564         plus.insert(i);
    565         modify(1, 0, n - 1, i, n - 1, 1);
    566         auto q = find_min(1, 0, n - 1, i, n - 1);
    567         if (q.first == -1) {
    568           int pos = q.second;
    569           plus.erase(pos);
    570           modify(1, 0, n - 1, pos, n - 1, -1);
    571           zero.insert(pos);
    572         }
    573       }
    574     }
    575     printf("%d\n", (int) plus.size() - (int) minus.size());
    576   }
    577   return 0;
    578 }
    579 ```
    580 
    581 **Test Data Generation**
    582 
    583 Tutorial is loading...
    584 
    585 **Code**
    586 
    587 ```
    588 #include <bits/stdc++.h>
    589 
    590 using namespace std;
    591 
    592 using ll = long long;
    593 using ld = long double;
    594 using D = double;
    595 using uint = unsigned int;
    596 template<typename T>
    597 using pair2 = pair<T, T>;
    598 
    599 #ifdef WIN32
    600     #define LLD "%I64d"
    601 #else
    602     #define LLD "%lld"
    603 #endif
    604 
    605 #define pb push_back
    606 #define mp make_pair
    607 #define all(x) (x).begin(),(x).end()
    608 #define fi first
    609 #define se second
    610 
    611 const long double pi = acos((ld)-1.0);
    612 
    613 const int maxn = 1 << 16;
    614 
    615 typedef complex<double> comp;
    616 
    617 comp oddc[maxn], evenc[maxn], tmp[maxn];
    618 comp w[maxn], invw[maxn];
    619 ll odd[maxn], even[maxn];
    620 int oldodd[maxn], oldeven[maxn];
    621 int btr[maxn];
    622 int n, A, mod;
    623 int st2;
    624 int answer;
    625 
    626 inline int bitrev(int x)
    627 {
    628     return btr[x];
    629 }
    630 
    631 void fft(comp *a, int n, comp *w, comp *res)
    632 {
    633     for (int i = 0; i < n; i++) res[bitrev(i)] = a[i];
    634     for (int len = 2; len <= n; len *= 2)
    635     {
    636         int step = n / len;
    637         for (int i = 0; i < n; i += len)
    638         {
    639             int curw = 0;
    640             for (int j = 0; j < len / 2; j++)
    641             {
    642                 comp x = res[i + j];
    643                 comp y = res[i + len / 2 + j] * w[curw];
    644                 res[i + j] = x + y;
    645                 res[i + len / 2 + j] = x - y;
    646                 curw += step;
    647             }
    648         }
    649     }
    650 }
    651 
    652 void preparefft(int n)
    653 {
    654     for (int i = 0; i < n; i++)
    655     {
    656         int cur = i;
    657         for (int j = 0; (1 << j) < n; j++)
    658         {
    659             btr[i] = (btr[i] << 1) | (cur & 1);
    660             cur >>= 1;
    661         }
    662     }
    663     for (int i = 0; i < n; i++)
    664     {
    665         w[i] = comp(cos(2 * pi / n * i), sin(2 * pi / n * i));
    666         invw[i] = w[i];
    667     }
    668     reverse(invw + 1, invw + n);
    669 }
    670 
    671 void conv(ll *from, comp *to)
    672 {
    673     for (int i = n + 1; i < st2; i++) tmp[i] = 0;
    674     for (int i = 0; i <= n; i++) tmp[i] = from[i];
    675     fft(tmp, st2, w, to);
    676 }
    677 
    678 void convback(comp *from, ll *to)
    679 {
    680     fft(from, st2, invw, tmp);
    681     for (int i = 0; i < st2; i++) tmp[i] /= st2;
    682     for (int i = 0; i <= n; i++)
    683     {
    684         to[i] = (ll)(tmp[i].real() + 0.5);
    685         assert(abs(tmp[i].imag()) < 0.1);
    686     }
    687 }
    688 
    689 void addans()
    690 {
    691     for (int i = 1; i <= n; i += 2) answer = (answer + odd[i]) % mod;
    692 }
    693 
    694 void go(int A)
    695 {
    696     if (A == 1)
    697     {
    698         even[0] = 1;
    699         odd[0] = 0;
    700         odd[1] = 1;
    701         addans();
    702         return;
    703     }
    704     go(A / 2);
    705 
    706     for (int i = 0; i <= n; i++) oldodd[i] = odd[i];
    707     for (int i = 0; i <= n; i++) oldeven[i] = even[i];
    708     conv(even, evenc);
    709     conv(odd, oddc);
    710     for (int i = 0; i < st2; i++)
    711     {
    712         if ((A / 2) % 2 == 0)
    713         {
    714             tie(oddc[i], evenc[i])  = make_pair((oddc[i] + evenc[i]) * oddc[i], (oddc[i] + evenc[i]) * (evenc[i] - (comp)1));
    715         } else
    716         {
    717             tie(evenc[i], oddc[i])  = make_pair((oddc[i] + evenc[i]) * oddc[i], (oddc[i] + evenc[i]) * (evenc[i] - (comp)1));
    718         }
    719     }
    720     convback(oddc, odd);
    721     convback(evenc, even);
    722     for (int i = n + 1; i <= 2 * n; i++)
    723     {
    724         odd[i] = 0;
    725         even[i] = 0;
    726     }
    727     for (int i = 0; i <= n; i++)
    728     {
    729         odd[i] = (odd[i] + oldodd[i]) % mod;
    730         even[i] = (even[i] + oldeven[i]) % mod;
    731     }
    732     if (A % 2 == 1)
    733     {
    734         for (int i = n; i >= 1; i--)
    735         {
    736             odd[i] = (odd[i] + odd[i - 1] + even[i - 1]) % mod;
    737         }
    738     }
    739     addans();
    740 }
    741 
    742 int main()
    743 {
    744     cin >> n >> A >> mod;
    745     if (A == 1)
    746     {
    747         cout << 0 << endl;
    748         return 0;
    749     }
    750     st2 = 0;
    751     while ((1 << st2) <= n) st2++;
    752     st2++;
    753     st2 = 1 << st2;
    754     preparefft(st2);
    755     go(A / 2);
    756     cout << answer << endl;
    757     return 0;
    758 }
    759 ```