codeforces-scrape

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

1380.md (16182B)


      1 Source: https://codeforces.com/blog/entry/80054
      2 
      3 [1380A - Three Indices](/contest/1380/problem/A "Educational Codeforces Round 91 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Ne0n25)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 const int N = 1000;
     19 
     20 int n;
     21 int a[N];
     22 
     23 void solve() {
     24 	cin >> n;
     25 	for (int i = 0; i < n; ++i)
     26 		cin >> a[i];
     27 	for (int i = 1; i < n - 1; ++i) {
     28 		if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
     29 			cout << "YES" << endl;
     30 			cout << i << ' ' << i + 1 << ' ' << i + 2 << endl;
     31 			return;
     32 		}
     33 	}
     34 	cout << "NO" << endl;
     35 }
     36 
     37 int main() {
     38 	int T;
     39 	cin >> T;
     40 	while (T--)
     41 		solve();
     42 }
     43 ```
     44 
     45 [1380B - Universal Solution](/contest/1380/problem/B "Educational Codeforces Round 91 (Rated for Div. 2)")
     46 
     47 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     48 
     49 **Tutorial**
     50 
     51 Tutorial is loading...
     52 
     53 **Solution (adedalic)**
     54 
     55 ```
     56 fun main() {
     57     val winBy = mapOf('R' to 'P', 'S' to 'R', 'P' to 'S')
     58     repeat(readLine()!!.toInt()) {
     59         val s = readLine()!!
     60         val maxCnt = s.groupingBy { it }.eachCount().maxBy { it.value }!!.key
     61         println("${winBy[maxCnt]}".repeat(s.length))
     62     }
     63 }
     64 ```
     65 
     66 [1380C - Create The Teams](/contest/1380/problem/C "Educational Codeforces Round 91 (Rated for Div. 2)")
     67 
     68 Idea: [Roms](/profile/Roms "Master Roms")
     69 
     70 **Tutorial**
     71 
     72 Tutorial is loading...
     73 
     74 **Solution (Roms)**
     75 
     76 ```
     77 for _ in range(int(input())):
     78     n, x = map(int, input().split())
     79     a = sorted(list(map(int, input().split())), reverse=True)
     80     res, cur = 0, 1
     81     for s in a:
     82         if s * cur >= x:
     83             res += 1
     84             cur = 0
     85         cur += 1
     86     print(res)
     87 ```
     88 
     89 [1380D - Berserk And Fireball](/contest/1380/problem/D "Educational Codeforces Round 91 (Rated for Div. 2)")
     90 
     91 Idea: [Roms](/profile/Roms "Master Roms")
     92 
     93 **Tutorial**
     94 
     95 Tutorial is loading...
     96 
     97 **Solution (Roms)**
     98 
     99 ```
    100 #include <bits/stdc++.h>
    101 
    102 using namespace std;
    103 
    104 const int N = int(2e5) + 9;
    105 
    106 int n, m;
    107 long long x, k, y;
    108 int a[N];
    109 int b[N];
    110 
    111 bool upd(int l, int r, long long &res) {
    112     if (l > r) return true;
    113     bool canDel = false;
    114     int mx = *max_element(a + l, a + r + 1);
    115     int len = r - l + 1;
    116     if (l - 1 >= 0 && a[l - 1] > mx) canDel = true;
    117     if (r + 1 < n && a[r + 1] > mx) canDel = true;
    118     if (len < k && !canDel) return false;
    119     
    120     int need = len % k;
    121     res += need * y;
    122     len -= need;
    123     
    124     if (y * k >= x) {
    125         res += len / k * x;
    126     } else if(canDel) {
    127         res += len * y;
    128     } else {
    129         res += (len - k) * y + x;
    130     }
    131     
    132     return true;
    133 }
    134 
    135 int main(){
    136     scanf("%d %d", &n, &m);
    137     scanf("%lld %lld %lld", &x, &k, &y);
    138     for (int i = 0; i < n; ++i) scanf("%d", a + i);
    139     for (int i = 0; i < m; ++i) scanf("%d", b + i);
    140     
    141     long long res = 0;
    142     int lst = -1, posa = 0, posb = 0;
    143     while (posb < m) {
    144         while(posa < n && a[posa] != b[posb]) ++posa;
    145         if (posa == n) {
    146             puts("-1");
    147             return 0;
    148         }
    149         
    150         if (!upd(lst + 1, posa - 1, res)) {
    151             puts("-1");
    152             return 0;
    153         }
    154         
    155         lst = posa;
    156         ++posb;
    157     }
    158     
    159     if (!upd(lst + 1, n - 1, res)) {
    160         puts("-1");
    161         return 0;
    162     }
    163     
    164     printf("%lld\n", res);
    165     
    166     return 0;
    167 }
    168 ```
    169 
    170 [1380E - Merging Towers](/contest/1380/problem/E "Educational Codeforces Round 91 (Rated for Div. 2)")
    171 
    172 Idea: [Roms](/profile/Roms "Master Roms") and [BledDest](/profile/BledDest "International Grandmaster BledDest")
    173 
    174 **Tutorial**
    175 
    176 Tutorial is loading...
    177 
    178 **Solution 1 (BledDest)**
    179 
    180 ```
    181 #include<bits/stdc++.h>
    182 
    183 using namespace std;
    184 
    185 const int N = 200043;
    186 const int L = 20;
    187 
    188 vector<int> g[2 * N];
    189 int p[2 * N];
    190 int up[2 * N][L];
    191 int idx[N];
    192 int psum[N];
    193 int cur[N];
    194 int tin[2 * N];
    195 int tout[2 * N];
    196 int T = 0;
    197 
    198 void dfs(int x, int y)
    199 {
    200 	tin[x] = T++;
    201 	p[x] = y;
    202 	up[x][0] = y;
    203 	for(int i = 1; i < L; i++)
    204 		up[x][i] = up[up[x][i - 1]][i - 1];
    205 	for(auto z : g[x])
    206 		dfs(z, x);
    207 	tout[x] = T++;
    208 }
    209 
    210 bool is_ancestor(int x, int y)
    211 {
    212 	return tin[x] <= tin[y] && tout[x] >= tout[y];
    213 }
    214 
    215 int lca(int x, int y)
    216 {
    217 	if(is_ancestor(x, y))
    218 		return x;
    219 	for(int i = L - 1; i >= 0; i--)
    220 		if(!is_ancestor(up[x][i], y))
    221 			x = up[x][i];
    222 	return p[x];
    223 }
    224 
    225 int main()
    226 {
    227 	int n, m;
    228 	scanf("%d %d", &n, &m);
    229 	for(int i = 0; i < n; i++)
    230 	{
    231 		scanf("%d", &idx[i]);
    232 		idx[i]--;
    233 	}
    234 	for(int i = 0; i < m; i++)
    235 		cur[i] = i;
    236 	for(int i = 0; i < m - 1; i++)
    237 	{
    238 		int x, y;
    239 		scanf("%d %d", &x, &y);
    240 		--x;
    241 		--y;
    242 		int nidx = m + i;
    243 		g[nidx].push_back(cur[x]);
    244 		g[nidx].push_back(cur[y]);
    245 		cur[x] = nidx;
    246 	}
    247 	int root = m * 2 - 2;
    248 	dfs(root, root);
    249 	for(int i = 0; i < n - 1; i++)
    250 	{
    251 		int t = lca(idx[i], idx[i + 1]);
    252 		if(t < m)
    253 			psum[0]++;
    254 		else
    255 			psum[t - m + 1]++;
    256 	}
    257 	for(int i = 0; i < m - 1; i++)
    258 		psum[i + 1] += psum[i];
    259 	for(int i = 0; i < m; i++)
    260 		printf("%d\n", n - 1 - psum[i]);
    261 }
    262 ```
    263 
    264 **Solution 2 (pikmike)**
    265 
    266 ```
    267 #include <bits/stdc++.h>
    268 
    269 #define forn(i, n) for (int i = 0; i < int(n); i++)
    270 
    271 using namespace std;
    272 
    273 int n, m;
    274 vector<int> p;
    275 vector<vector<int>> val;
    276 vector<int> who;
    277 
    278 int getp(int a){
    279 	return a == p[a] ? a : p[a] = getp(p[a]);
    280 }
    281 
    282 int main(){
    283 	scanf("%d%d", &n, &m);
    284 	p.resize(m);
    285 	val.resize(m);
    286 	who.resize(n);
    287 	int ans = n - 1;
    288 	forn(i, m)
    289 		p[i] = i;
    290 	forn(i, n){
    291 		int x;
    292 		scanf("%d", &x);
    293 		--x;
    294 		who[i] = x;
    295 		ans -= (i && who[i] == who[i - 1]);
    296 		val[who[i]].push_back(i);
    297 	}
    298 	printf("%d\n", ans);
    299 	forn(i, m - 1){
    300 		int v, u;
    301 		scanf("%d%d", &v, &u);
    302 		v = getp(v - 1), u = getp(u - 1);
    303 		if (val[v].size() < val[u].size())
    304 			swap(v, u);
    305 		for (int x : val[u]){
    306 			if (x) ans -= who[x - 1] == v;
    307 			if (x < n - 1) ans -= who[x + 1] == v;
    308 		}
    309 		for (int x : val[u]){
    310 			val[v].push_back(x);
    311 			who[x] = v;
    312 		}
    313 		p[u] = v;
    314 		printf("%d\n", ans);
    315 	}
    316 	return 0;
    317 }
    318 ```
    319 
    320 [1380F - Strange Addition](/contest/1380/problem/F "Educational Codeforces Round 91 (Rated for Div. 2)")
    321 
    322 Idea: [Roms](/profile/Roms "Master Roms")
    323 
    324 **Tutorial**
    325 
    326 Tutorial is loading...
    327 
    328 **Solution 1 (pikmike)**
    329 
    330 ```
    331 #include <bits/stdc++.h>
    332 
    333 using namespace std;
    334 
    335 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    336 
    337 const int MOD = 998244353;
    338 const int N = 500 * 1000 + 13;
    339 
    340 string s;
    341 
    342 int add(int a, int b){
    343 	a += b;
    344 	if (a >= MOD)
    345 		a -= MOD;
    346 	return a;
    347 }
    348 
    349 int mul(int a, int b){
    350 	return a * 1ll * b % MOD;
    351 }
    352 
    353 struct node{
    354 	int val[4], len;
    355 };
    356 
    357 node merge(const node &a, const node &b, int l, int r){
    358 	node c;
    359 	int na = a.len == 1 ? 0 : 1;
    360 	int nb = b.len == 1 ? 0 : 2;
    361 	c.len = a.len + b.len;
    362 	c.val[0] = mul(a.val[na], b.val[nb]);
    363 	c.val[1] = mul(a.val[na], b.val[3]);
    364 	c.val[2] = mul(a.val[3], b.val[nb]);
    365 	c.val[3] = mul(a.val[3], b.val[3]);
    366 	if (l == 1){
    367 		na = a.len == 1 ? 2 : 0;
    368 		nb = b.len == 1 ? 1 : 0;
    369 		c.val[na + nb] = add(c.val[na + nb], mul(mul(a.val[0], b.val[0]), 19 - (l * 10 + r)));
    370 		c.val[1 + na] = add(c.val[1 + na], mul(mul(a.val[0], b.val[1]), 19 - (l * 10 + r)));
    371 		c.val[2 + nb] = add(c.val[2 + nb], mul(mul(a.val[2], b.val[0]), 19 - (l * 10 + r)));
    372 		c.val[3] = add(c.val[3], mul(mul(a.val[2], b.val[1]), 19 - (l * 10 + r)));
    373 	}
    374 	return c;
    375 }
    376 
    377 node t[4 * N];
    378 
    379 void build(int v, int l, int r){
    380 	t[v].len = r - l;
    381 	if (l == r - 1){
    382 		t[v].val[0] = 1;
    383 		t[v].val[3] = s[l] + 1;
    384 		return;
    385 	}
    386 	int m = (l + r) / 2;
    387 	build(v * 2, l, m);
    388 	build(v * 2 + 1, m, r);
    389 	t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]);
    390 }
    391 
    392 void upd(int v, int l, int r, int x, int val){
    393 	if (l == r - 1){
    394 		s[l] = val;
    395 		t[v].val[3] = s[l] + 1;
    396 		return;
    397 	}
    398 	int m = (l + r) / 2;
    399 	if (x < m)
    400 		upd(v * 2, l, m, x, val);
    401 	else
    402 		upd(v * 2 + 1, m, r, x, val);
    403 	t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]);
    404 }
    405 
    406 int main(){
    407 	int n, m;
    408 
    409 	scanf("%d%d", &n, &m);
    410 	static char buf[N];
    411 	scanf("%s", buf);
    412 	s = buf;
    413 	forn(i, n) s[i] -= '0';
    414 	
    415 	memset(t, 0, sizeof(t));
    416 	build(1, 0, n);
    417 	
    418 	forn(i, m){
    419 		int x, v;
    420 		scanf("%d%d", &x, &v);
    421 		--x;
    422 		upd(1, 0, n, x, v);
    423 		printf("%d\n", t[1].val[3]);
    424 	}
    425 }
    426 ```
    427 
    428 **Solution 2 (Roms)**
    429 
    430 ```
    431 #include <bits/stdc++.h>
    432 
    433 using namespace std;
    434 
    435 const int N = int(5e5) + 9;
    436 const int MOD = 998244353;
    437 
    438 int mul(int a, int b) {
    439     return (a * 1LL * b) % MOD;
    440 }
    441 
    442 void add(int &a, int x) {
    443     a += x;
    444     a %= MOD;
    445 }
    446 
    447 int bp(int a, int n) {
    448     int res = 1;
    449     for (; n > 0; n >>= 1) {
    450         if (n & 1) res = mul(res, a);
    451         a = mul(a, a);
    452     }
    453     return res;
    454 }
    455 
    456 int inv(int a) {
    457     int ia = bp(a, MOD - 2);
    458     assert(mul(a, ia) == 1);
    459     return ia;
    460 }
    461 
    462 int n, m;
    463 string s;
    464 int dp[N][10];
    465 int idp[N][10];
    466 set <pair<int, int> > lr;
    467 int res = 1;
    468 
    469 void updRes(int l, int r, int c) {
    470     assert(l <= r);
    471     if (c == 1) {
    472         assert(!lr.count(make_pair(l, r)));
    473         lr.insert(make_pair(l, r));
    474         res = mul(res, dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']);
    475     } else {
    476         assert(lr.count(make_pair(l, r)));
    477         lr.erase(make_pair(l, r));
    478         res = mul(res, inv(dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']));
    479     }
    480 }
    481 
    482 void getLR(int &l, int &r, int pos) {
    483     l = r = -1;
    484     auto it = lr.lower_bound(make_pair(pos, n));
    485     if(it == lr.begin()) return;
    486     --it;
    487     if(!(it->first <= pos && pos <= it->second)) return;
    488     l = it->first, r = it->second;
    489 }
    490 
    491 char buf[N];
    492 int main(){
    493     scanf("%d %d\n", &n, &m);
    494     scanf("%s", buf);
    495     s = string(buf);
    496     for (int i = 0; i <= 9; ++i) {
    497         dp[0][i] = i + 1; //idp[0][i] = inv(dp[0][i]);
    498         dp[1][i] = 2 * (i + 1) + (9 - i); //idp[1][i] = inv(dp[1][i]);
    499     }
    500     for (int i = 2; i < N; ++i)
    501         for (int j = 0; j <= 9; ++j) {
    502             dp[i][j] = (2LL * dp[i - 1][j] + 8LL * dp[i - 2][j]) % MOD;
    503             //idp[i][j] = inv(dp[i][j]);
    504         }
    505     for (int i = 0; i < N; ++i) for(int j = 0; j < 10; ++j) assert(dp[i][j] != 0);
    506     for (int l = 0; l < n; ) {
    507         int r = l;
    508         while(r < n && s[r] == '1') ++r;
    509         res = mul(res, dp[r - l - (r == n)][r == n? 1 : s[r] - '0']);
    510         if (l != r) lr.insert(make_pair(l, r - 1));
    511         l = r + 1;
    512     }
    513     
    514     for (int i = 0; i < m; ++i) {
    515         int pos;
    516         char x;
    517         scanf("%d %c\n", &pos, &x);
    518         --pos;
    519         if (x == '1') {
    520             if (s[pos] != '1'){ 
    521                 int l1, r1, l2, r2;
    522                 getLR(l1, r1, pos - 1);
    523                 getLR(l2, r2, pos + 1);
    524                 
    525                 int l = pos, r = pos;
    526                 if (l1 != -1) {
    527                     assert(r1 == pos - 1);
    528                     updRes(l1, r1, -1);
    529                     l = l1;
    530                 } else {
    531                     res = mul(res, inv(dp[0][s[pos] - '0']));
    532                 }
    533                 
    534                 if (l2 != -1) {
    535                     assert(l2 == pos + 1);
    536                     updRes(l2, r2, -1);
    537                     r = r2;
    538                 } else {
    539                     if (pos + 1 != n) res = mul(res, inv(dp[0][s[pos + 1] - '0']));
    540                 }
    541                 
    542                 s[pos] = x;
    543                 updRes(l, r, 1);
    544             }
    545         } else {
    546             if (s[pos] != '1') {
    547                 if (pos - 1 >= 0 && s[pos - 1] == '1') {
    548                     int l, r;
    549                     getLR(l, r, pos - 1);
    550                     updRes(l, r, -1);
    551                     s[pos] = x;
    552                     updRes(l, r, 1);
    553                 } else {
    554                     res = mul(res, dp[0][x - '0']);
    555                     res = mul(res, inv(dp[0][s[pos] - '0']));
    556                     s[pos] = x;
    557                 }
    558             } else {
    559                 int l, r;
    560                 getLR(l, r, pos);
    561                 assert(l != -1 && r != -1);
    562                 
    563                 updRes(l, r, -1);
    564                 s[pos] = x;
    565                 if (l == r) {
    566                     res = mul(res, dp[0][s[pos] - '0']);
    567                     if (pos + 1 < n) res = mul(res, dp[0][s[pos + 1] - '0']);
    568                 } else if (pos == l) {
    569                     res = mul(res, dp[0][s[pos] - '0']);
    570                     updRes(l + 1, r, 1);
    571                 } else if (pos == r) {
    572                     if (pos + 1 != n) res = mul(res, dp[0][s[pos + 1] - '0']);
    573                     updRes(l, r - 1, 1);
    574                 } else {
    575                     updRes(l, pos - 1, 1);
    576                     updRes(pos + 1, r, 1);
    577                 }
    578             }
    579             
    580         }
    581         printf("%d\n", res);
    582     }
    583 }
    584 ```
    585 
    586 [1380G - Circular Dungeon](/contest/1380/problem/G "Educational Codeforces Round 91 (Rated for Div. 2)")
    587 
    588 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    589 
    590 **Tutorial**
    591 
    592 At first, let's say that the expected value is equal to the average of total earnings over all positions and is equal to the sum of earnings over all positions divided by $n$. So we can trasition to minimizing the sum.
    593 
    594 Let's learn how to solve the task for some fixed $k$. Fix some arrangement and rotate the rooms so that the last room contains a mimic. So now you have $cnt_1$ regular chests, then a single mimic, $cnt_2$ regular chests, single mimic, $\dots$, $cnt_k$ regular chests, single mimic. All $cnt_i \ge 0$ and $\sum \limits_{i=1}^{k} cnt_i = n - k$.
    595 
    596 Take a look at some of these intervals of length $cnt_i$. The last chest in the interval is taken from $cnt_i$ starting positions, the second-to-last is taken $cnt_i - 1$ times and so on.
    597 
    598 Now let's find the optimal way to choose $cnt_i$. Fix some values of $cnt_i$. Take a look at the smallest of these values and the largest of them. Let the values be $x$ and $y$. If they differ by at least $2$ ($x \le y - 2$), then the smaller result can always be achieved by moving a regular chest from the larger one to the smaller one.
    599 
    600 **Proof**
    601 
    602 Consider two sequences of coefficients for both intervals: $[1, 2, \dots, x - 1, x]$ and $[1, 2, \dots, y - 1, y]$.
    603 
    604 However, if you remove one chest, then they will be equal to $[1, 2, \dots, x - 1, x, x + 1]$ and $[1, 2, \dots, y - 1]$.
    605 
    606 If you only consider the difference between the numbers of both sequences, then you can see that only coefficient $y$ got removed and coefficient $x + 1$ was added. So you can rearrange the chests in such a way that all chests are assigned to the same value and only the chest that was assigned to $y$ becomes assigned to $x+1$, thus decreasing the total value.
    607 
    608 Now we have all $cnt_i$ set now. The only thing left is to assign chests optimally. Write down the union of all the coefficient sequences from all the intervals $\bigcup \limits_{i=1}^{n-k} [1, \dots, cnt_i-1, cnt_i]$ and sort them in the non-decreasing order. It's easy to show that the chests should be sorted in the non-increasing order (really classical thing, you can try proving that by showing that any other arrangement can easily be improved once again).
    609 
    610 That allows us to write a solution in $O(n^2)$. Sort all the chests in the beginning, after that for some $k$ multiply the value of the $i$-th chest by $\lfloor \frac{i}{k} \rfloor$ and sum up the results.
    611 
    612 Finally, let's speed this up with prefix sums. Notice that the first $k$ values are multiplied by $0$, the second $k$ values — by $1$ and so on. If $n$ is not divisible by $k$, then the last block just has length smaller than $k$. Thus, we can calculate the answer for some $k$ in $O(\frac{n}{k})$. And that's equal to $O(\sum \limits_{k=1}^{n} \frac{n}{k})$ = $O(n \log n)$.
    613 
    614 Overall complexity: $O(n \log n)$.
    615 
    616 **Solution (pikmike)**
    617 
    618 ```
    619 #include <bits/stdc++.h>
    620 
    621 #define forn(i, n) for (int i = 0; i < int(n); i++)
    622 
    623 using namespace std;
    624 
    625 const int MOD = 998244353;
    626 
    627 int add(int a, int b){
    628 	a += b;
    629 	if (a >= MOD)
    630 		a -= MOD;
    631 	if (a < 0)
    632 		a += MOD;
    633 	return a;
    634 }
    635 
    636 int mul(int a, int b){
    637 	return a * 1ll * b % MOD;
    638 }
    639 
    640 int binpow(int a, int b){
    641 	int res = 1;
    642 	while (b){
    643 		if (b & 1)
    644 			res = mul(res, a);
    645 		a = mul(a, a);
    646 		b >>= 1;
    647 	}
    648 	return res;
    649 }
    650 
    651 vector<int> pr;
    652 
    653 int main() {
    654 	int n;
    655 	scanf("%d", &n);
    656 	vector<int> c(n);
    657 	forn(i, n)
    658 		scanf("%d", &c[i]);
    659 	sort(c.begin(), c.end(), greater<int>());
    660 	pr.push_back(0);
    661 	forn(i, n)
    662 		pr.push_back(add(pr.back(), c[i]));
    663 	
    664 	int invn = binpow(n, MOD - 2);
    665 	for (int k = 1; k <= n; ++k){
    666 		int ans = 0;
    667 		for (int i = 0, j = 0; i < n; i += k, ++j)
    668 			ans = add(ans, mul(j, add(pr[min(n, i + k)], -pr[i])));
    669 		printf("%d ", mul(ans, invn));
    670 	}
    671 	puts("");
    672 	
    673 	return 0;
    674 }
    675 ```