codeforces-scrape

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

2173.md (15129B)


      1 Source: https://codeforces.com/blog/entry/148981
      2 
      3 [2173A-Sleeping Through Classes](https://codeforces.com/contest/2173/problem/A) Idea & Solution: [HHH666666](/profile/HHH666666 "Grandmaster HHH666666")
      4 
      5 **Tutorial**
      6 
      7 From the statement we can conclude that a class can be slept through $\textbf{if and only if}$:
      8 
      9 1. The class itself is not an important class.
     10 2. The class is not within $k$ classes after any important class.
     11 
     12 Here's an $O(nk)$ approach:
     13 
     14 We directly simulate the process: for each important class at position $i$, mark positions $i+1, i+2, \dots, \min(i+k, n)$ as “must stay awake”. After processing all important classes, count the classes that are neither important nor marked. This $O(nk)$ solution is acceptable under the constraints.
     15 
     16 There's also an $O(n)$ solution:
     17 
     18 For each unimportant class, we only need to focus on the nearest important class before it. Thus we maintain a variable $last$ storing the index of the most recent important class (or $-\infty$ if none seen yet), then for each $i$ from $1$ to $n$, if it's an important class we let $last = i$, otherwise if $last + k \lt i$, the class is able to be slept through and we add $1$ to the answer.
     19 
     20 **Solution**
     21 
     22 ```
     23 #include<bits/stdc++.h>
     24 using namespace std;
     25 int n,k;string s;
     26 void solve(){
     27 	cin>>n>>k>>s;
     28 	int ans=0;
     29 	for(int i=0;i<n;i++){
     30 		if(s[i]=='0'){
     31 			int ok=1;
     32 			for(int j=max(0,(int)i-k);j<i;j++){
     33 				if(s[j]=='1'){
     34 					ok=0;
     35 					break;
     36 				}
     37 			}
     38 			ans+=ok;
     39 		}
     40 	}
     41 	cout<<ans<<endl;
     42 }
     43 int main(){
     44 	ios_base::sync_with_stdio(false);
     45 	cin.tie(0),cout.tie(0);
     46 	int T;cin>>T;
     47 	for(;T--;)solve();
     48 	return 0;
     49 }
     50 ```
     51 
     52 [2173B-Niko's Tactical Cards](https://codeforces.com/contest/2173/problem/B) Idea & Solution: [HHH666666](/profile/HHH666666 "Grandmaster HHH666666")
     53 
     54 **Hint 1**
     55 
     56 Consider a simple greedy algorithm: For each turn, choose the option that gives the higher immediate score. That is, if our current score is $k$, it becomes $\max(k - a_i, b_i - k)$ after this turn. Why doesn't the algorithm work?
     57 
     58 **Hint 2**
     59 
     60 Try to improve the algorithm in Hint 1.
     61 
     62 **Tutorial**
     63 
     64 The greedy approach in Hint 1 fails because it assumes that if we know the maximum possible score after turn $i$ (denoted by $max_i$), we can determine $max_{i + 1}$ from it. However, this assumption is wrong and here is a counterexample:
     65 
     66 $a = [2, 0], b = [1, 0]$
     67 
     68 Here $max_1 = 1$ and $max_2 = 2$. The greedy approach takes the blue card in turn $1$. But to reach $max_2$, we must choose the red card in turn $1$, which turns our score into $-2$, and then choose the blue card in turn $2$. So in this example, $max_1$ does not give $max_2$.
     69 
     70 We see that $max_1$ does not help us find $max_2$ if we choose the blue card in the second turn. The reason is, if we want to maximize our score when choosing a blue card, we want our current score to be as **small** as possible, so we are looking for the minimum possible score. To maximize $b_i - k$ we should minimize $k$.
     71 
     72 From this we can see that if we have both the maximum possible score $max_{i - 1}$ and the minimum possible score $min_{i - 1}$ after turn $i - 1$, we can determine $max_{i} = \max(max_{i - 1} - a_i, b_i - min_{i - 1})$, because these two expressions cover the best outcomes from the red and blue options respectively. Similarly, the new minimum $min_{i} = \min(min_{i - 1} - a_i, b_i - max_{i - 1})$ comes from either taking the red card from the previous minimum, or the blue card from the previous maximum. And from $max_{i}, min_{i}$ we can move forward to $max_{i + 1}, min_{i + 1}$ and so on.
     73 
     74 Thus, we start with $max_0 = min_0 = 0$ and calculate each $max_i, min_i$ throughout the process using the formulas above. The answer is $max_n$. This runs in $O(n)$ time complexity.
     75 
     76 **Solution**
     77 
     78 ```
     79 #include<bits/stdc++.h>
     80 #define ll long long
     81 
     82 using namespace std;
     83 
     84 const int MAXN = 1e5 + 10;
     85 
     86 int n;
     87 int a[MAXN], b[MAXN];
     88 
     89 int main() {
     90     int t; cin >> t;
     91     while (t--) {
     92         int n; cin >> n;
     93         for (int i = 1; i <= n; ++i) cin >> a[i];
     94         for (int i = 1; i <= n; ++i) cin >> b[i];
     95         ll mx = 0, mn = 0;
     96         for (int i = 1; i <= n; ++i) {
     97             ll new_mx = max(mx - a[i], b[i] - mn);
     98             ll new_mn = min(mn - a[i], b[i] - mx);
     99             mx = new_mx, mn = new_mn;
    100         }
    101         cout << mx << endl;
    102     }
    103     return 0;
    104 }
    105 ```
    106 
    107 [2173C-Kanade's Perfect Multiples](https://codeforces.com/contest/2173/problem/C) Idea & Solution: [paulzrm](/profile/paulzrm "Grandmaster paulzrm")
    108 
    109 **Hint 1**
    110 
    111 Consider the cases $n = 1$ and $n = 2$. What do you observe?
    112 
    113 **Hint 2**
    114 
    115 Try to determine the "first" element that must belong to $B$.
    116 
    117 **Tutorial**
    118 
    119 Assume the minimum element in $A$ is $x$. We now prove that $x$ must be included in $B$.
    120 
    121 There are no elements smaller than $x$, which means $x$ has no proper divisor (other than $x$ itself) inside $A$. If we do **not** put $x$ into $B$, then the second rule would be violated.
    122 
    123 Thus we can determine the first element of $B$, and then check whether all its multiples $\le k$ are contained in $A$. We mark these multiples as "finished".
    124 
    125 Now think greedily. We never need to process elements that are already marked "finished". Each time, we just find the smallest unfinished element in $A$, check it, and add it to $B$ if possible.
    126 
    127 A loose upper bound on the running time is $O\bigl(n d(n) \log n\bigr)$, where $d(n)$ is the divisor function. However, this bound is rarely attained in practice: many operations are skipped thanks to the "finished" marks, so the algorithm runs much faster than this worst-case estimate.
    128 
    129 **Solution**
    130 
    131 ```
    132 #include<bits/stdc++.h>
    133 using namespace std;
    134 const int mxn=2e5+5;
    135 set<int>s;
    136 map<int,int>u;
    137 int n,a[mxn],k;
    138 void solve(){
    139 	s.clear(),u.clear();
    140 	cin>>n>>k;
    141 	for(int i=1;i<=n;i++)cin>>a[i],s.insert(a[i]),u[a[i]]=1;
    142 	vector<int>ans;ans.clear();
    143 	while(s.size()){
    144 		int t=*s.begin();
    145 		ans.push_back(t);
    146 		s.erase(s.begin());
    147 		for(int cur=t;cur<=k;cur+=t){
    148 			if(!u[cur]){
    149 				cout<<"-1\n";
    150 				return;
    151 			}
    152 			auto t=s.find(cur);
    153 			if(t!=s.end())s.erase(t);
    154 		}
    155 	}
    156 	cout<<ans.size()<<'\n';
    157 	for(int i:ans)cout<<i<<' ';cout<<'\n';
    158 }
    159 int main(){
    160 	ios_base::sync_with_stdio(false);
    161 	cin.tie(0),cout.tie(0);
    162 	int T=1;
    163 	cin>>T;
    164 	for(;T--;)solve();
    165 	return 0;
    166 }
    167 ```
    168 
    169 [2173D-Taiga's Carry Chains](https://codeforces.com/contest/2173/problem/D) Idea: [chen_zida](/profile/chen_zida "Grandmaster chen_zida") Solution: [paulzrm](/profile/paulzrm "Grandmaster paulzrm")
    170 
    171 **Hint 1**
    172 
    173 What is the answer when $k \geq 32$?
    174 
    175 **Hint 2**
    176 
    177 We can use dynamic programming to solve it.
    178 
    179 **Tutorial**
    180 
    181 When $k \geq 32$, we can, at each step, add the smallest $t$ such that adding $2^{t}$ to the current $n$ produces a carry. After $k$ such steps, $n$ will become a power of $2$, and the answer will be $\operatorname{popcount}(n) + k - 1$.
    182 
    183 Now we observe that the total number of carries in the end is $\operatorname{popcount}(n) + k - \operatorname{popcount}(n')$, where $n'$ is the final value of $n$ after all operations. To maximize this quantity, we want to minimize the final $\operatorname{popcount}(n')$.
    184 
    185 To this end, let $dp[i][j][c]$ denote the optimal value we can obtain after processing the $i$ least significant bits, having used $j$ operations in total, where $c \in {0,1}$ indicates whether there is a carry from the $(i-1)$-th bit.
    186 
    187 For the $i$-th least significant bit, we have two options: either select this bit (i.e., use one operation on this bit) or not select it.
    188 
    189 Let $n_i$ be the $i$-th bit of the original $n$, and let $t_i$ be the sum at this bit after adding everything in. If we select this bit, then $t_i = 1 + c + n_i$; otherwise, $t_i = c + n_i$. From $t_i$, we can determine whether this bit produces a carry to the next position (the next carry is $c' = \lfloor t_i / 2 \rfloor$) and whether the $i$-th bit of $n'$ is $1$ or $0$ (the resulting bit is $t_i \bmod 2$), which allows us to perform the DP transition.
    190 
    191 The time complexity is $O((\log_2 n)^2)$.
    192 
    193 **Solution**
    194 
    195 ```
    196 #include<bits/stdc++.h>
    197 #define int long long
    198 using namespace std;
    199 const int inf=1e9+7;
    200 const int mxb=64,mxk=32;
    201 int dp[mxb+2][mxk+2][2];
    202 void Min(int&x,int y){x=min(x,y);}
    203 void solve(){
    204 	int n,k;cin>>n>>k;
    205 	int pc=__builtin_popcount(n);
    206 	if(n==0){
    207 		cout<<max(0ll,k-1)<<'\n';
    208 		return;
    209 	}
    210 	if(k>=32){
    211 		cout<<k+pc-1<<'\n';
    212 		return;
    213 	}
    214 	for(int i=0;i<=mxb;i++)for(int j=0;j<=k;j++)dp[i][j][0]=dp[i][j][1]=inf;
    215 	dp[0][0][0]=0;
    216 	for(int i=0;i<mxb;i++){
    217 		int ni=(n>>i)&1ll;
    218 		for(int u=0;u<=k;u++)for(int c=0;c<=1;c++){
    219 			int cur=dp[i][u][c];
    220 			if(cur>=inf)continue;
    221 			{
    222 				int sum=ni+c,bit=sum&1,nc=sum>>1;
    223 				Min(dp[i+1][u][nc],cur+bit);		
    224 			}
    225 			if(u+1<=k){
    226 				int sum=ni+1+c,bit=sum&1,nc=sum>>1;
    227 				Min(dp[i+1][u+1][nc],cur+bit);
    228 			}
    229 		}
    230 	}
    231 	int bst=inf;
    232 	for(int u=0;u<=k;u++)for(int c=0;c<=1;c++){
    233 		int val=dp[mxb][u][c];
    234 		if(val<inf)Min(bst,val+c);
    235 	}
    236 	int ans=k+pc-bst;
    237 	cout<<ans<<'\n';
    238 }
    239 signed main(){
    240 	ios_base::sync_with_stdio(false);
    241 	cin.tie(0),cout.tie(0);
    242 	int T;cin>>T;
    243 	for(;T--;)solve();
    244 	return 0;
    245 }
    246 ```
    247 
    248 [2173E-Shiro's Mirror Duel](https://codeforces.com/contest/2173/problem/E) Idea & Solution: [paulzrm](/profile/paulzrm "Grandmaster paulzrm") It's my favourite problem :-)
    249 
    250 **Hint 1**
    251 
    252 $\lfloor 2.5n\rfloor$ is the expected number of operations. We add $800$ more to ensure that every correct solution would pass.
    253 
    254 **Hint 2**
    255 
    256 Think about how to solve it within $3n$, and how can we improve that.
    257 
    258 **Tutorial**
    259 
    260 We split the process into two phases. In the first phase, we make every pair $x$ and $n - x + 1$ symmetric; in the second phase, we turn the permutation into $1, 2, \dots, n$.
    261 
    262 Let $pos[x]$ be the current position of $x$. We iterate $x$ from $1$ to $n$ in increasing order. If $pos[x] + pos[n + 1 - x] \neq n + 1$, then $x$ and $n + 1 - x$ are not symmetric. In this case, we query $(pos[x],\, n - pos[n + 1 - x] + 1)$. No matter whether the interactive judge mirrors the array and then swaps or not, this operation will always make $x$ and $n + 1 - x$ symmetric. When $n$ is odd, we should first move $(n+1)/2$ to the middle.
    263 
    264 Next, we move these groups to their correct target positions in order. Suppose the target positions of a pair are $i$ and $n - i + 1$, while it is currently at $j$ and $n - j + 1$. We query $(i, j)$; this will surely place either the pair itself or its mirror into the correct positions.
    265 
    266 Now we compute the expectation. Let $T$ be the expected number of queries spent in this second phase for a single group. After we query once, with probability $1/2$ the group is already correctly placed and we are done after $1$ query; with probability $1/2$ it is mirrored into another group’s target positions, in which case we have spent $1$ query and still expect $T$ more. Thus $T = 1 + \frac{1}{2} \cdot 1 + \frac{1}{2}(T + 1)$, which solves to $T = 4$.
    267 
    268 There are $n/2$ groups, so this phase needs $2n$ queries in expectation. The first phase uses exactly $n/2$ queries (one per group), so the total expected number of queries is $5n/2$.
    269 
    270 **Solution**
    271 
    272 ```
    273 #include<bits/stdc++.h>
    274 using namespace std;
    275 const int mxn=40004;
    276 int n,a[mxn],pos[mxn];
    277 int mirror(int x){
    278 	return n-x+1;
    279 }
    280 pair<int,int>ask(int x,int y){
    281 	cout<<"? "<<x<<' '<<y<<endl;
    282 	fflush(stdout);
    283 	int u,v;cin>>u>>v;
    284 	return {u,v};
    285 }
    286 void solve(){
    287 	cin>>n;
    288 	for(int i=1;i<=n;i++){
    289 		cin>>a[i];
    290 		pos[a[i]]=i;
    291 	}
    292 	if(n%2==1){
    293 		int mid=(n+1)/2;
    294 		while(pos[mid]!=mid){
    295 			auto p=ask(mid,pos[mid]);
    296 			int u=p.first,v=p.second;
    297 			swap(a[u],a[v]);
    298 			pos[a[u]]=u,pos[a[v]]=v;
    299 		}
    300 	}
    301 	for(int i=1;i<=n/2;i++){
    302 		int x=pos[i],y=pos[mirror(i)];
    303 		if(x+y!=n+1){//not mirror
    304 			auto p=ask(x,mirror(y));
    305 			int u=p.first,v=p.second;
    306 			swap(a[u],a[v]);
    307 			pos[a[u]]=u,pos[a[v]]=v;
    308 		}
    309 	}
    310 	for(int i=1;i<=n/2;i++){
    311 		while(pos[i]!=i or pos[mirror(i)]!=mirror(i)){
    312 			if(pos[i]!=i){
    313 				auto p=ask(i,pos[i]);
    314 				int u=p.first,v=p.second;
    315 				swap(a[u],a[v]);
    316 				pos[a[u]]=u,pos[a[v]]=v;				
    317 			}else{
    318 				auto p=ask(mirror(i),pos[mirror(i)]);
    319 				int u=p.first,v=p.second;
    320 				swap(a[u],a[v]);
    321 				pos[a[u]]=u,pos[a[v]]=v;	
    322 			}
    323 		}
    324 	}
    325 	cout<<"!"<<endl;
    326 	fflush(stdout);
    327 }
    328 int main(){
    329 	int T=1;
    330 	cin>>T;
    331 	for(;T--;)solve();
    332 	return 0;
    333 }
    334 ```
    335 
    336 [2173F-Isla's Memory Thresholds](https://codeforces.com/contest/2173/problem/F) Idea & Solution: [paulzrm](/profile/paulzrm "Grandmaster paulzrm")
    337 
    338 **Tutorial**
    339 
    340 Consider the process. First note that, because the array $a$ is non-increasing, the length of each segment whose sum first reaches $\ge x$ and is then cleared is nondecreasing.
    341 
    342 We use the square-root decomposition idea. We fix a threshold $B$ that separates “short” segments from “long” ones. For segments of length at most $B$, we handle them using precomputed data; for segments of length greater than $B$, we use a slower direct procedure.
    343 
    344 Since there are at most $q$ distinct values of $x$, we can first collect all queries offline and discretize these values. Then we build a table $\text{f[i][len]}$ that records the rightmost starting position of a segment of length $\text{len}$ whose sum is at least the $i$-th largest value of $x$.
    345 
    346 When answering a query, we simply enumerate $\text{len} = 1, 2, \dots, B$ and, starting from the current left endpoint, quickly skip over and process all segments of length $\text{len}$. The time complexity for this part is $O(B)$ per query.
    347 
    348 For segments of length $ \gt B$, we directly binary search the ending position of each such segment. Since every such segment has length at least $B$, we make at most $n/B$ jumps, so this part runs in $O\bigl((n/B)\log n\bigr)$ time.
    349 
    350 If we choose $B = \sqrt{n\log n}$, the two parts balance and the total time complexity becomes $O\bigl(n\sqrt{n\log n}\bigr)$.
    351 
    352 **Solution**
    353 
    354 ```
    355 #include<bits/stdc++.h>
    356 #define ll long long
    357 using namespace std;
    358 const int mxn=2e5+5;
    359 const int B=512;
    360 int T,f[B+3][mxn],n,a[mxn],q;
    361 ll sum[mxn],N=1000000001;
    362 int l_[mxn],r_[mxn],x_[mxn];
    363 int id[mxn];
    364 void solve(){
    365 	cin>>n>>q;
    366 	vector<int>v;v.clear();
    367 	for(int i=1;i<=n;i++)
    368 		cin>>a[i],
    369 		sum[i]=sum[i-1]+a[i];
    370 	for(int i=1;i<=q;i++)
    371 		cin>>l_[i]>>r_[i]>>x_[i],
    372 		v.push_back(x_[i]);
    373 	v.push_back(0);
    374 	v.push_back(1000000008);
    375 	sort(v.begin(),v.end());
    376 	v.erase(unique(v.begin(),v.end()),v.end());
    377 	for(int i=1;i<=q;i++)
    378 		id[i]=lower_bound(v.begin(),v.end(),x_[i])-v.begin();
    379 	for(int i=1;i<=B;i++){
    380 		int k=0;
    381 		for(int j=n-i;j>=0;j--)
    382 			for(;v[k]<=min(sum[j+i]-sum[j],N);k++)
    383 				f[i][k]=j+1;
    384 	}
    385 	for(int t=1;t<=q;t++){
    386 		int l,r,x,cnt=0;
    387 		l=l_[t],r=r_[t],x=x_[t];
    388 		for(int i=1;i<=B;i++)
    389 			if(f[i][id[t]]>=l){
    390 				int w=min(r-l+1,f[i][id[t]]-l+i)/i;
    391 				cnt+=w;
    392 				l+=w*i;
    393 			}l--;
    394 		while(1){
    395 			if(sum[r]-sum[l]<x){
    396 				cout<<cnt<<' '<<sum[r]-sum[l]<<'\n';
    397 				break;
    398 			}cnt++;
    399 			int t=x,lo=l-1,hi=n+1,md;
    400 			ll req=sum[l]+t;
    401 			for(;lo<hi-1;){
    402 				md=lo+hi>>1;
    403 				if(sum[md]<req)lo=md;
    404 				else hi=md;
    405 			}
    406 			l=hi;
    407 		}
    408 	}
    409 	for(int i=0;i<max(n,(int)v.size())+3;i++)sum[i]=0;
    410 	for(int j=0;j<B+3;j++)for(int i=0;i<max(n,(int)v.size())+3;i++)f[j][i]=0;
    411 }
    412 signed main(){
    413 	ios_base::sync_with_stdio(0);
    414 	cin.tie(0),cout.tie(0);
    415 	T=1;cin>>T;
    416 	while(T--)solve();
    417 	return 0;
    418 }
    419 ```
    420 
    421 **Bonus**
    422 
    423 There exists an $O(n\sqrt{n})$ solution.