codeforces-scrape

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

1741.md (8782B)


      1 Source: https://codeforces.com/blog/entry/107908
      2 
      3 [1741A - Compare T-Shirt Sizes](/contest/1741/problem/A "Codeforces Round 826 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17  
     18 #define forn(i, n) for (int i = 0; i < int(n); i++)
     19 #define sz(v) (int)v.size()
     20 #define all(v) v.begin(),v.end()
     21 #define eb emplace_back
     22  
     23  
     24 void ct(char c) {
     25     cout << c << '\n';
     26 }
     27  
     28 void solve() {
     29     string a,b; cin >> a >> b;
     30     char ca = a.back();
     31     char cb = b.back();
     32     if (ca == cb) {
     33         if (sz(a) == sz(b)) cout << '=';
     34         else if (ca == 'S') {
     35             cout << (sz(a) < sz(b) ? '>' : '<');
     36         } else {
     37             cout << (sz(a) < sz(b) ? '<' : '>');
     38         }
     39     }else cout << (ca < cb ? '>' : '<');
     40     cout << '\n';
     41 }
     42  
     43 int main() {
     44     int t;
     45     cin >> t;
     46  
     47     forn(tt, t) {
     48         solve();
     49     }
     50 }
     51 ```
     52 
     53 [1741B - Funny Permutation](/contest/1741/problem/B "Codeforces Round 826 (Div. 3)")
     54 
     55 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     56 
     57 **Tutorial**
     58 
     59 Tutorial is loading...
     60 
     61 **Solution**
     62 
     63 ```
     64 #include "bits/stdc++.h"
     65 using namespace std;
     66 
     67 void solve(){
     68     int n;
     69     cin >> n;
     70     if(n == 3){
     71         cout << -1 << endl;
     72     }
     73     else{
     74         for(int i = 3; i <= n; i++) cout << i << ' ';
     75         cout << 2 << ' ' << 1 << endl;
     76     }
     77 }
     78 
     79 int main(){
     80     int t;
     81     cin >> t;
     82     while(t--){
     83         solve();
     84     }
     85 }
     86 ```
     87 
     88 [1741C - Minimize the Thickness](/contest/1741/problem/C "Codeforces Round 826 (Div. 3)")
     89 
     90 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     91 
     92 **Tutorial**
     93 
     94 Tutorial is loading...
     95 
     96 **Solution**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100 
    101 using namespace std;
    102 
    103 const int MAXN = 2020;
    104 
    105 int n;
    106 int arr[MAXN];
    107 
    108 int go(int i, int sum) {
    109 	if (i == n) return 0;
    110 	for (int j = i + 1, cur = 0; j <= n; ++j) {
    111 		cur += arr[j - 1];
    112 		if (cur > sum) return n;
    113 		if (cur == sum) return max(j - i, go(j, sum));
    114 	}
    115 	return n;
    116 }
    117 
    118 int solve() {
    119 	int ans = n;
    120 	for (int len = 1, sum = 0; len < n; ++len) {
    121 		sum += arr[len - 1];
    122 		ans = min(ans, go(0, sum));
    123 	}
    124 	return ans;
    125 }
    126 
    127 int main() {
    128 	int t; cin >> t;
    129 	while (t--) {
    130 		cin >> n;
    131 		for (int i = 0; i < n; ++i)
    132 			cin >> arr[i];
    133 		cout << solve() << endl;
    134 	}
    135 }
    136 ```
    137 
    138 [1741D - Masha and a Beautiful Tree](/contest/1741/problem/D "Codeforces Round 826 (Div. 3)")
    139 
    140 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40")
    141 
    142 **Tutorial**
    143 
    144 Tutorial is loading...
    145 
    146 **Solution**
    147 
    148 ```
    149 #include <bits/stdc++.h>
    150 
    151 using namespace std;
    152 
    153 const int MAXM = 300300;
    154 
    155 int n, m;
    156 int arr[MAXM];
    157 
    158 int solve(int l, int r) {
    159 	if (r - l == 1) return 0;
    160 	int mid = (l + r) >> 1;
    161 	int mal = *max_element(arr + l, arr + mid);
    162 	int mar = *max_element(arr + mid, arr + r);
    163 	int ans = 0;
    164 	if (mal > mar) {
    165 		++ans;
    166 		for (int i = 0; i < (mid - l); ++i)
    167 			swap(arr[l + i], arr[mid + i]);
    168 	}
    169 	return solve(l, mid) + solve(mid, r) + ans;
    170 }
    171 
    172 int solve() {
    173 	int ans = solve(0, m);
    174 	if (is_sorted(arr, arr + m))
    175 		return ans;
    176 	return -1;
    177 }
    178 
    179 int main() {
    180 	int t; cin >> t;
    181 	while (t--) {
    182 		cin >> m;
    183 		for (int i = 0; i < m; ++i)
    184 			cin >> arr[i];
    185 		cout << solve() << endl;
    186 	}
    187 }
    188 ```
    189 
    190 [1741E - Sending a Sequence Over the Network](/contest/1741/problem/E "Codeforces Round 826 (Div. 3)")
    191 
    192 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    193 
    194 **Tutorial**
    195 
    196 Tutorial is loading...
    197 
    198 **Solution**
    199 
    200 ```
    201 #include <bits/stdc++.h>
    202 
    203 using namespace std;
    204 
    205 #define forn(i, n) for (int i = 0; i < int(n); i++)
    206 #define sz(v) (int)v.size()
    207 #define all(v) v.begin(),v.end()
    208 #define eb emplace_back
    209 
    210 void solve() {
    211     int n; cin >> n;
    212     vector<int> a(n+1);
    213     for (int i = 1; i <= n; ++i) {
    214         cin >> a[i];
    215     }
    216 
    217     vector<bool> dp(n+1, false);
    218     dp[0] = true;
    219     for (int i = 1; i <= n; ++i) {
    220         if (i + a[i] <= n && dp[i-1]) dp[i + a[i]] = true;
    221         if (i - a[i] - 1 >= 0 && dp[i - a[i] - 1]) dp[i] = true;
    222     }
    223     cout << (dp[n] ? "YES" : "NO") << '\n';
    224 }
    225 
    226 int main() {
    227     int t;
    228     cin >> t;
    229 
    230     forn(tt, t) {
    231         solve();
    232     }
    233 }
    234 ```
    235 
    236 [1741F - Multi-Colored Segments](/contest/1741/problem/F "Codeforces Round 826 (Div. 3)")
    237 
    238 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
    239 
    240 **Tutorial**
    241 
    242 Tutorial is loading...
    243 
    244 **Solution**
    245 
    246 ```
    247 #include <iostream>
    248 #include <vector>
    249 #include <algorithm>
    250 #include <set>
    251 #include <queue>
    252 
    253 using namespace std;
    254 
    255 int n;
    256 
    257 vector<int> calc(vector<vector<int>> a) {
    258     vector<pair<int, int>> l(n), r(n);
    259     for (int i = 0; i < n; ++i) {
    260         l[i] = {a[i][0], i};
    261         r[i] = {a[i][1], i};
    262     }
    263     sort(l.begin(), l.end());
    264     sort(r.begin(), r.end());
    265     vector<vector<pair<int, int>>> suf(n);
    266     vector<pair<int, int>> curr;
    267     for (int i0 = n - 1; i0 >= 0; --i0) {
    268         int xr = r[i0].first;
    269         int i = r[i0].second;
    270         int xl = a[i][0];
    271         int c = a[i][2];
    272         if (curr.empty()) {
    273             curr.emplace_back(xl, c);
    274         } else if (curr.size() == 1) {
    275             if (curr[0].second == c) {
    276                 curr[0].first = min(curr[0].first, xl);
    277             } else {
    278                 curr.emplace_back(xl, c);
    279             }
    280         } else {
    281             if (curr[0].second == c) {
    282                 curr[0].first = min(curr[0].first, xl);
    283             } else if (curr[1].second == c) {
    284                 curr[1].first = min(curr[1].first, xl);
    285             } else {
    286                 curr.emplace_back(xl, c);
    287             }
    288         }
    289         sort(curr.begin(), curr.end());
    290         if (curr.size() == 3) {
    291             curr.pop_back();
    292         }
    293         suf[i0] = curr;
    294     }
    295     vector<int> ans(n, 1e9);
    296     int j = 0;
    297     for (int i0 = 0; i0 < n; ++i0) {
    298         int xl = l[i0].first, i = l[i0].second;
    299         int xr = a[i][1], c = a[i][2];
    300         while (j < n && r[j].first < xl) {
    301             j++;
    302         }
    303         if (j < n) {
    304             vector<pair<int, int>> s = suf[j];
    305             if (s[0].second != c) {
    306                 ans[i] = min(ans[i], max(0, s[0].first - xr));
    307             } else if (s.size() == 2) {
    308                 ans[i] = min(ans[i], max(0, s[1].first - xr));
    309             }
    310         }
    311     }
    312     return ans;
    313 }
    314 
    315 const int K = 1e9 + 1;
    316 
    317 void solve() {
    318     cin >> n;
    319     vector<vector<int>> a(n, vector<int>(3)), b(n, vector<int>(3));
    320     vector<pair<int, int>> l(n), r(n);
    321     for (int i = 0; i < n; ++i) {
    322         for (int j = 0; j < 3; ++j) {
    323             cin >> a[i][j];
    324             if (j == 2) {
    325                 b[i][j] = a[i][j];
    326             } else {
    327                 b[i][1 - j] = K - a[i][j];
    328             }
    329         }
    330     }
    331     vector<int> ans1 = calc(a), ans2 = calc(b);
    332     for (int i = 0; i < n; ++i) {
    333         cout << min(ans1[i], ans2[i]) << ' ';
    334     }
    335     cout << '\n';
    336 }
    337 
    338 int main() {
    339     ios_base::sync_with_stdio(0);
    340     cin.tie(0), cout.tie(0);
    341     int t = 1;
    342     cin >> t;
    343     for (int it = 0; it < t; ++it) {
    344         solve();
    345     }
    346     return 0;
    347 }
    348 ```
    349 
    350 [1741G - Kirill and Company](/contest/1741/problem/G "Codeforces Round 826 (Div. 3)")
    351 
    352 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    353 
    354 **Tutorial**
    355 
    356 Tutorial is loading...
    357 
    358 **Solution**
    359 
    360 ```
    361 from collections import deque
    362  
    363  
    364 def solve():
    365     n, m = map(int, input().split())
    366     sl = [[] for _ in range(n)]
    367     for _ in range(m):
    368         u, v = map(int, input().split())
    369         u -= 1
    370         v -= 1
    371         sl[u] += [v]
    372         sl[v] += [u]
    373     f = int(input())
    374     h = [int(x) - 1 for x in input().split()]
    375     mask = [0] * n
    376     k = int(input())
    377     p = [int(x) - 1 for x in input().split()] + [-1]
    378     for i in range(k):
    379         mask[h[p[i]]] += 1 << i
    380     vars = [set() for _ in range(n)]
    381     dist = [-1] * n
    382     dist[0] = 0
    383     vars[0].add(mask[0])
    384     q = deque([0])
    385     while len(q) > 0:
    386         v = q.popleft()
    387         for u in sl[v]:
    388             if dist[u] == -1:
    389                 dist[u] = dist[v] + 1
    390                 q.append(u)
    391             if dist[u] == dist[v] + 1:
    392                 for msk in vars[v]:
    393                     vars[u].add(msk | mask[u])
    394     backpack = [False] * (1 << k)
    395     backpack[0] = True
    396     j = 0
    397     for i in range(f):
    398         if i == p[j]:
    399             j += 1
    400             continue
    401         nw = backpack.copy()
    402         for msk in range(1 << k):
    403             if not backpack[msk]:
    404                 continue
    405             for var in vars[h[i]]:
    406                 nw[msk | var] = True
    407         backpack, nw = nw, backpack
    408     mn = k
    409     for msk in range(1 << k):
    410         if not backpack[msk]:
    411             continue
    412         ans = 0
    413         for b in range(k):
    414             if msk & (1 << b) == 0:
    415                 ans += 1
    416         mn = min(mn, ans)
    417     print(mn)
    418  
    419  
    420 t = int(input())
    421 for _ in range(t):
    422     solve()
    423 ```