codeforces-scrape

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

1684.md (12742B)


      1 Source: https://codeforces.com/blog/entry/102995
      2 
      3 We know about FST and we are really, really sorry about it. Even though we still hope that you liked the problems.
      4 
      5 **A: Digit Minimization**
      6 
      7 [1684A - Digit Minimization](/contest/1684/problem/A)
      8 
      9 **Editorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Implementation**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 using namespace std;
     18 
     19 int main() {
     20     int T;
     21     cin >> T;
     22     while (T --> 0) {
     23         string n;
     24         cin >> n;
     25         if (n.size() == 2) {
     26             cout << n[1] << '\n';
     27         } else {
     28             cout << *min_element(n.begin(), n.end()) << '\n';
     29         }
     30     }
     31     return 0;
     32 }
     33 ```
     34 
     35 **B: Z mod X = C**
     36 
     37 [1684B - Z mod X = C](/contest/1684/problem/B)
     38 
     39 **Editorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Implementation**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47 using namespace std;
     48 
     49 void solve() {
     50     int a, b, c;
     51     cin >> a >> b >> c;
     52     cout << a + b + c << " " << b + c << " " << c << "\n";
     53 }
     54 
     55 int main() {
     56     int t;
     57     cin >> t;
     58     while (t--) solve();
     59     return 0;
     60 }
     61 ```
     62 
     63 **C: Column Swapping**
     64 
     65 [1684C - Column Swapping](/contest/1684/problem/C)
     66 
     67 **Editorial**
     68 
     69 Tutorial is loading...
     70 
     71 **Implementation**
     72 
     73 ```
     74 #include <bits/stdc++.h>
     75 
     76 using namespace std;
     77 
     78 void solve(vector<vector<int>> &a) {
     79     int n = a.size(), m = a[0].size();
     80     vector<int> bad;
     81     for (int i = 0; i < n && bad.empty(); i++) {
     82         vector<int> b = a[i];
     83         sort(b.begin(), b.end());
     84         for (int j = 0; j < m; j++) {
     85             if (a[i][j] != b[j]) bad.push_back(j);
     86         }
     87     }
     88     if ((int)bad.size() == 0) {
     89     	cout << 1 << " " << 1 << "\n";
     90     	return;
     91     }
     92     if ((int)bad.size() > 2) {
     93     	cout << -1 << "\n";
     94     	return;
     95     }
     96     for (int i = 0; i < n; i++) {
     97         swap(a[i][bad[0]], a[i][bad[1]]);
     98     }
     99     for (int i = 0; i < n; i++) {
    100         for (int j = 1; j < m; j++) {
    101             if (a[i][j] < a[i][j - 1]) {
    102             	cout << -1 << "\n";
    103             	return;
    104            	}
    105         }
    106     }
    107     cout << bad[0] + 1 << " " << bad[1] + 1 << "\n";
    108     return;
    109 }
    110 
    111 int main() {
    112 	#ifdef LOCAL
    113         freopen("input.txt", "r", stdin);
    114         freopen("output.txt", "w", stdout);
    115     #else
    116         ios_base::sync_with_stdio(0);
    117         cin.tie(0);
    118         cout.tie(0);
    119     #endif
    120 	int T;
    121 	cin >> T;
    122 	while (T--) {
    123 		int n, m;
    124 		cin >> n >> m;
    125 		vector<vector<int>> a(n, vector<int>(m));
    126 		for (int i = 0; i < n; i++) {
    127 			for (int j = 0; j < m; j++) {
    128 				cin >> a[i][j];
    129 			}
    130 		}
    131 		solve(a);
    132 	}
    133 	return 0;
    134 }
    135 ```
    136 
    137 **D: Traps**
    138 
    139 [1684D - Traps](/contest/1684/problem/D)
    140 
    141 **Editorial**
    142 
    143 Tutorial is loading...
    144 
    145 **Implementation**
    146 
    147 ```
    148 #include <bits/stdc++.h>
    149 using namespace std;
    150 
    151 #define all(x) (x).begin(), (x).end()
    152 
    153 void solve() {
    154     int n, k;
    155     cin >> n >> k;
    156     long long ans = 0;
    157     vector<int> a(n);
    158     for (int i = 0; i < n; i++) {
    159         cin >> a[i];
    160         ans += a[i];
    161         a[i] += i + 1;
    162     }
    163     sort(all(a));
    164     reverse(all(a));
    165     for (int i = 0; i < k; i++) ans -= a[i];
    166     for (int i = 0; i < k; i++) {
    167         ans += n;
    168         ans -= i;
    169     }
    170     cout << ans << "\n";
    171 }
    172 
    173 int main() {
    174     #ifdef LOCAL
    175         freopen("input.txt", "r", stdin);
    176         freopen("output.txt", "w", stdout);
    177     #else
    178         ios_base::sync_with_stdio(0);
    179         cin.tie(0);
    180         cout.tie(0);
    181     #endif
    182     int t;
    183     cin >> t;
    184     while (t--) solve();
    185     return 0;
    186 }
    187 ```
    188 
    189 **E: MEX vs DIFF**
    190 
    191 [1684E - MEX vs DIFF](/contest/1684/problem/E)
    192 
    193 **Editorial**
    194 
    195 Tutorial is loading...
    196 
    197 **Implementation**
    198 
    199 ```
    200 #include <bits/stdc++.h>
    201 
    202 using namespace std;
    203 
    204 #define pb emplace_back
    205 #define all(x) (x).begin(), (x).end()
    206 #define fi first
    207 #define se second
    208 #define pii pair<int, int>
    209 #define puu pair<unsigned, unsigned>
    210 #define ll long long
    211 #define mp make_pair
    212 #define ui unsigned
    213 #define ull unsigned long long
    214 #define ld double
    215 #define pld pair<ld, ld>
    216 #define pll pair<ll, ll>
    217 
    218 const int INF = 1e9 + 1;
    219 const ll INFLL = 1e18;
    220 
    221 void solve() {
    222     int n, k;
    223     cin >> n >> k;
    224     vector<int> a(n);
    225     for (auto &c : a) cin >> c;
    226     map<int, int> cnt;
    227     for (auto &c : a) cnt[c]++;
    228     set<pii> s1, s2;
    229     int sum1 = 0;
    230     for (auto &c : cnt) s2.insert(mp(c.se, c.fi));
    231     int ans = INF;
    232     int skip = 0;
    233     for (int x = 0; x <= n; x++) {
    234         if (s1.find(mp(cnt[x - 1], x - 1)) != s1.end()) {
    235             sum1 -= cnt[x - 1];
    236             s1.erase(mp(cnt[x - 1], x - 1));
    237         }
    238         if (s2.find(mp(cnt[x - 1], x - 1)) != s2.end()) {
    239             s2.erase(mp(cnt[x - 1], x - 1));
    240         }
    241         while (s2.size() && sum1 + s2.begin()->fi <= k) {
    242             s1.insert(*s2.begin());
    243             sum1 += s2.begin()->fi;
    244             s2.erase(s2.begin());
    245         }
    246         if (k < skip) break;
    247         int now = x + s2.size();
    248         if (x == 0) {
    249             now = max(1, (int)s2.size());
    250         }
    251         ans = min(ans, now - x);
    252         if (cnt[x] == 0) skip++;
    253     }
    254     cout << ans << "\n";
    255 }
    256 
    257 int main() {
    258     #ifdef LOCAL
    259         freopen("input.txt", "r", stdin);
    260         freopen("output.txt", "w", stdout);
    261     #else
    262         ios_base::sync_with_stdio(0);
    263         cin.tie(0);
    264         cout.tie(0);
    265     #endif
    266     int t;
    267     cin >> t;
    268     while (t--) solve();
    269     return 0;
    270 }
    271 ```
    272 
    273 **F: Diverse Segments**
    274 
    275 [1684F - Diverse Segments](/contest/1684/problem/F)
    276 
    277 **Editorial**
    278 
    279 Tutorial is loading...
    280 
    281 **Implementation**
    282 
    283 ```
    284 #include <bits/stdc++.h>
    285 
    286 using namespace std;
    287 
    288 #define pb emplace_back
    289 #define all(x) (x).begin(), (x).end()
    290 #define fi first
    291 #define se second
    292 #define pii pair<int, int>
    293 #define puu pair<unsigned, unsigned>
    294 #define ll long long
    295 #define mp make_pair
    296 #define ui unsigned
    297 #define ull unsigned long long
    298 #define ld double
    299 #define pld pair<ld, ld>
    300 #define pll pair<ll, ll>
    301 
    302 const int INF = 1e9 + 1;
    303 const ll INFLL = 1e18;
    304 
    305 vector<int> f;
    306 
    307 void incr(int x, int d) {
    308     for (; x < (int)f.size(); x |= (x + 1)) f[x] = max(f[x], d);
    309 }
    310 
    311 int get(int x) {
    312     int ans = -1;
    313     for (; x >= 0; x = (x & (x + 1)) - 1) ans = max(ans, f[x]);
    314     return ans;
    315 }
    316 
    317 void solve() {
    318     int n, m;
    319     cin >> n >> m;
    320     vector<int> a(n);
    321     for (auto &c : a) cin >> c;
    322     map<int, vector<int>> gist;
    323     for (int i = 0; i < n; i++) gist[a[i]].pb(i);
    324     vector<pii> seg(m);
    325     f.assign(n, -1);
    326     for (auto &c : seg) {
    327         cin >> c.fi >> c.se; c.fi--; c.se--;
    328         incr(c.fi, c.se);
    329     }
    330     vector<int> mnl(n);
    331     set<int> s;
    332     int l = n;
    333     for (int r = n - 1; r >= 0; r--) {
    334         while (l - 1 >= 0 && !s.count(a[l - 1])) {
    335             l--;
    336             s.insert(a[l]);
    337         }
    338         mnl[r] = l;
    339         s.erase(a[r]);
    340     }
    341     int mnr = -1;
    342     for (auto &c : seg) {
    343         int l = c.fi, r = c.se;
    344         if (mnl[r] <= l) continue;
    345         mnr = max(mnr, mnl[r] - 1);
    346     }
    347     if (mnr == -1) {
    348         cout << 0 << "\n";
    349         return;
    350     }
    351     int ans = mnr + 1;
    352     for (int l = 0; l + 1 < n; l++) {
    353         if (gist[a[l]][0] != l) {
    354             int id = lower_bound(all(gist[a[l]]), l) - gist[a[l]].begin() - 1;
    355             int pr = gist[a[l]][id];
    356             if (get(pr) >= l) {
    357                 break;
    358             }
    359         }
    360         int id = upper_bound(all(gist[a[l]]), mnr) - gist[a[l]].begin();
    361         if (id != (int)gist[a[l]].size()) {
    362             int nxt = gist[a[l]][id];
    363             if (get(l) >= nxt) {
    364                 mnr = nxt;
    365             }
    366         }
    367         mnr = max(mnr, l + 1);
    368         ans = min(ans, mnr - l);
    369     }
    370     cout << ans << "\n";
    371 }
    372 
    373 int main() {
    374     #ifdef LOCAL
    375         freopen("input.txt", "r", stdin);
    376         freopen("output.txt", "w", stdout);
    377     #else
    378         ios_base::sync_with_stdio(0);
    379         cin.tie(0);
    380         cout.tie(0);
    381     #endif
    382     int t;
    383     cin >> t;
    384     while (t--) solve();
    385     return 0;
    386 }
    387 ```
    388 
    389 **G: Euclid Guess**
    390 
    391 [1684G - Euclid Guess](/contest/1684/problem/G)
    392 
    393 **Editorial**
    394 
    395 Tutorial is loading...
    396 
    397 **Implementation**
    398 
    399 ```
    400 #include <bits/stdc++.h>
    401  
    402 using namespace std;
    403  
    404 #define pb emplace_back
    405 #define all(x) (x).begin(), (x).end()
    406 #define fi first
    407 #define se second
    408 #define pii pair<int, int>
    409 #define puu pair<unsigned, unsigned>
    410 #define ll long long
    411 #define mp make_pair
    412 #define ui unsigned
    413 #define ull unsigned long long
    414 #define ld double
    415 #define pld pair<ld, ld>
    416 #define pll pair<ll, ll>
    417 #define int ll
    418 
    419 const int INF = 1e9 + 1;
    420 const ll INFLL = 1e18;
    421  
    422 vector<vector<int>> g;
    423 vector<int> with;
    424 vector<int> usd;
    425  
    426 int dfs(int v) {
    427     if (usd[v]) return 0;
    428     usd[v] = 1;
    429     for (auto &to : g[v]) {
    430         if (with[to] == -1) {
    431             with[to] = v;
    432             return 1;
    433         }
    434     }
    435     for (auto &to : g[v]) {
    436         if (dfs(with[to])) {
    437             with[to] = v;
    438             return 1;
    439         }
    440     }
    441     return 0;
    442 }
    443 
    444 signed main() {
    445     #ifdef LOCAL
    446         freopen("input.txt", "r", stdin);
    447         freopen("output.txt", "w", stdout);
    448     #else
    449         ios_base::sync_with_stdio(0);
    450         cin.tie(0);
    451         cout.tie(0);
    452     #endif
    453     int n, A;
    454     cin >> n >> A;
    455     vector<int> a(n);
    456     vector<int> l, r;
    457     for (auto &c : a) {
    458         cin >> c;
    459         if (3 * c > A) {
    460             l.pb(c);
    461         } else {
    462             r.pb(c);
    463         }
    464     }
    465     g.resize(l.size());
    466     with.resize(r.size(), -1);
    467     for (int i = 0; i < (int)l.size(); i++) {
    468         for (int j = 0; j < (int)r.size(); j++) {
    469             if (l[i] % r[j] == 0 && 2 * l[i] + r[j] <= A) {
    470                 g[i].pb(j);
    471             }
    472         }
    473     }
    474     int cnt = 0;
    475     for (int i = 0; i < (int)l.size(); i++) {
    476         usd.assign(l.size(), 0);
    477         cnt += dfs(i);
    478     }
    479     if (cnt < (int)l.size()) {
    480         cout << -1;
    481         return 0;
    482     }
    483     vector<pii> ans;
    484     for (int j = 0; j < (int)r.size(); j++) {
    485         if (with[j] == -1) {
    486             ans.pb(3 * r[j], 2 * r[j]);
    487         } else {
    488             ans.pb(2 * l[with[j]] + r[j], l[with[j]] + r[j]);
    489         }
    490     }
    491     cout << ans.size() << "\n";
    492     for (auto &c : ans) cout << c.fi << " " << c.se << "\n";
    493     return 0;
    494 }
    495 ```
    496 
    497 **H: Hard Cut**
    498 
    499 [1684H - Hard Cut](/contest/1684/problem/H)
    500 
    501 **Editorial**
    502 
    503 Tutorial is loading...
    504 
    505 **Implementation**
    506 
    507 ```
    508 #include <bits/stdc++.h>
    509 using namespace std;
    510 
    511 const int MAXN = 1e6;
    512 int g[MAXN + 1];
    513 string s;
    514 
    515 vector<pair<int, int>> segments; // [l, r]
    516 
    517 int get(int k, int i) { // get k-th '1' on [i, |s|)
    518 	--i;
    519 	while (k --> 0) i = s.find('1', i + 1);
    520 	return i;
    521 }
    522 
    523 void five() {
    524 	int first = get(1, 0), last = get(5, 0);
    525 	int r = (int)s.size() - 1;
    526 	if (last - first + 1 == 5) { // creating 16: ['001111', '1', '0000']
    527 		segments.emplace_back(0, last - 1);
    528 		segments.emplace_back(last, last);
    529 		if (last < r) segments.emplace_back(last + 1, r);
    530 	} else { // creating 8: cut out '101' or '100' and cut everything in single digits
    531 		int pos = s.find("101");
    532 		if (pos == string::npos) pos = s.find("100");
    533 		for (int i = 0; i < pos; ++i) segments.emplace_back(i, i);
    534 		segments.emplace_back(pos, pos + 2);
    535 		for (int i = pos + 3; i <= r; ++i) segments.emplace_back(i, i);
    536 	}
    537 }
    538 
    539 void solve(int l, int r, int k, int n) { // [l; r]
    540 	if (k == n) { // cutting into single digits
    541 		for (int i = l; i <= r; ++i) segments.emplace_back(i, i);
    542 
    543 	} else if (k == 2 && n == 3) {
    544 		int pos = get(1, l);
    545 		if (s[pos + 1] == '1') { // ['11', '00...00']
    546 			segments.emplace_back(l, pos + 1);
    547 			if (pos + 2 <= r) segments.emplace_back(pos + 2, r);
    548 
    549 		} else { // ['10', '0001', '00000']
    550 			int newpos = get(1, pos + 1);
    551 			segments.emplace_back(l, pos + 1);
    552 			segments.emplace_back(pos + 2, newpos);
    553 			if (newpos + 1 <= r) segments.emplace_back(newpos + 1, r);
    554 		}
    555 
    556 	} else if (3 * k / 2 >= n) { // using previous if technique
    557 		int pos = get(2, l);
    558 		solve(l, pos, 2, 3);
    559 		if (k > 2) solve(pos + 1, r, k - 2, n - 3);
    560 
    561 	} else if ((k == 4 && n == 8) || (k == 9 && n == 16)) {
    562 		int pos = get(1, l);
    563 		string sub = s.substr(pos, 3);
    564 		segments.emplace_back(l, pos + 2);
    565 		if (sub == "100") solve(pos + 3, r, k - 1, n - 4);
    566 		if (sub == "101") solve(pos + 3, r, k - 2, n - 5);
    567 		if (sub == "110") solve(pos + 3, r, k - 2, n - 6);
    568 		if (sub == "111") solve(pos + 3, r, k - 3, n - 7);
    569 
    570 	} else if ((k == 7 && n == 11) || (k == 10 && n == 16)) {
    571 		int mid = get(4, l);
    572 		solve(l, mid, 4, 8);
    573 		solve(mid + 1, r, k - 4, n - 8);
    574 
    575 	} else { // common case
    576 		int mid = get(k / 2, l);
    577 		solve(l, mid, k / 2, n / 2);
    578 		solve(mid + 1, r, k - k / 2, n / 2);
    579 
    580 	}
    581 }
    582 
    583 signed main() {
    584 	ios_base::sync_with_stdio(false);
    585 	cin.tie(nullptr);
    586 	g[1] = 1;
    587 	for (int i = 2; i <= MAXN; ++i) g[i] = g[(i + 1) / 2] * 2;
    588 	int T;
    589 	cin >> T;
    590 	while (T --> 0) {
    591 		cin >> s;
    592 		int k = count(s.begin(), s.end(), '1');
    593 		if (!k) {
    594 			cout << -1 << '\n';
    595 			continue;
    596 		}
    597 		segments.clear();
    598 		if (k == 5) five();
    599 		else solve(0, (int)s.size() - 1, k, g[k]);
    600 		cout << segments.size() << '\n';
    601 		for (auto &[l, r] : segments) {
    602 			cout << l + 1 << ' ' << r + 1 << '\n';
    603 		}
    604 	}
    605 	return 0;
    606 }
    607 ```