codeforces-scrape

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

2253.md (10900B)


      1 Source: https://codeforces.com/blog/entry/155813
      2 
      3 [2253A - The Best Card](/contest/2253/problem/A "Educational Codeforces Round 193 (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     good = True
     18     for j in range(2, n + 1):
     19         if (n + 1) % j == 0:
     20             good = False
     21     if good:
     22         print('YES')
     23     else:
     24         print('NO')
     25 ```
     26 
     27 [2253B - Hypercarp and the Control Panel](/contest/2253/problem/B "Educational Codeforces Round 193 (Rated for Div. 2)")
     28 
     29 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
     30 
     31 **Tutorial**
     32 
     33 Tutorial is loading...
     34 
     35 **Solution (FelixArg)**
     36 
     37 ```
     38 #include <bits/stdc++.h>
     39  
     40 using namespace std;
     41 #define int long long
     42 
     43 void solve(){
     44 	int n;
     45 	cin >> n;
     46 	vector<int> a(n);
     47 	for (int i = 0; i < n; i++){
     48 		cin >> a[i];
     49 	}
     50 	vector<pair<int, int>> b;
     51 	for (int i = 0; i < n; i++){
     52 		if (b.empty() || b.back().first != a[i]){
     53 			b.emplace_back(a[i], 1);
     54 		}
     55 		else{
     56 			b.back().second++;
     57 		}
     58 	}
     59 	int m = b.size();
     60 	for (int i = 0; i < m - 1; i++){
     61 		if (b[i].second > 1 && b[i + 1].second > 1){
     62 			cout << m + 2 << '\n';
     63 			return;
     64 		}
     65 	}
     66 	for (int i = 0; i < m; i++){
     67 		if (i < m - 1 && b[i].second > 1 && (i + 2 >= m || b[i + 2].first != b[i].first)){
     68 			cout << m + 1 << '\n';
     69 			return;
     70 		}
     71 		if (i > 0 && b[i].second > 1 && (i - 2 < 0 || b[i - 2].first != b[i].first)){
     72 			cout << m + 1 << '\n';
     73 			return;
     74 		}
     75 	}
     76 	cout << m << '\n';
     77 }
     78 
     79 signed main()
     80 {
     81 #ifdef FELIX
     82 	auto _clock_start = chrono::high_resolution_clock::now();
     83 #endif
     84 	ios_base::sync_with_stdio(false);
     85 	cin.tie(0);
     86 	cout.tie(0);
     87  
     88 	int tests = 1;
     89 	cin >> tests;
     90 	while(tests--){
     91 		solve();
     92 	}
     93  
     94 #ifdef FELIX
     95 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
     96 		chrono::high_resolution_clock::now()
     97 			- _clock_start).count() << "ms." << endl;
     98 #endif
     99 	return 0;
    100 }
    101 ```
    102 
    103 [2253C - Sum of Distinct Values in a Matrix](/contest/2253/problem/C "Educational Codeforces Round 193 (Rated for Div. 2)")
    104 
    105 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    106 
    107 **Tutorial**
    108 
    109 Tutorial is loading...
    110 
    111 **Solution (BledDest)**
    112 
    113 ```
    114 def get_k_last(l, k):
    115     if k < len(l):
    116         return l[len(l)-k:]
    117     else:
    118         return l
    119 
    120 t = int(input())
    121 for _ in range(t):
    122     n, m, x, y = map(int, input().split())
    123     a = list(map(int, input().split()))
    124     b = list(map(int, input().split()))
    125     
    126     c = []
    127     d = []
    128     e = []
    129     i = 0
    130     j = 0
    131     while i < x and j < y:
    132         if a[i] == b[j]:
    133             c.append(a[i])
    134             i += 1
    135             j += 1
    136         elif a[i] < b[j]:
    137             d.append(a[i])
    138             i += 1
    139         else:
    140             e.append(b[j])
    141             j += 1
    142     d.extend(a[i:])
    143     e.extend(b[j:])
    144     
    145     res = sorted(get_k_last(d, n) + get_k_last(e, m) + c)
    146     res = get_k_last(res, n + m - 1)
    147     print(sum(res))
    148 ```
    149 
    150 [2253D - Hypercarp and Interdimensional Jumps](/contest/2253/problem/D "Educational Codeforces Round 193 (Rated for Div. 2)")
    151 
    152 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
    153 
    154 **Tutorial**
    155 
    156 Tutorial is loading...
    157 
    158 **Solution (FelixArg)**
    159 
    160 ```
    161 #include <bits/stdc++.h>
    162  
    163 using namespace std;
    164 #define int long long
    165 
    166 void solve(){
    167 	int x, y;
    168 	cin >> x >> y;
    169 
    170 	int su = x + y;
    171 	int k = 0;
    172 	while((k + 1) * (k + 2) / 2 <= su){
    173 		k++;
    174 	}
    175 
    176 	int p1x = k * (k + 1) / 2 - y;
    177 	int p1y = y;
    178 
    179 	int p2x = x;
    180 	int p2y = k * (k + 1) / 2 - x;
    181 
    182 	vector<pair<int, int>> cand;
    183 	if ((p1x + p2x) < 0){
    184 		cand.emplace_back((p1x + p2x) / 2, k * (k + 1) / 2 - (p1x + p2x) / 2);
    185 		cand.emplace_back((p1x + p2x - 1) / 2, k * (k + 1) / 2 - (p1x + p2x - 1) / 2);
    186 	}
    187 	else{
    188 		cand.emplace_back((p1x + p2x) / 2, k * (k + 1) / 2 - (p1x + p2x) / 2);
    189 		cand.emplace_back((p1x + p2x + 1) / 2, k * (k + 1) / 2 - (p1x + p2x + 1) / 2);
    190 	}
    191 
    192 	auto best = cand[0];
    193 	for (auto [p, q] : cand){
    194 		if (p < 0){
    195 			p = 0;
    196 		}
    197 		if (q < 0){
    198 			q = 0;
    199 		}
    200 		if ((p - x) * (p - x) + (q - y) * (q - y) < 
    201 			(best.first - x) * (best.first - x) + (best.second - y) * (best.second - y)){
    202 				best = {p, q};
    203 		}
    204 	}
    205 
    206 	string ans(k, 'Y');
    207 	for (int i = 0; i < k; i++){
    208 		if (best.first >= k - i){
    209 			ans[i] = 'X';
    210 			best.first -= (k - i);
    211 		}
    212 	}
    213 
    214 	cout << ans << '\n';
    215 }
    216 
    217 signed main()
    218 {
    219 #ifdef FELIX
    220 	auto _clock_start = chrono::high_resolution_clock::now();
    221 #endif
    222 	ios_base::sync_with_stdio(false);
    223 	cin.tie(0);
    224 	cout.tie(0);
    225  
    226 	int tests = 1;
    227 	cin >> tests;
    228 	while(tests--){
    229 		solve();
    230 	}
    231  
    232 #ifdef FELIX
    233 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    234 		chrono::high_resolution_clock::now()
    235 			- _clock_start).count() << "ms." << endl;
    236 #endif
    237 	return 0;
    238 }
    239 ```
    240 
    241 [2253E - Diameter Intersections](/contest/2253/problem/E "Educational Codeforces Round 193 (Rated for Div. 2)")
    242 
    243 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    244 
    245 **Tutorial**
    246 
    247 Tutorial is loading...
    248 
    249 **Solution (BledDest)**
    250 
    251 ```
    252 #include<bits/stdc++.h>
    253 
    254 using namespace std;
    255 
    256 const int N = 1000043;
    257 
    258 vector<int> g[N];
    259 int n;
    260 
    261 vector<int> get_dist(int x)
    262 {
    263     vector<int> d(n, -1);
    264     d[x] = 0;
    265     queue<int> q;
    266     q.push(x);
    267     while(!q.empty())
    268     {
    269         int k = q.front();
    270         q.pop();
    271         for(auto y : g[k])
    272             if(d[y] == -1)
    273             {
    274                 d[y] = d[k] + 1;
    275                 q.push(y);
    276             }   
    277     }
    278     return d;
    279 }
    280 
    281 void remove_edge(int x, int y)
    282 {
    283     int idx = -1;
    284     for(int i = 0; i < g[x].size(); i++)
    285         if(g[x][i] == y)
    286             idx = i;
    287     g[x].erase(g[x].begin() + idx, g[x].begin() + idx + 1);    
    288 } 
    289 
    290 vector<int> process(int v)
    291 {
    292     vector<int> d(n, -1), p(n, -1);
    293     queue<int> q;
    294     q.push(v);
    295     d[v] = 0;
    296     vector<int> visited;
    297     while(!q.empty())
    298     {
    299         int k = q.front();
    300         q.pop();
    301         visited.push_back(k);
    302         for(auto y : g[k])
    303             if(d[y] == -1)
    304             {
    305                 d[y] = d[k] + 1;
    306                 q.push(y);
    307                 p[y] = k;
    308             }
    309     }
    310     int max_dist = *max_element(d.begin(), d.end());
    311     vector<bool> has_end(n, false);
    312     has_end[v] = true;
    313     for(auto x : visited)
    314         if(d[x] == max_dist)
    315         {
    316             int cur = x;
    317             while(!has_end[cur])
    318             {
    319                 has_end[cur] = true;
    320                 cur = p[cur];
    321             }
    322         }
    323 
    324     vector<int> res;
    325     for(auto x : visited)
    326     {
    327         if(!has_end[x]) continue;
    328         int good_children = 0;
    329         for(auto y : g[x])
    330             if(p[x] != y && has_end[y]) good_children++;
    331         if(good_children != 1) res.push_back(d[x]);
    332     }   
    333     sort(res.begin(), res.end());
    334     res.erase(unique(res.begin(), res.end()), res.end());
    335     return res;
    336 }
    337 
    338 void solve()
    339 {
    340     cin >> n;
    341     for(int i = 0; i < n; i++)
    342         g[i].clear();
    343     for(int i = 0; i < n - 1; i++)
    344     {
    345         int x, y;
    346         cin >> x >> y;
    347         --x;
    348         --y;
    349         g[x].push_back(y);
    350         g[y].push_back(x);
    351     }
    352 
    353     auto dist0 = get_dist(0);
    354     int e1 = max_element(dist0.begin(), dist0.end()) - dist0.begin();
    355     auto dist1 = get_dist(e1);
    356     int e2 = max_element(dist1.begin(), dist1.end()) - dist1.begin();
    357     auto dist2 = get_dist(e2);
    358     int d = dist1[e2];
    359 
    360     int x = -1, y = -1;
    361     for(int i = 0; i < n; i++)
    362         if(dist1[i] + dist2[i] == d)
    363         {
    364             if(dist1[i] == dist2[i] - 1)
    365                 x = i;
    366             else if(dist1[i] == dist2[i] + 1)
    367                 y = i;
    368         }
    369 
    370     remove_edge(x, y);
    371     remove_edge(y, x);
    372     auto ans1 = process(x);
    373     auto ans2 = process(y);
    374 
    375     vector<bool> res(n + 1);
    376     for(auto x : ans1)
    377         for(auto y : ans2)
    378             res[x + y + 1] = true;
    379     int cnt = 0;
    380     for(auto x : res)
    381         if(x) cnt++;
    382     cout << cnt;
    383     for(int i = 0; i <= n; i++)
    384         if(res[i])
    385             cout << " " << i;
    386     cout << endl;
    387 }
    388 
    389 int main()
    390 {
    391     ios_base::sync_with_stdio(0);
    392     cin.tie(0);
    393     int t;
    394     cin >> t;
    395     for(int i = 0; i < t; i++)
    396         solve();
    397 }
    398 ```
    399 
    400 [2253F - 4-beauty](/contest/2253/problem/F "Educational Codeforces Round 193 (Rated for Div. 2)")
    401 
    402 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    403 
    404 **Tutorial**
    405 
    406 Tutorial is loading...
    407 
    408 **Solution (BledDest)**
    409 
    410 ```
    411 #include<bits/stdc++.h>
    412 
    413 using namespace std;
    414 
    415 const int N = int(5e5) + 43;
    416 const long long INF64 = (long long)(1e18);
    417 
    418 int n;
    419 int cost[N];
    420 
    421 void upd(long long& x, long long y)
    422 {
    423     if(x > y) x = y;
    424 }
    425 
    426 bool check_bit(int x, int y)
    427 {
    428     return bool((x >> y) & 1);
    429 }
    430 
    431 long long calc_dp(const vector<vector<int>>& c)
    432 {
    433     int n = c.size();
    434     int m = c[0].size();
    435     int full = (1 << m) - 1;
    436     vector<vector<vector<long long>>> dp(2, vector<vector<long long>>(m, vector<long long>(1 << m, INF64)));
    437     dp[0][0][0] = 0;
    438     for(int i = 0; i < n; i++)
    439     {
    440         int i1 = i & 1;
    441         int i2 = i1 ^ 1;
    442         for(int j = 0; j < m; j++)
    443             for(int f = 0; f < (1 << m); f++)
    444                 dp[i2][j][f] = INF64;
    445         for(int j = 0; j < m; j++)
    446             for(int f = 0; f < (1 << m); f++)
    447             {
    448                 if(dp[i1][j][f] == INF64) continue;
    449                 int ni = i1;
    450                 int nj = j + 1;
    451                 if(nj == m)
    452                 {
    453                     ni = i2;
    454                     nj = 0;
    455                 }
    456                 bool can = true;
    457                 if(i > 0 && j + 2 < m && check_bit(f, m - 1) && check_bit(f, m - 2) && check_bit(f, m - 3))
    458                     can = false;
    459                 if(can)
    460                 {
    461                     int nf = ((f << 1) & full) | 1;
    462                     upd(dp[ni][nj][nf], dp[i1][j][f]); 
    463                 }
    464                 int nf = (f << 1) & full;
    465                 upd(dp[ni][nj][nf], dp[i1][j][f] + c[i][j]);
    466             }
    467     }   
    468     return *min_element(dp[n & 1][0].begin(), dp[n & 1][0].end());
    469 }
    470 
    471 long long calc_comp(int x)
    472 {
    473     int d2 = 0, d3 = 0;
    474     int p2 = 1, p3 = 1;
    475     while(x * (p2 * 2) <= n)
    476     {
    477         p2 *= 2;
    478         d2++;
    479     }
    480     while(x * (p3 * 3) <= n)
    481     {
    482         p3 *= 3;
    483         d3++;
    484     }
    485     d2++;
    486     d3++;
    487     vector<int> pow2(d2, 1), pow3(d3, 1);
    488     for(int i = 1; i < d2; i++)
    489         pow2[i] = pow2[i - 1] * 2;
    490     for(int i = 1; i < d3; i++)
    491         pow3[i] = pow3[i - 1] * 3;
    492     vector<vector<int>> cur(d3, vector<int>(d2, 0));
    493     for(int i = 0; i < d2; i++)
    494         for(int j = 0; j < d3; j++)
    495             if(x * 1ll * pow2[i] * 1ll * pow3[j] <= n)
    496                 cur[j][i] = cost[x * pow2[i] * pow3[j]];
    497     return calc_dp(cur);
    498 }   
    499 
    500 void solve()
    501 {
    502     cin >> n;
    503     for(int i = 1; i <= n; i++)
    504         cin >> cost[i];
    505     long long ans = 0;
    506     for(int i = 1; i <= n; i++)
    507         if(i % 2 != 0 && i % 3 != 0)
    508             ans += calc_comp(i);
    509     cout << ans << endl; 
    510 }
    511 
    512 int main()
    513 {
    514     ios_base::sync_with_stdio(0);
    515     int t = 1;
    516     for(int i = 0; i < t; i++)
    517         solve();    
    518 }
    519 ```