codeforces-scrape

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

1028.md (16178B)


      1 Source: https://codeforces.com/blog/entry/61493
      2 
      3 Thanks [bmerry](/profile/bmerry "Legendary Grandmaster bmerry") for posting his solutions, we gently took some of them as a base for editorial.
      4 
      5 Tutorial is loading...
      6 
      7 Problem author: [VadymKa](/profile/VadymKa "Expert VadymKa")
      8 
      9 Problem developers: [riadwaw](/profile/riadwaw "Grandmaster riadwaw"), [malcolm](/profile/malcolm "Master malcolm")
     10 
     11 **Code**
     12 
     13 ```
     14 static class SquareInside {
     15         final int inf = (int) 1e9;
     16 
     17         public void solve(int testNumber, InputReader in, PrintWriter out) {
     18             int n = in.readInt(), m = in.readInt();
     19             char[][] s = new char[n][];
     20             for (int i = 0; i < n; i++) {
     21                 s[i] = in.readWord().toCharArray();
     22             }
     23             int minX = inf, maxX = -inf, minY = inf, maxY = -inf;
     24             for (int i = 0; i < n; i++) {
     25                 for (int j = 0; j < m; j++) {
     26                     if (s[i][j] == 'B') {
     27                         minX = Math.min(minX, i);
     28                         minY = Math.min(minY, j);
     29                         maxX = Math.max(maxX, i);
     30                         maxY = Math.max(maxY, j);
     31                     }
     32                 }
     33             }
     34             out.print((minX + maxX) / 2 + 1);
     35             out.print(' ');
     36             out.println((minY + maxY) / 2 + 1);
     37         }
     38 
     39     }
     40 ```
     41 
     42 Tutorial is loading...
     43 
     44 Problem author: [VadymKa](/profile/VadymKa "Expert VadymKa")
     45 
     46 Problem developers: [riadwaw](/profile/riadwaw "Grandmaster riadwaw"), [malcolm](/profile/malcolm "Master malcolm"), [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma"), [Errichto](/profile/Errichto "International Grandmaster Errichto")
     47 
     48 **Code**
     49 
     50 ```
     51   int len = 400;
     52   cout << string(len, '5') << "\n";
     53   cout << (string(len - 1, '4') + '5') << "\n";
     54 ```
     55 
     56 Tutorial is loading...
     57 
     58 Problem author: [malcolm](/profile/malcolm "Master malcolm")
     59 
     60 Problem developers: [yarrr](/profile/yarrr "Candidate Master yarrr"), [Edvard](/profile/Edvard "Candidate Master Edvard"), [malcolm](/profile/malcolm "Master malcolm"), [Errichto](/profile/Errichto "International Grandmaster Errichto")
     61 
     62 **Code**
     63 
     64 ```
     65 static class Rectangle {
     66         public Point topLeft, bottomRight;
     67 
     68         public Rectangle(Point topLeft, Point bottomRight) {
     69             this.topLeft = topLeft;
     70             this.bottomRight = bottomRight;
     71         }
     72 
     73         public Rectangle intersect(Rectangle other) {
     74             if (other == null) {
     75                 return null;
     76             }
     77             int x0 = Math.max(topLeft.x, other.topLeft.x);
     78             int y0 = Math.max(topLeft.y, other.topLeft.y);
     79             int x1 = Math.min(bottomRight.x, other.bottomRight.x);
     80             int y1 = Math.min(bottomRight.y, other.bottomRight.y);
     81             if (x0 > x1 || y0 > y1) {
     82                 return null;
     83             }
     84             return new Rectangle(new Point(x0, y0), new Point(x1, y1));
     85         }
     86     }
     87 
     88     private void solve() throws IOException {
     89         int rectanglesCount = nextInt();
     90         Rectangle[] rectangles = new Rectangle[rectanglesCount];
     91         for (int i = 0; i < rectanglesCount; i++) {
     92             Point topLeft = new Point(nextInt(), nextInt());
     93             Point bottomRight = new Point(nextInt(), nextInt());
     94             rectangles[i] = new Rectangle(topLeft, bottomRight);
     95         }
     96         Rectangle[] prefixIntersection = new Rectangle[rectanglesCount + 1];
     97         Rectangle[] suffixIntersection = new Rectangle[rectanglesCount + 1];
     98         prefixIntersection[0] = suffixIntersection[0] = new Rectangle(
     99             new Point(Integer.MIN_VALUE, Integer.MIN_VALUE),
    100             new Point(Integer.MAX_VALUE, Integer.MAX_VALUE)
    101         );
    102         for (int i = 1; i <= rectanglesCount; i++) {
    103             prefixIntersection[i] = rectangles[i - 1].intersect(prefixIntersection[i - 1]);
    104             suffixIntersection[i] = rectangles[rectanglesCount - i].intersect(suffixIntersection[i - 1]);
    105         }
    106 
    107         for (int i = 0; i <= rectanglesCount; i++) {
    108             if (prefixIntersection[i] != null) {
    109                 Rectangle intersection = prefixIntersection[i].intersect(suffixIntersection[rectanglesCount - i - 1]);
    110                 if (intersection != null) {
    111                     out.println(intersection.topLeft);
    112                     return;
    113                 }
    114             }
    115         }
    116         throw new AssertionError();
    117     }
    118 ```
    119 
    120 **Bonus:** Solve the problem, if you need to find intersection of some *n* - *k* of *n* rectangles, if *k* ≤ 10. Without data structures.
    121 
    122 Tutorial is loading...
    123 
    124 Problem author: [Errichto](/profile/Errichto "International Grandmaster Errichto")
    125 
    126 Problem developers: [zemen](/profile/zemen "International Grandmaster zemen"), [Errichto](/profile/Errichto "International Grandmaster Errichto"), [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma"), [riadwaw](/profile/riadwaw "Grandmaster riadwaw")
    127 
    128 **Code**
    129 
    130 ```
    131 #include <bits/stdc++.h>
    132 using namespace std;
    133 using ll = long long;
    134 using ld = long double;
    135 
    136 const int mod = 1e9 + 7;
    137 
    138 signed main() {
    139 #ifdef LOCAL
    140   assert(freopen("test.in", "r", stdin));
    141 #endif
    142   int n;
    143   cin >> n;
    144   map<int, int> a{{INT_MIN, 1}, {INT_MAX, 0}};
    145   set<int*> non0{&a.begin()->second};
    146   for (int i = 0; i < n; ++i) {
    147     string t;
    148     int x;
    149     cin >> t >> x;
    150     if (t == "ADD") {
    151       auto it = a.lower_bound(x);
    152       assert(it != a.begin());
    153       --it;
    154       int ways = it->second;
    155       auto m = a.emplace(x, ways).first;
    156       non0.insert(&m->second);
    157     } else {
    158       auto m = a.find(x);
    159       assert(m != a.end() && m != a.begin());
    160       auto it = prev(m);
    161       auto& w = it->second;
    162       w = (w + m->second) % mod;
    163       non0.insert(&it->second);
    164       non0.erase(&m->second);
    165       a.erase(m);
    166       for (auto it2 = non0.begin(); it2 != non0.end(); ) {
    167         if (*it2 == &it->second) {
    168           ++it2;
    169         } else {
    170           *(*it2) = 0;
    171           it2 = non0.erase(it2);
    172         }
    173       }
    174     }
    175   }
    176   int res = 0;
    177   for (auto p : a) {
    178     res = (res + p.second) % mod;
    179   }
    180   cout << res << '\n';
    181 }
    182 ```
    183 
    184 Tutorial is loading...
    185 
    186 Problem author: [zemen](/profile/zemen "International Grandmaster zemen")
    187 
    188 Problem developers: [yarrr](/profile/yarrr "Candidate Master yarrr"), [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma")
    189 
    190 **Code**
    191 
    192 ```
    193 void solve(__attribute__((unused)) bool read) {
    194   int n;
    195   cin >> n;
    196   vector<int> b(n, 0);
    197   for (int i = 0; i < n; ++i) {
    198     cin >> b[i];
    199   }
    200   int mx = *max_element(all(b));
    201   int start_pos = -1;
    202   for (int i = 0; i < n; ++i) {
    203     if (b[i] == mx && b[(i - 1 + n) % n] != mx) {
    204       start_pos = i;
    205       break;
    206     }
    207   }
    208   if (start_pos == -1) {
    209     if (mx == 0) {
    210       cout << "YES\n";
    211       for (int i = 0; i < n; ++i) {
    212         cout << 1 << " \n"[i + 1 == n];
    213       }
    214       return;
    215     }
    216     cout << "NO\n";
    217     return;
    218   }
    219   auto a = b;
    220   for (int i = 1; i < n; ++i) {
    221     int pos = (start_pos - i + n) % n, prev_pos = (start_pos + 1 - i + n) % n;
    222     a[pos] += a[prev_pos];
    223     if (i == 1) {
    224       a[pos] += mx;
    225     }
    226   }
    227   cout << "YES\n";
    228   for (int x : a) {
    229     cout << x << " ";
    230   }
    231   cout << "\n";
    232 
    233 }
    234 ```
    235 
    236 Tutorial is loading...
    237 
    238 Problem author: [Errichto](/profile/Errichto "International Grandmaster Errichto")
    239 
    240 Problem developers: [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma"), [malcolm](/profile/malcolm "Master malcolm")
    241 
    242 **Code**
    243 
    244 ```
    245 struct Point {
    246   int x, y;
    247   Point() {}
    248   Point(int x, int y) : x(x), y(y) {}
    249   void scan() {
    250     cin >> x >> y;
    251   }
    252   auto key() const {
    253     return make_pair(x, y);
    254   }
    255   bool operator < (const Point& ot) const {
    256     return key() < ot.key();
    257   }
    258   bool operator == (const Point& ot) const {
    259     return key() == ot.key();
    260   }
    261   Point operator + (const Point& ot) const {
    262     return Point(x + ot.x, y + ot.y);
    263   }
    264   li sqr_dist() {
    265     return x * 1LL * x + y * 1LL * y;
    266   }
    267   void normalize() {
    268     auto g = gcd(x, y);
    269     x /= g;
    270     y /= g;
    271   }
    272 };
    273 
    274 struct Hasher {
    275   size_t operator () (const Point& pt) const {
    276     return pt.x * 2352345 + pt.y;
    277   }
    278 };
    279 
    280 enum Type {
    281   INSERT = 1,
    282   REMOVE = 2,
    283   QUERY = 3
    284 };
    285 
    286 struct Query {
    287   Type type;
    288   Point pt;
    289   int dist_id;
    290   void scan() {
    291     int type1;
    292     cin >> type1;
    293     type = Type(type1);
    294     pt.scan();
    295   }
    296 };
    297 
    298 void solve(__attribute__((unused)) bool read) {
    299   int Q;
    300   cin >> Q;
    301   vector<Query> queries(Q);
    302   map<li, vector<Point>> all_points;
    303   vector<li> dists;
    304   set<Point> have;
    305   for (int i = 0; i < Q; ++i) {
    306     queries[i].scan();
    307     auto& pt = queries[i].pt;
    308     if (queries[i].type != QUERY) {
    309       all_points[pt.sqr_dist()].push_back(pt);
    310       dists.push_back(pt.sqr_dist());
    311     } else {
    312       pt.normalize();
    313     }
    314   }
    315   make_unique(dists);
    316   for (auto& q : queries) {
    317     q.dist_id = (int)(lower_bound(all(dists), q.pt.sqr_dist()) - dists.begin());
    318   }
    319   vector<vector<char>> has_point(dists.size());
    320   vector<vector<Point>> points_by_dist_id(dists.size());
    321   vector<vector<vector<Point>>> sum_points(dists.size());
    322   unordered_map<Point, pair<int, int>, Hasher> point_position;
    323   for (auto& item : all_points) {
    324     make_unique(item.second);
    325     int dist_id = (int)(lower_bound(all(dists), item.first) - dists.begin());
    326     has_point[dist_id].assign(item.second.size(), false);
    327     points_by_dist_id[dist_id] = item.second;
    328     sum_points[dist_id].assign(item.second.size(), vector<Point>(item.second.size()));
    329     for (int i = 0; i < item.second.size(); ++i) {
    330       point_position[item.second[i]] = {dist_id, i};
    331       for (int j = 0; j < item.second.size(); ++j) {
    332         sum_points[dist_id][i][j] = item.second[i] + item.second[j];
    333         sum_points[dist_id][i][j].normalize();
    334       }
    335     }
    336   }
    337   unordered_map<Point, int, Hasher> on_line;
    338   unordered_map<Point, int, Hasher> good_pairs;
    339 
    340   auto change_on_line = [&] (Point pt, bool add) {
    341     pt.normalize();
    342     if (add) {
    343       ++on_line[pt];
    344     } else {
    345       assert(on_line[pt] > 0);
    346       --on_line[pt];
    347     }
    348   };
    349 
    350   int n_points = 0;
    351   for (auto& cur_q : queries) {
    352     auto& pt = cur_q.pt;
    353     int dist_id = cur_q.dist_id;
    354     if (cur_q.type == INSERT) {
    355       ++n_points;
    356       int pos = point_position[pt].second;
    357       assert(!has_point[dist_id][pos]);
    358       change_on_line(pt, true);
    359       for (int i = 0; i < points_by_dist_id[dist_id].size(); ++i) {
    360         if (i == pos || !has_point[dist_id][i]) {
    361           continue;
    362         }
    363         ++good_pairs[sum_points[dist_id][i][pos]];
    364       }
    365       has_point[dist_id][pos] = true;
    366     } else if (cur_q.type == REMOVE) {
    367       --n_points;
    368       int pos = point_position[pt].second;
    369       assert(has_point[dist_id][pos]);
    370       change_on_line(pt, false);
    371       for (int i = 0; i < points_by_dist_id[dist_id].size(); ++i) {
    372         if (i == pos || !has_point[dist_id][i]) {
    373           continue;
    374         }
    375         --good_pairs[sum_points[dist_id][i][pos]];
    376       }
    377       has_point[dist_id][pos] = false;
    378     } else if (cur_q.type == QUERY) {
    379       pt.normalize();
    380       cout << n_points - 2 * good_pairs[pt] - on_line[pt] << "\n";
    381     }
    382   }
    383 
    384 }
    385 ```
    386 
    387 Tutorial is loading...
    388 
    389 Problem author: [zeliboba](/profile/zeliboba "Grandmaster zeliboba")
    390 
    391 Problem developers: [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma"), [riadwaw](/profile/riadwaw "Grandmaster riadwaw")
    392 
    393 **Code**
    394 
    395 ```
    396 private static final int MAX_WIDTH = 10000;
    397     private static final int QUERIES = 5;
    398     public static final long INF = 20000000000000000L;
    399     long[][] memo = new long[QUERIES + 1][MAX_WIDTH + 1];
    400 
    401     long dp(int guesses, long l) {
    402         if (guesses == 0) {
    403             return l;
    404         }
    405         if (l > MAX_WIDTH) {
    406             return Math.min(INF, dp(guesses, MAX_WIDTH) + l - MAX_WIDTH);
    407         }
    408 
    409         if (memo[guesses][(int) l] != 0) {
    410             return memo[guesses][(int) l];
    411         }
    412         long ans = l;
    413         for (int i = 0; i < l; ++i) {
    414             ans = dp(guesses - 1, ans);
    415             ++ans;
    416         }
    417         ans = dp(guesses - 1, ans);
    418         return memo[guesses][(int) l] = Math.min(ans, INF);
    419     }
    420     private void run() throws IOException {
    421         long l = 1;
    422         long r = dp(QUERIES, 1);
    423         for (int queriesNext = QUERIES - 1; queriesNext >= 0; --queriesNext) {
    424             List<Long> query = new ArrayList<>();
    425             long curL = l;
    426             for (int i = 0, e = (int)Math.min(l, MAX_WIDTH); i < e; ++i) {
    427                 long end = dp(queriesNext, curL);
    428                 query.add(end);
    429                 curL = end + 1;
    430             }
    431             assert r == dp(queriesNext, curL);
    432             out.print(query.size());
    433             for (long x: query) {
    434                 out.print(" ");
    435                 out.print(x);
    436             }
    437             out.println();
    438             out.flush();
    439             System.out.flush();
    440 
    441             int ans = readInt();
    442             if (ans < 0) {
    443                 return;
    444             }
    445             if (ans > 0) {
    446                 l = query.get(ans - 1) + 1;
    447             }
    448             if (ans != query.size()) {
    449                 r = query.get(ans);
    450             }
    451 
    452             assert dp(queriesNext, l) == r;
    453         }
    454     }
    455 ```
    456 
    457 Tutorial is loading...
    458 
    459 Problem author: [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma")
    460 
    461 Problem developers: [Kostroma](/profile/Kostroma "Legendary Grandmaster Kostroma"), [riadwaw](/profile/riadwaw "Grandmaster riadwaw"), [gchebanov](/profile/gchebanov "International Master gchebanov"), [malcolm](/profile/malcolm "Master malcolm")
    462 
    463 **Code**
    464 
    465 ```
    466 const int C = 5032107 + 1;
    467 int lp[C];
    468 int fred[C];
    469 int num_primes[C];
    470 
    471 const int MAX_DIVISORS = 7;
    472 const int MAX_ANS = 2 * MAX_DIVISORS;
    473 
    474 int max_left[MAX_DIVISORS + 1][C];
    475 int max_border[MAX_ANS + 1];
    476 
    477 vector<int> cur_primes;
    478 
    479 vector<int> divs;
    480 
    481 void get_divisors(int n) {
    482     divs = {1};
    483     while (n > 1) {
    484         int p = lp[n];
    485         n /= p;
    486         int sz = divs.size();
    487         for (int i = 0; i < sz; ++i) {
    488             divs.push_back(divs[i] * p);
    489         }
    490     }
    491 }
    492 
    493 void solve(bool read) {
    494     vector<int> pr;
    495     for (int i = 2; i < C; ++i) {
    496         if (lp[i] == 0) {
    497             lp[i] = i;
    498             pr.push_back(i);
    499         }
    500         for (int j = 0; j < pr.size() && pr[j] <= lp[i] && i * pr[j] < C; ++j) {
    501             lp[i * pr[j]] = pr[j];
    502         }
    503     }
    504     fred[1] = 1;
    505     for (int i = 2; i < C; ++i) {
    506         int p = lp[i];
    507         int cur = i / p;
    508         if (cur % p == 0) {
    509             fred[i] = fred[cur / p];
    510             num_primes[i] = num_primes[cur / p];
    511         } else {
    512             fred[i] = p * fred[cur];
    513             num_primes[i] = num_primes[cur] + 1;
    514         }
    515     }
    516 
    517     for (int i = 0; i < C; ++i) {
    518         for (int j = 0; j <= MAX_DIVISORS; ++j) {
    519             max_left[j][i] = -1;
    520         }
    521     }
    522     memset(max_border, -1, sizeof(max_border));
    523 
    524     int n;
    525     cin >> n;
    526     int Q;
    527     cin >> Q;
    528     vector<int> a(n);
    529     for (int i = 0; i < n; ++i) {
    530         cin >> a[i];
    531         a[i] = fred[a[i]];
    532     }
    533 
    534     vector<vector<pair<int, int>>> queries(n);
    535 
    536     vector<int> res(Q);
    537     for (int i = 0; i < Q; ++i) {
    538         int l, r;
    539         cin >> l >> r;
    540         --l; --r;
    541         queries[r].push_back({l, i});
    542     }
    543 
    544     for (int i = 0; i < n; ++i) {
    545         get_divisors(a[i]);
    546         for (int d : divs) {
    547             int first_add = num_primes[a[i]] - num_primes[d];
    548             for (int prev_ans = 0; prev_ans <= MAX_DIVISORS; ++prev_ans) {
    549                 int cur_left = max_left[prev_ans][d];
    550                 int cur_ans = first_add + prev_ans;
    551                 if (cur_ans <= MAX_ANS) {
    552                     relax_max(max_border[cur_ans], cur_left);
    553                 }
    554             }
    555         }
    556         for (int d : divs) {
    557             int first_add = num_primes[a[i]] - num_primes[d];
    558             relax_max(max_left[first_add][d], i);
    559         }
    560         for (auto q : queries[i]) {
    561             res[q.second] = MAX_ANS + 1;
    562             for (int cur_ans = 0; cur_ans <= MAX_ANS; ++cur_ans) {
    563                 if (max_border[cur_ans] >= q.first) {
    564                     res[q.second] = cur_ans;
    565                     break;
    566                 }
    567             }
    568             assert(res[q.second] <= MAX_ANS);
    569         }
    570     }
    571 
    572     int sum_ans = 0;
    573     for (int i = 0; i < Q; ++i) {
    574         cout << res[i] << '\n';
    575     }
    576 }
    577 ```