codeforces-scrape

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

1794.md (7702B)


      1 Source: https://codeforces.com/blog/entry/113500
      2 
      3 Thanks for participating in the round! I hope you enjoyed the problems!
      4 
      5 [1794A - Prefix and Suffix Array](/contest/1794/problem/A "Codeforces Round 856 (Div. 2)")
      6 
      7 **Solution**
      8 
      9 Tutorial is loading...
     10 
     11 **Code**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 using namespace std;
     16  
     17 int main(){
     18 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     19 	int t; cin >> t;
     20 	for(int test_number = 0; test_number < t; test_number++){
     21 		int n; cin >> n;
     22 		vector <string> long_subs;
     23 		for(int i = 0; i < 2 * n - 2; i++){
     24 			string s; 
     25 			cin >> s;
     26 			if((int)s.size() == n - 1){
     27 				long_subs.push_back(s);
     28 			}
     29 		}
     30 		reverse(long_subs[1].begin(), long_subs[1].end());
     31 		if(long_subs[0] == long_subs[1]){
     32 			cout<<"YES\n";
     33 		}else{
     34 			cout<<"NO\n";
     35 		}
     36 	}
     37 	
     38 	return 0;
     39 }
     40 ```
     41 
     42 **Feedback**
     43 
     44 * Amazing problem:
     45 * Good problem:
     46 * Bad problem:
     47 * Didn't solve:
     48 
     49 [1794B - Not Dividing](/contest/1794/problem/B "Codeforces Round 856 (Div. 2)")
     50 
     51 **Solution**
     52 
     53 Tutorial is loading...
     54 
     55 **Code**
     56 
     57 ```
     58 #include <bits/stdc++.h>
     59 using namespace std;
     60  
     61 int main(){
     62 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     63 	int t; cin >> t;
     64 	for(int test_number = 0; test_number < t; test_number++){
     65 		int n; cin >> n;
     66 		vector <int> a(n);
     67 		for(int i = 0; i < n; i++){
     68 			cin >> a[i];
     69 		}
     70 		for(int i = 0; i < n; i++){
     71 			if(a[i] == 1){
     72 				a[i]++;
     73 			}
     74 		}
     75 		for(int i = 1; i < n; i++){
     76 			if(a[i] % a[i - 1] == 0){
     77 				a[i]++;
     78 			}
     79 		}
     80 		for(auto i : a){
     81 			cout << i << " ";
     82 		}
     83 		cout << "\n";
     84 	}
     85 	return 0;
     86 }
     87 ```
     88 
     89 **Additional comment**
     90 
     91 Actually, the maximum number of operations performed by this algorithm is $\frac{3}{2}n$. Try to prove it!
     92 
     93 **Feedback**
     94 
     95 * Amazing problem:
     96 * Good problem:
     97 * Bad problem:
     98 * Didn't solve:
     99 
    100 [1794C - Scoring Subsequences](/contest/1794/problem/C "Codeforces Round 856 (Div. 2)")
    101 
    102 **Solution**
    103 
    104 Tutorial is loading...
    105 
    106 **Code**
    107 
    108 ```
    109 #include <bits/stdc++.h>
    110 using namespace std;
    111  
    112 int main(){
    113 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    114 	int t; cin >> t;
    115 	for(int test_number = 0; test_number < t; test_number++){
    116 		int n; cin >> n;
    117 		vector <int> a(n);
    118 		for(int i = 0; i < n; i++){
    119 			cin >> a[i];
    120 		}
    121 		vector<int> res;
    122 		for(int i = 0; i < n; i++){
    123 			int l = 1, r = i + 1;
    124 			while(l <= r){
    125 				int m = (l + r) / 2;
    126 				if(a[i - m + 1] >= m){
    127 					l = m + 1;
    128 				}else{
    129 					r = m - 1;
    130 				}
    131 			}
    132 			res.push_back(r);
    133 		}
    134 		for(auto i : res){
    135 			cout << i << " ";
    136 		}
    137 		cout<<"\n";
    138 	}
    139 	return 0;
    140 }
    141 ```
    142 
    143 **Feedback**
    144 
    145 * Amazing problem:
    146 * Good problem:
    147 * Bad problem:
    148 * Didn't solve:
    149 
    150 [1794D - Counting Factorizations](/contest/1794/problem/D "Codeforces Round 856 (Div. 2)")
    151 
    152 **Solution**
    153 
    154 Tutorial is loading...
    155 
    156 **Code**
    157 
    158 ```
    159 #include <bits/stdc++.h>
    160 using namespace std;
    161 typedef long long ll;
    162  
    163 const ll MOD = 998244353;
    164  
    165 //checks if n is prime
    166 bool is_prime(ll n){
    167 	if(n == 1){
    168 		return false;
    169 	}
    170 	for(ll i = 2; i * i <= n; i++){
    171 		if(n %i == 0){
    172 			return false;
    173 		}
    174 	}
    175 	return true;
    176 }
    177  
    178 //computes b ** e % MOD
    179 ll fast_pow(ll b, ll e){
    180 	ll res = 1;
    181 	while(e > 0){
    182 		if(e % 2 == 1){
    183 			res = res * b % MOD;
    184 		}
    185 		b = b * b % MOD;
    186 		e /= 2;
    187 	}
    188 	return res;
    189 }
    190  
    191 vector<pair<ll, ll>> primes;
    192  
    193 const int MAXN = 5050;
    194  
    195 ll dp[MAXN][MAXN];
    196  
    197 ll fact[MAXN], fact_inv[MAXN];
    198  
    199 ll f(ll x, ll y){
    200 	ll &res = dp[x][y];
    201 	if(res >= 0){
    202 		return res;
    203 	}
    204 	if(x == (int)primes.size()){
    205 		return res = (y == 0);
    206 	}
    207 	res = fact_inv[primes[x].second] * f(x + 1, y) % MOD;
    208 	if(y > 0){
    209 		res = (res + fact_inv[primes[x].second - 1] * f(x + 1, y - 1)) % MOD;	
    210 	}
    211 	return res;
    212 }
    213  
    214 int main(){
    215 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    216 	//reading the input
    217 	int n; cin >> n;
    218 	vector<ll> a(2 * n);
    219 	for(int i = 0; i < 2 * n; i++){
    220 		cin >> a[i];
    221 	}
    222 	sort(a.begin(), a.end());
    223 	//compressed version of a, pairs {value, #occurrences}
    224 	vector<pair<ll, ll>> a_comp;
    225 	for(int i = 0; i < 2 * n; i++){
    226 		if(a_comp.size() == 0u || a_comp.back().first != a[i]){
    227 			a_comp.push_back({a[i], 1});
    228 		}else{
    229 			a_comp.back().second++;
    230 		}
    231 	}
    232 	//computing factorials and inverses
    233 	fact[0] = 1;
    234 	for(ll i = 1; i < MAXN; i++){
    235 		fact[i] = fact[i-1] * i % MOD;
    236 	}
    237 	fact_inv[0] = 1;
    238 	for(ll i = 0; i < MAXN; i++){
    239 		fact_inv[i] = fast_pow(fact[i], MOD - 2);
    240 	}
    241 	//adding only primes for the dp
    242 	for(auto i : a_comp){
    243 		if(is_prime(i.first)){
    244 			primes.push_back(i);
    245 		}
    246 	}
    247 	memset(dp, -1, sizeof(dp));
    248 	ll res = f(0, n);
    249 	//we have to consider the contribution of non-primes too!
    250 	for(auto i : a_comp){
    251 		if(!is_prime(i.first)){
    252 			res = res * fact_inv[i.second] % MOD;
    253 		}
    254 	}
    255 	res = res * fact[n] % MOD;
    256 	cout << res << "\n";
    257 	return 0;
    258 }
    259 ```
    260 
    261 **Additional comment**
    262 
    263 It is possible to solve the problem with greater constraints, like $n \leq 10^5$. Try to solve it with this new constraint!
    264 
    265 **Feedback**
    266 
    267 * Amazing problem:
    268 * Good problem:
    269 * Bad problem:
    270 * Didn't solve:
    271 
    272 [1794E - Labeling the Tree with Distances](/contest/1794/problem/E "Codeforces Round 856 (Div. 2)")
    273 
    274 **Solution**
    275 
    276 Tutorial is loading...
    277 
    278 **Code**
    279 
    280 ```
    281 #include <bits/stdc++.h>
    282 using namespace std;
    283 typedef long long ll;
    284  
    285 const int MAXN = 200005;
    286 mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
    287  
    288 //Hashing stuff
    289 const ll MOD[3] = {999727999, 1070777777, 1000000007};
    290 ll B[3];
    291  
    292 vector<ll> shift(vector<ll> h, ll val = 0){
    293 	for(int k = 0; k < 3; k++){
    294 		h[k] = (h[k] * B[k] + val) % MOD[k];
    295 	}
    296 	return h;
    297 }
    298  
    299 vector<ll> add(vector<ll> a, vector<ll> b){
    300 	vector<ll> res(3);
    301 	for(int k = 0; k < 3; k++){
    302 		res[k] = (a[k] + b[k]) % MOD[k];
    303 	}
    304 	return res;
    305 }
    306  
    307 vector<ll> sub(vector<ll> a, vector<ll> b){
    308 	vector<ll> res(3);
    309 	for(int k = 0; k < 3; k++){
    310 		res[k] = (a[k] - b[k] + MOD[k]) % MOD[k];
    311 	}
    312 	return res;
    313 }
    314  
    315 //Tree stuff
    316 vector<int> g[MAXN];
    317  
    318 bool vis[MAXN];
    319 int parent[MAXN];
    320 vector<ll> dp[MAXN], dp2[MAXN];
    321  
    322 void dfs(int x){
    323 	vis[x] = true;
    324 	for(auto i : g[x]){
    325 		if(!vis[i]){
    326 			parent[i] = x;
    327 			dfs(i);
    328 			dp[x] = add(dp[x], shift(dp[i]));
    329 		}
    330 	}
    331 	dp[x] = add(dp[x], {1, 1, 1});
    332 }
    333  
    334 void dfs2(int x){
    335 	if(x != 0){
    336 		dp2[x] = sub(dp[parent[x]], shift(dp[x]));
    337 		dp2[x] = add(dp2[x], shift(dp2[parent[x]]));
    338 	}
    339 	for(auto i : g[x]){
    340 		if(i != parent[x]){
    341 			dfs2(i);
    342 		}
    343 	}
    344 }
    345  
    346 int main(){
    347 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    348 	for(int k = 0; k < 3; k++){
    349 		B[k] = rng() % MOD[k];
    350 	}
    351 	//reading the input
    352 	int n; cin >> n;
    353 	vector<int> occurrences(n);
    354 	for(int i = 0; i < n - 1; i++){
    355 		int a; cin >> a;
    356 		occurrences[a]++;
    357 	}
    358 	for(int i = 0; i < n - 1; i++){
    359 		int u, v; cin >> u >> v;
    360 		u--; v--;
    361 		g[u].push_back(v);
    362 		g[v].push_back(u);
    363 	}
    364 	//calculating possible list hashes
    365 	vector<vector<ll>> list_hashes;
    366 	vector<ll> h = {0, 0, 0};
    367 	for(int i = n - 1; i >= 0; i--){
    368 		h = shift(h, occurrences[i]);
    369 	}
    370 	vector<ll> extra = {1, 1, 1};
    371 	for(int i = 0; i < n; i++){
    372 		list_hashes.push_back(add(h, extra));
    373 		extra = shift(extra);
    374 	}
    375 	//calculating possible tree hashes
    376 	for(int i = 0; i < n; i++){
    377 		dp[i] = {0, 0, 0};
    378 		dp2[i] = {0, 0, 0};
    379 	}
    380 	parent[0] = -1;
    381 	dfs(0);
    382 	dfs2(0);
    383 	vector<pair<vector<ll>, int>> tree_hashes;
    384 	for(int i = 0; i < n; i++){
    385 		if(i == 0){
    386 			tree_hashes.push_back({dp[i], i});
    387 		}else{
    388 			tree_hashes.push_back({add(dp[i], shift(dp2[i])), i});
    389 		}
    390 	}
    391 	//calculting the answer
    392 	sort(list_hashes.begin(), list_hashes.end());
    393 	sort(tree_hashes.begin(), tree_hashes.end());
    394 	vector<int> res;
    395 	int pos = 0;
    396 	for(auto lh : list_hashes){
    397 		while(pos < n && tree_hashes[pos].first < lh){
    398 			pos++;
    399 		}
    400 		while(pos < n && tree_hashes[pos].first == lh){
    401 			res.push_back(tree_hashes[pos].second);
    402 			pos++;
    403 		}
    404 	}
    405 	sort(res.begin(), res.end());
    406 	cout << res.size() << "\n";
    407 	for(auto i : res){
    408 		cout << i + 1 << " ";
    409 	}
    410 	cout << "\n";
    411 	return 0;
    412 }
    413 ```
    414 
    415 **Feedback**
    416 
    417 * Amazing problem:
    418 * Good problem:
    419 * Bad problem:
    420 * Didn't solve: