codeforces-scrape

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

1535.md (9703B)


      1 Source: https://codeforces.com/blog/entry/91481
      2 
      3 [1535A - Fair Playoff](/contest/1535/problem/A "Educational Codeforces Round 110 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19   int t;
     20   cin >> t;
     21   while (t--) {
     22     vector<int> s(4);
     23     for (int& x : s) cin >> x;
     24     if (min(s[0], s[1]) > max(s[2], s[3]) || max(s[0], s[1]) < min(s[2], s[3]))
     25       cout << "NO\n";
     26     else
     27       cout << "YES\n";
     28   }
     29 }
     30 ```
     31 
     32 [1535B - Array Reodering](/contest/1535/problem/B "Educational Codeforces Round 110 (Rated for Div. 2)")
     33 
     34 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     35 
     36 **Tutorial**
     37 
     38 Tutorial is loading...
     39 
     40 **Solution (Neon)**
     41 
     42 ```
     43 #include <bits/stdc++.h>
     44 
     45 using namespace std;
     46 
     47 int main() {
     48   int t;
     49   cin >> t;
     50   while (t--) {
     51     int n;
     52     cin >> n;
     53     vector<int> a(n);
     54     for (int &x : a) cin >> x;
     55     sort(a.begin(), a.end(), [](int x, int y) {
     56       return x % 2 < y % 2;
     57     });
     58     int ans = 0;
     59     for (int i = 0; i < n; ++i) {
     60       for (int j = i + 1; j < n; ++j) {
     61         ans += __gcd(a[i], a[j] * 2) > 1;
     62       }
     63     }
     64     cout << ans << endl;
     65   }
     66 }
     67 ```
     68 
     69 [1535C - Unstable String](/contest/1535/problem/C "Educational Codeforces Round 110 (Rated for Div. 2)")
     70 
     71 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     72 
     73 **Tutorial**
     74 
     75 Tutorial is loading...
     76 
     77 **Solution (Neon)**
     78 
     79 ```
     80 #include <bits/stdc++.h>
     81 
     82 using namespace std;
     83 
     84 int main() {
     85   int t;
     86   cin >> t;
     87   while (t--) {
     88     string s;
     89     cin >> s;
     90     vector<vector<int>> lst(2, vector<int>(2, -1));
     91     long long ans = 0;
     92     for (int i = 0; i < int(s.size()); ++i) {
     93       int j = i - 1;
     94       int p = i & 1;
     95       if (s[i] != '1') j = min(j, max(lst[0][p ^ 1], lst[1][p]));
     96       if (s[i] != '0') j = min(j, max(lst[0][p], lst[1][p ^ 1]));
     97       ans += i - j;
     98       if (s[i] != '?') lst[s[i] - '0'][p] = i;
     99     }
    100     cout << ans << '\n';
    101   }
    102 }
    103 ```
    104 
    105 [1535D - Playoff Tournament](/contest/1535/problem/D "Educational Codeforces Round 110 (Rated for Div. 2)")
    106 
    107 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    108 
    109 **Tutorial**
    110 
    111 Tutorial is loading...
    112 
    113 **Solution (Neon)**
    114 
    115 ```
    116 #include <bits/stdc++.h>
    117 
    118 using namespace std;
    119 
    120 int main() {
    121   ios_base::sync_with_stdio(false);
    122   cin.tie(NULL); 
    123   
    124   int k;
    125   cin >> k;
    126   string s;
    127   cin >> s;
    128   reverse(s.begin(), s.end());
    129   
    130   int n = 1 << k;
    131   vector<int> cnt(2 * n, 1);
    132   
    133   auto upd = [&](int i) {
    134     return cnt[i] = (s[i] != '0' ? cnt[i * 2 + 1] : 0) + (s[i] != '1' ? cnt[i * 2 + 2] : 0);
    135   };
    136   
    137   for (int i = n - 2; i >= 0; i--) {
    138     upd(i);
    139   }
    140   
    141   int q;
    142   cin >> q;
    143   while (q--) {
    144     int p;
    145     char c;
    146     cin >> p >> c;
    147     p = n - p - 1;
    148     s[p] = c;
    149     while (p) {
    150       upd(p);
    151       p = (p - 1) / 2;
    152     }
    153     cout << upd(0) << '\n';
    154   }
    155 }
    156 ```
    157 
    158 [1535E - Gold Transfer](/contest/1535/problem/E "Educational Codeforces Round 110 (Rated for Div. 2)")
    159 
    160 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    161 
    162 **Tutorial**
    163 
    164 Tutorial is loading...
    165 
    166 **Solution (adedalic)**
    167 
    168 ```
    169 #include<bits/stdc++.h>
    170 
    171 using namespace std;
    172 
    173 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    174 #define sz(a) int((a).size())
    175 
    176 #define x first
    177 #define y second
    178 
    179 typedef long long li;
    180 typedef pair<int, int> pt;
    181 
    182 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    183 	return out << "(" << p.x << ", " << p.y << ")";
    184 }
    185 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    186 	out << "[";
    187 	fore(i, 0, sz(v)) {
    188 		if(i) out << ", ";
    189 		out << v[i];
    190 	}
    191 	return out << "]";
    192 }
    193 
    194 const int INF = int(1e9);
    195 const li INF64 = li(1e18);
    196 
    197 const int LOG = 20;
    198 
    199 int q;
    200 vector<int> a, c;
    201 vector<int> p[LOG];
    202 
    203 int main() {
    204 	cin >> q;
    205 	a.resize(q + 1);
    206 	c.resize(q + 1);
    207 	
    208 	fore (lg, 0, LOG)
    209 		p[lg].resize(q + 1);
    210 
    211 	fore (lg, 0, LOG)
    212 		p[lg][0] = 0;
    213 	cin >> a[0] >> c[0];
    214 	
    215 	fore (id, 1, q + 1) {
    216 		int tp; cin >> tp;
    217 		if (tp == 1) {
    218 			int pr; cin >> pr;
    219 			cin >> a[id] >> c[id];
    220 			
    221 			p[0][id] = pr;
    222 			fore (lg, 1, LOG)
    223 				p[lg][id] = p[lg - 1][p[lg - 1][id]];
    224 		} 
    225 		else {
    226 			int v, w;
    227 			cin >> v >> w;
    228 			
    229 			int ansR = 0;
    230 			li ansS = 0;
    231 			
    232 			while (w > 0 && a[v] > 0) {
    233 				int u = v;
    234 				for (int lg = LOG - 1; lg >= 0; lg--) {
    235 					if (a[p[lg][u]] > 0)
    236 						u = p[lg][u];
    237 				}
    238 				int mn = min(a[u], w);
    239 				a[u] -= mn;
    240 				w -= mn;
    241 				
    242 				ansR += mn;
    243 				ansS += mn * 1ll * c[u];
    244 			}
    245 			cout << ansR << " " << ansS << endl;
    246 		}
    247 	}
    248 		
    249 	return 0;
    250 }
    251 ```
    252 
    253 [1535F - String Distance](/contest/1535/problem/F "Educational Codeforces Round 110 (Rated for Div. 2)")
    254 
    255 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    256 
    257 **Tutorial**
    258 
    259 Tutorial is loading...
    260 
    261 **Solution (BledDest)**
    262 
    263 ```
    264 #include<bits/stdc++.h>   
    265 using namespace std;
    266 
    267 const int LN = 20;
    268 const int K = 12000;
    269 
    270 int pw2[1 << LN];
    271 
    272 vector<int> sorted_segments(const string& s)
    273 {
    274  	int n = int(s.size()) - 1;
    275  	vector<int> res(n);
    276  	for(int i = 0; i < n; i++)
    277  		if(s[i] <= s[i + 1])
    278  			res[i] = 0;
    279  		else
    280  			res[i] = 1;
    281  	return res;
    282 }
    283 
    284 vector<int> prefix_sum(const vector<int>& s)
    285 {
    286  	int n = s.size();
    287  	vector<int> p(n + 1);
    288  	for(int i = 0; i < n; i++)
    289  		p[i + 1] = p[i] + s[i];
    290  	return p;
    291 }
    292 
    293 int naiveLCP(const string& s, const string& t)
    294 {
    295  	int ans = 0;
    296  	int n = s.size();
    297  	int m = t.size();
    298  	while(ans < n && ans < m && s[ans] == t[ans])
    299  		ans++;
    300  	return ans;
    301 }
    302 
    303 vector<vector<int>> build_table(const vector<int>& a)
    304 {
    305 	int n = a.size();
    306 	vector<vector<int>> table(LN, vector<int>(n));
    307 	for(int i = 0; i < n; i++)
    308 		table[0][i] = a[i];
    309 	for(int i = 1; i < LN; i++)
    310 		for(int j = 0; j < n; j++)
    311 			if(j + (1 << (i - 1)) < n)
    312 				table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
    313 			else
    314 				table[i][j] = table[i - 1][j];
    315 	return table; 	
    316 }
    317 
    318 struct LCP
    319 {
    320  	vector<int> idx;
    321  	vector<vector<int>> table;
    322 
    323  	int query_inner(int x, int y)
    324  	{
    325  	 	if(x > y) swap(x, y);
    326  	 	int len = y - x;
    327  	 	int d = pw2[len];
    328  	 	return min(table[d][x], table[d][y - (1 << d)]);
    329  	}
    330 
    331  	int query(int x, int y)
    332  	{
    333  	 	return query_inner(idx[x], idx[y]);
    334  	}
    335 
    336  	LCP() {};
    337  	LCP(vector<string> s) 
    338  	{
    339  		int n = s.size();
    340 		vector<pair<string, int>> t;
    341 		for(int i = 0; i < n; i++)
    342 		{
    343 		 	t.push_back(make_pair(s[i], i));
    344 	   	}
    345 	   	sort(t.begin(), t.end());
    346 	   	idx.resize(n);
    347 	   	for(int i = 0; i < n; i++)
    348 	   	{
    349 	   		idx[t[i].second] = i;
    350 	   	}
    351 	   	vector<int> LCPs;
    352 	   	for(int i = 0; i < n - 1; i++)
    353 	   		LCPs.push_back(naiveLCP(t[i].first, t[i + 1].first));
    354 	   	table = build_table(LCPs);		
    355  	};
    356 };
    357 
    358 const int T = int(2e7);
    359 
    360 map<char, int> nxt[T];
    361 int cur = 1;
    362 int root = 0;
    363 int cnt[T];
    364 
    365 void clear_trie()
    366 {
    367  	root = cur++;
    368 }
    369 
    370 int go(int x, char c)
    371 {
    372  	if(!nxt[x].count(c))
    373  		nxt[x][c] = cur++;
    374  	return nxt[x][c];
    375 }
    376 
    377 void add(int v, const string& s, int l, int r, int n, bool sw, const vector<int>& ps)
    378 {
    379 	if(sw && l + r < n - 1 && ps[n - r - 1] == ps[l])
    380 	{
    381 		cnt[v]++;
    382 	}
    383 	if(sw)
    384 	{
    385 		if(l + r < n - 1)
    386 			add(go(v, s[n - r - 1]), s, l, r + 1, n, sw, ps);
    387  	}
    388  	else
    389  	{
    390  		add(go(v, '$'), s, l, r, n, true, ps);
    391  		if(l < n - 1)
    392  			add(go(v, s[l]), s, l + 1, r, n, sw, ps);
    393  	}
    394 }
    395 
    396 int calc(int v, const string& s, int l, int r, int n, bool sw, const vector<vector<int>>& good)
    397 {
    398 	int ans = 0;
    399 	if(sw && l + r < n - 1 && good[l][r])
    400 	{
    401 		ans = cnt[v];
    402 	}
    403 	if(sw)
    404 	{
    405 		if(l + r < n)
    406 			ans += calc(go(v, s[n - r - 1]), s, l, r + 1, n, sw, good);
    407 	}
    408 	else
    409 	{
    410 	 	ans += calc(go(v, '$'), s, l, r, n, true, good);
    411 	 	if(l < n)
    412 	 		ans += calc(go(v, s[l]), s, l + 1, r, n, sw, good);	
    413 	}
    414 	return ans;
    415 }
    416 
    417 long long solve_short(vector<string> s, int n)
    418 {
    419 	long long ans = 0;
    420  	clear_trie();
    421  	sort(s.begin(), s.end());
    422  	for(int i = 0; i < n; i++)
    423  	{
    424  	 	string cur = s[i];
    425  	 	int len = cur.size();
    426  	 	vector<vector<int>> good(len + 1, vector<int>(len + 1));
    427  	 	for(int l = 0; l < len; l++)
    428  	 	{
    429  	 	 	set<char> q;
    430  	 	 	for(int r = l; r < len; r++)
    431  	 	 	{
    432  	 	 	 	q.insert(cur[r]);
    433  	 	 	 	if(cur[l] != *q.begin() && cur[r] != *q.rbegin())
    434  	 	 	 	{
    435  	 	 	 		good[l][len - r - 1] = 1;
    436  	 	 	 	}
    437  	 	 	}
    438  	 	}
    439  	 	vector<int> p = prefix_sum(sorted_segments(cur));
    440  	 	add(root, cur, 0, 0, len, false, p);
    441  	 	ans += calc(root, cur, 0, 0, len, false, good);
    442  	}
    443  	ans = n * 1ll * (n - 1) - ans;
    444  	return ans;
    445 }
    446 
    447 long long solve_long(vector<string> s, int n)
    448 {                     
    449 	int len = s[0].size();
    450  	sort(s.begin(), s.end());
    451  	vector<string> t = s;
    452  	for(int i = 0; i < n; i++)
    453  		reverse(t[i].begin(), t[i].end());
    454  	LCP ls(s);
    455  	LCP lt(t);
    456  	long long ans = 0;
    457  	for(int i = 0; i < n; i++)
    458  	{
    459  	 	vector<int> aux = prefix_sum(sorted_segments(s[i]));
    460  	 	for(int j = i + 1; j < n; j++)
    461  	 	{
    462  	 	 	int lf = ls.query(i, j);
    463  	 	 	int rg = lt.query(i, j);
    464  	 	 	if(aux[len - rg - 1] - aux[lf] == 0)
    465  	 	 		ans++;
    466  	 	 	else
    467  	 	 		ans += 2;
    468  	 	}
    469 	}
    470 	return ans;
    471 }
    472 
    473 long long solve_class(vector<string> s, int n)
    474 {                       
    475 	if(n <= K)
    476 		return solve_long(s, n);
    477 	else
    478 		return solve_short(s, n); 	
    479 }
    480 
    481 vector<int> get_class(string s)
    482 {
    483 	vector<int> c(26);
    484 	for(auto x : s) c[x - 'a']++;
    485 	return c;
    486 }
    487 
    488 int main()
    489 {
    490 	pw2[1] = 0;
    491 	for(int i = 2; i < (1 << LN); i++)
    492 		pw2[i] = pw2[i >> 1] + 1;
    493 	int n;
    494 	cin >> n;
    495 	vector<string> s(n);
    496 	for(int i = 0; i < n; i++)   
    497 		cin >> s[i];         
    498 	long long ans = 0;
    499 	map<vector<int>, vector<string>> classes;
    500 	for(int i = 0; i < n; i++)
    501 		classes[get_class(s[i])].push_back(s[i]);
    502 	int cnt = 0;
    503 	for(auto x : classes)
    504 	{                       
    505 	 	ans += solve_class(x.second, x.second.size());
    506 	 	ans += cnt * 1337ll * x.second.size();
    507 	 	cnt += x.second.size();
    508 	}
    509 	cout << ans << endl;
    510 }
    511 ```