codeforces-scrape

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

1499.md (12737B)


      1 Source: https://codeforces.com/blog/entry/88812
      2 
      3 [1499A - Domino on Windowsill](/contest/1499/problem/A "Educational Codeforces Round 106 (Rated for Div. 2)")
      4 
      5 Idea: [adedalic](/profile/adedalic "International Master adedalic")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (adedalic)**
     12 
     13 ```
     14 fun main() {
     15     repeat(readLine()!!.toInt()) {
     16         val (n, k1, k2) = readLine()!!.split(' ').map { it.toInt() }
     17         val (w, b) = readLine()!!.split(' ').map { it.toInt() }
     18 
     19         if (k1 + k2 >= 2 * w && (n - k1) + (n - k2) >= 2 * b)
     20             println("YES")
     21         else
     22             println("NO")
     23     }
     24 }
     25 ```
     26 
     27 [1499B - Binary Removals](/contest/1499/problem/B "Educational Codeforces Round 106 (Rated for Div. 2)")
     28 
     29 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     30 
     31 **Tutorial**
     32 
     33 Tutorial is loading...
     34 
     35 **Solution (Neon)**
     36 
     37 ```
     38 #include <bits/stdc++.h>
     39 
     40 using namespace std;
     41 
     42 int main() {
     43   int t;
     44   cin >> t;
     45   while (t--) {
     46     string s;
     47     cin >> s;
     48     int i = s.find("11");
     49     int j = s.rfind("00");
     50     cout << (i != -1 && j != -1 && i < j ? "NO" : "YES") << endl;
     51   }
     52 }
     53 ```
     54 
     55 [1499C - Minimum Grid Path](/contest/1499/problem/C "Educational Codeforces Round 106 (Rated for Div. 2)")
     56 
     57 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     58 
     59 **Tutorial**
     60 
     61 Tutorial is loading...
     62 
     63 **Solution (adedalic)**
     64 
     65 ```
     66 fun main() {
     67     repeat(readLine()!!.toInt()) {
     68         val n = readLine()!!.toInt()
     69         val c = readLine()!!.split(' ').map { it.toInt() }
     70 
     71         val mn = intArrayOf(1e9.toInt(), 1e9.toInt())
     72         val rem = longArrayOf(n.toLong(), n.toLong())
     73         var sum = 0L
     74         var ans = 1e18.toLong()
     75         for (i in c.indices) {
     76             mn[i % 2] = minOf(mn[i % 2], c[i])
     77             rem[i % 2]--
     78             sum += c[i]
     79             if (i > 0) {
     80                 val cur = sum + rem[0] * mn[0] + rem[1] * mn[1]
     81                 ans = minOf(ans, cur)
     82             }
     83         }
     84         println(ans)
     85     }
     86 }
     87 ```
     88 
     89 [1499D - The Number of Pairs](/contest/1499/problem/D "Educational Codeforces Round 106 (Rated for Div. 2)")
     90 
     91 Idea: [Neon](/profile/Neon "Candidate Master Neon")
     92 
     93 **Tutorial**
     94 
     95 Tutorial is loading...
     96 
     97 **Solution (Neon)**
     98 
     99 ```
    100 #include <bits/stdc++.h>
    101 
    102 using namespace std;
    103 
    104 const int N = 2e7 + 13;
    105 
    106 int main() {
    107   vector<int> mind(N, -1), val(N);
    108   mind[1] = 1;
    109   for (int i = 2; i < N; ++i) if (mind[i] == -1)
    110     for (int j = i; j < N; j += i) if (mind[j] == -1)
    111       mind[j] = i;
    112   for (int i = 2; i < N; ++i) {
    113     int j = i / mind[i];
    114     val[i] = val[j] + (mind[i] != mind[j]);
    115   }
    116   int t;
    117   scanf("%d", &t);
    118   while (t--) {
    119     int c, d, x;
    120     scanf("%d%d%d", &c, &d, &x);
    121     int ans = 0;
    122     for (int i = 1; i * i <= x; ++i) {
    123       if (x % i != 0) continue;
    124       int k1 = x / i + d; 
    125       if (k1 % c == 0) ans += 1 << val[k1 / c];
    126       if (i * i == x) continue;
    127       int k2 = i + d;
    128       if (k2 % c == 0) ans += 1 << val[k2 / c]; 
    129     }
    130     printf("%d\n", ans);
    131   }
    132 }
    133 ```
    134 
    135 [1499E - Chaotic Merge](/contest/1499/problem/E "Educational Codeforces Round 106 (Rated for Div. 2)")
    136 
    137 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    138 
    139 **Tutorial**
    140 
    141 Tutorial is loading...
    142 
    143 **Solution 1 (awoo)**
    144 
    145 ```
    146 #include <bits/stdc++.h>
    147 
    148 #define forn(i, n) for (int i = 0; i < int(n); i++)
    149 
    150 using namespace std;
    151 
    152 const int MOD = 998244353;
    153 
    154 int add(int a, int b){
    155 	a += b;
    156 	if (a >= MOD)
    157 		a -= MOD;
    158 	if (a < 0)
    159 		a += MOD;
    160 	return a;
    161 }
    162 
    163 int main() {
    164 	string s, t;
    165 	cin >> s >> t;
    166 	int n = s.size(), m = t.size();
    167 	vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(2, 0)));
    168 	int ans = 0;
    169 	forn(i, n + 1) forn(j, m + 1){
    170 		if (i < n) dp[i + 1][j][0] = add(dp[i + 1][j][0], 1);
    171 		if (j < m) dp[i][j + 1][1] = add(dp[i][j + 1][1], 1);
    172 		if (0 < i && i < n && s[i - 1] != s[i]) dp[i + 1][j][0] = add(dp[i + 1][j][0], dp[i][j][0]);
    173 		if (0 < j && i < n && t[j - 1] != s[i]) dp[i + 1][j][0] = add(dp[i + 1][j][0], dp[i][j][1]);
    174 		if (0 < i && j < m && s[i - 1] != t[j]) dp[i][j + 1][1] = add(dp[i][j + 1][1], dp[i][j][0]);
    175 		if (0 < j && j < m && t[j - 1] != t[j]) dp[i][j + 1][1] = add(dp[i][j + 1][1], dp[i][j][1]);
    176 		ans = add(ans, dp[i][j][0]);
    177 		ans = add(ans, dp[i][j][1]);
    178 	}
    179 	forn(i, n){
    180 		int j = i;
    181 		while (j + 1 < n && s[j] != s[j + 1]) ++j;
    182 		int len = j - i + 1;
    183 		int val = (len * 1ll * (len + 1) / 2) % MOD * (m + 1) % MOD;
    184 		ans = add(ans, -val);
    185 		i = j;
    186 	}
    187 	forn(i, m){
    188 		int j = i;
    189 		while (j + 1 < m && t[j] != t[j + 1]) ++j;
    190 		int len = j - i + 1;
    191 		int val = (len * 1ll * (len + 1) / 2) % MOD * (n + 1) % MOD;
    192 		ans = add(ans, -val);
    193 		i = j;
    194 	}
    195 	printf("%d\n", ans);
    196 	return 0;
    197 }
    198 ```
    199 
    200 **Solution 2 (awoo)**
    201 
    202 ```
    203 #include <bits/stdc++.h>
    204 
    205 #define forn(i, n) for (int i = 0; i < int(n); i++)
    206 
    207 using namespace std;
    208 
    209 const int MOD = 998244353;
    210 
    211 int add(int a, int b){
    212 	a += b;
    213 	if (a >= MOD)
    214 		a -= MOD;
    215 	if (a < 0)
    216 		a += MOD;
    217 	return a;
    218 }
    219 
    220 int main() {
    221 	string s, t;
    222 	cin >> s >> t;
    223 	int n = s.size(), m = t.size();
    224 	vector<vector<vector<vector<int>>>> dp(n + 1, vector<vector<vector<int>>>(m + 1, vector<vector<int>>(2, vector<int>(4, 0))));
    225 	int ans = 0;
    226 	forn(i, n + 1) forn(j, m + 1){
    227 		if (i < n) dp[i + 1][j][0][1] = add(dp[i + 1][j][0][1], 1);
    228 		if (j < m) dp[i][j + 1][1][2] = add(dp[i][j + 1][1][2], 1);
    229 		forn(mask, 4){
    230 			if (0 < i && i < n && s[i - 1] != s[i]) dp[i + 1][j][0][mask | 1] = add(dp[i + 1][j][0][mask | 1], dp[i][j][0][mask]);
    231 			if (0 < j && i < n && t[j - 1] != s[i]) dp[i + 1][j][0][mask | 1] = add(dp[i + 1][j][0][mask | 1], dp[i][j][1][mask]);
    232 			if (0 < i && j < m && s[i - 1] != t[j]) dp[i][j + 1][1][mask | 2] = add(dp[i][j + 1][1][mask | 2], dp[i][j][0][mask]);
    233 			if (0 < j && j < m && t[j - 1] != t[j]) dp[i][j + 1][1][mask | 2] = add(dp[i][j + 1][1][mask | 2], dp[i][j][1][mask]);
    234 		}
    235 		ans = add(ans, dp[i][j][0][3]);
    236 		ans = add(ans, dp[i][j][1][3]);
    237 	}
    238 	printf("%d\n", ans);
    239 	return 0;
    240 }
    241 ```
    242 
    243 [1499F - Diameter Cuts](/contest/1499/problem/F "Educational Codeforces Round 106 (Rated for Div. 2)")
    244 
    245 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    246 
    247 **Tutorial**
    248 
    249 Tutorial is loading...
    250 
    251 **Solution (awoo)**
    252 
    253 ```
    254 #include <bits/stdc++.h>
    255 
    256 #define forn(i, n) for (int i = 0; i < int(n); i++)
    257 
    258 using namespace std;
    259 
    260 const int MOD = 998244353;
    261 
    262 int add(int a, int b){
    263 	a += b;
    264 	if (a >= MOD)
    265 		a -= MOD;
    266 	if (a < 0)
    267 		a += MOD;
    268 	return a;
    269 }
    270 
    271 int mul(int a, int b){
    272 	return a * 1ll * b % MOD;
    273 }
    274 
    275 int k;
    276 vector<vector<int>> g;
    277 vector<vector<int>> dp;
    278 
    279 int dfs(int v, int p = -1){
    280 	dp[v][0] = 1;
    281 	int h = 0;
    282 	for (int u : g[v]) if (u != p){
    283 		int nh = dfs(u, v);
    284 		vector<int> tmp(max(h, nh + 1) + 1);
    285 		forn(i, h + 1) forn(j, nh + 1){
    286 			if (i + j + 1 <= k)
    287 				tmp[max(i, j + 1)] = add(tmp[max(i, j + 1)], mul(dp[v][i], dp[u][j]));
    288 			if (i <= k && j <= k)
    289 				tmp[i] = add(tmp[i], mul(dp[v][i], dp[u][j]));
    290 		}
    291 		h = max(h, nh + 1);
    292 		forn(i, h + 1){
    293 			dp[v][i] = tmp[i];
    294 		}
    295 	}
    296 	return h;
    297 }
    298 
    299 int main() {
    300 	int n;
    301 	scanf("%d%d", &n, &k);
    302 	g.resize(n);
    303 	dp.resize(n, vector<int>(n, 0));
    304 	forn(i, n - 1){
    305 		int v, u;
    306 		scanf("%d%d", &v, &u);
    307 		--v, --u;
    308 		g[v].push_back(u);
    309 		g[u].push_back(v);
    310 	}
    311 	dfs(0);
    312 	int ans = 0;
    313 	forn(i, k + 1) ans = add(ans, dp[0][i]);
    314 	printf("%d\n", ans);
    315 	return 0;
    316 }
    317 ```
    318 
    319 [1499G - Graph Coloring](/contest/1499/problem/G "Educational Codeforces Round 106 (Rated for Div. 2)")
    320 
    321 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    322 
    323 **Tutorial**
    324 
    325 Tutorial is loading...
    326 
    327 **Solution (BledDest)**
    328 
    329 ```
    330 #include <bits/stdc++.h>
    331 
    332 using namespace std;
    333 
    334 const int MOD = 998244353;
    335 const int N = 1000043;
    336 
    337 int add(int x, int y)
    338 {
    339     x += y;
    340     while(x >= MOD) x -= MOD;
    341     while(x < 0) x += MOD;
    342     return x;
    343 }
    344 
    345 int sub(int x, int y)
    346 {
    347     return add(x, -y);
    348 }
    349 
    350 int mul(int x, int y)
    351 {
    352     return (x * 1ll * y) % MOD;
    353 }                               
    354 
    355 int binpow(int x, int y)
    356 {
    357     int z = 1;
    358     while(y > 0)
    359     {
    360         if(y % 2 == 1)
    361             z = mul(z, x);
    362         x = mul(x, x);
    363         y /= 2;
    364     }
    365     return z;
    366 }
    367 
    368 int global_hash = 0;
    369 
    370 void reverse(deque<pair<int, int>>& d)
    371 {
    372     stack<pair<int, int>> s;
    373     while(!d.empty())
    374     {
    375         s.push(d.back());
    376         d.pop_back();
    377     }
    378     while(!s.empty())
    379     {
    380         d.push_front(s.top());
    381         s.pop();
    382     }
    383 }
    384 
    385 void safe_push_front(deque<pair<int, int>>& d, int c, int& res)
    386 {
    387     int z = d.front().first ^ 1;
    388     res = add(res, mul(binpow(2, c), z));
    389     d.push_front(make_pair(z, c));
    390 }
    391 
    392 void safe_push_back(deque<pair<int, int>>& d, int c, int& res)
    393 {
    394     int z = d.back().first ^ 1;
    395     res = add(res, mul(binpow(2, c), z));
    396     d.push_back(make_pair(z, c));
    397 }
    398 
    399 deque<pair<int, int>> ds[N];
    400 
    401 struct path
    402 {
    403     int s;
    404     int t;
    405     int d;
    406     int c;
    407 
    408     path() {};
    409     path(int s, int t, int d, int c) : s(s), t(t), d(d), c(c) {};
    410 
    411     void push_front(int i)
    412     {
    413         safe_push_front(ds[d], i, c);
    414     }
    415 
    416     void push_back(int i)
    417     {
    418         safe_push_back(ds[d], i, c);
    419     }
    420 
    421     void pop_front()
    422     {
    423         ds[d].pop_front();
    424     }
    425 
    426     void pop_back()
    427     {
    428         ds[d].pop_back();
    429     }
    430 
    431     int front()
    432     {
    433         return ds[d].front().second;
    434     }
    435 
    436     int back()
    437     {
    438         return ds[d].back().second;
    439     }
    440 
    441     void reverse()
    442     {
    443         ::reverse(ds[d]);
    444         swap(s, t);
    445     }
    446 
    447     int size()
    448     {
    449         return ds[d].size();
    450     }
    451 };
    452 
    453 path link_to_left(path x, path y)
    454 {
    455     path z = x;
    456     while(y.size() > 0)
    457     {
    458         z.push_back(y.front());
    459         y.pop_front();
    460     }
    461     z.t = y.t;
    462     return z;
    463 }
    464 
    465 path link_to_right(path x, path y)
    466 {
    467     path z = y;
    468     while(x.size() > 0)
    469     {
    470         z.push_front(x.back());
    471         x.pop_back();
    472     }
    473     z.s = x.s;
    474     return z;
    475 }
    476 
    477 int cur = 0;
    478 
    479 path make(int x, int y, int i)
    480 {
    481     int cost = i;
    482     ds[cur].push_back(make_pair(0, cost));
    483     return path(x, y, cur++, 0);    
    484 }
    485 
    486 set<int> paths;
    487 vector<int> paths_v[N];
    488 path ps[N];
    489 
    490 path merge(path x, path y, int v)
    491 {
    492     if(x.size() > y.size())
    493         swap(x, y);
    494     if(y.s == v)
    495     {
    496         if(x.t != v)
    497             x.reverse();
    498         return link_to_right(x, y);    
    499     }
    500     else
    501     {
    502         if(x.s != v)
    503             x.reverse();
    504         return link_to_left(y, x);
    505     }    
    506 }
    507 
    508 int cur2 = 0;       
    509 
    510 void modify(vector<int>& v, int x, int y)
    511 {
    512     for(int i = 0; i < v.size(); i++)
    513         if(v[i] == x)
    514             v[i] = y;
    515 }   
    516 
    517 void reassign(path p, int x, int y)
    518 {
    519     modify(paths_v[p.s], x, y);
    520     modify(paths_v[p.t], x, y);    
    521 }
    522 
    523 void merge_paths(int x, int y, int v)
    524 {
    525     if(x == y)
    526     {                         
    527 
    528     }
    529     else
    530     {
    531         global_hash = sub(global_hash, ps[x].c);
    532         global_hash = sub(global_hash, ps[y].c);
    533         ps[cur2++] = merge(ps[x], ps[y], v);
    534         paths.erase(x);
    535         paths.erase(y);
    536         paths.insert(cur2 - 1);
    537         reassign(ps[x], x, cur2 - 1);
    538         reassign(ps[y], y, cur2 - 1);
    539         global_hash = add(global_hash, ps[cur2 - 1].c);   
    540     }
    541 }
    542 
    543 void relax(int v)
    544 {
    545     while(paths_v[v].size() >= 2)
    546     {
    547         int x = paths_v[v].back();
    548         paths_v[v].pop_back();
    549         int y = paths_v[v].back();
    550         paths_v[v].pop_back();
    551         merge_paths(x, y, v);
    552     }
    553 }
    554 
    555 void add_edge(int x, int y, int i)
    556 {
    557     //cerr << x << " " << y << " " << i << endl;
    558     int c = cur2;
    559     ps[cur2++] = make(x, y, i);
    560     paths_v[x].push_back(c);
    561     paths_v[y].push_back(c);
    562     paths.insert(c);
    563     relax(x);
    564     relax(y);
    565 }
    566 
    567 void print_coloring()
    568 {
    569     vector<int> ans;
    570     for(auto x : paths)
    571     {
    572         for(auto y : ds[ps[x].d])
    573         {
    574             if(y.first == 1)
    575                 ans.push_back(y.second);
    576         }
    577     }
    578     printf("%d", int(ans.size()));
    579     for(auto x : ans)
    580         printf(" %d", x);
    581     puts("");
    582     fflush(stdout);
    583 }
    584 
    585 int e = 0;
    586 
    587 void process_query()
    588 {
    589     int t;
    590     scanf("%d", &t);
    591     if(t == 1)
    592     {
    593         int x, y;
    594         scanf("%d %d", &x, &y);
    595         y += 200001;
    596         add_edge(x, y, ++e);
    597         printf("%d\n", global_hash);
    598         fflush(stdout);
    599     }
    600     else
    601         print_coloring();
    602 }
    603 
    604 void print_info()
    605 {
    606     cerr << "Paths\n";
    607     for(auto x : paths)
    608         cerr << x << " start: " << ps[x].s << " " << " end: " << ps[x].t << endl;
    609     cerr << "Vertices\n";
    610     for(int i = 0; i < N; i++)
    611         if(!paths_v[i].empty())
    612         {
    613             cerr << i << ": ";
    614             for(auto x : paths_v[i])
    615                 cerr << x << " ";
    616             cerr << endl;
    617         }
    618 
    619 }
    620         
    621 int main()
    622 {
    623     int n1, n2, m;
    624     scanf("%d %d %d", &n1, &n2, &m);
    625     for(int i = 0; i < m; i++)
    626     {
    627         int x, y;
    628         scanf("%d %d", &x, &y);
    629         y += 200001;
    630         add_edge(x, y, ++e);
    631     }
    632     int q;
    633     scanf("%d", &q);
    634     for(int i = 0; i < q; i++)
    635     {
    636         //print_info();
    637         process_query();
    638     }
    639 }
    640 ```