codeforces-scrape

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

989.md (9112B)


      1 Source: https://codeforces.com/blog/entry/59968
      2 
      3 Selamat petang!
      4 
      5 The curtain has fallen on [Codeforces Round 487 (Div. 2)](/contest/989 "Codeforces Round 487 (Div. 2)"). Have you enjoyed the problems themselves? Or the stories? Or both? Neither?
      6 
      7 I hadn't ever intended to create a hard contest, believe me... (╥﹏╥) The author will try to find ways to estimate the difficulty better in the future. Also, stronger pretests, notes taken.
      8 
      9 Anyways, hope you've all enjoyed the challenges you've faced, and gained something from this round. Congratulations to those who performed well, and commiserations to those waiting for their next chance to shine (^_−)−☆
     10 
     11 Below are the tutorials of all problems. Feel free to point out mistakes (if any) or share your ideas in the comments! I might be overcomplicating or confusing something > <
     12 
     13 Tutorial is loading...
     14 
     15 **Short Ruby solution**
     16 
     17 ```
     18 puts gets.codepoints.each_cons(3).any?{|x,y,z|x*y*z==287430}?'Yes':'No'
     19 ```
     20 
     21 Tutorial is loading...
     22 
     23 **Noam's C++ solution**
     24 
     25 ```
     26 #include <bits/stdc++.h>
     27 #define endl '\n'
     28 #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
     29 #define finish(x) return cout << x << endl, 0
     30 using namespace std;
     31 
     32 string s, t;
     33 int n, p;
     34 
     35 bool isperiod() {
     36 	for (int i = p; i < n; i++)
     37 		if (t[i] != t[i - p]) return false;
     38 	return true;
     39 }
     40 
     41 int main() {
     42 	fast;
     43 	cin >> n >> p >> s;
     44 
     45 	// attempt 1
     46 	t = s;
     47 	for (auto &i : t)
     48 		if (i == '.') i = '0';
     49 	if (!isperiod()) finish(t);
     50 
     51 	// attempt 2
     52 	int i = 0;
     53 	while (i < n && s[i] != '.') i++;
     54 	if (i + p < n) {
     55 		t[i] = '1';
     56 		finish(t);
     57 	}
     58 	i = n - 1;
     59 	while (i >= 0 && s[i] != '.') i--;
     60 	if (i - p >= 0) {
     61 		t[i] = '1';
     62 		finish(t);
     63 	}
     64 
     65 	finish("No");
     66 }
     67 ```
     68 
     69 **Python solution for the original problem as well as for the last challenge**
     70 
     71 ```
     72 n, p = map(int, input().split())
     73 s = input()
     74 
     75 t = s.replace('.', '0')
     76 
     77 if all(t[i] == t[i + p] for i in range(n - p)):
     78     rmost = -1
     79     for r in range(p - 1, -1, -1):
     80         x = s[r::p].rfind('.')
     81         if x != -1 and s[r::p] != '.':
     82             rmost = max(rmost, x * p + r)
     83     if rmost == -1:
     84         print('No')
     85     else:
     86         print(t[:rmost] + '1' + t[(rmost + 1):])
     87 else:
     88     print(t)
     89 ```
     90 
     91 **C++ seemingly-brute-force solution**
     92 
     93 ```
     94 #include <algorithm>
     95 #include <cstdio>
     96 
     97 static const int MAXN = 2005;
     98 
     99 static int n, p;
    100 static char s[MAXN];
    101 
    102 static int dots_ct = 0, dots[MAXN];
    103 
    104 int main()
    105 {
    106     scanf("%d%d%s", &n, &p, s);
    107 
    108     for (int i = 0; i < n; ++i) if (s[i] == '.') {
    109         dots[dots_ct++] = i;
    110         s[i] = '0';
    111     }
    112 
    113     for (int i = 1; i <= (1 << std::min(dots_ct, 19)); ++i) {
    114         bool is_period = true;
    115         for (int j = 0; j < n - p; ++j)
    116             if (s[j] != s[j + p]) { is_period = false; break; }
    117         if (!is_period) {
    118             puts(s);
    119             return 0;
    120         }
    121         for (int j = 0; j <= __builtin_ctz(i); ++j)
    122             s[dots[j]] ^= 1;
    123     }
    124 
    125     puts("No");
    126     return 0;
    127 }
    128 ```
    129 
    130 Tutorial is loading...
    131 
    132 **Model solution**
    133 
    134 ```
    135 #include <cstdio>
    136 #include <cstdlib>
    137 #include <algorithm>
    138 #include <string>
    139 #include <utility>
    140 #include <vector>
    141 
    142 static const int MAXM = 50;
    143 
    144 int main()
    145 {
    146     srand(1);
    147 
    148     int a[4];
    149     scanf("%d%d%d%d", &a[0], &a[1], &a[2], &a[3]);
    150 
    151     int M = std::max(2, std::min(MAXM, *std::max_element(a, a + 4)));
    152     std::vector<std::string> g;
    153 
    154     for (int k = 0; k < 4; ++k) {
    155         int islands = a[(k + 1) % 4] - 1;
    156         std::string s(M, 'A' + k);
    157         std::vector<std::pair<int, int>> pos;
    158 
    159         g.push_back(s);
    160         for (int x = 0; x < (islands + (M - 2)) / (M - 1); ++x) {
    161             for (int i = 0; i < 3; ++i) g.push_back(s);
    162             for (int i = (x & 1); i < M - !(x & 1); ++i)
    163                 pos.push_back({(int)g.size() - 2 - ((i ^ x) & 1), i});
    164         }
    165 
    166         std::random_shuffle(pos.begin(), pos.end());
    167         for (int i = 0; i < islands; ++i)
    168             g[pos[i].first][pos[i].second] = 'A' + (k + 1) % 4;
    169     }
    170 
    171     if (g.size() <= M) {
    172         printf("%lu %d\n", g.size(), M);
    173         for (int i = 0; i < g.size(); ++i) puts(g[i].c_str());
    174     } else {
    175         printf("%d %lu\n", M, g.size());
    176         for (int i = 0; i < M; ++i) {
    177             for (int j = 0; j < g.size(); ++j) putchar(g[j][i]);
    178             putchar('\n');
    179         }
    180     }
    181 
    182     return 0;
    183 }
    184 ```
    185 
    186 Tutorial is loading...
    187 
    188 **Model solution**
    189 
    190 ```
    191 #include <cstdio>
    192 #include <algorithm>
    193 #include <vector>
    194 
    195 static const int MAXN = 1e5 + 3;
    196 static const int INF32 = 0x7fffffff;
    197 typedef long long int64;
    198 
    199 static int n, l, w;
    200 static int x[MAXN], v[MAXN];
    201 static std::vector<int> pos, neg;
    202 
    203 inline int div_floor(int64 a, int b)
    204 {
    205     if (b == 0) return (a > 0 ? +INF32 : -INF32);
    206     if (a % b < 0) a -= (b + a % b);
    207     return a / b;
    208 }
    209 
    210 int main()
    211 {
    212     scanf("%d%d%d", &n, &l, &w);
    213 
    214     for (int i = 0; i < n; ++i) {
    215         scanf("%d%d", &x[i], &v[i]);
    216         (v[i] == +1 ? pos : neg).push_back(x[i]);
    217     }
    218     std::sort(pos.begin(), pos.end());
    219     std::sort(neg.begin(), neg.end());
    220 
    221     int64 ans = 0;
    222     for (int v : neg) {
    223         auto barrier = std::lower_bound(pos.begin(), pos.end(), -v - l);
    224         int u_max_0 = div_floor((int64)(v + l) * (w + 1) - 1, w - 1),
    225             u_max_1 = div_floor((int64)(v + l) * (w - 1) - 1, w + 1);
    226         ans +=
    227             (std::upper_bound(pos.begin(), barrier, u_max_0) - pos.begin()) +
    228             (std::upper_bound(barrier, pos.end(), std::min(v, u_max_1)) - barrier);
    229     }
    230 
    231     printf("%lld\n", ans);
    232     return 0;
    233 }
    234 ```
    235 
    236 Tutorial is loading...
    237 
    238 **Model solution**
    239 
    240 ```
    241 #include <cassert>
    242 #include <cstdio>
    243 #include <algorithm>
    244 #include <utility>
    245 #include <vector>
    246 
    247 static const int MAXN = 202;
    248 static const int LOGM = 15;
    249 
    250 static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
    251 
    252 struct point {
    253     int x, y;
    254     point(int x = 0, int y = 0) : x(x), y(y) { }
    255 };
    256 
    257 struct line {
    258     // ax + by + c = 0
    259     int a, b, c;
    260 
    261     line() : a(0), b(0), c(0) { }
    262     line(const point &p, const point &q)
    263         : a(p.y - q.y)
    264         , b(q.x - p.x)
    265         , c(q.y * p.x - q.x * p.y)
    266     {
    267         int g = gcd(gcd(a, b), c);
    268         if (g != 1) { a /= g; b /= g; c /= g; }
    269         if (a < 0) { a = -a; b = -b; c = -c; }
    270     }
    271 
    272     inline bool contains(const point &p) {
    273         return a * p.x + b * p.y + c == 0;
    274     }
    275 
    276     // For sorting & duplicate removing
    277     inline bool operator < (const line &other) const {
    278         return a != other.a ? a < other.a :
    279             b != other.b ? b < other.b : c < other.c;
    280     }
    281     inline bool operator == (const line &other) const {
    282         return a == other.a && b == other.b && c == other.c;
    283     }
    284 };
    285 
    286 struct mat {
    287     static const int N = ::MAXN;
    288     int sz;
    289     double a[N][N];
    290 
    291     mat(int sz = N, int id = 0) : sz(sz) {
    292         for (int i = 0; i < N; ++i)
    293             for (int j = 0; j < N; ++j)
    294                 a[i][j] = (i == j ? id : 0);
    295     }
    296 
    297     inline mat operator * (const mat &other) {
    298         assert(other.sz == this->sz);
    299         mat ret(sz, 0);
    300         for (int i = 0; i < sz; ++i)
    301             for (int k = 0; k < sz; ++k)
    302                 for (int j = 0; j < sz; ++j)
    303                     ret.a[i][j] += this->a[i][k] * other.a[k][j];
    304         return ret;
    305     }
    306 
    307     inline std::vector<double> operator * (const std::vector<double> &u) {
    308         assert(u.size() == this->sz);
    309         std::vector<double> v(sz);
    310         for (int i = 0; i < sz; ++i)
    311             for (int j = 0; j < sz; ++j)
    312                 v[i] += a[i][j] * u[j];
    313         return v;
    314     }
    315 };
    316 
    317 static int n, q;
    318 static point p[MAXN];
    319 
    320 static line l[MAXN * MAXN / 2];
    321 // Lists of lines that pass through points
    322 static std::vector<int> pl[MAXN];
    323 // Lists of points that lie on lines
    324 static std::vector<int> lp[MAXN * MAXN / 2];
    325 
    326 static mat A, Ap[LOGM];
    327 
    328 int main()
    329 {
    330     scanf("%d", &n);
    331     for (int i = 0; i < n; ++i) scanf("%d%d", &p[i].x, &p[i].y);
    332 
    333     int l_num = 0;
    334     for (int i = 0; i < n; ++i)
    335         for (int j = i + 1; j < n; ++j)
    336             l[l_num++] = line(p[i], p[j]);
    337     std::sort(l, l + l_num);
    338     l_num = std::unique(l, l + l_num) - &l[0];
    339 
    340     for (int i = 0; i < n; ++i)
    341         for (int j = 0; j < l_num; ++j)
    342             if (l[j].contains(p[i])) {
    343                 pl[i].push_back(j);
    344                 lp[j].push_back(i);
    345             }
    346 
    347     A = mat(n, 0);
    348     for (int i = 0; i < n; ++i) {
    349         for (int j : pl[i])
    350             for (int k : lp[j])
    351                 A.a[i][k] += 1.0L / (pl[i].size() * lp[j].size());
    352     }
    353 
    354     Ap[0] = A;
    355     for (int i = 1; i < LOGM; ++i) Ap[i] = Ap[i - 1] * Ap[i - 1];
    356 
    357     scanf("%d", &q);
    358     std::vector<double> u(n);
    359     for (int i = 0, t, m; i < q; ++i) {
    360         scanf("%d%d", &t, &m); --t;
    361 
    362         std::fill(u.begin(), u.end(), 0);
    363         u[t] = 1.0;
    364         for (int j = 0; j < LOGM; ++j)
    365             if ((m - 1) & (1 << j)) u = Ap[j] * u;
    366 
    367         double max = -1.0;
    368         for (int j = 0; j < l_num; ++j) {
    369             double cur = 0.0;
    370             for (int k : lp[j]) cur += u[k];
    371             cur /= lp[j].size();
    372             max = std::max(max, cur);
    373         }
    374         printf("%.12lf\n", (double)max);
    375     }
    376 
    377     return 0;
    378 }
    379 ```
    380 
    381 ---
    382 
    383 See you next time! I hope I'll be welcomed. Cheers!