codeforces-scrape

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

2069.md (8740B)


      1 Source: https://codeforces.com/blog/entry/139774
      2 
      3 [2069A - Was there an Array?](/contest/2069/problem/A "Educational Codeforces Round 174 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     n = int(input())
     17     s = list(input().split())
     18     s = "".join(s)
     19     if "101" in s:
     20         print('NO')
     21     else:
     22         print('YES')
     23 ```
     24 
     25 [2069B - Set of Strangers](/contest/2069/problem/B "Educational Codeforces Round 174 (Rated for Div. 2)")
     26 
     27 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     28 
     29 **Tutorial**
     30 
     31 Tutorial is loading...
     32 
     33 **Solution (adedalic)**
     34 
     35 ```
     36 for _ in range(int(input())):
     37     n, m = map(int, input().split())
     38     a = [list(map(int, input().split())) for i in range(n)]
     39     hasColor = [0] * (n * m)
     40     hasBad = [0] * (n * m)
     41     for i in range(n):
     42         for j in range(m):
     43             hasColor[a[i][j] - 1] = 1
     44             if i + 1 < n and a[i][j] == a[i + 1][j]:
     45                 hasBad[a[i][j] - 1] = 1
     46             if j + 1 < m and a[i][j] == a[i][j + 1]:
     47                 hasBad[a[i][j] - 1] = 1
     48     print(sum(hasColor) + sum(hasBad) - 1 - max(hasBad))
     49 ```
     50 
     51 [2069C - Beautiful Sequence](/contest/2069/problem/C "Educational Codeforces Round 174 (Rated for Div. 2)")
     52 
     53 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     54 
     55 **Tutorial**
     56 
     57 Tutorial is loading...
     58 
     59 **Solution (Neon)**
     60 
     61 ```
     62 #include <bits/stdc++.h>
     63  
     64 using namespace std;
     65 
     66 const int MOD = 998244353;
     67 
     68 int add(int x, int y) {
     69   x += y;
     70   if (x >= MOD) x -= MOD;
     71   return x;
     72 }
     73 
     74 int main() {
     75   int t;
     76   cin >> t;
     77   while (t--) {
     78     int n;
     79     cin >> n;
     80     vector<int> dp(4, 0);
     81     dp[0] = 1;
     82     while (n--) {
     83       int x;
     84       cin >> x;
     85       if (x == 2) dp[x] = add(dp[x], dp[x]);
     86       dp[x] = add(dp[x], dp[x - 1]);
     87     }
     88     cout << dp[3] << '\n';
     89   }
     90 }
     91 ```
     92 
     93 [2069D - Palindrome Shuffle](/contest/2069/problem/D "Educational Codeforces Round 174 (Rated for Div. 2)")
     94 
     95 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     96 
     97 **Tutorial**
     98 
     99 Tutorial is loading...
    100 
    101 **Solution (Neon)**
    102 
    103 ```
    104 #include <bits/stdc++.h>
    105  
    106 using namespace std;
    107 
    108 int main() {
    109   int t;
    110   cin >> t;
    111   while (t--) {
    112     string s;
    113     cin >> s;
    114     int n = s.size();
    115     int i = 0;
    116     while (i < n / 2 && s[i] == s[n - i - 1]) ++i;
    117     n -= 2 * i;
    118     s = s.substr(i, n);
    119     int ans = n;
    120     for (int z = 0; z < 2; ++z) {
    121       int l = 0, r = n;
    122       while (l <= r) {
    123         int m = (l + r) / 2;
    124         vector<int> cnt(26);
    125         for (int i = 0; i < m; ++i)
    126           cnt[s[i] - 'a']++;
    127         bool ok = true;
    128         for (int i = 0; i < min(n / 2, n - m); ++i) {
    129           char c = s[n - i - 1];
    130           if (i < m) {
    131             ok &= cnt[c - 'a'] > 0;
    132             cnt[c - 'a']--;
    133           } else {
    134             ok &= (c == s[i]);
    135           }
    136         }
    137         for (auto x : cnt)
    138           ok &= (x % 2 == 0);
    139         if (ok) {
    140           r = m - 1;
    141         } else {
    142           l = m + 1;
    143         }
    144       }
    145       ans = min(ans, r + 1); 
    146       reverse(s.begin(), s.end());
    147     }
    148     cout << ans << '\n';
    149   }
    150 }
    151 ```
    152 
    153 [2069E - A, B, AB and BA](/contest/2069/problem/E "Educational Codeforces Round 174 (Rated for Div. 2)")
    154 
    155 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    156 
    157 **Tutorial**
    158 
    159 Tutorial is loading...
    160 
    161 **Solution (adedalic)**
    162 
    163 ```
    164 #include<bits/stdc++.h>
    165 
    166 using namespace std;
    167 
    168 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    169 #define sz(a) int((a).size())
    170 
    171 typedef long long li;
    172 
    173 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    174 	return out << "(" << p.x << ", " << p.y << ")";
    175 }
    176 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    177 	fore(i, 0, sz(v)) {
    178 		if(i) out << " ";
    179 		out << v[i];
    180 	}
    181 	return out;
    182 }
    183 
    184 const int INF = int(1e9);
    185 const li INF64 = li(1e18);
    186 
    187 string s;
    188 int a, b, ab, ba;
    189 
    190 inline bool read() {
    191 	if(!(cin >> s))
    192 		return false;
    193 	cin >> a >> b >> ab >> ba;
    194 	return true;
    195 }
    196 
    197 int process(vector<int> &rem, int &tot) {
    198 	int placed = 0;
    199 	sort(rem.begin(), rem.end(), greater<int>());
    200 	while (!rem.empty() && tot > 0) {
    201 		int cnt = min(rem.back() / 2, tot);
    202 		placed += cnt;
    203 		tot -= cnt;
    204 		rem.back() -= 2 * cnt;
    205 		if (rem.back() == 0)
    206 			rem.pop_back();
    207 	}
    208 	return placed;
    209 }
    210 
    211 int remnants(vector<int> &rem, int &tot) {
    212 	int placed = 0;
    213 	for (int &cur : rem) {
    214 		int cnt = min(tot, (cur - 2) / 2);
    215 		placed += cnt;
    216 		tot -= cnt;
    217 		cur -= 2 * cnt + 2;
    218 	}
    219 	return placed;
    220 }
    221 
    222 inline void solve() {
    223 	s.push_back(s.back());
    224 	int eq = 0, placedPairs = 0;
    225 	vector<int> remAB, remBA;
    226 
    227 	int lst = 0;
    228 //	cerr << "s = " << s << endl;
    229 	fore (i, 1, sz(s)) {
    230 		if (s[i] != s[i - 1])
    231 			continue;
    232 		
    233 		if (s[lst] == s[i - 1]) {
    234 			// ABA..A or BAB..B
    235 			eq += (i - lst) / 2;
    236 		}
    237 		else {
    238 			int len = i - lst;
    239 			if (s[lst] == 'A') {
    240 				// ABA..B
    241 				remAB.push_back(len);
    242 			}
    243 			else {
    244 				// BAB..A
    245 				remBA.push_back(len);
    246 			}
    247 		}
    248 //		cerr << lst << ", " << i << endl;
    249 		lst = i;
    250 	}
    251 	s.pop_back();
    252 	
    253 	placedPairs += process(remAB, ab);
    254 	assert(remAB.empty() || ab == 0);
    255 
    256 	placedPairs += process(remBA, ba);
    257 	assert(remBA.empty() || ba == 0);
    258 
    259 	placedPairs += remnants(remAB, ba);
    260 	placedPairs += remnants(remBA, ab);
    261 
    262 	int remPlaced = min(eq, ab + ba);
    263 	placedPairs += remPlaced;
    264 
    265 	int needA = count(s.begin(), s.end(), 'A') - placedPairs;
    266 	int needB = count(s.begin(), s.end(), 'B') - placedPairs;
    267 
    268 	if (needA <= a && needB <= b)
    269 		cout << "YES\n";
    270 	else
    271 		cout << "NO\n";
    272 }
    273 
    274 int main() {
    275 #ifdef _DEBUG
    276 	freopen("input.txt", "r", stdin);
    277 	int tt = clock();
    278 #endif
    279 	ios_base::sync_with_stdio(false);
    280 	cin.tie(0), cout.tie(0);
    281 	cout << fixed << setprecision(15);
    282 	
    283 	int t; cin >> t;
    284 	while (t--) {
    285 		read();
    286 		solve();
    287 		
    288 #ifdef _DEBUG
    289 		cerr << "TIME = " << clock() - tt << endl;
    290 		tt = clock();
    291 #endif
    292 	}
    293 	return 0;
    294 }
    295 ```
    296 
    297 [2069F - Graph Inclusion](/contest/2069/problem/F "Educational Codeforces Round 174 (Rated for Div. 2)")
    298 
    299 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    300 
    301 **Tutorial**
    302 
    303 Tutorial is loading...
    304 
    305 **Solution (BledDest)**
    306 
    307 ```
    308 #include<bits/stdc++.h>
    309 
    310 using namespace std;             
    311 
    312 const int N = 400043;
    313 const int BUF = N * 20;
    314 
    315 int* where[BUF];
    316 int val[BUF];
    317 int cur = 0;
    318 
    319 void change(int& x, int y)
    320 {
    321     val[cur] = x;
    322     where[cur] = &x;
    323     x = y;
    324     cur++;
    325 }
    326 
    327 void rollback()
    328 {
    329     cur--;
    330     (*where[cur]) = val[cur];
    331 }
    332 
    333 struct DSU
    334 {
    335     vector<int> p, s;
    336     int n;
    337     int comps;
    338 
    339     int get(int x)
    340     {
    341         if(p[x] == x) return x;
    342         return get(p[x]);
    343     }
    344 
    345     void merge(int x, int y)
    346     {
    347         x = get(x);
    348         y = get(y);
    349         if(x == y) return;
    350         change(comps, comps - 1);
    351         if(s[x] < s[y]) swap(x, y);
    352         change(p[y], x);
    353         change(s[x], s[x] + s[y]);    
    354     }
    355 
    356     DSU(int n = 0)
    357     {
    358         this->n = n;
    359         s = vector<int>(n, 1);
    360         p = vector<int>(n);
    361         iota(p.begin(), p.end(), 0);
    362         comps = n;
    363     }
    364 };
    365 
    366 struct edge
    367 {
    368     char g;
    369     int x;
    370     int y;
    371     edge(char g = 'A', int x = 0, int y = 0) : g(g), x(x), y(y) {};
    372 };
    373 
    374 DSU A, united;
    375 vector<edge> T[4 * N];
    376 int ans[N];
    377 
    378 void dfs(int v, int l, int r)
    379 {
    380     int state = cur;
    381     for(auto e : T[v])
    382     {
    383         united.merge(e.x, e.y);
    384         if(e.g == 'A') A.merge(e.x, e.y);   
    385     }
    386     if(l == r - 1)
    387     {
    388         ans[l] = A.comps - united.comps;
    389     }
    390     else
    391     {
    392         int m = (l + r) / 2;
    393         dfs(v * 2 + 1, l, m);
    394         dfs(v * 2 + 2, m, r);
    395     }
    396     while(state != cur) rollback();
    397 }
    398 
    399 void add_edge(int v, int l, int r, int L, int R, edge e)
    400 {
    401     if(L >= R) return;
    402     if(L == l && R == r) T[v].push_back(e);
    403     else
    404     {
    405         int m = (l + r) / 2;
    406         add_edge(v * 2 + 1, l, m, L, min(m, R), e);
    407         add_edge(v * 2 + 2, m, r, max(L, m), R, e);
    408     }
    409 }
    410 
    411 map<pair<int, int>, int> last[2];
    412 
    413 int main()
    414 {
    415     ios_base::sync_with_stdio(0);
    416     cin.tie(0);
    417     int n, q;
    418     cin >> n >> q;
    419     A = DSU(n);
    420     united = DSU(n);
    421     for(int i = 0; i < q; i++)
    422     {
    423         string s;
    424         int x, y;
    425         cin >> s >> x >> y;
    426         --x;
    427         --y;
    428         int idx = (s[0] == 'A' ? 0 : 1);
    429         if(x > y) swap(x, y);
    430         if(last[idx].count(make_pair(x, y)) == 0)
    431         {
    432             last[idx][make_pair(x, y)] = i;
    433         }
    434         else
    435         {
    436             add_edge(0, 0, q, last[idx][make_pair(x, y)], i, edge(s[0], x, y));
    437             last[idx].erase(make_pair(x, y));
    438         }
    439     }
    440     for(int i = 0; i < 2; i++)
    441         for(auto a : last[i])
    442             add_edge(0, 0, q, a.second, q, edge(char(i + 'A'), a.first.first, a.first.second));
    443     dfs(0, 0, q);
    444     for(int i = 0; i < q; i++)
    445         cout << ans[i] << "\n";
    446 }
    447 ```