codeforces-scrape

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

1860.md (7830B)


      1 Source: https://codeforces.com/blog/entry/119504
      2 
      3 [1860A - Not a Substring](/contest/1860/problem/A "Educational Codeforces Round 153 (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   ios::sync_with_stdio(false); cin.tie(0);
     20   int t;
     21   cin >> t;
     22   while (t--) {
     23 	string s;
     24 	cin >> s;
     25 	int n = s.size();
     26 	string a, b;
     27 	for (int i = 0; i < 2 * n; ++i) {
     28 	  a += "()"[i & 1];
     29 	  b += ")("[i < n];
     30 	}
     31 	if (a.find(s) == string::npos) {
     32 	  cout << "YES\n" << a << '\n';
     33 	} else if (b.find(s) == string::npos) {
     34 	  cout << "YES\n" << b << '\n';
     35 	} else {
     36 	  cout << "NO\n";
     37 	}
     38   }
     39 }
     40 ```
     41 
     42 [1860B - Fancy Coins](/contest/1860/problem/B "Educational Codeforces Round 153 (Rated for Div. 2)")
     43 
     44 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     45 
     46 **Tutorial**
     47 
     48 Tutorial is loading...
     49 
     50 **Solution 1 (BledDest)**
     51 
     52 ```
     53 #include<bits/stdc++.h>
     54  
     55 using namespace std;
     56  
     57 int main()
     58 {
     59 	int t;
     60 	cin >> t;
     61 	for(int i = 0; i < t; i++)
     62 	{
     63 		int m, k, a1, ak;
     64 		cin >> m >> k >> a1 >> ak;
     65 		int taken_k = m / k;
     66 		int taken_1 = m % k;
     67 		int taken_fancy_1 = max(0, taken_1 - a1);
     68 		int left_regular_1 = max(0, a1 - taken_1);
     69 		int taken_fancy_k = max(0, taken_k - ak);
     70 		int to_replace = min(left_regular_1 / k, taken_fancy_k);
     71 		int ans = taken_fancy_1 + taken_fancy_k - to_replace;
     72 		cout << ans << endl;
     73 	}
     74 }
     75 ```
     76 
     77 **Solution 2 (BledDest)**
     78 
     79 ```
     80 #include<bits/stdc++.h>
     81  
     82 using namespace std;
     83  
     84 int main()
     85 {
     86 	int t;
     87 	cin >> t;
     88 	for(int i = 0; i < t; i++)
     89 	{
     90 		int m, k, a1, ak;
     91 		cin >> m >> k >> a1 >> ak;
     92 		// function which calculates the number of fancy coins taken
     93 		// if we take exactly x coins of value k
     94 		auto f = [m, k, a1, ak](int x)
     95 		{
     96 			int taken_1 = m - k * x;
     97 			return max(0, taken_1 - a1) + max(0, x - ak);
     98 		};
     99 		
    100 		int lf = 0;
    101 		int rg = m / k;
    102 		while(rg - lf > 2)
    103 		{
    104 			int mid = (lf + rg) / 2;
    105 			if(f(mid) < f(mid + 1))
    106 				rg = mid + 1;
    107 			else
    108 				lf = mid;
    109 		}
    110 		int ans = 1e9;
    111 		for(int i = lf; i <= rg; i++) ans = min(ans, f(i));
    112 		cout << ans << endl;
    113 	}
    114 }
    115 ```
    116 
    117 [1860C - Game on Permutation](/contest/1860/problem/C "Educational Codeforces Round 153 (Rated for Div. 2)")
    118 
    119 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    120 
    121 **Tutorial**
    122 
    123 Tutorial is loading...
    124 
    125 **Solution (Neon)**
    126 
    127 ```
    128 #include <bits/stdc++.h>
    129  
    130 using namespace std;
    131  
    132 int main() {
    133   ios::sync_with_stdio(false); cin.tie(0);
    134   int t;
    135   cin >> t;
    136   while (t--) {
    137     int n;
    138     cin >> n;
    139     int ans = 0;
    140     int mn = n + 1, mnWin = n + 1;
    141     while (n--) {
    142       int x;
    143       cin >> x;
    144       if (mn < x && x < mnWin) {
    145       	ans += 1;
    146       	mnWin = x;
    147       }
    148       mn = min(mn, x);
    149     }
    150     cout << ans << '\n';
    151   }
    152 }
    153 ```
    154 
    155 [1860D - Balanced String](/contest/1860/problem/D "Educational Codeforces Round 153 (Rated for Div. 2)")
    156 
    157 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    158 
    159 **Tutorial**
    160 
    161 Tutorial is loading...
    162 
    163 **Solution (Neon)**
    164 
    165 ```
    166 #include <bits/stdc++.h>
    167  
    168 using namespace std;
    169  
    170 using li = long long;
    171  
    172 const int N = 111;
    173  
    174 int n;
    175 string s;
    176 int dp[2][N][N * N];
    177  
    178 int main() {
    179   cin >> s;
    180   n = s.size();
    181   dp[0][0][0] = 0;
    182   for (int i = 0; i < n; ++i) {
    183     for (int j = 0; j <= i + 1; ++j) {
    184       for (int cnt = 0; cnt <= j * (i + 1 - j); ++cnt) {
    185         dp[1][j][cnt] = n;   
    186       }
    187     }
    188     for (int j = 0; j <= i; ++j) {
    189       for (int cnt = 0; cnt <= j * (i - j); ++cnt) {
    190         dp[1][j + 1][cnt] = min(dp[1][j + 1][cnt], dp[0][j][cnt] + (s[i] != '0'));
    191         dp[1][j][cnt + j] = min(dp[1][j][cnt + j], dp[0][j][cnt] + (s[i] != '1'));
    192       }
    193     } 
    194     swap(dp[0], dp[1]);
    195   }
    196   int cnt0 = count(s.begin(), s.end(), '0');
    197   cout << dp[0][cnt0][cnt0 * (n - cnt0) / 2] / 2 << '\n';
    198 }
    199 ```
    200 
    201 [1860E - Fast Travel Text Editor](/contest/1860/problem/E "Educational Codeforces Round 153 (Rated for Div. 2)")
    202 
    203 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    204 
    205 **Tutorial**
    206 
    207 Tutorial is loading...
    208 
    209 **Solution (awoo)**
    210 
    211 ```
    212 #include <bits/stdc++.h>
    213  
    214 #define forn(i, n) for (int i = 0; i < int(n); i++)
    215  
    216 using namespace std;
    217  
    218 const int INF = 1e9;
    219 const int AL = 26;
    220  
    221 struct query{
    222 	int f, t, ans;
    223 };
    224  
    225 struct edge{
    226 	int u, w;
    227 };
    228  
    229 int main() {
    230 	cin.tie(0);
    231 	iostream::sync_with_stdio(false);
    232 	string s;
    233 	cin >> s;
    234 	int n = s.size();
    235 	
    236 	int m;
    237 	cin >> m;
    238 	vector<query> a(m);
    239 	forn(i, m){
    240 		cin >> a[i].f >> a[i].t;
    241 		--a[i].f, --a[i].t;
    242 		a[i].ans = abs(a[i].f - a[i].t);
    243 	}
    244 	
    245 	int k = n - 1 + AL * AL;
    246 	vector<vector<edge>> g(k);
    247 	forn(i, n - 1){
    248 		int j = n - 1 + (s[i] - 'a') * AL + (s[i + 1] - 'a');
    249 		g[i].push_back({j, 0});
    250 		g[j].push_back({i, 1});
    251 		if (i > 0){
    252 			g[i].push_back({i - 1, 1});
    253 			g[i - 1].push_back({i, 1});
    254 		}
    255 	}
    256 	
    257 	for (int st = n - 1; st < k; ++st){
    258 		vector<int> d(k, INF);
    259 		d[st] = 0;
    260 		deque<int> q;
    261 		q.push_back(st);
    262 		while (!q.empty()){
    263 			int v = q.front();
    264 			q.pop_front();
    265 			for (auto it : g[v]){
    266 				if (d[it.u] <= d[v] + it.w) continue;
    267 				d[it.u] = d[v] + it.w;
    268 				if (it.w == 0) q.push_front(it.u);
    269 				else q.push_back(it.u);
    270 			}
    271 		}
    272 		forn(i, m){
    273 			a[i].ans = min(a[i].ans, d[a[i].f] + d[a[i].t] - 1);
    274 		}
    275 	}
    276 	
    277 	forn(i, m) cout << a[i].ans << '\n';
    278 	return 0;
    279 }
    280 ```
    281 
    282 [1860F - Evaluate RBS](/contest/1860/problem/F "Educational Codeforces Round 153 (Rated for Div. 2)")
    283 
    284 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    285 
    286 **Tutorial**
    287 
    288 Tutorial is loading...
    289 
    290 **Solution (awoo)**
    291 
    292 ```
    293 #include <bits/stdc++.h>
    294  
    295 #define forn(i, n) for (int i = 0; i < int(n); i++)
    296  
    297 using namespace std;
    298  
    299 const int INF = 1e9;
    300  
    301 struct bracket{
    302 	int a, b, c;
    303 };
    304  
    305 struct point{
    306 	int x, y;
    307 };
    308  
    309 long long cross(const point &a, const point &b){
    310 	return a.x * 1ll * b.y - a.y * 1ll * b.x;
    311 }
    312  
    313 long long dot(const point &a, const bracket &b){
    314 	return a.x * 1ll * b.a + a.y * 1ll * b.b;
    315 }
    316  
    317 bool operator <(const point &a, const point &b){
    318 	return cross(a, b) > 0;
    319 }
    320  
    321 int main() {
    322 	int t;
    323 	cin >> t;
    324 	while (t--){
    325 		int n;
    326 		cin >> n;
    327 		vector<bracket> val;
    328 		forn(i, 2 * n){
    329 			int a, b;
    330 			string c;
    331 			cin >> a >> b >> c;
    332 			val.push_back({a, b, c[0] == '(' ? 1 : -1});
    333 		}
    334 		map<point, vector<int>> opts;
    335 		forn(i, 2 * n) forn(j, 2 * n){
    336 			int dx = val[i].b - val[j].b;
    337 			int dy = val[j].a - val[i].a;
    338 			if (dx <= 0 || dy <= 0) continue;
    339 			opts[{dx, dy}].push_back(i);
    340 			opts[{dx, dy}].push_back(j);
    341 		}
    342 		opts[{1, INF}];
    343 		vector<int> ord(2 * n), rord(2 * n);
    344 		iota(ord.begin(), ord.end(), 0);
    345 		sort(ord.begin(), ord.end(), [&](int i, int j){
    346 			long long di = dot({INF, 1}, val[i]);
    347 			long long dj = dot({INF, 1}, val[j]);
    348 			if (di != dj) return di < dj;
    349 			return val[i].c > val[j].c;
    350 		});
    351 		forn(i, 2 * n) rord[ord[i]] = i;
    352 		int neg = 0, cur = 0;
    353 		vector<int> bal(1, 0);
    354 		for (int i : ord){
    355 			cur += val[i].c;
    356 			bal.push_back(cur);
    357 			neg += cur < 0;
    358 		}
    359 		bool ans = neg == 0;
    360 		vector<int> prv;
    361 		for (auto it : opts){
    362 			vector<int> tot = prv;
    363 			for (int x : it.second) tot.push_back(x);
    364 			sort(tot.begin(), tot.end(), [&](int i, int j){
    365 				return rord[i] < rord[j];
    366 			});
    367 			tot.resize(unique(tot.begin(), tot.end()) - tot.begin());
    368 			for (int x : tot) neg -= bal[rord[x] + 1] < 0;
    369 			vector<int> tmp = tot;
    370 			sort(tot.begin(), tot.end(), [&](int i, int j){
    371 				long long di = dot(it.first, val[i]);
    372 				long long dj = dot(it.first, val[j]);
    373 				if (di != dj) return di < dj;
    374 				return val[i].c > val[j].c;
    375 			});
    376 			vector<int> nrord(tot.size());
    377 			forn(i, tot.size()) nrord[i] = rord[tmp[i]];
    378 			forn(i, tot.size()) rord[tot[i]] = nrord[i];
    379 			for (int x : tot){
    380 				bal[rord[x] + 1] = bal[rord[x]] + val[x].c;
    381 				neg += bal[rord[x] + 1] < 0;
    382 			}
    383 			if (neg == 0){
    384 				ans = true;
    385 				break;
    386 			}
    387 			prv = it.second;
    388 		}
    389 		puts(ans ? "YES" : "NO");
    390 	}
    391 	return 0;
    392 }
    393 ```