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.