codeforces-scrape

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

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 ![ ](/predownloaded/fb/d0/fbd0cca70d0eea3dee410609efbd37c522895473.png)
    235 
    236 **Pattern for n=5**
    237 
    238 ![ ](/predownloaded/38/4e/384e43e3518619d3898e56bc9d04d6ba10380219.png)
    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