codeforces-scrape

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

1240.md (14864B)


      1 Source: https://codeforces.com/blog/entry/70358
      2 
      3 [1223A - CME](/contest/1223/problem/A "Technocup 2020 - Elimination Round 1")
      4 
      5 Idea: [Roms](/profile/Roms "Master Roms")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Roms)**
     12 
     13 ```
     14 for t in range(int(input())):
     15 	n = int(input())
     16 	print(2 if n == 2 else (n & 1))
     17 ```
     18 
     19 [1223B - Strings Equalization](/contest/1223/problem/B "Technocup 2020 - Elimination Round 1")
     20 
     21 Idea: [Roms](/profile/Roms "Master Roms")
     22 
     23 **Tutorial**
     24 
     25 Tutorial is loading...
     26 
     27 **Solution (Roms)**
     28 
     29 ```
     30 for t in range(int(input())):
     31     print('NO' if len(set(input()) & set(input())) == 0 else 'YES')
     32 ```
     33 
     34 [1223C - Save the Nature](/contest/1223/problem/C "Technocup 2020 - Elimination Round 1")
     35 
     36 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     37 
     38 **Tutorial**
     39 
     40 Tutorial is loading...
     41 
     42 **Solution (adedalic)**
     43 
     44 ```
     45 fun calc(p: IntArray, len: Int, x: Int, a: Int, y: Int, b: Int): Long {
     46     var ans = 0L
     47     var (cX, cY, cXY) = listOf(0, 0, 0)
     48     for (i in 1..len) {
     49         if (i % a == 0 && i % b == 0) cXY++
     50         else if (i % a == 0) cX++
     51         else if (i % b == 0) cY++
     52     }
     53     for (i in 0 until cXY)
     54         ans += p[i] * (x + y)
     55     for (i in 0 until cX)
     56         ans += p[cXY + i] * x
     57     for (i in 0 until cY)
     58         ans += p[cXY + cX + i] * y;
     59     return ans
     60 }
     61 
     62 fun main() {
     63     val q = readLine()!!.toInt()
     64     for (ct in 1..q) {
     65         val n = readLine()!!.toInt()
     66         val p = readLine()!!.split(' ').map { it.toInt() / 100 }
     67                 .sortedDescending().toIntArray()
     68         var (x, a) = readLine()!!.split(' ').map { it.toInt() }
     69         var (y, b) = readLine()!!.split(' ').map { it.toInt() }
     70         val k = readLine()!!.toLong()
     71 
     72         if (x < y) {
     73             x = y.also { y = x }
     74             a = b.also { b = a }
     75         }
     76 
     77         var lf = 0; var rg = n + 1
     78         while (rg - lf > 1) {
     79             val mid = (lf + rg) / 2
     80             if (calc(p, mid, x, a, y, b) >= k)
     81                 rg = mid
     82             else
     83                 lf = mid
     84         }
     85 
     86         if (rg > n) rg = -1
     87         println(rg)
     88     }
     89 }
     90 ```
     91 
     92 [1223D - Sequence Sorting](/contest/1223/problem/D "Technocup 2020 - Elimination Round 1")
     93 
     94 Idea: [Roms](/profile/Roms "Master Roms")
     95 
     96 **Tutorial**
     97 
     98 Tutorial is loading...
     99 
    100 **Solution (Roms)**
    101 
    102 ```
    103 #include <bits/stdc++.h>
    104 
    105 using namespace std;
    106 
    107 const int N = int(3e5) + 99;
    108 const int INF = int(1e9) + 99;
    109 
    110 int t, n;
    111 int a[N];
    112 int l[N], r[N];
    113 int dp[N];
    114 
    115 int main() {
    116 	scanf("%d", &t);
    117 	for(int tc = 0; tc < t; ++tc){
    118 		scanf("%d", &n);
    119 		for(int i = 0; i < n; ++i){
    120 			l[i] = INF;
    121 			r[i] = -INF;
    122 			dp[i] = 0;
    123 		}
    124 
    125 		vector <int> v;	
    126 		for(int i = 0; i < n; ++i){
    127 			scanf("%d", a + i);
    128 			--a[i];
    129 			v.push_back(a[i]);
    130 			l[a[i]] = min(l[a[i]], i);
    131 			r[a[i]] = max(r[a[i]], i);
    132 		}
    133 
    134 		sort(v.begin(), v.end());
    135 		v.erase(unique(v.begin(), v.end()), v.end());
    136 	
    137 		int res = n;
    138 		for(int i = v.size() - 1; i >= 0; --i){
    139 			if(i + 1 == v.size() || r[v[i]] >= l[v[i + 1]]) dp[i] = 1;
    140 			else dp[i] = 1 + dp[i + 1];
    141 			res = min(res, int(v.size())- dp[i]);
    142 		}
    143 
    144 		printf("%d\n", res);
    145 	}	
    146 
    147 	return 0;
    148 }                             	
    149 ```
    150 
    151 [1223E - Paint the Tree](/contest/1223/problem/E "Technocup 2020 - Elimination Round 1")
    152 
    153 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    154 
    155 **Tutorial**
    156 
    157 Tutorial is loading...
    158 
    159 **Solution (Ne0n25)**
    160 
    161 ```
    162 #include <bits/stdc++.h>
    163 
    164 using namespace std;
    165 
    166 #define x first
    167 #define y second
    168 #define mp make_pair
    169 #define pb push_back
    170 #define sz(a) int((a).size())
    171 #define all(a) (a).begin(), (a).end()
    172 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    173 
    174 const int N = 500 * 1000 + 13;
    175 
    176 int n, k;
    177 vector<pair<int, int>> g[N];
    178 long long dp[N][2];
    179 
    180 void calc(int v, int p = -1) {
    181 	long long cur = 0;
    182 	vector<long long> adds;
    183 	
    184 	for (auto it : g[v]) {
    185 		int to = it.x;
    186 		int w = it.y;
    187 		if (to == p)
    188 			continue;
    189 		calc(to, v);
    190 		
    191 		cur += dp[to][0];
    192 		adds.pb(dp[to][1] + w - dp[to][0]);
    193 	}
    194 	
    195 	sort(all(adds), greater<long long>());
    196 	forn(i, min(sz(adds), k)) if (adds[i] > 0)
    197 		cur += adds[i];
    198 	
    199 	dp[v][0] = dp[v][1] = cur;
    200 	if (k <= sz(adds) && adds[k - 1] > 0)
    201 		dp[v][1] -= adds[k - 1];
    202 }
    203 
    204 long long solve() {
    205     scanf("%d%d", &n, &k);
    206     forn(i, n) g[i].clear();
    207 	forn(i, n - 1) {
    208 		int x, y, w;
    209 		scanf("%d%d%d", &x, &y, &w);
    210 		--x; --y;
    211 		g[x].pb(mp(y, w));
    212 		g[y].pb(mp(x, w));
    213 	}
    214 	
    215 	calc(0);
    216 	
    217 	return dp[0][0];
    218 }
    219 
    220 int main() {
    221 	int q;
    222 	scanf("%d", &q);
    223 	forn(i, q) printf("%lld\n", solve());
    224 }
    225 ```
    226 
    227 [1223F - Stack Exterminable Arrays](/contest/1223/problem/F "Technocup 2020 - Elimination Round 1")
    228 
    229 Idea: [Roms](/profile/Roms "Master Roms")
    230 
    231 **Tutorial**
    232 
    233 Tutorial is loading...
    234 
    235 **Solution (Roms)**
    236 
    237 ```
    238 #include <bits/stdc++.h>
    239 
    240 using namespace std;
    241 
    242 const int N = int(3e5) + 99;
    243 
    244 int t, n;
    245 int a[N];
    246 int nxt[N];
    247 int dp[N];
    248 map<int, int> nxtX[N];
    249 
    250 int main() {	
    251 	scanf("%d", &t);
    252 	for(int tc = 0; tc < t; ++tc){
    253 		scanf("%d", &n);
    254 		for(int i = 0; i < n; ++i)
    255 			scanf("%d", a + i);
    256 		for(int i = 0; i < n + 2; ++i){
    257 			nxt[i] = -1;
    258 			nxtX[i].clear();
    259 			dp[i] = 0;
    260 		}
    261 
    262 		for(int i = n - 1; i >= 0; --i){
    263 			if(nxtX[i + 1].count(a[i])){
    264 				int pos = nxtX[i + 1][a[i]];
    265 				assert(pos < n && a[pos] == a[i]);
    266 				nxt[i] = pos;
    267 				swap(nxtX[i], nxtX[pos + 1]);
    268 				if(pos < n - 1)
    269 					nxtX[i][a[pos + 1]] = pos + 1;
    270 			}
    271 			nxtX[i][a[i]] = i;
    272 		}	
    273 
    274 		long long res = 0;
    275 		for(int i = n - 1; i >= 0; --i){
    276 			if(nxt[i] == -1) continue;	
    277 			dp[i] = 1 + dp[nxt[i] + 1];
    278 			res += dp[i];
    279 		}
    280 
    281 		printf("%lld\n", res);
    282 	}
    283 	return 0;
    284 }
    285 ```
    286 
    287 [1223G - Wooden Raft](/contest/1223/problem/G "Technocup 2020 - Elimination Round 1")
    288 
    289 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    290 
    291 **Tutorial**
    292 
    293 Tutorial is loading...
    294 
    295 **Solution (adedalic)**
    296 
    297 ```
    298 #include<bits/stdc++.h>
    299 using namespace std;
    300 
    301 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    302 #define sz(a) (int)(a).size()
    303 #define all(a) (a).begin(), (a).end()
    304 
    305 #define x first
    306 #define y second
    307 
    308 typedef long long li;
    309 typedef pair<int, int> pt;
    310 
    311 const int INF = int(1e9);
    312 const li INF64 = li(1e18);
    313 
    314 int n;
    315 vector<int> a;
    316 
    317 inline bool read() {
    318     if(!(cin >> n))
    319         return false;
    320     a.resize(n);
    321     fore(i, 0, n)
    322         cin >> a[i];
    323     return true;
    324 }
    325 
    326 template<class A>
    327 pair<A, A> upd(const pair<A, A> &mx, const A &val) {
    328     return {max(mx.x, val), max(mx.y, min(mx.x, val))};
    329 }
    330 
    331 vector<int> cnt, sum;
    332 vector<int> prv;
    333 
    334 li getSum(int l, int r) {
    335     return sum[r] - sum[l];
    336 }
    337 
    338 li ans, rx, ry;
    339 void updAns(li x, li y) {
    340     if (x < 2 || y < 2)
    341         return;
    342     if (ans >= x * y)
    343         return;
    344     ans = x * y;
    345     rx = x, ry = y;
    346 }
    347 
    348 inline void solve() {
    349     cnt.assign(*max_element(all(a)) + 1, 0);
    350     fore(i, 0, n)
    351         cnt[a[i]]++;
    352     sum.assign(sz(cnt) + 1, 0);
    353     fore(i, 0, sz(cnt))
    354         sum[i + 1] = sum[i] + cnt[i];
    355     prv.assign(sz(cnt), -1);
    356     fore(i, 0, sz(prv)) {
    357         if(i > 0)
    358             prv[i] = prv[i - 1];
    359         if(cnt[i] > 0)
    360             prv[i] = i;
    361     }
    362 
    363     ans = 0;
    364     fore(y, 2, sz(cnt)) {
    365         li cntY = 0;
    366         for(int i = 0; y * i < sz(cnt); i++)
    367             cntY += i * 1ll * getSum(i * y, min((i + 1) * y, sz(cnt)));
    368 
    369         pair<pt, pt> mx = {{-1, -1}, {-1, -1}};
    370         int lf = (sz(cnt) - 1) / y * y, rg = sz(cnt);
    371         while(lf >= 0) {
    372             int cntMore = (mx.x.x >= 0) + (mx.y.x >= 0);
    373             int val1 = prv[rg - 1];
    374             if (val1 >= lf) {
    375                 mx = upd(mx, pt{val1 % y, val1});
    376                 if (cnt[val1] == 1)
    377                     val1 = prv[val1 - 1];
    378                 if (val1 >= lf)
    379                     mx = upd(mx, pt{val1 % y, val1});
    380             }
    381 
    382             if (mx.x.x >= 0) {
    383                 li x = (lf + mx.x.x) / 2;
    384                 li cur = cntY - lf / y;
    385                 updAns(min(cur, x), y);
    386             }
    387             if (mx.y.x >= 0) {
    388                 li x = lf + mx.y.x;
    389                 li cur = cntY - 2 * (lf / y);
    390                 updAns(min(cur, x), y);
    391 
    392                 if(cntMore + (mx.x.y < rg) >= 2) {
    393                     x = lf + mx.x.x;
    394                     cur--;
    395                     updAns(min(cur, x), y);
    396                 }
    397             }
    398 
    399             rg = lf;
    400             lf -= y;
    401         }
    402     }
    403     cout << ans << endl;
    404     cerr << rx << " " << ry << endl;
    405 }
    406 
    407 int main() {
    408 #ifdef _DEBUG
    409     freopen("input.txt", "r", stdin);
    410     int tt = clock();
    411 #endif
    412     ios_base::sync_with_stdio(0);
    413     cin.tie(0), cout.tie(0);
    414     cerr << fixed << setprecision(15);
    415 
    416     if(read()) {
    417         solve();
    418 
    419 #ifdef _DEBUG
    420         cerr << "TIME = " << clock() - tt << endl;
    421         tt = clock();
    422 #endif
    423     }
    424     return 0;
    425 }
    426 ```
    427 
    428 [1240F - Football](/contest/1240/problem/F "Codeforces Round 591 (Div. 1, based on Technocup 2020 Elimination Round 1)")
    429 
    430 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    431 
    432 **Tutorial**
    433 
    434 Tutorial is loading...
    435 
    436 **Solution (arsijo)**
    437 
    438 ```
    439 #include <bits/stdc++.h>
    440 using namespace std;
    441 typedef long long ll;
    442 const int MAX_N = 101;
    443 const int MAX_M = 1001;
    444 
    445 int n, m, k;
    446 
    447 vector<pair<int, int> > v[MAX_N];
    448 int w[MAX_N];
    449 int a[MAX_M], b[MAX_M], c[MAX_M], color[MAX_M];
    450 
    451 set<pair<int, int> > s[MAX_N], s2;
    452 int deg[MAX_N][MAX_M];
    453 inline pair<int, int> get_s2(int i){
    454     return {s[i].begin()->first - s[i].rbegin()->first, i};
    455 }
    456 inline void change_edge_color(int edge, int d){
    457     int pos1 = a[edge];
    458     int pos2 = b[edge];
    459     assert(s[pos1].find({deg[pos1][color[edge]], color[edge]}) != s[pos1].end());
    460     s[pos1].erase({deg[pos1][color[edge]], color[edge]});
    461     s[pos2].erase({deg[pos2][color[edge]], color[edge]});
    462     deg[pos1][color[edge]] += d;
    463     deg[pos2][color[edge]] += d;
    464     s[pos1].insert({deg[pos1][color[edge]], color[edge]});
    465     s[pos2].insert({deg[pos2][color[edge]], color[edge]});
    466 }
    467 inline void change_color(int edge, int col){
    468     if (edge == 0 || edge > m || color[edge] == col)
    469         return;
    470     int pos1 = a[edge];
    471     int pos2 = b[edge];
    472     s2.erase(get_s2(pos1));
    473     s2.erase(get_s2(pos2));
    474     change_edge_color(edge, -1);
    475     color[edge] = col;
    476     change_edge_color(edge, 1);
    477     s2.insert(get_s2(pos1));
    478     s2.insert(get_s2(pos2));
    479 }
    480 
    481 vector<pair<int, int> > v2[MAX_N];
    482 int deg2[MAX_N];
    483 vector<int> vertices;
    484 int used[MAX_N];
    485 void dfs2(int pos){
    486     used[pos] = 2;
    487     for (auto e : v2[pos]){
    488         if (used[e.first] != 2){
    489             dfs2(e.first);
    490         }
    491     }
    492     vertices.push_back(pos);
    493 }
    494 int _col[2];
    495 set<int> used3;
    496 int i;
    497 vector<int> euler;
    498 void dfs3(int pos, int prev = -1, int pr2 = 0){
    499     while(!v2[pos].empty()){
    500         int ind = v2[pos].back().second;
    501         int to = v2[pos].back().first;
    502         v2[pos].pop_back();
    503         if (used3.find(ind) != used3.end()){
    504             continue;
    505         }
    506         used3.insert(ind);
    507         dfs3(to, ind, pos);
    508     }
    509     if (prev != -1){
    510         euler.push_back(prev);
    511     }
    512 }
    513 
    514 void stabilize_two_colors(const vector<int> &e, int col1, int col2){
    515     assert(!e.empty());
    516     v2[0].clear();
    517     for (auto edge : e){
    518         v2[a[edge]].clear();
    519         v2[b[edge]].clear();
    520         deg2[a[edge]] = 0;
    521         deg2[b[edge]] = 0;
    522         used[a[edge]] = 0;
    523         used[b[edge]] = 0;
    524     }
    525     for (auto edge : e){
    526         v2[a[edge]].push_back({b[edge], edge});
    527         v2[b[edge]].push_back({a[edge], edge});
    528     }
    529     vertices.clear();
    530     int u = m;
    531     for (auto edge : e){
    532         if (used[a[edge]] != 2){
    533             int k = (int) vertices.size();
    534             dfs2(a[edge]);
    535             bool find = false;
    536             for (int i = k; i < (int) vertices.size(); i++){
    537                 int v = vertices[i];
    538                 if (v2[v].size() % 2 == 1){
    539                     find = true;
    540                     ++u;
    541                     v2[v].push_back({0, u});
    542                     v2[0].push_back({v, u});
    543                 }
    544             }
    545             if (!find){
    546                 int v = vertices[k];
    547                 for (int j = 0; j < 2; j++){
    548                     ++u;
    549                     v2[v].push_back({0, u});
    550                     v2[0].push_back({v, u});
    551                 }
    552             }
    553         }
    554     }
    555     used3.clear();
    556     euler.clear();
    557     dfs3(0);
    558     for (int a : euler){
    559         change_color(a, col1);
    560         swap(col1, col2);
    561     }
    562 }
    563 
    564 void stabilize(const vector<int> &e){
    565     s2.clear();
    566     for (int i = 1; i <= n; i++){
    567         s[i].clear();
    568         for (int j = 1; j <= k; j++){
    569             deg[i][j] = 0;
    570         }
    571     }
    572     for (int edge : e){
    573         deg[a[edge]][color[edge]]++;
    574         deg[b[edge]][color[edge]]++;
    575     }
    576     for (int i = 1; i <= n; i++){
    577         for (int j = 1; j <= k; j++){
    578             s[i].insert({deg[i][j], j});
    579         }
    580         s2.insert(get_s2(i));
    581     }
    582     while(-s2.begin()->first > 2){
    583 
    584         int ind = s2.begin()->second;
    585         int col1 = s[ind].begin()->second;
    586         int col2 = s[ind].rbegin()->second;
    587         vector<int> e2;
    588         for (int edge : e){
    589             if (color[edge] == col1 || color[edge] == col2){
    590                 e2.push_back(edge);
    591             }
    592         }
    593         stabilize_two_colors(e2, col1, col2);
    594     }
    595 }
    596 
    597 void make_random(vector<int> e){
    598     random_shuffle(e.begin(), e.end());
    599     for (int i = 0; i < (int) e.size(); i++){
    600         color[e[i]] = i % k + 1;
    601     }
    602     stabilize(e);
    603 }
    604 
    605 int change[MAX_N];
    606 
    607 void build(vector<int> e){
    608     if ((int) e.size() <= n * k){
    609         make_random(e);
    610         return;
    611     }
    612     random_shuffle(e.begin(), e.end());
    613     vector<int> e1, e2;
    614     int s = (int) e.size() / 2;
    615     for (int i = 0; i < (int) e.size(); i++){
    616         if (i < s){
    617             e1.push_back(e[i]);
    618         }else{
    619             e2.push_back(e[i]);
    620         }
    621     }
    622     build(e1);
    623     build(e2);
    624     vector<pair<int, int> > v1(k), v2(k);
    625     for (int i = 1; i <= k; i++){
    626         v1[i - 1].first = v2[i - 1].first = 0;
    627         v1[i - 1].second = v2[i - 1].second = i;
    628     }
    629     for (int edge : e1){
    630         v1[color[edge] - 1].first++;
    631     }
    632     for (int edge : e2){
    633         v2[color[edge] - 1].first++;
    634     }
    635     sort(v1.rbegin(), v1.rend());
    636     sort(v2.begin(), v2.end());
    637     for (int i = 0; i < k; i++){
    638         change[v1[i].second] = i + 1;
    639     }
    640     for (int edge : e1){
    641         color[edge] = change[color[edge]];
    642     }
    643     for (int i = 0; i < k; i++){
    644         change[v2[i].second] = i + 1;
    645     }
    646     for (int edge : e2){
    647         color[edge] = change[color[edge]];
    648     }
    649     stabilize(e);
    650 }
    651 
    652 int main() {
    653     ios_base::sync_with_stdio(0);
    654     cin.tie(0);
    655     cout.tie(0);
    656     srand(time(NULL));
    657 #ifdef LOCAL
    658     freopen("/Users/antontsypko/tsypko/input.txt", "r", stdin);
    659 #endif
    660     
    661     cin >> n >> m >> k;
    662     
    663     for (int i = 1; i <= n; i++){
    664         cin >> w[i];
    665     }
    666     
    667     ll sum = 0;
    668     vector<int> e;
    669     for (int i = 1; i <= m; i++){
    670         cin >> a[i] >> b[i];
    671         sum += w[a[i]] + w[b[i]];
    672         e.push_back(i);
    673     }
    674     
    675     build(e);
    676     
    677     for (int i = 1; i <= m; i++){
    678         assert(color[i]);
    679         cout << color[i] << endl;
    680     }
    681     
    682 }
    683 ```