codeforces-scrape

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

1878.md (14676B)


      1 Source: https://codeforces.com/blog/entry/120813
      2 
      3 Thank you for participating in the first ever Serbian Div. 3 Codeforces round!
      4 
      5 **Sorry**
      6 
      7 Before the editorial, we are sorry for the big gap between problems C and D.
      8 
      9 This was the first round we ever created (except for [wxhtzdy](/profile/wxhtzdy "Master wxhtzdy")).
     10 
     11 We are striving to become better problem-setters and create more balanced problems-sets in the future.
     12 
     13 Also a massive thanks to [Vladosiya](/profile/Vladosiya "Expert Vladosiya") for giving us a chance to create a divison 3 round!
     14 
     15 [1878A - How Much Does Daytona Cost?](/contest/1878/problem/A "Codeforces Round 900 (Div. 3)")
     16 
     17 **Problem was authored and prepared by**
     18 
     19 Author: [wxhtzdy](/profile/wxhtzdy "Master wxhtzdy")
     20 
     21 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AndrewPav](/profile/AndrewPav "Specialist AndrewPav"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06")
     22 
     23 **Hints**
     24 
     25 **Hint 1**
     26 
     27 When is the answer definitely "NO"?
     28 
     29 **Hint 2**
     30 
     31 What happens if there is no element equal to $k$ in the array?
     32 
     33 **Hint 3**
     34 
     35 What happens if there is an element equal to $k$ in the array?
     36 
     37 **Tutorial**
     38 
     39 Tutorial is loading...
     40 
     41 **Solution**
     42 
     43 ```
     44 #include <bits/stdc++.h>
     45 
     46 using namespace std;
     47 
     48 int main(){
     49 	int t; //read the number of test cases
     50 	cin >> t;
     51 	while(t--){
     52 		int n, k;
     53 		cin >> n >> k; //read n and k
     54 		bool ys=0; //bool value if true then there exists a subsegment which satisfies the condition, else it doesn't exist
     55 		for(int i=0; i< n; i++){
     56 			int a; //read the i-th element of the array
     57 			cin >> a;
     58 			if(a==k)ys=1; //if the element is equal to k, then the subsegment [i, i] has the most common element equal to k
     59 		}
     60 		if(ys)cout << "YES\n"; //output the answer
     61 		else cout << "NO\n";
     62 	}
     63 }
     64 ```
     65 
     66 [1878B - Aleksa and Stack](/contest/1878/problem/B "Codeforces Round 900 (Div. 3)")
     67 
     68 **Problem was authored and prepared by**
     69 
     70 Author: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic")
     71 
     72 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06")
     73 
     74 **Hints**
     75 
     76 **Hint 1**
     77 
     78 Watch parity.
     79 
     80 **Hint 2**
     81 
     82 What does the parity of $3 \cdot x$ depend on?
     83 
     84 **Hint 3**
     85 
     86 What parity are numbers which divide odd numbers?
     87 
     88 **Tutorial**
     89 
     90 Tutorial is loading...
     91 
     92 **Solution**
     93 
     94 ```
     95 #include <bits/stdc++.h>
     96 
     97 using namespace std;
     98 
     99 int main(){
    100 	int t; //read the number of test cases
    101 	cin >> t;
    102 	while(t--){
    103 		int n; //read n
    104 		cin >> n;
    105 		for(int i=0; i< n; i++)cout << i*2+1 << " "; //write the first n odd numbers in order
    106 		cout << '\n';
    107 	}
    108 }
    109 ```
    110 
    111 [1878C - Vasilije in Cacak](/contest/1878/problem/C "Codeforces Round 900 (Div. 3)")
    112 
    113 **Problem was authored and prepared by**
    114 
    115 Author: [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06")
    116 
    117 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06")
    118 
    119 **Hints**
    120 
    121 **Hint 1**
    122 
    123 Prove that the answer for the second test case is "NO".
    124 
    125 **Hint 2**
    126 
    127 $ 1 + 2 + 3 \gt 5$
    128 
    129 **Hint 3**
    130 
    131 Determine the minimum and maximum sum achievable.
    132 
    133 **Hint 4**
    134 
    135 Prove that it's possible to construct the desired sequence for any requested sum between the minimum and maximum possible sum.
    136 
    137 **Tutorial**
    138 
    139 Tutorial is loading...
    140 
    141 **Solution**
    142 
    143 ```
    144 #include <iostream>
    145 
    146 using namespace std;
    147 
    148 int main(){
    149 	int t; //read the number of test cases
    150 	cin >> t;
    151 	while(t--){
    152 		long long n, x, k; //read n, x, k for each test case
    153 		cin >> n >> x >> k;
    154 		if(2*k>=x*(x+1) && 2*k<=n*(n+1)-(n-x)*(n-x+1)){ //check if k is between the minimum and maximum sum 
    155 			cout << "YES\n";
    156 		}
    157 		else cout << "NO\n";
    158 	}	
    159 }
    160 ```
    161 
    162 [1878D - Reverse Madness](/contest/1878/problem/D "Codeforces Round 900 (Div. 3)")
    163 
    164 **Problem was authored and prepared by**
    165 
    166 Author: [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06")
    167 
    168 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06")
    169 
    170 **Hints**
    171 
    172 **Hint 1**
    173 
    174 For each $i$, ($1 \le i \le k$), we can treat the substring $[l_i, r_i]$ as a seperate test case.
    175 
    176 **Hint 2**
    177 
    178 What happens when we make the same modification twice?
    179 
    180 **Hint 3**
    181 
    182 Does the order of the operations matter?
    183 
    184 **Hint 4**
    185 
    186 Try pre-processing the queries
    187 
    188 **Tutorial**
    189 
    190 Tutorial is loading...
    191 
    192 **Solution**
    193 
    194 ```
    195 #include <bits/stdc++.h>
    196  
    197 using namespace std;
    198  
    199 int main(){
    200 	int t; //number of test cases
    201 	cin >> t;
    202 	while(t--){
    203 		int n, k; //read the input
    204 		cin >> n >> k;
    205 		string s;
    206 		cin >> s;
    207 		int a[k]; int b[k];
    208 		for(int i=0; i< k; i++){cin >> a[i]; a[i]--;}
    209 		for(int i=0; i< k; i++){cin >> b[i]; b[i]--;}
    210 		int q;
    211 		cin >> q;
    212 		int cnt[n+1]={0}; //read and preprocess queries
    213 		for(int i=0; i< q; i++){
    214 			int x; cin >> x; cnt[x-1]++;
    215 		}
    216 		string ans="";
    217 		for(int i=0; i<k; i++){ //treat each interval as a seperate test case
    218 			string s1=s.substr(a[i], b[i]-a[i]+1);
    219 			int sum=0;
    220 			int l=a[i];
    221 			int r=b[i];
    222 			for(int j=l; j<=(l+r)/2; j++){
    223 				sum+=cnt[j]+cnt[r-j+l];
    224 				if(sum&1)swap(s1[j-l], s1[r-j]);
    225 			}
    226 			ans+=s1;
    227 		}
    228 		cout << ans << '\n';
    229 	}
    230 }
    231 ```
    232 
    233 [1878E - Iva & Pav](/contest/1878/problem/E "Codeforces Round 900 (Div. 3)")
    234 
    235 **Problem was authored and prepared by**
    236 
    237 Author: [AndrewPav](/profile/AndrewPav "Specialist AndrewPav"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06")
    238 
    239 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AndrewPav](/profile/AndrewPav "Specialist AndrewPav"), [OAleksa](/profile/OAleksa "Specialist OAleksa"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06")
    240 
    241 **Hints**
    242 
    243 **Hint 1**
    244 
    245 Try calculating $f(l, r)$ bit by bit
    246 
    247 **Hint 2**
    248 
    249 Which condition has to hold true for all elements on a subsegment $[l,r]$, and for a certain bit, for that bit to be present in $f(l,r)$?
    250 
    251 **Hint 3**
    252 
    253 How can we check if that condition is true for a certain bit fast?
    254 
    255 **Hint 4**
    256 
    257 Try prefix sums.
    258 
    259 **Hint 5**
    260 
    261 Try binary search.
    262 
    263 **Tutorial**
    264 
    265 Tutorial is loading...
    266 
    267 **Solution**
    268 
    269 ```
    270 #include <bits/stdc++.h>
    271 using namespace std;
    272 using ll = long long;
    273  
    274  
    275 const int N =200003;
    276 const int bits=30;
    277 int pref[N][bits];
    278 int a[N];
    279 void Buildprefix(int n){ //Builds the prefix sums for each bit
    280     for(int i=0; i< n; i++){
    281         for(int j=0; j<30; j++){
    282             if(a[i]&(1<<j)){
    283                 pref[i+1][j]=pref[i][j]+1;
    284             }
    285             else{
    286                 pref[i+1][j]=pref[i][j];
    287             }
    288         }
    289     }
    290 }
    291 void solve(){
    292     int n;
    293     cin >> n;
    294     for(int i=0; i< n; i++){
    295         cin >> a[i];
    296     }
    297     Buildprefix(n);
    298     int q;
    299     cin >> q;
    300     while(q--){
    301         int l, k;
    302         cin >> l >> k;
    303         if(a[l-1]<k){
    304             cout << -1 << '\n';
    305             continue;
    306         }
    307         int lo=l;
    308         int hi=n;
    309         int ans=l;
    310         while(lo<=hi){
    311             int s=(lo+hi)/2;
    312             int num=0;
    313             for(int j=0; j< bits; j++){
    314                 if(pref[s][j]-pref[l-1][j]==s-l+1){
    315                     num+=(1<<j);
    316                 }
    317             }
    318             if(num>=k){
    319                 lo=s+1;
    320                 ans=max(ans, s);
    321             }
    322             else hi=s-1;
    323         }
    324         cout << ans << '\n';
    325     }
    326 }
    327  
    328 int main(){
    329     int t = 1;
    330     cin >> t;
    331     while(t--){
    332         solve();
    333     }
    334 }
    335 ```
    336 
    337 [1878F - Vasilije Loves Number Theory](/contest/1878/problem/F "Codeforces Round 900 (Div. 3)")
    338 
    339 **Problem was authored and prepared by**
    340 
    341 Author: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06")
    342 
    343 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06")
    344 
    345 **Hints**
    346 
    347 **Hint 1**
    348 
    349 What does the condition $gcd(a, n) = 1$ allow us to do?
    350 
    351 **Hint 2**
    352 
    353 How does any allowed operation affect $d(a \cdot n)$?
    354 
    355 **Hint 3**
    356 
    357 Try to prove that the answer is "YES" if $d(n)$ divides $n$.
    358 
    359 **Hint 4**
    360 
    361 Try to prove that the answer is "NO" otherwise.
    362 
    363 **Hint 5**
    364 
    365 How can you find and maintain the number of divisors quickly?
    366 
    367 **Hint 6**
    368 
    369 To make the implementation easier, try using the condition $d(n) \le 10^9$.
    370 
    371 **Tutorial**
    372 
    373 Tutorial is loading...
    374 
    375 **Solution**
    376 
    377 ```
    378 #include <bits/stdc++.h>
    379 
    380 using ll = long long;
    381 using namespace std;
    382 
    383 const int N = 1000003;
    384 map<int, int> powers; //key is a prime number, value is te highest powert
    385 map<int, int> original_divisors; //same as map powers but isn't updated during queries, it's used to reset the powers
    386 int smallest_divisor[N]; //precalculated smallest divisors to make factorization O(logx) 
    387 bool mark[N]; //marks numbers which aren't prime (used for sieve)
    388 ll divisor_count = 1; //the number of divisors (updated during queries)
    389 
    390 void prime(){ //calculates the smallers divisor for each number from 1 to N (sieve of erathosetenes)
    391 	smallest_divisor[1]=1;
    392 	smallest_divisor[2]=2;
    393 	for(int i=4; i<N; i+=2){
    394 		mark[i]=true;
    395 		smallest_divisor[i]=2;
    396 	}	
    397 	for(int i=3; i<N; i+=2){
    398 		if(!mark[i]){
    399 			smallest_divisor[i]=i;
    400 			for(ll j = i*1ll*i; j<N; j+=2*i){
    401 				if(!mark[j]){
    402 					smallest_divisor[j]=i;
    403 					mark[j]=1;
    404 				}
    405 			}
    406 		}
    407 	}
    408 }
    409 //a function for factorizing a number (used to process queries and factorize n in the beginning)
    410 //it also updates the highest prime which divides n (powers map), and the number of divisors of n (divisor_count)
    411 void factorize(int x){ 
    412 	int p=0;
    413 	int current_divisor = 1;
    414 	while(x>1){ //while x has non 1 divisors, divide it by it's smallest divisor which isn't 1(smallers divisor if always prime)
    415 		if(smallest_divisor[x]!=current_divisor){
    416 			if(p>0){
    417 				divisor_count/=powers[current_divisor]+1;
    418 				powers[current_divisor]+=p;
    419 				divisor_count*=powers[current_divisor]+1;
    420 			}
    421 			p=1;
    422 			current_divisor=smallest_divisor[x];
    423 		}
    424 		else{
    425 			p++;
    426 		}
    427 		x/=smallest_divisor[x];
    428 	}
    429 	if(p>0){
    430 		divisor_count/=powers[current_divisor]+1;
    431 		powers[current_divisor]+=p;
    432 		divisor_count*=powers[current_divisor]+1;
    433 	}
    434 	return;
    435 }
    436 
    437 int main(){
    438 	prime(); //precalculate smallest divisors
    439 	int t;
    440 	cin >> t;
    441 	while(t--){
    442 	    //read n and q
    443     	int n; int q;
    444     	cin >> n >> q;
    445     	//factorize n
    446     	factorize(n);
    447     	//since factorize updates the powers map, update the origional_divisors map too
    448     	for(auto prime : powers){
    449     		original_divisors[prime.first]=prime.second;
    450     	}
    451     	int original_divisor_count = divisor_count; //since factorize updates the divisor_count we update the original_divisor_count too
    452     	vector<int> queries; //storing previous queries
    453     	//processing queries
    454     	while(q--){
    455     		int query_type;
    456     		cin >> query_type;
    457     		if(query_type==1){ //query of type 1 (multiply n by x)
    458     			int x;
    459     			cin >> x;
    460     			factorize(x); //factorize x, update the powers map, and the number of divisors
    461     			queries.push_back(x); //add x to the list of previous queries
    462     			ll num=n;
    463     			for(int query : queries){ //check if the product of all previous queries and n is divisible by d(n)
    464     				num*=query;
    465     				num%=divisor_count;
    466     			}
    467     			if(num==0){ //if it is the answer is yes else the answer is no
    468     				cout << "YES\n";
    469     			}
    470     			else cout << "NO\n";
    471     		}
    472     		else{ //here we should reset everything related to the type 1 query
    473     			powers.clear(); //clear the powers map and set it to original divisors and powers
    474     			for(auto original_div : original_divisors){
    475     				powers[original_div.first]=original_div.second;
    476     			}
    477     			divisor_count=original_divisor_count; //restart the divisor_count
    478     			queries.clear(); //clear the queries (since we only need the queries since the previous type 2 query)
    479     		}
    480     	}
    481     	original_divisors.clear();
    482     	powers.clear();
    483     	divisor_count=1;
    484     	original_divisor_count =1;
    485     	if(t) cout << "\n";
    486 	}
    487 }
    488 ```
    489 
    490 [1878G - wxhtzdy ORO Tree](/contest/1878/problem/G "Codeforces Round 900 (Div. 3)")
    491 
    492 **Problem was authored and prepared by**
    493 
    494 Author: [wxhtzdy](/profile/wxhtzdy "Master wxhtzdy")
    495 
    496 Prepared by: [ognjentesic](/profile/ognjentesic "Pupil ognjentesic"), [OAleksa](/profile/OAleksa "Specialist OAleksa"), [AlphaMale06](/profile/AlphaMale06 "Expert AlphaMale06")
    497 
    498 **Hints**
    499 
    500 **Hint 1**
    501 
    502 How many vertices actually matter on the path from $x$ to $y$?
    503 
    504 **Hint 2**
    505 
    506 How do we find them?
    507 
    508 **Hint 3**
    509 
    510 Root the tree arbitrarily.
    511 
    512 **Hint 4**
    513 
    514 Try calculating the number of occurrences for each bit on the path from the root to a certain vertex.
    515 
    516 **Hint 5**
    517 
    518 Try binary search.
    519 
    520 **Hint 6**
    521 
    522 Try LCA (Lowest common ancestor).
    523 
    524 **Tutorial**
    525 
    526 Tutorial is loading...
    527 
    528 **Solution**
    529 
    530 ```
    531 #include <bits/stdc++.h>
    532 #define f first
    533 #define s second
    534 using namespace std;
    535 #define int long long
    536 const int maxn = 2e5 + 69;
    537 const int k = 19;
    538 const int bits = 30;
    539 vector<int> g[maxn];
    540 int n, q, a[maxn], up[maxn][k], tin[maxn], tout[maxn], timer, d[maxn];
    541 int r[maxn][k];
    542 int bst[maxn][bits];
    543 void dfs(int v, int p, vector<int> b) {
    544 	tin[v] = ++timer;
    545 	up[v][0] = p;
    546 	r[v][0] = a[p];
    547 	d[v] = d[p] + 1;
    548 	for (int i = 0;i < bits;i++) {
    549 		bst[v][i] = b[i];
    550 		if (a[v] & (1 << i))
    551 			b[i] = v;
    552 	}
    553 	for (int i = 1;i < k;i++) {
    554 		up[v][i] = up[up[v][i - 1]][i - 1];
    555 		r[v][i] = r[v][i - 1] | r[up[v][i - 1]][i - 1];
    556 	}
    557 	for (auto u : g[v]) {
    558 		if (u != p)
    559 			dfs(u, v, b);
    560 	}
    561 	tout[v] = timer;
    562 }
    563 
    564 bool is_anc(int u, int v) {
    565 	return tin[u] <= tin[v] && tout[u] >= tout[v];
    566 }
    567 
    568 int lca(int u, int v) {
    569 	if(is_anc(u, v))
    570 		return u;
    571 	else if(is_anc(v, u))
    572 		return v;
    573 	for (int i = k - 1;i >= 0;i--) {
    574 		if (!is_anc(up[u][i], v) && up[u][i] > 0)
    575 			u = up[u][i];
    576 	}
    577 	return up[u][0];
    578 }
    579 
    580 int OR(int u, int dis) {
    581 	int res = a[u];
    582 	for (int j = 0;j < bits;j++) {
    583 		if (dis & (1 << j)) {
    584 			res |= r[u][j];
    585 			u = up[u][j];
    586 		}
    587 	}
    588 	return res;
    589 }
    590 
    591 int Qry(int u, int v) {
    592 	int lc = lca(u, v);
    593 	return OR(u, d[u] - d[lc]) | OR(v, d[v] - d[lc]);
    594 }
    595 
    596 signed main()
    597 {
    598 	int tt = 1;
    599 	cin >> tt;
    600 	while(tt--) {
    601 		cin >> n;
    602 		timer = 0;
    603 		for (int i = 1;i <= n;i++)
    604             g[i].clear();
    605 		for (int i = 1;i <= n;i++)
    606 			cin >> a[i];
    607 		for (int i = 1;i <= n - 1;i++) {
    608 			int x, y;
    609 			cin >> x >> y;
    610 			g[x].push_back(y);
    611 			g[y].push_back(x);
    612 		}
    613 		vector<int> temp(30, -1);
    614 		dfs(1, 0, temp);
    615 		cin >> q;
    616 		for (int i = 1;i <= q;i++) {
    617 			int x, y;
    618 			cin >> x >> y;
    619 			int LCA = lca(x, y);
    620 			vector<int> t;
    621 			t.push_back(x);
    622 			t.push_back(y);
    623 			for (int i = 0;i < bits;i++) {
    624 				if (bst[x][i] != -1 && is_anc(LCA, bst[x][i]))
    625 					t.push_back(bst[x][i]);
    626 				if (bst[y][i] != -1 && is_anc(LCA, bst[y][i]))
    627 					t.push_back(bst[y][i]);
    628 			}
    629 			int ans =  __builtin_popcount(a[x]) + __builtin_popcount(a[y]);
    630 			for (auto p : t) {
    631 				int x1 = a[x], x2 = a[y];
    632 				x1 |= Qry(x, p);
    633 				x2 |= Qry(y, p);
    634 				ans = max(ans, 1ll * __builtin_popcount(x1) + __builtin_popcount(x2));
    635 			}
    636 			cout << ans << " ";
    637 		}
    638 		cout << "\n";
    639 	}
    640    return 0;
    641 }
    642 ```