1956.md (12863B)
1 Source: https://codeforces.com/blog/entry/128426 2 3 Thank you for taking part in our contest, we know leaves a lot to be desired. But we believe that you can find interesting among our problems. 4 5 ## [A. Nene's Game](https://codeforces.com/contest/1956/problem/A) 6 7 Idea: [Otomachi_Una](/profile/Otomachi_Una "Grandmaster Otomachi_Una") 8 9 **Tutorial** 10 11 Obviously, a person at place $p$ will be kicked out if and only if $p \ge a_1$. 12 13 Therefore, the answer is $\min(n,a_1-1)$. 14 15 **Solution** 16 17 ``` 18 #include<bits/stdc++.h> 19 using namespace std; 20 #define ll long long 21 #define MP make_pair 22 mt19937 rnd(time(0)); 23 int a[105]; 24 void solve(){ 25 int q,k,n;cin>>k>>q; 26 for(int i=1;i<=k;i++) cin>>a[i]; 27 for(int i=1;i<=q;i++){ 28 cin>>n; 29 cout<<min(a[1]-1,n)<<' '; 30 } 31 cout<<endl; 32 } 33 int main(){ 34 ios::sync_with_stdio(false); 35 int _;cin>>_; 36 while(_--) solve(); 37 } 38 ``` 39 40 ## [B. Nene and the Card Game](https://codeforces.com/contest/1956/problem/B) 41 42 Idea: [Otomachi_Una](/profile/Otomachi_Una "Grandmaster Otomachi_Una") 43 44 **Hint** 45 46 The number of pairs on each side should be the same. 47 48 **Tutorial** 49 50 For each color (in the following text, "this point" refers to the point someone got by playing a card with this color): 51 52 * If you have both cards of this color in your hand, you will be able to get this point. 53 * If Nene has both cards, you will not be able to get this point. 54 * If you have only one card, you cannot get this point when Nene is using the following strategy: 55 56 > When you play one of your paired cards, Nene also plays one of her paired cards; Otherwise, Nene will have the card with the same color. She can play it and get this point. 57 58 Therefore, the answer will be the amount of pairs in your hand. 59 60 **Solution** 61 62 ``` 63 #include<bits/stdc++.h> 64 using namespace std; 65 const int MAXN=4e5+5; 66 int cnt[MAXN]; 67 void solve() { 68 int n,ans=0; 69 scanf("%d",&n); 70 fill(cnt+1,cnt+n+1,0); 71 for(int i=1,a;i<=n;++i) scanf("%d",&a),ans+=(++cnt[a]==2); 72 printf("%d\n",ans); 73 } 74 signed main() { 75 int T; 76 scanf("%d",&T); 77 while(T--) solve(); 78 return 0; 79 } 80 ``` 81 82 ## [C. Nene's Magical Matrix](https://codeforces.com/contest/1956/problem/C) 83 84 Idea: [Otomachi_Una](/profile/Otomachi_Una "Grandmaster Otomachi_Una") 85 86 **Hint** 87 88 When $n=3$, the optimal matrix is the following: 89 90 ``` 91 1 2 3 92 2 2 3 93 3 3 3 94 ``` 95 96 **Tutorial** 97 98 The optimal matrix would be: 99 100 ``` 101 1 2 3 ... n 102 2 2 3 ... n 103 3 3 3 ... n 104 ..... ... n 105 n n n n n n 106 ``` 107 108 Construction method: 109 110 ``` 111 for i in [n, n-1, ..., 1]: 112 set the i-th column to [1, 2, ..., n]; 113 set the i-th row to [1, 2, ..., n]; 114 ``` 115 116 This takes exactly $2n$ operations. 117 118 **Proof** 119 120 For the final matrix, we define $f(x)$ as the number of elements greater or equal to $x$. The sum of all elements in the matrix is $\sum_{i=1}^n f(i)$ because an element with value $x$ will be counted $x$ times in the formula before. 121 122 Now, we proof that $f(x) \le n^2-(x-1)^2$: 123 124 Let's rewrite the problem to make it a little simpler: 125 126 > You have an $n\times n$ matrix. In each operation, you can paint exactly $x-1$ cells white and $n-(x-1)$ cells black in a row or a column. Proof that there will be at most $n^2-(x-1)^2$ black cells. 127 128 Try to strengthen the conclusion by stating that: 129 130 > For any matrix of size $n\times m$, each operation can paint a row into $x$ white cells and $m-x$ black cells, or a column into $y$ white cells and $n-y$ black cells. No matter how we paint, the final matrix will have at most $nm-xy$ black cells. 131 132 We will prove this by induction. 133 134 If $x=m$ or $y=n$, the conclusion holds. 135 136 Otherwise, if the last operation is to paint a row, then this row has exactly $m-x$ black cells. And, by induction, other rows will contain at most $(n-1)m-x(y-1)$ black cells. Painting a column in the last step is similar. 137 138 Then, we have proven the conclusion above. 139 140 Since the construction above maximizes each $f(x)$, it is the optimal answer. 141 142 **Solution** 143 144 ``` 145 #include<bits/stdc++.h> 146 using namespace std; 147 #define ll long long 148 #define MP make_pair 149 mt19937 rnd(time(0)); 150 void solve(){ 151 int n;cin>>n; 152 int ans=0; 153 for(int i=1;i<=n;i++) ans+=(2*i-1)*i; 154 cout<<ans<<' '<<2*n<<endl; 155 for(int i=n;i>=1;i--){ 156 cout<<"1 "<<i<<' '; 157 for(int j=1;j<=n;j++) cout<<j<<' ';cout<<endl; 158 cout<<"2 "<<i<<' '; 159 for(int j=1;j<=n;j++) cout<<j<<' ';cout<<endl; 160 } 161 } 162 int main(){ 163 ios::sync_with_stdio(false); 164 int _;cin>>_; 165 while(_--) solve(); 166 } 167 ``` 168 169 ## [D. Nene and the Mex Operator](https://codeforces.com/contest/1956/problem/D) 170 171 Idea: [Otomachi_Una](/profile/Otomachi_Una "Grandmaster Otomachi_Una") 172 173 **Hint** 174 175 What is the answer when $a_i = 0$? 176 177 **Tutorial** 178 179 When $a_i =0$, the sum can hit $n^2$ with making $a_i = n$ at last. Construction: 180 181 ``` 182 //! a function which sets a_1 ... a_k into k. 183 function solve(k): 184 if k is 1: 185 operate [1,1] 186 return 187 end if 188 solve(k-1); 189 for i in [k-2, ..., 1]: 190 operate [1,i] //! this sets a_1 ... a_i into 0 191 solve(i) 192 //! here, a should be [i, i, ..., i, i+1, i+2, ..., k-1, 0] 193 end for 194 //! here, a should be [1, 2, 3, ..., k-1, 0] 195 operate [1,k] 196 return 197 ``` 198 199 Here, `solve(k)` will take about $2^k$ operations. 200 201 Since doing operation $[l,r]$ will make $a_l,\cdots,a_r \le r-l+1$, if for all $l\le i\le r$, $a_i$ is included in at least one of the operations and $a_{l-1},a_{r+1}$ are not, the optimal strategy will be setting $a_i = r-l+1$ for $i\in[l,r]$ using the construction above. 202 203 Finally, we can use DFS or DP to determine whether each element is included in operations. 204 205 The number of operations used will not exceed $2^n$. 206 207 **Solution** 208 209 ``` 210 #include<bits/stdc++.h> 211 using namespace std; 212 int n,a[20],cnt[20]; 213 vector <array<int,2>> I; 214 void oper(int l,int r) { 215 fill(cnt,cnt+n+1,0); 216 for(int i=l;i<=r;++i) if(a[i]<=n) ++cnt[a[i]]; 217 int mex=0; 218 while(cnt[mex]) ++mex; 219 for(int i=l;i<=r;++i) a[i]=mex; 220 I.push_back({l,r}); 221 } 222 void build(int l,int r) { 223 if(l==r) { 224 if(a[l]) oper(l,r); 225 return ; 226 } 227 build(l,r-1); 228 if(a[r]!=r-l) oper(l,r),build(l,r-1); 229 } 230 void solve() { 231 scanf("%d",&n),I.clear(),memset(a,0,sizeof(a)); 232 for(int i=0;i<n;++i) scanf("%d",&a[i]); 233 int cur=0,ans=0; 234 for(int s=0;s<(1<<n);++s) { 235 int tmp=0; 236 for(int l=0;l<n;++l) { 237 if(s&(1<<l)) { 238 int r=l; 239 while(r+1<n&&(s&(1<<(r+1)))) ++r; 240 tmp+=(r-l+1)*(r-l+1); 241 l=r; 242 } else tmp+=a[l]; 243 } 244 if(tmp>ans) ans=tmp,cur=s; 245 } 246 for(int l=0;l<n;++l) if(cur&(1<<l)) { 247 int r=l; 248 while(r+1<n&&(cur&(1<<(r+1)))) ++r; 249 build(l,r),oper(l,r),l=r; 250 } 251 printf("%d %d\n",ans,(int)I.size()); 252 for(auto i:I) printf("%d %d\n",i[0]+1,i[1]+1); 253 } 254 signed main() { 255 solve(); 256 return 0; 257 } 258 ``` 259 260 ## [E. Nene vs. Monsters](https://codeforces.com/contest/1956/problem/E2) 261 262 idea: [Otomachi_Una](/profile/Otomachi_Una "Grandmaster Otomachi_Una") 263 264 **Hint1** 265 266 If three consecutive monsters have energy level $0,x,y\ (x,y \gt 0)$, the monster with energy lever $y$ will "die"(have energy level $0$) at last. 267 268 **Hint2** 269 270 If four consecutive monsters have energy levels $0,x,y,z\ (x,y,z \gt 0)$, what will happen to the monster $z$? 271 272 **Hint3** 273 274 If four consecutive monsters have energy level $x,y,z,w\ (x,y,z,w \gt 0)$, how many rounds of spells must be used to make at least one of these monsters die? 275 276 **Tutorial** 277 278 If four consecutive monsters have energy level $x,y,z,w\ (x,y,z,w \gt 0)$ and they did not die after $t$ rounds of spells, then $y$ will receive at least $t$ points of damage, $z$ will receive at least $(t-1) +(t-2)+\cdots=O(t^2)$ of damage, and $w$ will receive at least $O(t^3)$ of damage. 279 280 That is to say, let $V=\max_{i=1}^n a_i$, after $O(\sqrt[3]{V})$ rounds, at least one of $x,y,z,w$ will die. 281 282 So, we can simulate the process by brute force until there are no four consecutive alive monsters, and then the problem is reduced to the one described in Hint 2. 283 284 If four consecutive monster have energy level $0,x,y,z\ (x,y,z \gt 0)$, $x$ will remain alive, $y$ will die at last and sending $D=(y-x)+(y-2x)+\cdots+(y\bmod x)$ damage to $z$ before that. Therefore, $z$ will remain alive if and only if $z \gt D$. 285 286 The time complexity is $O(n\sqrt[3]{V})$. 287 288 Bonus: Actually, it can be shown that after $O(\sqrt[k]{V})$ rounds, there will be no $k$ consecutive alive monsters. Making $k$ bigger than $3$ can further reduce the time complexity, but it will be harder to implement and optimize little on actual performance. 289 290 **Solution** 291 292 ``` 293 #include<bits/stdc++.h> 294 using namespace std; 295 #define ll long long 296 #define MP make_pair 297 mt19937 rnd(time(0)); 298 const int MAXN=2e5+5; 299 int n,a[MAXN];bool b[MAXN]; 300 bool check(){ 301 a[n+1]=a[1],a[n+2]=a[2],a[n+3]=a[3]; 302 for(int i=1;i<=n;i++) 303 if(a[i]&&a[i+1]&&a[i+2]&&a[i+3]) return true; 304 return false; 305 } 306 void solve(){ 307 cin>>n; 308 for(int i=1;i<=n;i++) cin>>a[i]; 309 if(n==2){ 310 while(a[1]&&a[2]){ 311 a[2]=max(0,a[2]-a[1]); 312 a[1]=max(0,a[1]-a[2]); 313 } 314 b[1]=(a[1]>0);b[2]=(a[2]>0); 315 }else if(n==3){ 316 while(a[1]&&a[2]&&a[3]){ 317 a[2]=max(0,a[2]-a[1]); 318 a[3]=max(0,a[3]-a[2]); 319 a[1]=max(0,a[1]-a[3]); 320 } 321 b[1]=(!a[3]&&a[1]); 322 b[2]=(!a[1]&&a[2]); 323 b[3]=(!a[2]&&a[3]); 324 }else{ 325 while(check()){ 326 for(int i=1;i<=n;i++) a[i%n+1]=max(0,a[i%n+1]-a[i]); 327 } 328 for(int i=1;i<=n;i++) b[i]=false; 329 auto attack=[&](ll x,ll y){ 330 ll k=x/y; 331 return (2*x-(k+1)*y)*k/2; 332 }; 333 for(int p=1;p<=n;p++) 334 if(a[p]&&a[p%n+1]) a[p%n+1]=max(0,a[p%n+1]-a[p]); 335 else break; 336 for(int i=1;i<=n;i++) if(!a[i]&&a[i%n+1]){ 337 b[i%n+1]=true; 338 b[(i+2)%n+1]=(a[(i+2)%n+1]>attack(a[(i+1)%n+1],a[i%n+1])); 339 } 340 } 341 int cnt=0; 342 for(int i=0;i<=n;i++) if(b[i]) cnt++; 343 cout<<cnt<<endl; 344 for(int i=1;i<=n;i++) if(b[i]) cout<<i<<' '; 345 cout<<endl; 346 } 347 int main(){ 348 ios::sync_with_stdio(false); 349 int _;cin>>_; 350 while(_--) solve(); 351 } 352 ``` 353 354 ## [F. Nene and the Passing Game](https://codeforces.com/contest/1956/problem/F) 355 356 idea: [Otomachi_Una](/profile/Otomachi_Una "Grandmaster Otomachi_Una") 357 358 **Hint** 359 360 Two people $i$ and $j\ (i \lt j)$ can pass the ball to each other directly if and only if $[i+l_i,i+r_i]\cap[j-r_j,j-l_j]\neq \varnothing$ 361 362 **Tutorial** 363 364 According to the hint above, we can build the following graph: 365 366 * There are $2n$ vertices in the graph. Vertice $i$ links to vertices $([n+i-r_i,n+i-l_1]\cup[n+i+l_i,n+i+r_i])\cap[n+1,2n]\cap Z$. 367 368 That is, assuming vertices $1$ to $n$ are players, vertices $n+1$ to $2n$ are temporary spots, and player $i$ links to all the spots where his/her arm can reach. 369 370 Then, the answer will be the number of connected components in this graph which contains at least one vertice with an index less than or equal to $n$. 371 372 But there's still a little problem with the solution. For two players $i, j\ (i \lt j)$ satisfying $[i+l_i,i+r_i]\cap[j+l_i,j+r_i]\neq \varnothing$ (that is, both players reaching out their "right arm"s), they are incorrectly counted as connected. 373 374 To solve that, we can delete all the vertices $n+x$ such that $\forall i,\ x\not\in[i-r_i,i-l_i]$ or $\forall i,\ x\not\in[i+l_i,i+r_i]$ (that is, nobody's left/right arm can reach $x$). Finding such $x$ can be done easily in $O(n)$. 375 376 The last issue is, the graph contains $O(n^2)$ edges. but since we only care about connectivity, operation "link $x$ to $[y,z]$" can be changed to "link $x$ to $y$, and link $i$ to $i+1$ for all $i$ in $[y,z-1]$". After that and removing multiple edges, the number of edges is reduced to $O(n)$. 377 378 Finally, counting connected components in a graph can be easily done in $O(n)$, so the time complexity is $O(n)$. 379 380 **Solution** 381 382 ``` 383 #include<bits/stdc++.h> 384 using namespace std; 385 #define ll long long 386 #define MP make_pair 387 const int MAXN=2e6+5; 388 int n,tot,le[MAXN],ri[MAXN]; 389 int fa[MAXN<<1],s[MAXN],t[MAXN],pre[MAXN],suf[MAXN]; 390 inline int find(int x){ 391 while(x^fa[x]) x=fa[x]=fa[fa[x]]; 392 return x; 393 } 394 void solve(){ 395 cin>>n; 396 for(int i=1;i<=2*n+1;i++) fa[i]=i; 397 for(int i=0;i<=n+1;i++) s[i]=t[i]=pre[i]=suf[i]=0; 398 for(int i=1;i<=n;i++){ 399 cin>>le[i]>>ri[i]; 400 s[max(1,i-ri[i])]++;s[max(0,i-le[i])+1]--; 401 t[min(n+1,i+le[i])]++;t[min(n,i+ri[i])+1]--; 402 } 403 tot=n; 404 for(int i=1;i<=n;i++){ 405 s[i]+=s[i-1],t[i]+=t[i-1]; 406 if(s[i]&&t[i]) suf[i]=pre[i]=++tot; 407 } 408 suf[n+1]=0; 409 for(int i=1;i<=n;i++) pre[i]=(pre[i]?pre[i]:pre[i-1]); 410 for(int i=n;i>=1;i--) suf[i]=(suf[i]?suf[i]:suf[i+1]); 411 for(int i=1;i<=n;i++){ 412 int l=max(1,i-ri[i]),r=max(0,i-le[i]); 413 if(l<=r){ 414 l=suf[l],r=pre[r]; 415 if(l&&r&&l<=r) for(int i=find(l);i<r;i=find(i)) fa[i]=i+1; 416 } 417 l=min(n+1,i+le[i]),r=min(n,i+ri[i]); 418 if(l<=r){ 419 l=suf[l],r=pre[r]; 420 if(l&&r&&l<=r) for(int i=find(l);i<r;i=find(i)) fa[i]=i+1; 421 } 422 } 423 for(int i=1;i<=n;i++){ 424 int l=max(1,i-ri[i]),r=max(0,i-le[i]); 425 if(l<=r){ 426 l=suf[l],r=pre[r]; 427 if(l&&r&&l<=r) fa[find(i)]=find(l); 428 } 429 l=min(n+1,i+le[i]),r=min(n,i+ri[i]); 430 if(l<=r){ 431 l=suf[l],r=pre[r]; 432 if(l&&r&&l<=r) fa[find(i)]=find(l); 433 } 434 } 435 int ans=0; 436 for(int i=1;i<=tot;i++) if(fa[i]==i) ans++; 437 cout<<ans<<'\n'; 438 } 439 int main(){ 440 ios::sync_with_stdio(false); 441 // freopen("Otomachi_Una.in","r",stdin); 442 // freopen("Otomachi_Una.out","w",stdout); 443 int _;cin>>_; 444 while(_--) solve(); 445 return 0; 446 } 447 ```