1968.md (8231B)
1 Source: https://codeforces.com/blog/entry/129096 2 3 We thank everyone who participated in the round. 4 5 [1968A - Maximize?](/contest/1968/problem/A "Codeforces Round 943 (Div. 3)") 6 7 Author: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape") 8 9 **Hint 1** 10 11 Try to find the upper bound of $\gcd(x,y)+y$. 12 13 **Hint 2** 14 15 $\gcd(x,y)+y=\gcd(x-y,y)+y$. 16 17 **Hint 3** 18 19 $\gcd(x,y)+y\le x$. Try to find such $y$, that $\gcd(x,y)+y=x$? 20 21 **Solution** 22 23 Tutorial is loading... 24 25 **Implementation** 26 27 ``` 28 #include<iostream> 29 using namespace std; 30 int main(){ 31 int t; 32 cin>>t; 33 while(t--){ 34 int x; 35 cin>>x; 36 cout<<x-1<<"\n"; 37 } 38 } 39 ``` 40 41 **Rate the problem** 42 43 * Didn't solve 44 * Good task 45 * Average task 46 * Bad task 47 48 [1968B - Prefiquence](/contest/1968/problem/B "Codeforces Round 943 (Div. 3)") 49 50 Author: [FBI](/profile/FBI "Expert FBI") 51 52 **Hint 1** 53 54 Try to check for every $k$ if the prefix of $a$ of length $k$ is a subsequence of $b$. 55 56 **Solution** 57 58 Tutorial is loading... 59 60 **Implementation** 61 62 ``` 63 #include<iostream> 64 #include<vector> 65 using namespace std; 66 int main(){ 67 int t; 68 cin>>t; 69 while(t--){ 70 int n,m; 71 cin>>n>>m; 72 vector<char>a(n+1),b(m+1); 73 for(int i=1;i<=n;i++){ 74 cin>>a[i]; 75 } 76 for(int i=1;i<=m;i++){ 77 cin>>b[i]; 78 } 79 vector<int>dp(m+1); 80 dp[1]=(a[1]==b[1]?1:0); 81 for(int i=2;i<=m;i++){ 82 if(dp[i-1]!=n && b[i]==a[dp[i-1]+1]){ 83 dp[i]=dp[i-1]+1; 84 }else{ 85 dp[i]=dp[i-1]; 86 } 87 } 88 cout<<dp[m]<<"\n"; 89 } 90 } 91 ``` 92 93 **Rate the problem** 94 95 * Didn't solve 96 * Good task 97 * Average task 98 * Bad task 99 100 [1968C - Assembly via Remainders](/contest/1968/problem/C "Codeforces Round 943 (Div. 3)") 101 102 Author: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape") 103 104 **Hint 1** 105 106 Why constraints are small? 107 108 **Hint 2** 109 110 Try to think about increacing $a_1,\dots,a_n$. 111 112 **Hint 3** 113 114 $((a + b)\bmod a) = b$ for $0\le b \lt a$. 115 116 **Solution** 117 118 Tutorial is loading... 119 120 **Implementation** 121 122 ``` 123 #include<iostream> 124 using namespace std; 125 int main(){ 126 int t; 127 cin>>t; 128 while(t--){ 129 int n; 130 cin>>n; 131 int S=1000; 132 cout<<S<<" "; 133 for(int i=2;i<=n;i++){ 134 int x; 135 cin>>x; 136 S+=x; 137 cout<<S<<" "; 138 } 139 cout<<"\n"; 140 } 141 } 142 ``` 143 144 **Rate the problem** 145 146 * Didn't solve 147 * Good task 148 * Average task 149 * Bad task 150 151 [1968D - Permutation Game](/contest/1968/problem/D "Codeforces Round 943 (Div. 3)") 152 153 Author: [FBI](/profile/FBI "Expert FBI") 154 155 **Hint 1** 156 157 Consider a cycle of the permutation. 158 159 **Hint 2** 160 161 When it is optimal to stay on the same place till the end of the game? 162 163 **Solution** 164 165 Tutorial is loading... 166 167 **Implementation** 168 169 ``` 170 #include<bits/stdc++.h> 171 using namespace std; 172 long long score(vector<int>&p,vector<int>&a,int s,int k){ 173 int n=p.size(); 174 long long mx=0,cur=0; 175 vector<bool>vis(n); 176 while(!vis[s]&&k>0){ 177 vis[s]=1; 178 mx=max(mx,cur+1ll*k*a[s]); 179 cur+=a[s]; 180 k--; 181 s=p[s]; 182 } 183 return mx; 184 } 185 int main(){ 186 int t; 187 cin>>t; 188 while(t--){ 189 int n,k,s1,s2; 190 cin>>n>>k>>s1>>s2; 191 vector<int>p(n),a(n); 192 for(auto&e:p){ 193 cin>>e; 194 e--; 195 } 196 for(auto&e:a){ 197 cin>>e; 198 } 199 long long A=score(p,a,s1-1,k),B=score(p,a,s2-1,k); 200 cout<<(A>B?"Bodya\n":A<B?"Sasha\n":"Draw\n"); 201 } 202 } 203 ``` 204 205 **Rate the problem** 206 207 * Didn't solve 208 * Good task 209 * Average task 210 * Bad task 211 212 [1968E - Cells Arrangement](/contest/1968/problem/E "Codeforces Round 943 (Div. 3)") 213 214 Author: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape") 215 216 **Hint 1** 217 218 What is the maximal possible size of $\mathcal{H}$? 219 220 **Hint 2** 221 222 Can you always get that size for $n\geq 4$? 223 224 **Hint 3** 225 226 Consider odd and even distances independently. 227 228 **Solution** 229 230 Let us find an interesting pattern for $n\geq 4$. 231 232 **Pattern for n=4** 233 234  235 236 **Pattern for n=5** 237 238  239 240 Can you generalize the pattern? We put $n-2$ cells on the main diagonal. Then put two cells at $(n-1,n)$ and $(n,n)$. 241 242 But why does it work? Interesting fact, that in such way we generate all possible Manhattan distances. Odd distances are generated between cells from the main diagonal and $(n-1,n)$. Even distances are generated between cells from the main diagonal and $(n,n)$. 243 244 **Implementation** 245 246 ``` 247 #include<iostream> 248 using namespace std; 249 int main(){ 250 int t; 251 cin>>t; 252 while(t--){ 253 int n; 254 cin>>n; 255 for(int i=1;i<=n-2;i++){ 256 cout<<i<<' '<<i<<"\n"; 257 } 258 cout<<n-1<<' '<<n<<"\n"<<n<<' '<<n<<"\n"; 259 } 260 } 261 ``` 262 263 **Rate the problem** 264 265 * Didn't solve 266 * Good task 267 * Average task 268 * Bad task 269 270 [1968F - Equal XOR Segments](/contest/1968/problem/F "Codeforces Round 943 (Div. 3)") 271 272 Author: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape") 273 274 **Hint 1** 275 276 Is it useful to divide the segment into more than three segments? 277 278 **Hint 2** 279 280 Use the fact, that $x\oplus x=0$ and $x\oplus x\oplus x=x$. 281 282 **Hint 3** 283 284 When you can divide the segment into $2$ parts? 285 286 **Hint 4** 287 288 When can you divide the segment into $3$ parts? 289 290 **Solution** 291 292 Tutorial is loading... 293 294 **Implementation** 295 296 ``` 297 #include<bits/stdc++.h> 298 using namespace std; 299 const int N=200005; 300 int a[N]; 301 int main(){ 302 int t; 303 cin>>t; 304 while(t--){ 305 int n,q; 306 cin>>n>>q; 307 map<int,vector<int>>id; 308 id[0].push_back(0); 309 for(int i=1;i<=n;i++){ 310 cin>>a[i]; 311 a[i]^=a[i-1]; 312 id[a[i]].push_back(i); 313 } 314 while(q--){ 315 int l,r; 316 cin>>l>>r; 317 if(a[r]==a[l-1]){ 318 cout<<"YES\n"; 319 continue; 320 } 321 int pL=*--lower_bound(id[a[l-1]].begin(),id[a[l-1]].end(),r); 322 int pR=*lower_bound(id[a[r]].begin(),id[a[r]].end(),l); 323 cout<<(pL>pR?"YES\n":"NO\n"); 324 } 325 if(t)cout << "\n"; 326 } 327 } 328 ``` 329 330 **Rate the problem** 331 332 * Didn't solve 333 * Good task 334 * Average task 335 * Bad task 336 337 [1968G1 - Division + LCP (easy version)](/contest/1968/problem/G1 "Codeforces Round 943 (Div. 3)") 338 339 Author: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape") 340 341 **Hint 1** 342 343 Binary search. 344 345 **Hint 2** 346 347 How to check if two strings are equal? 348 349 **Solution** 350 351 Tutorial is loading... 352 353 **Implementation** 354 355 ``` 356 #include<bits/stdc++.h> 357 using namespace std; 358 vector<int>Zfunc(string& str){ 359 int n=str.size(); 360 vector<int>z(n); 361 int l=0,r=0; 362 for(int i=1;i<n;i++){ 363 if(i<=r){ 364 z[i]=min(r-i+1,z[i-l]); 365 } 366 while(i+z[i]<n&&str[z[i]]==str[i+z[i]]){ 367 z[i]++; 368 } 369 if(i+z[i]-1>r){ 370 l=i; 371 r=i+z[i]-1; 372 } 373 } 374 return z; 375 } 376 int f(vector<int>&z,int len){ 377 int n=z.size(); 378 int cnt=1; 379 for(int i=len;i<n;){ 380 if(z[i]>=len){ 381 cnt++; 382 i+=len; 383 }else{ 384 i++; 385 } 386 } 387 return cnt; 388 } 389 int main(){ 390 int t; 391 cin>>t; 392 while(t--){ 393 int n,k; 394 string s; 395 cin>>n>>k>>k>>s; 396 vector<int>z=Zfunc(s); 397 int l=0,r=n+1; 398 while(r-l>1){ 399 int mid=(l+r)/2; 400 if(f(z,mid)>=k){ 401 l=mid; 402 }else{ 403 r=mid; 404 } 405 } 406 cout<<l<<"\n"; 407 } 408 } 409 ``` 410 411 **Rate the problem** 412 413 * Didn't solve 414 * Good task 415 * Average task 416 * Bad task 417 418 [1968G2 - Division + LCP (hard version)](/contest/1968/problem/G2 "Codeforces Round 943 (Div. 3)") 419 420 Author: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape") 421 422 **Hint 1** 423 424 Consider the general case: $L=1$ and $R=n$. 425 426 **Hint 2** 427 428 You must find the answer for each $k$ in the range $[1,n]$. Consider the cases $k\le \sqrt{n}$ and $k\geq \sqrt{n}$. 429 430 **Solution** 431 432 Tutorial is loading... 433 434 **Implementation** 435 436 ``` 437 #include<bits/stdc++.h> 438 using namespace std; 439 vector<int>Zfunc(string& str){ 440 int n=str.size(); 441 vector<int>z(n); 442 int l=0,r=0; 443 for(int i=1;i<n;i++){ 444 if(i<=r){ 445 z[i]=min(r-i+1,z[i-l]); 446 } 447 while(i+z[i]<n&&str[z[i]]==str[i+z[i]]){ 448 z[i]++; 449 } 450 if(i+z[i]-1>r){ 451 l=i; 452 r=i+z[i]-1; 453 } 454 } 455 return z; 456 } 457 int f(vector<int>&z,int len){ 458 int n=z.size(); 459 int cnt=1; 460 for(int i=len;i<n;){ 461 if(z[i]>=len){ 462 cnt++; 463 i+=len; 464 }else{ 465 i++; 466 } 467 } 468 return cnt; 469 } 470 int main(){ 471 int t; 472 cin>>t; 473 while(t--){ 474 int n,L,R; 475 string s; 476 cin>>n>>L>>R>>s; 477 vector<int>z=Zfunc(s); 478 const int E=ceil(sqrt(n)); 479 vector<int>ans(n+1); 480 for(int k=1;k<=E;k++){ 481 int l=0,r=n+1; 482 while(r-l>1){ 483 int mid=(l+r)/2; 484 if(f(z,mid)>=k){ 485 l=mid; 486 }else{ 487 r=mid; 488 } 489 } 490 ans[k]=l; 491 } 492 for(int len=1;len<=E;len++){ 493 int k=1; 494 for(int i=len;i<n;){ 495 if(z[i]>=len){ 496 k++; 497 i+=len; 498 }else{ 499 i++; 500 } 501 } 502 ans[k]=max(ans[k],len); 503 } 504 for(int i=n-1;i>=1;i--){ 505 ans[i]=max(ans[i],ans[i+1]); 506 } 507 for(int i=L;i<=R;i++){ 508 cout<<ans[i]<<' '; 509 } 510 cout<<"\n"; 511 } 512 } 513 ``` 514 515 **Rate the problem** 516 517 * Didn't solve 518 * Good task 519 * Average task 520 * Bad task