codeforces-scrape

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

1792.md (11833B)


      1 Source: https://codeforces.com/blog/entry/111835
      2 
      3 [1792A - GamingForces](/contest/1792/problem/A "Educational Codeforces Round 142 (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     int n;
     23     cin >> n;
     24     int cnt1 = 0;
     25     for (int i = 0; i < n; ++i) {
     26       int x;
     27       cin >> x;
     28       cnt1 += (x == 1);
     29     }
     30     cout << n - cnt1 / 2 << '\n';
     31   }
     32 }
     33 ```
     34 
     35 [1792B - Stand-up Comedian](/contest/1792/problem/B "Educational Codeforces Round 142 (Rated for Div. 2)")
     36 
     37 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution (awoo)**
     44 
     45 ```
     46 for _ in range(int(input())):
     47     a1, a2, a3, a4 = map(int, input().split())
     48     if a1 == 0:
     49         print(1)
     50     else:
     51         print(a1 + min(a2, a3) * 2 + min(a1 + 1, abs(a2 - a3) + a4))
     52 ```
     53 
     54 [1792C - Min Max Sort](/contest/1792/problem/C "Educational Codeforces Round 142 (Rated for Div. 2)")
     55 
     56 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     57 
     58 **Tutorial**
     59 
     60 Tutorial is loading...
     61 
     62 **Solution (Neon)**
     63 
     64 ```
     65 #include <bits/stdc++.h>
     66 
     67 using namespace std;
     68 
     69 int main() {
     70   int t;
     71   cin >> t;
     72   while (t--) {
     73     int n;
     74     cin >> n;
     75     vector<int> pos(n + 1);
     76     for (int i = 0; i < n; ++i) {
     77       int x;
     78       cin >> x;
     79       pos[x] = i;
     80     }
     81     int l = (n + 1) / 2, r = (n + 2) / 2;
     82     while (l > 0 && (l == r || (pos[l] < pos[l + 1] && pos[r - 1] < pos[r]))) {
     83       --l;
     84       ++r;
     85     }
     86     cout << (n - r + l + 1) / 2 << '\n';
     87   }
     88 }
     89 ```
     90 
     91 [1792D - Fixed Prefix Permutations](/contest/1792/problem/D "Educational Codeforces Round 142 (Rated for Div. 2)")
     92 
     93 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     94 
     95 **Tutorial**
     96 
     97 Tutorial is loading...
     98 
     99 **Solution (awoo)**
    100 
    101 ```
    102 #include <bits/stdc++.h>
    103  
    104 using namespace std;
    105  
    106 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    107 
    108 int get(const vector<int> &a, const vector<int> &b){
    109 	int res = 0;
    110 	while (res < int(a.size()) && a[res] == b[res])
    111 		++res;
    112 	return res;
    113 }
    114 
    115 int main(){
    116 	int t;
    117 	scanf("%d", &t);
    118 	while (t--){
    119 		int n, m;
    120 		scanf("%d%d", &n, &m);
    121 		vector<vector<int>> a(n, vector<int>(m));
    122 		forn(i, n) forn(j, m){
    123 			scanf("%d", &a[i][j]);
    124 			--a[i][j];
    125 		}
    126 		vector<vector<int>> b(n, vector<int>(m));
    127 		forn(i, n) forn(j, m) b[i][a[i][j]] = j;
    128 		sort(b.begin(), b.end());
    129 		forn(i, n){
    130 			int j = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
    131 			int ans = 0;
    132 			if (j > 0) ans = max(ans, get(a[i], b[j - 1]));
    133 			if (j < n) ans = max(ans, get(a[i], b[j]));
    134 			printf("%d ", ans);
    135 		}
    136 		puts("");
    137 	}
    138 }
    139 ```
    140 
    141 [1792E - Divisors and Table](/contest/1792/problem/E "Educational Codeforces Round 142 (Rated for Div. 2)")
    142 
    143 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    144 
    145 **Tutorial**
    146 
    147 Tutorial is loading...
    148 
    149 **Solution (adedalic)**
    150 
    151 ```
    152 #include<bits/stdc++.h>
    153 
    154 using namespace std;
    155 
    156 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    157 #define sz(a) int((a).size())
    158 
    159 #define x first
    160 #define y second
    161 
    162 typedef long long li;
    163 typedef long double ld;
    164 typedef pair<int, int> pt;
    165 
    166 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    167 	return out << "(" << p.x << ", " << p.y << ")";
    168 }
    169 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    170 	fore(i, 0, sz(v)) {
    171 		if(i) out << " ";
    172 		out << v[i];
    173 	}
    174 	return out;
    175 }
    176 
    177 const int INF = int(1e9);
    178 const li INF64 = li(1e18);
    179 const ld EPS = 1e-9;
    180 
    181 int n;
    182 li m1, m2;
    183 
    184 inline bool read() {
    185 	if(!(cin >> n >> m1 >> m2))
    186 		return false;
    187 	return true;
    188 }
    189 
    190 vector<pt> mFact;
    191 vector<li> divs;
    192 
    193 void factM(li m1, li m2) {
    194 	mFact.clear();
    195 
    196 	for (int d = 2; d * d <= m1 || d * d <= m2; d++) {
    197 		int cnt = 0;
    198 		while (m1 % d == 0) {
    199 			m1 /= d;
    200 			cnt++;
    201 		}
    202 		while (m2 % d == 0) {
    203 			m2 /= d;
    204 			cnt++;
    205 		}
    206 		if (cnt > 0)
    207 			mFact.push_back({d, cnt});
    208 	}
    209 	if (m1 > m2)
    210 		swap(m1, m2);
    211 	if (m1 > 1)
    212 		mFact.push_back({m1, 1});
    213 	if (m2 > 1) {
    214 		if (m2 == m1)
    215 			mFact.back().y++;
    216 		else
    217 			mFact.push_back({m2, 1});
    218 	}
    219 }
    220 
    221 void genDivisors(int pos, li val) {
    222 	if (pos >= sz(mFact)) {
    223 		divs.push_back(val);
    224 		return;
    225 	}
    226 	li cur = val;
    227 	fore (pw, 0, mFact[pos].y + 1) {
    228 		genDivisors(pos + 1, cur);
    229 		if (pw < mFact[pos].y)
    230 			cur *= mFact[pos].x;
    231 	}
    232 }
    233 
    234 inline void solve() {
    235 	factM(m1, m2);
    236 
    237 	divs.clear();
    238 	genDivisors(0, 1);
    239 	sort(divs.begin(), divs.end());
    240 
    241 	vector<int> ans(sz(divs), 0);
    242 
    243 	vector<li> dp(sz(divs), -1);
    244 	fore (id, 0, sz(divs)) {
    245 		if (divs[id] <= n)
    246 			dp[id] = divs[id];
    247 		for (auto [p, pw] : mFact) {
    248 			if (divs[id] % p != 0)
    249 				continue;
    250 			
    251 			int pos = int(lower_bound(divs.begin(), divs.end(), divs[id] / p) - divs.begin());
    252 			dp[id] = max(dp[id], dp[pos]);
    253 		}
    254 
    255 		if (divs[id] / dp[id] <= n)
    256 			ans[id] = divs[id] / dp[id];
    257 	}
    258 
    259 	int cnt = 0;
    260 	int xorSum = 0;
    261 	fore (i, 0, sz(ans)) {
    262 		cnt += ans[i] > 0;
    263 		xorSum ^= ans[i];
    264 	}
    265 	
    266 //	cout << sz(ans) << endl;
    267 //	cout << ans << endl;
    268 	cout << cnt << " " << xorSum << endl;
    269 }
    270 
    271 int main() {
    272 #ifdef _DEBUG
    273 	freopen("input.txt", "r", stdin);
    274 	int tt = clock();
    275 #endif
    276 	ios_base::sync_with_stdio(false);
    277 	cin.tie(0), cout.tie(0);
    278 	cout << fixed << setprecision(15);
    279 
    280 	int t; cin >> t;
    281 	
    282 	while (t--) {
    283 		
    284 		read();
    285 		solve();
    286 		
    287 #ifdef _DEBUG
    288 		cerr << "TIME = " << clock() - tt << endl;
    289 		tt = clock();
    290 #endif
    291 	}
    292 	return 0;
    293 }
    294 ```
    295 
    296 [1792F1 - Graph Coloring (easy version)](/contest/1792/problem/F1 "Educational Codeforces Round 142 (Rated for Div. 2)")
    297 
    298 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    299 
    300 **Tutorial**
    301 
    302 Tutorial is loading...
    303 
    304 **Solution (BledDest)**
    305 
    306 ```
    307 #include<bits/stdc++.h>
    308 
    309 using namespace std;
    310 
    311 const int MOD = 998244353;
    312 
    313 int add(int x, int y)
    314 {
    315     x += y;
    316     while(x >= MOD) x -= MOD;
    317     while(x < 0) x += MOD;
    318     return x;
    319 }
    320 
    321 int mul(int x, int y)
    322 {
    323     return (x * 1ll * y) % MOD;
    324 }
    325 
    326 int varMul(int x)
    327 {
    328     return x;
    329 }
    330 
    331 template<typename... Args>
    332 int varMul(int x, Args... args)
    333 {
    334     return mul(x, varMul(args...));
    335 }
    336 
    337 int binpow(int x, int y)
    338 {
    339     int z = 1;
    340     while(y)
    341     {
    342         if(y & 1) z = mul(z, x);
    343         x = mul(x, x);
    344         y /= 2;
    345     }
    346     return z;
    347 }
    348 
    349 vector<int> fact, rfact;
    350 vector<int> dp;
    351 int n;
    352 
    353 void precalc()
    354 {
    355     fact.resize(n + 1);
    356     rfact.resize(n + 1);
    357     fact[0] = 1;
    358     for(int i = 1; i <= n; i++)
    359         fact[i] = mul(i, fact[i - 1]);
    360     for(int i = 0; i <= n; i++)
    361         rfact[i] = binpow(fact[i], MOD - 2);
    362     dp.resize(n + 1, -1);
    363 }
    364 
    365 int C(int n, int k)
    366 {
    367     if(n < 0 || n < k || k < 0) return 0;
    368     return varMul(fact[n], rfact[k], rfact[n - k]);
    369 }
    370 
    371 int calc(int x)
    372 {
    373     if(dp[x] != -1) return dp[x];
    374     if(x == 1) return dp[x] = 1;
    375     if(x == 2) return dp[x] = 1;
    376     dp[x] = 0;
    377     int& d = dp[x];
    378     for(int i = 1; i < x; i++)
    379     {
    380         d = add(d, varMul(calc(i), (i == x - 1 ? (MOD + 1) / 2 : calc(x - i)), 2, C(x - 1, i - 1)));
    381     }   
    382     return d;
    383 }
    384 
    385 int main()
    386 {
    387     cin >> n;
    388     precalc();
    389     cout << add(mul(calc(n), 2), -2) << endl;
    390 }
    391 ```
    392 
    393 [1792F2 - Graph Coloring (hard version)](/contest/1792/problem/F2 "Educational Codeforces Round 142 (Rated for Div. 2)")
    394 
    395 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    396 
    397 **Tutorial**
    398 
    399 Tutorial is loading...
    400 
    401 **Solution (BledDest)**
    402 
    403 ```
    404 #include<bits/stdc++.h>
    405 
    406 using namespace std;
    407 
    408 const int LOGN = 18;
    409 const int N = (1 << LOGN);
    410 const int MOD = 998244353;
    411 const int g = 3;
    412 
    413 #define forn(i, n) for(int i = 0; i < int(n); i++)
    414 
    415 inline int mul(int a, int b)
    416 {
    417     return (a * 1ll * b) % MOD;
    418 }
    419 
    420 inline int norm(int a) 
    421 {
    422     while(a >= MOD)
    423         a -= MOD;
    424     while(a < 0)
    425         a += MOD;
    426     return a;
    427 }
    428 
    429 inline int binPow(int a, int k) 
    430 {
    431     int ans = 1;
    432     while(k > 0) 
    433     {
    434         if(k & 1)
    435             ans = mul(ans, a);
    436         a = mul(a, a);
    437         k >>= 1;
    438     }
    439     return ans;
    440 }
    441 
    442 inline int inv(int a) 
    443 {
    444     return binPow(a, MOD - 2);
    445 }
    446 
    447 vector<int> w[LOGN];
    448 vector<int> iw[LOGN];
    449 vector<int> rv[LOGN];
    450 
    451 void precalc() 
    452 {
    453     int wb = binPow(g, (MOD - 1) / (1 << LOGN));
    454     
    455     for(int st = 0; st < LOGN; st++) 
    456     {
    457         w[st].assign(1 << st, 1);
    458         iw[st].assign(1 << st, 1);
    459         
    460         int bw = binPow(wb, 1 << (LOGN - st - 1));
    461         int ibw = inv(bw);
    462         
    463         int cw = 1;
    464         int icw = 1;
    465         
    466         for(int k = 0; k < (1 << st); k++) 
    467         {
    468             w[st][k] = cw;
    469             iw[st][k] = icw;
    470             
    471             cw = mul(cw, bw);
    472             icw = mul(icw, ibw);
    473         }
    474         
    475         rv[st].assign(1 << st, 0);
    476         
    477         if(st == 0) 
    478         {
    479             rv[st][0] = 0;
    480             continue;
    481         }
    482         int h = (1 << (st - 1));
    483         for(int k = 0; k < (1 << st); k++)
    484             rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    485     }
    486 }
    487 
    488 inline void fft(int a[N], int n, int ln, bool inverse) 
    489 {   
    490     for(int i = 0; i < n; i++) 
    491     {
    492         int ni = rv[ln][i];
    493         if(i < ni)
    494             swap(a[i], a[ni]);
    495     }
    496     
    497     for(int st = 0; (1 << st) < n; st++) 
    498     {
    499         int len = (1 << st);
    500         for(int k = 0; k < n; k += (len << 1)) 
    501         {
    502             for(int pos = k; pos < k + len; pos++) 
    503             {
    504                 int l = a[pos];
    505                 int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k]));
    506                 
    507                 a[pos] = norm(l + r);
    508                 a[pos + len] = norm(l - r);
    509             }
    510         }
    511     }
    512     
    513     if(inverse) 
    514     {
    515         int in = inv(n);
    516         for(int i = 0; i < n; i++)
    517             a[i] = mul(a[i], in);
    518     }
    519 }
    520 
    521 int aa[N], bb[N], cc[N];
    522 
    523 vector<int> multiply(vector<int> a, vector<int> b) 
    524 {
    525     int sza = a.size();
    526     int szb = b.size();
    527     int n = 1, ln = 0;
    528     while(n < (sza + szb))
    529         n <<= 1, ln++;
    530     for(int i = 0; i < n; i++)
    531         aa[i] = (i < sza ? a[i] : 0);
    532     for(int i = 0; i < n; i++)
    533         bb[i] = (i < szb ? b[i] : 0);
    534         
    535     fft(aa, n, ln, false);
    536     fft(bb, n, ln, false);
    537     
    538     for(int i = 0; i < n; i++)
    539         cc[i] = mul(aa[i], bb[i]);
    540         
    541     fft(cc, n, ln, true);
    542     
    543     int szc = n;
    544     vector<int> c(szc);
    545     szc = n;
    546     for(int i = 0; i < n; i++)
    547         c[i] = cc[i];
    548     return c;
    549 }                    
    550 
    551 int main()
    552 {
    553     int n;
    554     cin >> n;
    555     vector<int> fact(n + 1);
    556     fact[0] = 1;
    557     for(int i = 0; i < n; i++)
    558         fact[i + 1] = mul(fact[i], i + 1);
    559     precalc();
    560     vector<int> A = {0, 1, 2};
    561     vector<int> B = {0, 1, 1};
    562     vector<int> C = {0, 1, 1};
    563     vector<int> D = {0, 1, 1};
    564     vector<int> conv;
    565     const int K = 2000;
    566     int last_conv = -1e9;
    567     while(A.size() <= n)
    568     {
    569         int cur = A.size();
    570         if(cur - last_conv >= K)
    571         {
    572             last_conv = cur - 1;
    573             conv = multiply(C, D);
    574         }
    575         /*for(auto x : conv) cerr << x << " ";
    576         cerr << endl;*/
    577         int val_A;
    578         if(last_conv * 2 >= cur)
    579         {
    580             val_A = conv[cur];
    581             // [cur - last_conv, last_conv] are already used
    582             for(int i = 1; i < (cur - last_conv); i++)
    583             {
    584                 val_A = norm(val_A + mul(C[i], D[cur - i]));
    585             }
    586             for(int i = last_conv + 1; i < cur; i++)
    587             {
    588                 val_A = norm(val_A + mul(C[i], D[cur - i]));
    589             }
    590         }
    591         else
    592         {
    593             val_A = 0;
    594             for(int i = 1; i <= cur - 1; i++)
    595             {
    596                 val_A = norm(val_A + mul(C[i], D[cur - i]));
    597             }
    598         }
    599         val_A = mul(val_A, fact[cur - 1]);
    600         val_A = mul(val_A, 2);
    601         A.push_back(val_A);
    602         B.push_back(mul(val_A, inv(2)));
    603         C.push_back(mul(val_A, inv(fact[cur])));
    604         D.push_back(mul(B.back(), inv(fact[cur - 1])));
    605     }
    606     cout << norm(A[n] - 2) << endl;
    607 }
    608 ```