codeforces-scrape

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

1737.md (11603B)


      1 Source: https://codeforces.com/blog/entry/107567
      2 
      3 > It has been a wild ride the final 24 hours in the preparation of this contest! And we really hope you liked the problemset we gave today!
      4 
      5 ## [1737A - Ela Sorting Books](/contest/1737/problem/A "Dytechlab Cup 2022")
      6 
      7 Author: [low_](/profile/low_ "Master low_")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution snippet ( low_ C++)**
     14 
     15 ```
     16 ...
     17 void execute(int test_number)
     18 {
     19   cin>>n>>k>>str;
     20   vector <int> count_char(26, 0);
     21   for (char c: str) count_char[c - 'a']++;
     22   string ans = "";
     23   for (int i = 0; i < min(25, n/k); i++) {
     24     while (k - ans.size() > count_char[i]) {
     25       ans.push_back(i + 'a');
     26     }
     27   }
     28 
     29   char c = 'a' + min(n / k, 25);
     30   while (k > ans.size()) {
     31     ans += c;
     32   }
     33   reverse(ans.begin(), ans.end());
     34   cout << ans << "\n";
     35 }
     36 ...
     37 ```
     38 
     39 ## [1737B - Ela's Fitness and the Luxury Number](/contest/1737/problem/B "Dytechlab Cup 2022")
     40 
     41 Author: [low_](/profile/low_ "Master low_")
     42 
     43 **Tutorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Solution snippet (low_, C++)**
     48 
     49 ```
     50 ...
     51 ll l, r;
     52 
     53 ll bs_sqrt(ll x) {
     54   ll left = 0, right = 2000000123;
     55   while (right > left) {
     56       ll mid = (left + right) / 2;
     57       
     58       if (mid * mid > x) right = mid;
     59       else left = mid + 1;
     60   }
     61   return left - 1;
     62 }
     63 
     64 // main solution goes here:
     65 void execute(int test_number)
     66 {
     67   cin >> l >> r;
     68   ll sql = bs_sqrt(l), sqr = bs_sqrt(r);
     69   ll ans;
     70   if (sql == sqr) {
     71     ans = 0;
     72     for (int i = 0; i < 3; i++) {
     73       if (l <= sql * (sql + i) && sql * (sql + i) <= r) ans++;
     74     }
     75   } else {
     76     ans = (sqr - sql - 1) * 3;
     77     for (int i = 0; i < 3; i++) {
     78       if (l <= sql * (sql + i) && sql * (sql + i) <= r) ans++;
     79       if (l <= sqr * (sqr + i) && sqr * (sqr + i) <= r) ans++;
     80     }
     81   }
     82   cout << ans << "\n";
     83 }
     84 ...
     85 ```
     86 
     87 ## [1737C - Ela and Crickets](/contest/1737/problem/C "Dytechlab Cup 2022")
     88 
     89 Author: [low_](/profile/low_ "Master low_")
     90 
     91 **Tutorial**
     92 
     93 Tutorial is loading...
     94 
     95 **Solution snippet (low_, C++)**
     96 
     97 ```
     98 ...
     99 int n;
    100 int x[3], y[3];
    101 int u, v;
    102 
    103 pii centralSquare() {
    104   int a = (x[0] == x[1]) ? x[0] : x[2];
    105   int b = (y[0] == y[1]) ? y[0] : y[2];
    106   return {a, b};
    107 }
    108 // main solution goes here:
    109 void execute(int test_number)
    110 {
    111   cin>>n;
    112   for (int i=0; i<3; i++) cin>>x[i]>>y[i];
    113   cin>>u>>v;
    114 
    115   int cx = centralSquare().first, cy = centralSquare().second;
    116 
    117   if ((cx == 1 || cx == n) && (cy == 1 || cy == n)) { // "corner" case, literally
    118     // the crickets can only reach coordinates within the edges that already contains at least 2 crickets,
    119     // which contains the centralSquare of the L
    120     cout << ((u == cx || v == cy) ? "YES\n" : "NO\n");
    121   } else {
    122     if ((cx + cy) % 2 == (u + v) % 2) {
    123       cout << (cx % 2 == u % 2 ? "YES\n" : "NO\n"); 
    124     } else { // can be prove to always reach, since we have ways to align 2 crickets in the same diagonal as target
    125       cout << "YES\n"; 
    126     }
    127   }
    128 }
    129 ...
    130 ```
    131 
    132 ## [1737D - Ela and the Wiring Wizard](/contest/1737/problem/D "Dytechlab Cup 2022")
    133 
    134 Author: [low_](/profile/low_ "Master low_")
    135 
    136 **Tutorial**
    137 
    138 Tutorial is loading...
    139 
    140 **Solution (magnified, C++)**
    141 
    142 ```
    143 #include <bits/stdc++.h>
    144 #define ll long long
    145 #define db long double
    146 #define ull unsigned long long
    147 #define x first
    148 #define y second
    149 #define mp make_pair
    150 #define pb push_back
    151 #define all(a) a.begin(), a.end()
    152 
    153 using namespace std;
    154 
    155 #define pper(a) cerr << #a << " = " << a << endl;
    156 
    157 void per() { cerr << endl; }
    158 template<typename Head, typename... Tail> void per(Head H, Tail... T) { cerr << H << ' '; per(T...); }
    159 
    160 template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
    161 template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
    162 
    163 template<class U, class V> 
    164 ostream& operator<<(ostream& out, const pair<U, V>& a) {
    165   return out << "(" << a.x << ", " << a.y << ")";
    166 }
    167 
    168 template<class U, class V> 
    169 istream& operator>>(istream& in, pair<U, V>& a) {
    170   return in >> a.x >> a.y;
    171 }
    172 
    173 template<typename W, typename T = typename enable_if<!is_same<W, string>::value, typename W::value_type>::type>
    174 ostream& operator<<(ostream& out, const W& v) { out << "{ "; for (const auto& x : v) out << x << ", "; return out << '}'; }
    175 
    176 template<class T>
    177 void readArr(T from, T to) {
    178   for (auto i = from; i != to; ++i) cin >> *i;
    179 }
    180 
    181 mt19937 mrand(1337); 
    182 unsigned int myRand32() {
    183   return mrand() & (unsigned int)(-1);
    184 }
    185  
    186 unsigned ll myRand64() {
    187   return ((ull)myRand32() << 32) ^ myRand32();
    188 }
    189 
    190 const int mod = 1000000007;
    191 
    192 void add(int& a, int b) {
    193   a += b; if (a >= mod) a -= mod;
    194 }
    195 
    196 void dec(int &a, int b) {
    197   a -= b; if (a < 0) a += mod;
    198 }
    199 
    200 int mult(int a, int b) {
    201   return a * (ll)b % mod;
    202 }
    203 
    204 int bp(int a, int b) {
    205   int res = 1;
    206   while (b > 0) {
    207     if (b & 1) res = mult(res, a);
    208     a = mult(a, a);
    209     b >>= 1;
    210   }
    211   return res;
    212 }
    213 
    214 const int N = 507;
    215 
    216 ll f[N][N];
    217 
    218 int main(){
    219 #ifdef LOCAL
    220 	freopen("N_input.txt", "r", stdin);
    221 	//freopen("N_output.txt", "w", stdout);
    222 #endif
    223 	ios_base::sync_with_stdio(0);
    224 	cin.tie(0);
    225 
    226   int t;
    227   cin >> t;
    228 
    229   for (int a = 0; a < t; ++a) {
    230 
    231     int n, m;
    232     cin >> n >> m;
    233 
    234     for (int i = 0; i < n; ++i) {
    235       for (int j = 0; j < n; ++j) {
    236         f[i][j] = 1e18;
    237       }
    238       f[i][i] = 0;
    239     }
    240 
    241     vector<tuple<int, int, int> > ed;
    242 
    243     for (int i = 0; i < m; ++i) {
    244       int u, v, w;
    245       cin >> u >> v >> w;
    246       ed.pb(make_tuple(u - 1, v - 1, w));
    247       f[u - 1][v - 1] = 1;
    248       f[v - 1][u - 1] = 1;
    249     }
    250 
    251     for (int k = 0; k < n; ++k) {
    252       for (int i = 0; i < n; ++i) {
    253         for (int j = 0; j < n; ++j) {
    254           f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    255         }
    256       }
    257     }
    258 
    259     ll ans = 1e18;
    260     for (auto x : ed) {
    261       int u = get<0>(x);
    262       int v = get<1>(x);
    263       int w = get<2>(x);
    264 
    265 //      per(ans, u, v, w);
    266 
    267       ans = min(ans, (ll) w * (f[0][u] + f[n - 1][v] + 1));
    268       ans = min(ans, (ll) w * (f[0][v] + f[n - 1][u] + 1));
    269 
    270   //    per(ans, u, v, w);
    271 
    272       for (int i = 0; i < n; ++i) {
    273         ans = min(ans, (ll) w * (f[v][i] + 1 + f[i][0] + f[i][n-1] + 1));
    274         ans = min(ans, (ll) w * (f[u][i] + 1 + f[i][0] + f[i][n-1] + 1));
    275       }
    276 
    277     }
    278 
    279     cout << ans << '\n';
    280 
    281   }
    282 }
    283 ```
    284 
    285 ## [1737E - Ela Goes Hiking](/contest/1737/problem/E "Dytechlab Cup 2022")
    286 
    287 Author: [ngfam_kongu](/profile/ngfam_kongu "Master ngfam_kongu")
    288 
    289 **Tutorial**
    290 
    291 Tutorial is loading...
    292 
    293 **Solution snippet (low_, C++)**
    294 
    295 ```
    296 ...
    297 // data preprocessing: (e.g.: divisor generating, prime sieve)
    298 ll POW2[mn];
    299 void preprocess()
    300 {
    301   POW2[0] = 1;
    302   for (int i = 1; i < mn; i++) POW2[i] = POW2[i &mdash; 1] * 2 % mod;
    303 }
    304  
    305 // global variables:
    306 ll n;
    307  
    308 ll POW(ll u, ll v) {
    309   if (v == 0) return 1;
    310   ll mid = POW(u, v / 2);
    311   mid = (mid * mid) % mod;
    312   return (v & 1) ? (mid * u % mod) : mid;
    313 }
    314 // main solution goes here:
    315 void execute(int test_number)
    316 {
    317   cin>>n;
    318  
    319   if (n == 1) {
    320     cout << "1\n";
    321     return;
    322   }
    323   vector <ll> ans(n + 1, 0), sufsum(n + 1, 0);
    324   sufsum[n] = ans[n] = POW(POW2[(n &mdash; 1) / 2], mod &mdash; 2);
    325   for (int i = n &mdash; 1; i > 1; i--) {
    326     ans[i] = POW(POW2[(i + 1) / 2], mod &mdash; 2);
    327     if (2 * i <= n) ans[i] = ans[i] * (1 &mdash; sufsum[i * 2] + mod) % mod;
    328     sufsum[i] = (sufsum[i + 1] + ans[i]) % mod;
    329   }
    330   for (int i = 1; i <= n; i++) cout << ans[i] << "\n";
    331  
    332 }
    333 ...
    334 ```
    335 
    336 ## [1737F - Ela and Prime GCD](/contest/1737/problem/F "Dytechlab Cup 2022")
    337 
    338 Author: [055D](/profile/055D "Master 055D")
    339 
    340 **Tutorial**
    341 
    342 Observation: Assume that x is composite number and divisor of n. Among all the multiples of x, the number of the divisor of n must be less than or equal to m/2.
    343 
    344 First, factorize n. Assume that w is divisor of n. If w is in the form of a^4, a^3b^2, or a^2b^2c^2, it can be proved that there is no answer. Otherwise, there can be two cases.
    345 
    346 If the possible maximum exponent of prime factor is 2, place the divisors like this: 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a / 1 a^2 a. And expand the sequence as follows:
    347 
    348 1. Repeat the current sequence twice — 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a / 1 a^2 a 1 a^2 a.
    349 2. Multiply the odd-indexed elements of first half and the even-indexed elements of second half by the new prime factor. Index 1 is exception — 1 a^2b^2 bc a^2b b^2c ab a^2c ab^2 ac c a^2b^2c b a^2bc b^2 abc a^2 ab^2c a / 1 a^2 ab b a^2b a.
    350 3. If more prime factor exists, jump to "Otherwise".
    351 
    352 Otherwise, place the divisors like this: 1 a^3 a a^2 / 1 a. Now the exponents of other prime factors are all 1, and we can expand the sequence as follows:
    353 
    354 1. Repeat the current sequence twice — 1 a^3 a a^2 1 a^3 a a^2 / 1 a 1 a.
    355 2. Multiply the even-indexed elements of first half and the odd-indexed elements of second half by the new prime factor — 1 a^3b a a^2b b a^3 ab a^2 / 1 ab b a. 3-1. If the maximum exponent is 3, swap a and b — 1 a^3b b a^2b a a^3 ab a^2 3-2. Otherwise, swap b and ab — 1 b ab a.
    356 
    357 Like this, we can expand the sequence
    358 
    359 **Solution (C++)**
    360 
    361 ```
    362 #import<bits/stdc++.h>
    363 #define endl '\n'
    364 using namespace std;
    365 
    366 int m, t, b[18], check[18], cnt[5];
    367 vector<int>v;
    368 vector<vector<int>>a;
    369 
    370 void initialize(int m)
    371 {
    372 	fill(b, b + m + 1, 0);
    373 	fill(check, check + m + 1, 0);
    374 	fill(cnt, cnt + 5, 0);
    375 	v.clear();
    376 	a.clear();
    377 }
    378 void insert1(int p1, int c1)
    379 {
    380 	v[p1] = c1;
    381 	a.push_back(v);
    382 }
    383 void insert2(int p1, int p2, int c1, int c2)
    384 {
    385 	v[p1] = c1;
    386 	v[p2] = c2;
    387 	a.push_back(v);
    388 }
    389 
    390 void f1(int x)
    391 {
    392 	int n = a.size();
    393 	for(int i = 0; i < n; i++)a.push_back(a[i]);
    394 	for(int i = 0; i < n; i += 2)
    395 	{
    396 		a[i + 1][x] = 1;
    397 		a[i + n][x] = 1;
    398 	}
    399 	swap(a[n / 2], a[n]);
    400 }
    401 void f2(int x)
    402 {
    403 	int n = a.size();
    404 	for(int i = 0; i < n; i++)a.push_back(a[i]);
    405 	for(int i = 1; i < n; i += 2)
    406 	{
    407 		a[i + 1][x] = 1;
    408 		a[i + n][x] = 1;
    409 	}
    410 	a[n][x] = 1;
    411 }
    412 void f3(int x)
    413 {
    414 	int n = a.size();
    415 	for(int i = 0; i < n; i++)a.push_back(a[i]);
    416 	for(int i = 0; i < n; i += 2)
    417 	{
    418 		a[i + 1][x] = 1;
    419 		a[i + n][x] = 1;
    420 	}
    421 	swap(a[n], a[2 * n &mdash; 1]);
    422 }
    423 
    424 int main()
    425 {
    426 	ios::sync_with_stdio(0);
    427 	cin.tie(0);
    428 	for(cin >> t; t--;)
    429 	{
    430 		cin >> m;
    431 		for(int i = 1; i <= m; i++)
    432 		{
    433 			cin >> b[i];
    434 			cnt[min(b[i], 4)]++;
    435 		}
    436 		if(cnt[4] || cnt[3] >= 2 || cnt[3] && cnt[2] || cnt[2] >= 3)
    437 		{
    438 			cout << -1 << endl;
    439 			initialize(m);
    440 			continue;
    441 		}
    442 		
    443 		for(int i = 1; i <= m; i++)v.push_back(0);
    444 		a.push_back(v);
    445 		
    446 		if(cnt[2])
    447 		{
    448 			int p1 = -1, p2 = -1;
    449 			for(int i = 1; i <= m; i++)
    450 			{
    451 				if(b[i] == 2)
    452 				{
    453 					if(~p1)p2 = i - 1;
    454 					else p1 = i - 1;
    455 				}
    456 			}
    457 			if(~p2)
    458 			{
    459 				insert2(p1, p2, 2, 2);
    460 				insert2(p1, p2, 0, 1);
    461 				insert2(p1, p2, 2, 1);
    462 				insert2(p1, p2, 0, 2);
    463 				insert2(p1, p2, 1, 1);
    464 				insert2(p1, p2, 2, 0);
    465 				insert2(p1, p2, 1, 2);
    466 				insert2(p1, p2, 1, 0);
    467 				check[p1 + 1] = check[p2 + 1] = 1;
    468 			}
    469 			else
    470 			{
    471 				insert1(p1, 2);
    472 				insert1(p1, 1);
    473 				check[p1 + 1] = 1;
    474 			}
    475 			for(int i = 1; i <= m; i++)
    476 			{
    477 				if(check[i])continue;
    478 				if(a.size() % 2)f2(i - 1);
    479 				else f3(i - 1);
    480 			}
    481 		}
    482 		else
    483 		{
    484 			if(cnt[3])
    485 			{
    486 				int p = 0;
    487 				for(int i = 1; i <= m; i++)
    488 				{
    489 					if(b[i] == 3)p = i - 1;
    490 				}
    491 				insert1(p, 3);
    492 				insert1(p, 1);
    493 				insert1(p, 2);
    494 				check[p + 1] = 1;
    495 			}
    496 			else
    497 			{
    498 				insert1(0, 1);
    499 				check[1] = 1;
    500 			}
    501 			for(int i = 1; i <= m; i++)
    502 			{
    503 				if(!check[i])f1(i - 1);
    504 			}
    505 		}
    506 		
    507 		for(auto &v: a)
    508 		{
    509 			if(*max_element(v.begin(), v.end()))
    510 			{
    511 				for(auto &p: v)cout << p << ' ';
    512 				cout << endl;
    513 			}
    514 		}
    515 		initialize(m);
    516 	}
    517 }
    518 ```
    519 
    520 ## [1737G - Ela Takes Dancing Class](/contest/1737/problem/G "Dytechlab Cup 2022")
    521 
    522 Author: [magnified](/profile/magnified "Master magnified")
    523 
    524 **Tutorial**
    525 
    526 Tutorial is loading...
    527 
    528 **Solution (C++)**
    529 
    530 [175061586](/contest/1737/submission/175061586 "Submission 175061586 by magnified")