codeforces-scrape

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

1401.md (8178B)


      1 Source: https://codeforces.com/blog/entry/81700
      2 
      3 Thank you for participating. I hope you enjoyed the contest!
      4 
      5 [1401A - Distance and Axis](/contest/1401/problem/A "Codeforces Round 665 (Div. 2)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution Code**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 
     16 #define endl '\n'
     17 
     18 using namespace std;
     19 
     20 main()
     21 {
     22     ios_base::sync_with_stdio(0);
     23     cin.tie(0);
     24     cout.tie(0);
     25 
     26     int k, n, t;
     27 
     28     cin >> t;
     29     for(;t--;)
     30     {
     31         cin >> n >> k;
     32 
     33         if(n < k)
     34             cout << k - n << endl;
     35 
     36         else if(n % 2 == k % 2)
     37             cout << 0 << endl;
     38 
     39         else
     40             cout << 1 << endl;
     41     }
     42 
     43     return 0;
     44 }
     45 ```
     46 
     47 **Behind Story**
     48 
     49 After 2 problems got rejected, I made this problem but it has 2D coordinate originally.
     50 
     51 [1401B - Ternary Sequence](/contest/1401/problem/B "Codeforces Round 665 (Div. 2)")
     52 
     53 **Tutorial**
     54 
     55 Tutorial is loading...
     56 
     57 **Solution Code**
     58 
     59 ```
     60 #include<bits/stdc++.h>
     61 
     62 #define endl '\n'
     63 
     64 using namespace std;
     65 
     66 main()
     67 {
     68     ios_base::sync_with_stdio(0);
     69     cin.tie(0);
     70     cout.tie(0);
     71 
     72     int t;
     73 
     74     cin >> t;
     75     for(;t--;)
     76     {
     77 	int m, sum = 0, x0, x1, x2, y0, y1, y2;
     78 
     79 	cin >> x0 >> x1 >> x2 >> y0 >> y1 >> y2;
     80 
     81 	m = min(x0, y2);
     82 	x0 -= m;
     83 	y2 -= m;
     84 
     85 	m = min(x1, y0);
     86 	x1 -= m;
     87 	y0 -= m;
     88 
     89 	m = min(x2, y1);
     90 	x2 -= m;
     91 	y1 -= m;
     92 	sum += 2 * m;
     93 
     94 	sum -= 2 * min(x1, y2);
     95 
     96 	cout << sum << endl;
     97     }
     98 }
     99 ```
    100 
    101 **Behind Story**
    102 
    103 One tester suggested to swap $A$ and $B$ but I and [adedalic](/profile/adedalic "International Master adedalic") thought it is not good idea, so the order didn't changed.
    104 
    105 [1401C - Mere Array](/contest/1401/problem/C "Codeforces Round 665 (Div. 2)")
    106 
    107 **Tutorial**
    108 
    109 Tutorial is loading...
    110 
    111 **Solution Code**
    112 
    113 ```
    114 #import<bits/stdc++.h>
    115 
    116 #define endl '\n'
    117 
    118 using namespace std;
    119 
    120 int a[100005], b[100005];
    121 main()
    122 {
    123     ios_base::sync_with_stdio(0);
    124     cin.tie(0);
    125     cout.tie(0);
    126 
    127     int t;
    128     cin >> t;
    129     for(;t--;)
    130     {
    131 	int k = 0, m = 1000000000, n;
    132 
    133 	cin >> n;
    134 
    135 	for(int i = 0; i < n; i++)
    136 	{
    137 	    cin >> a[i];
    138             b[i] = a[i];
    139 	    m = min(m, a[i]);
    140 	}
    141 
    142         sort(b, b + n);
    143 
    144 	for(int i = 0; i < n; i++)
    145 	    if(a[i] != b[i] && a[i] % m > 0)
    146 		k = 1;
    147 
    148 	if(k)
    149 	    cout<<"NO"<<endl;
    150 	else
    151 	    cout<<"YES"<<endl;
    152     }
    153 }
    154 ```
    155 
    156 **Behind Story**
    157 
    158 Most testers especially liked this problem.
    159 
    160 [1401D - Maximum Distributed Tree](/contest/1401/problem/D "Codeforces Round 665 (Div. 2)")
    161 
    162 **Tutorial**
    163 
    164 Tutorial is loading...
    165 
    166 **Solution Code**
    167 
    168 ```
    169 #include<bits/stdc++.h>
    170 
    171 #define endl '\n'
    172 
    173 using namespace std;
    174 
    175 typedef long long LL;
    176 
    177 struct H{int x, y;};
    178 
    179 int ii, n;
    180 const int q = 1e9 + 7;
    181 LL p[100005], pv[100005], vi[100005], w[100005];
    182 H e[200040];
    183 
    184 int C(H a, H b){return a.x < b.x;}
    185 int G(LL a, LL b){return a > b;}
    186 
    187 LL dfs(int v)
    188 {
    189     LL d = 1;
    190 
    191     vi[v] = 1;
    192 
    193     for(int i = pv[v]; i < pv[v+1]; i++)
    194 	if(!vi[e[i].y])
    195 	    d += dfs(e[i].y);
    196 
    197     w[ii] = d * (n - d);
    198     ii++;
    199 
    200     return d;
    201 }
    202 
    203 main()
    204 {
    205     ios_base::sync_with_stdio(0);
    206     cin.tie(0);
    207     cout.tie(0);
    208 
    209     int t;
    210 
    211     cin >> t;
    212 
    213     for(;t--;)
    214     {
    215 	int k = 0, m;
    216 	LL x = 1;
    217 
    218 	cin >> n;
    219 
    220 	for(int i = 0; i < n - 1; i++)
    221 	{
    222 	    cin >> e[i].x >> e[i].y;
    223 	    e[i + n - 1].x = e[i].y;
    224 	    e[i + n - 1].y = e[i].x;
    225 	}
    226 
    227 	int sz = 2 * n - 2;
    228 
    229 	sort(e, e + sz, C);
    230 
    231 	for(int i = 1; i < sz; i++)
    232 	{
    233 	    if(e[i].x > e[i - 1].x)
    234 	    {
    235 		for(int j = e[i - 1].x + 1; j <= e[i].x; j++)
    236 		    pv[j] = i;
    237 	    }
    238 	}
    239 	for(int j = e[sz - 1].x + 1; j <= n + 2; j++)
    240 	    pv[j] = sz;
    241 
    242 	ii = k = 0;
    243 	dfs(1);
    244 
    245 	cin >> m;
    246 
    247 	for(int i = 0; i < m; i++)
    248 	    cin >> p[i];
    249 
    250 	sort(p, p + m, G);
    251 	sort(w, w + n - 1, G);
    252 
    253 	if(m < n)
    254 	    for(int i = m; i < n - 1; i++)
    255 		p[i] = 1;
    256 	else
    257 	{
    258 	    int i;
    259 
    260 	    for(i = m - 1; i > m - n; k = i, i--)
    261 		w[i] = w[i - m + n - 1];
    262 
    263 	    for(; i; i--)
    264 		w[i] = w[0];
    265 	}
    266 
    267 	int l = max(m, n - 1);
    268 	
    269 	int i;
    270 	for(i = 0, x = w[0]; i <= k; i++)
    271 	    x = x * p[i] % q;
    272 
    273 	for(;i < l; i++)
    274 	    x = (x + w[i] * p[i]) % q;
    275 
    276 	cout << x << endl;
    277 
    278 	for(int i = 1; i <= n; i++)
    279 	    vi[i] = 0;
    280     }
    281 }
    282 ```
    283 
    284 **Behind Story**
    285 
    286 This problem was inspired by [1187E - Tree Painting](/contest/1187/problem/E "Educational Codeforces Round 67 (Rated for Div. 2)") and [1281E - Jeremy Bearimy](/contest/1281/problem/E "Codeforces Round 607 (Div. 2)"). Originally this was proposed as E, but after some fixing it became more easier than original one. And the modulo was new one originally, but I changed it later by myself.
    287 
    288 [1401E - Divide Square](/contest/1401/problem/E "Codeforces Round 665 (Div. 2)")
    289 
    290 **Tutorial**
    291 
    292 Tutorial is loading...
    293 
    294 **Solution Code**
    295 
    296 ```
    297 #include<bits/stdc++.h>
    298 
    299 using namespace std;
    300 
    301 typedef long long LL;
    302 
    303 struct H{int k, l, r;};
    304 
    305 const int p = 1048576;
    306 
    307 LL l[2100000], r[2100000], z[2100000];
    308 
    309 H h[100005], v[200040];
    310 
    311 int C(H a, H b){return a.k < b.k;}
    312 int D(H a, H b){return a.l < b.l || a.l == b.l && a.r > b.r;}
    313 
    314 LL sum(int x, int y, int d) // find the sum of range [x, y]
    315 {
    316     if(x <= l[d] && r[d] <= y)
    317 	return z[d];
    318 
    319     if(x > r[d] || y < l[d])
    320 	return 0;
    321 
    322     return sum(x, y, d << 1) + sum(x, y, (d << 1) + 1);
    323 }
    324 
    325 void REP(int i, LL k) // add k to i-th number
    326 {
    327     i += p;
    328 
    329     for(z[i] += k; i >>= 1;)
    330 	z[i] = z[i << 1] + z[(i << 1) + 1];
    331 }
    332 
    333 main()
    334 {
    335     ios_base::sync_with_stdio(0);
    336     cin.tie(0);
    337     cout.tie(0);
    338 
    339     LL m, n, s = 1;
    340 
    341     cin >> n >> m;
    342 
    343     for(int i = 0; i < p; i++)
    344 	l[i + p] = r[i + p] = i;
    345 
    346     for(int i = p; --i;)
    347     {
    348 	l[i] = l[i << 1];
    349 	r[i] = r[(i << 1) + 1];
    350     }
    351 
    352     for(int i = 0; i < n; i++)
    353     {
    354 	cin >> h[i].k >> h[i].l >> h[i].r;
    355 
    356 	if(h[i].r - h[i].l == 1000000)
    357 	    s++;
    358     }
    359 
    360     sort(h, h + n, C);
    361 
    362     for(int i = 0; i < m; i++)
    363     {
    364 	int j = i << 1;
    365 
    366 	cin >> v[j].k >> v[j].l >> v[j+1].l;
    367 
    368 	v[j + 1].k = v[j].k;
    369 	v[j].r = 1;
    370 	v[j + 1].r = -1;
    371 
    372 	if(v[j + 1].l - v[j].l == 1000000)
    373 	    s++;
    374     }
    375 
    376     sort(v, v + 2 * m, D);
    377 
    378     for(int i = 0, j = 0; i < n && j < 2 * m;)
    379     {
    380 	if(h[i].k < v[j].l || h[i].k == v[j].l && v[j].r < 0)
    381 	{
    382 	    s += sum(h[i].l, h[i].r, 1);
    383 	    i++;
    384 	}
    385 	else
    386 	{
    387 	    REP(v[j].k, v[j].r);
    388 	    j++;
    389 	}
    390     }
    391 
    392     cout << s;
    393 
    394     return 0;
    395 }
    396 ```
    397 
    398 **Behind Story**
    399 
    400 This problem was inspired by [1075C - The Tower is Going Home](/contest/1075/problem/C "Lyft Level 5 Challenge 2018 - Final Round (Open Div. 2)"). Originally the restriction of $n, m$ was small so $O(n^2)$ solution could pass, but [adedalic](/profile/adedalic "International Master adedalic") suggested to increase them up to $10^5$. In fact, I only knew brute forces solution until he tells me the solution using segment tree. And the size of the square was $10^9 \times 10^9$ so coordinate compression would be done additionally, but we eliminated it to avoid too many implementation.
    401 
    402 [1401F - Reverse and Swap](/contest/1401/problem/F "Codeforces Round 665 (Div. 2)")
    403 
    404 **Tutorial**
    405 
    406 Tutorial is loading...
    407 
    408 **Solution Code**
    409 
    410 ```
    411 #include<bits/stdc++.h>
    412 
    413 #define endl '\n'
    414 
    415 using namespace std;
    416 
    417 typedef long long LL;
    418 
    419 LL p, a[528000], ll[528000], rr[528000];
    420 
    421 LL SUM(LL l, LL r, LL d)
    422 {
    423     LL x, y, z;
    424 
    425     x = ll[d];
    426     y = rr[d];
    427     z = b & ~(y - x);
    428 
    429     x ^= z;
    430     y ^= z;
    431 
    432     if(x > r || y < l)
    433 	return 0;
    434 
    435     else if(x < l || y > r)
    436 	return(SUM(l, r, z << 1) + SUM(l, r, (z << 1) + 1));
    437 
    438     else
    439 	return a[z];
    440 }
    441 
    442 void REP(LL i,LL k)
    443 {
    444     i += p;
    445 
    446     for(a[i] = k; i >>= 1;)
    447 	a[i] = (a[i << 1] + a[(i << 1) + 1]);
    448 }
    449 
    450 main()
    451 {
    452     ios_base::sync_with_stdio(0);
    453     cin.tie(0);
    454     cout.tie(0);
    455 
    456     int b = 0, i, n, q;
    457 
    458     cin >> n >> q;
    459     p = 1 << n;
    460 
    461     for(i = 0; i < p; i++)
    462     {
    463 	cin >> a[p + i];
    464 	ll[p + i] = rr[p + i] = i;
    465     }
    466 
    467     for(; i < p; i++)
    468 	ll[p + i] = rr[p + i] = i;
    469 
    470     for(; --i;)
    471     {
    472 	a[i] = (a[i << 1] + a[(i << 1) + 1]);
    473 	ll[i] = ll[i << 1];
    474 	rr[i] = rr[(i << 1) + 1];
    475     }
    476 
    477     for(; q--;)
    478     {
    479 	int m;
    480 
    481 	cin >> m;
    482 
    483 	if(m == 1)
    484 	{
    485 	    int k, x;
    486 
    487 	    cin >> x >> k;
    488 
    489 	    REP((x - 1) ^ b, k);
    490 	}
    491 
    492 	else if(m == 2)
    493 	{
    494 	    int k;
    495 
    496 	    cin >> k;
    497 
    498 	    b ^= (1 << k) - 1;
    499 	}
    500 
    501 	else if(m == 3)
    502 	{
    503 	    int k;
    504 
    505 	    cin >> k;
    506 
    507 	    b ^= 1 << k;
    508 	}
    509 
    510 	else
    511 	{
    512 	    int l, r;
    513 
    514 	    cin >> l >> r;
    515 
    516 	    cout << SUM(l - 1, r - 1, 1) << endl;
    517 	}
    518     }
    519 }
    520 ```
    521 
    522 **Behind Story**
    523 
    524 This problem has 6 generators, and I most liked it among 6 problems.