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: