codeforces-scrape

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

1153.md (11676B)


      1 Source: https://codeforces.com/blog/entry/66539
      2 
      3 [1153A - Сервал и автобус](/contest/1153/problem/A "Codeforces Round 551 (Div. 2)")
      4 
      5 Author: [Serval](/profile/Serval "Кандидат в мастера Serval"), preparation: [bzh](/profile/bzh "Мастер bzh")
      6 
      7 **Editorial**
      8 
      9 Find the first bus Serval can see in each route and find the earliest one. For each route, finding the first bus Serval sees can work in $O(1)$.
     10 
     11 Or mark all the time no more than $\max(s_i,t+\max(d_i))$ which bus would come or there will be no bus, then search the nearest one.
     12 
     13 [1153B - Сервал и игрушечные кубики](/contest/1153/problem/B "Codeforces Round 551 (Div. 2)")
     14 
     15 Author: [Serval](/profile/Serval "Кандидат в мастера Serval"), Preparation: [bzh](/profile/bzh "Мастер bzh")
     16 
     17 **Editorial**
     18 
     19 Fill in all the bricks, and then remove all bricks you must remove (which in some view, there is empty). This can be solved in $O(nm)$.
     20 
     21 [1153C - Сервал и скобочная последовательность](/contest/1153/problem/C "Codeforces Round 551 (Div. 2)")
     22 
     23 Author & preparation: [Serval](/profile/Serval "Кандидат в мастера Serval")
     24 
     25 **Editorial**
     26 
     27 First let `(` be $+1$, `)` be $-1$ and `?` be a missing place, so we will replace all the missing places in the new $+1$,$-1$ sequence by $+1$ and $-1$.
     28 
     29 Obviously, for each prefix of a correct parenthesis sequence, the sum of the new $+1$,$-1$ sequence is not less than $0$. And for the correct parenthesis sequence itself, the sum of the new sequence should be $0$. So we can calculate how many $+1$ (let $a$ denotes it) and how many $-1$ (let $b$ denotes it) that we should fill in the missing places.
     30 
     31 According to the problem, our goal is to fill the missing place with $+1$ and $-1$ to make sure there is no strict prefix (prefixes except the whole sequence itself) exists with the sum equal to $0$. This can be solved in greedy. We want the sum of prefixes as large as possible to avoid the sum touching $0$. So let the first $a$ missing places be filled with $+1$ and the last $b$ missing places be filled with $-1$.
     32 
     33 Check it whether it is a correct parenthesis sequence or not at last. The complexity is $O(n)$.
     34 
     35 [1153D - Сервал и подвешенное дерево](/contest/1153/problem/D "Codeforces Round 551 (Div. 2)")
     36 
     37 Author & preparation: [bzh](/profile/bzh "Мастер bzh")
     38 
     39 **Editorial**
     40 
     41 If we want to check whether $x$ is the answer (I didn't say I want to do binary search), then we can set all the numbers no less than $x$ as $1$, and the numbers less than $x$ as $0$. Then we can use $dp_i$ to represent that the maximum number on node $i$ is the $dp_i$-th smallest number of leaves within subtree of $i$. There should be at least $dp_i$ ones in the subtree of $i$ such that the number on $i$ is one. Then $k+1-dp_1$ is the final answer. Complexity $O(n)$.
     42 
     43 **Code**
     44 
     45 ```
     46 #include <cstdio>
     47 using namespace std;
     48 struct node{
     49 	int to;
     50 	node *next;
     51 };
     52 int i,j,m,n,a[1000005],f[1000005],dp[1000005],deg[1000005],k;
     53 node *nd[1000005];
     54 void addd(int u,int v){
     55 	node *p=new node();
     56 	p->to=v;
     57 	p->next=nd[u];
     58 	nd[u]=p;
     59 }
     60 void dfs(int u){
     61 	node *p=nd[u];
     62 	if ((u>1)&&(deg[u]==1)){//note that u>1
     63 		dp[u]=1;
     64 		k++;
     65 		return;
     66 	}
     67 	if (a[u]) dp[u]=1000000000;
     68 	else dp[u]=0;
     69 	while(p){
     70 		dfs(p->to);
     71 		if (a[u]){
     72 			if (dp[p->to]<dp[u]) dp[u]=dp[p->to];
     73 		}else{
     74 			dp[u]+=dp[p->to];
     75 		}
     76 		p=p->next;
     77 	}
     78 }
     79 int main(){
     80 	scanf("%d",&n);
     81 	for(i=1;i<=n;i++){
     82 		scanf("%d",&a[i]);
     83 	}
     84 	for(i=2;i<=n;i++){
     85 		scanf("%d",&f[i]);
     86 		deg[i]++;
     87 		deg[f[i]]++;
     88 		addd(f[i],i);
     89 	}
     90 	dfs(1);
     91 	printf("%d\n",k+1-dp[1]);
     92 	return 0;
     93 }
     94 ```
     95 
     96 **Another Solution**
     97 
     98 We can solve this problem in greedy. At first we use $leaf_u$ to represent the number of leaves in the subtree whose root is $u$, and $f_u$ to represent the maximum number we can get on the node $u$. Note that since we are concidering the subtree of $u$, we just number those $leaf_u$ nodes from $1$ to $leaf_u$, and $f_u$ is between $1$ and $leaf_u$, too.
     99 
    100 Let's think how to find the maximum number a node can get.
    101 
    102 1. If the operation of the node $u$ we concerned is $\max$, for all the nodes $v$ whose father or parent is $u$, we can find the minimum $leaf_v-f_v$. Let $v_{min}$ denotes the node reaches the minimum. And we can construct an arrangement so that the number written in the node $u$ can be $leaf_u-(leaf_{v_{min}}-f_{v_{min}})$. When we number the leaves in the subtree of $u$ from $1$ to $leaf_u$, we number the leaves in other subtrees of children of $u$ first, and then number the leaves in subtree of $v_{min}$. It can be proved this arrangement is optimal.
    103 2. If the operation of the node $u$ is $\min$, we can construct an arrangement of the numbers written in the leaves to make the number written in $u$ be as large as possible. For all sons or children $v$ of $u$, we number the first $f_v-1$ leaves in subtree of $v$ first according to the optimal arrangement of the node $v$. And then no matter how we arrange the remaining numbers, the number written in $u$ is $1+\sum_{v \text{ is a son of } u} (f_v-1)$. This is the optimal arrangement.
    104 
    105 We can use this method and get the final answer $f_1$.
    106 
    107 **Code for Another Solution**
    108 
    109 ```
    110 #include <cstdio>
    111 using namespace std;
    112 const int N=1000005;
    113 int n,p;
    114 int h[N],nx[N];
    115 int t[N],sz[N];
    116 void getsize(int u)
    117 {
    118 	if (!h[u])
    119 		sz[u]++;
    120 	for (int i=h[u];i;i=nx[i])
    121 	{
    122 		getsize(i);
    123 		sz[u]+=sz[i];
    124 	}
    125 }
    126 int getans(int u)
    127 {
    128 	if (!h[u])
    129 		return 1;
    130 	int ret=0,tmp;
    131 	if (t[u])
    132 	{
    133 		for (int i=h[u];i;i=nx[i])
    134 		{
    135 			tmp=getans(i)+sz[u]-sz[i];
    136 			if (tmp>ret)
    137 				ret=tmp;
    138 		}
    139 		return ret;
    140 	}
    141 	for (int i=h[u];i;i=nx[i])
    142 		ret+=getans(i)-1;
    143 	return ret+1;
    144 }
    145 int main()
    146 {
    147 	scanf("%d",&n);
    148 	for (int i=1;i<=n;i++)
    149 		scanf("%d",&t[i]);
    150 	for (int i=2;i<=n;i++)
    151 	{
    152 		scanf("%d",&p);
    153 		nx[i]=h[p];
    154 		h[p]=i;
    155 	}
    156 	getsize(1);
    157 	printf("%d\n",getans(1));
    158 	return 0;
    159 }
    160 ```
    161 
    162 [1153E - Сервал и Змейка](/contest/1153/problem/E "Codeforces Round 551 (Div. 2)")
    163 
    164 Authors & preparation: [Serval](/profile/Serval "Кандидат в мастера Serval"), [bzh](/profile/bzh "Мастер bzh")
    165 
    166 **Editorial**
    167 
    168 If the answer to a rectangle is odd, there must be exactly one head or tail in that rectangle. Otherwise, there must be even number ($0$ or $2$) of head and tail in the given rectangle.
    169 
    170 We make queries for each of the columns except the last one, then we can know for each column whether there are odd number of head and tails in it or not. Because the sum is even, we can know the parity of the last column.
    171 
    172 If the head and tail are in different columns, we can find two columns with odd answer and get them. Then we can do binary search for each of those two columns separately and get the answer in no more than $999+10+10=1019$ queries totally.
    173 
    174 If the head and tail are in the same column, we will get all even answer and know that fact. Then we apply the same method for rows. Then we can just do binary search for one of the rows, and use the fact that the other is in the same column as this one. In this case, we have made no more than $999+999+10=2008$ queries.
    175 
    176 **Bonus: How to save more queries?**
    177 
    178 How to save one more query? We first make queries for row $2$ to row $n-1$. If we find any ones, make the last query for row, and use the method above. If we cannot find any ones, we make $n-1$ queries for columns. If none of them provide one, we know that for row $1$ and row $n$, there must be exactly one head or tail in them, and they are in the same column. In this case, we do binary search for one of the rows, then the total number of queries is $998+999+10=2007$.
    179 
    180 If we can find two ones in the columns, we know that: if one of them is in row $2$ to row $n-1$, the other must be in the same row, because for row $2$ to row $n$, we know that there are even number of head and tails, and them can't appear in the other columns. Then we do binary search, when we divide the length into two halves, we let the one close the the middle to be the longer one, and the one close to one end to be the shorter one. Then, if it turns out that, the answer is in row $1$ (or row $n$), the number of queries must be $\log n$ rounded down, and we can use one more query to identify, whether the head or tail in the other column is in row $1$ or row $n$. If it turns out that, the answer is in one of the rows in row $2$ to row $n$, we may used $\log n$ queries rounded up, but in this case, we don't need that extra query. So the total number of queries is $999+998+9+1=2007$ (or $999+998+10=2007$).
    181 
    182 In fact, if the interactor is not adaptive and we query for columns and rows randomly, we can use far less than $2007$ queries. And if we query for rows and columns alternatively, we can save more queries.
    183 
    184 [1153F - Сервал и бонусная задача](/contest/1153/problem/F "Codeforces Round 551 (Div. 2)")
    185 
    186 Author: [Serval](/profile/Serval "Кандидат в мастера Serval"), preparation: [Serval](/profile/Serval "Кандидат в мастера Serval"), [bzh](/profile/bzh "Мастер bzh")
    187 
    188 **Editorial**
    189 
    190 Without loss of generality, assume that $l=1$. For a segment covering, the total length of the legal intervals is the probability that we choose another point $P$ on this segment randomly such that it is in the legal intervals. Since all $2n+1$ points ($P$ and the endpoints of each segment) are chosen randomly and independently, we only need to find the probability that point $P$ is in the legal intervals. Note that only the order of these $2n+1$ points make sense. Because the points are chosen in the segment, the probability that some of them coincide is $0$, so we can assume that all points do not coincide.
    191 
    192 Now the problem is, how to calculate the number of arrangements that $P$ is between at least $k$ pairs of endpoints. It can be solved by dynamic programming in time complexity of $O(n^2)$. We define $f(i,j,x)$ as the number of arrangements for the first $i$ positions, with $j$ points haven't been matched, and $P$ appeared $x$ times (obviously $x=0$ or $1$). So we can get three different types of transition for the $i$-th position below:
    193 
    194 * Place $P$ at $i$-th position (if $j\geq k$): $f(i-1,j,0)\rightarrow f(i,j,1)$
    195 * Start a new segment (if $i+j+x \lt 2n$): $f(i-1,j-1,x)\rightarrow f(i,j,x)$
    196 * Match a started segment, note that we have $j$ choices of segments: $f(i-1,j+1,x)\times (j+1)\rightarrow f(i,j,x)$
    197 
    198 Then $f(2n+1,0,1)$ is the number of legal arrangements. Obviously, the total number of arrangements is $(2n+1)!$. However, there are $n$ pairs of endpoints whose indices can be swapped, and the indices $n$ segments can be rearranged. So the final answer is $\frac{f(2n+1,0,1)\times n! \times 2^n}{(2n+1)!}$.
    199 
    200 **Code**
    201 
    202 ```
    203 #include <cstdio>
    204 using namespace std;
    205 const int mod=998244353;
    206 const int N=4005;
    207 const int K=2005;
    208 int n,k,l;
    209 int fac,ans;
    210 int f[N][K][2];
    211 int fpw(int b,int e=mod-2)
    212 {
    213 	if (!e)
    214 		return 1;
    215 	int ret=fpw(b,e>>1);
    216 	ret=1ll*ret*ret%mod;
    217 	if (e&1)
    218 		ret=1ll*ret*b%mod;
    219 	return ret;
    220 }
    221 int main()
    222 {
    223 	scanf("%d%d%d",&n,&k,&l);
    224 	f[0][0][0]=1;
    225 	for (int i=1;i<=2*n+1;i++)
    226 		for (int j=0;j<=n;j++)
    227 			for (int x=0;x<=1;x++)
    228 				if (f[i-1][j][x])
    229 				{
    230 					if (j)
    231 						f[i][j-1][x]=(f[i][j-1][x]+1ll*f[i-1][j][x]*j)%mod;
    232 					if (i+j-1<2*n+x)
    233 						f[i][j+1][x]=(f[i][j+1][x]+f[i-1][j][x])%mod;
    234 					if (j>=k&&!x)
    235 						f[i][j][1]=(f[i][j][1]+f[i-1][j][x])%mod;
    236 				}
    237 	fac=1;
    238 	for (int i=n+1;i<=2*n+1;i++)
    239 		fac=1ll*fac*i%mod;
    240 	ans=f[2*n+1][0][1];
    241 	ans=1ll*ans*fpw(2,n)%mod;
    242 	ans=1ll*ans*fpw(fac)%mod*l%mod;
    243 	printf("%d\n",ans);
    244 	return 0;
    245 }
    246 ```
    247 
    248 **UPD:** We fixed some mistakes and added another solution for D.