codeforces-scrape

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

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 ```