Author: Serval, preparation: bzh
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)$$$.
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.
Author: Serval, Preparation: bzh
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)$$$.
1153C - Serval and Parenthesis Sequence
Author & preparation: Serval
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$$$.
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.
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$$$.
Check it whether it is a correct parenthesis sequence or not at last. The complexity is $$$O(n)$$$.
1153D - Serval and Rooted Tree
Author & preparation: bzh
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)$$$.
#include <cstdio>
using namespace std;
struct node{
int to;
node *next;
};
int i,j,m,n,a[1000005],f[1000005],dp[1000005],deg[1000005],k;
node *nd[1000005];
void addd(int u,int v){
node *p=new node();
p->to=v;
p->next=nd[u];
nd[u]=p;
}
void dfs(int u){
node *p=nd[u];
if ((u>1)&&(deg[u]==1)){//note that u>1
dp[u]=1;
k++;
return;
}
if (a[u]) dp[u]=1000000000;
else dp[u]=0;
while(p){
dfs(p->to);
if (a[u]){
if (dp[p->to]<dp[u]) dp[u]=dp[p->to];
}else{
dp[u]+=dp[p->to];
}
p=p->next;
}
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(i=2;i<=n;i++){
scanf("%d",&f[i]);
deg[i]++;
deg[f[i]]++;
addd(f[i],i);
}
dfs(1);
printf("%d\n",k+1-dp[1]);
return 0;
}
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.
Let's think how to find the maximum number a node can get.
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.
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.
We can use this method and get the final answer $$$f_1$$$.
#include <cstdio>
using namespace std;
const int N=1000005;
int n,p;
int h[N],nx[N];
int t[N],sz[N];
void getsize(int u)
{
if (!h[u])
sz[u]++;
for (int i=h[u];i;i=nx[i])
{
getsize(i);
sz[u]+=sz[i];
}
}
int getans(int u)
{
if (!h[u])
return 1;
int ret=0,tmp;
if (t[u])
{
for (int i=h[u];i;i=nx[i])
{
tmp=getans(i)+sz[u]-sz[i];
if (tmp>ret)
ret=tmp;
}
return ret;
}
for (int i=h[u];i;i=nx[i])
ret+=getans(i)-1;
return ret+1;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&t[i]);
for (int i=2;i<=n;i++)
{
scanf("%d",&p);
nx[i]=h[p];
h[p]=i;
}
getsize(1);
printf("%d\n",getans(1));
return 0;
}
Authors & preparation: Serval, bzh
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.
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.
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.
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.
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$$$.
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$$$).
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.
1153F - Serval and Bonus Problem
Author: Serval, preparation: Serval, bzh
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.
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:
- Place $$$P$$$ at $$$i$$$-th position (if $$$j\geq k$$$): $$$f(i-1,j,0)\rightarrow f(i,j,1)$$$
- Start a new segment (if $$$i+j+x<2n$$$): $$$f(i-1,j-1,x)\rightarrow f(i,j,x)$$$
- 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)$$$
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)!}$$$.
#include <cstdio>
using namespace std;
const int mod=998244353;
const int N=4005;
const int K=2005;
int n,k,l;
int fac,ans;
int f[N][K][2];
int fpw(int b,int e=mod-2)
{
if (!e)
return 1;
int ret=fpw(b,e>>1);
ret=1ll*ret*ret%mod;
if (e&1)
ret=1ll*ret*b%mod;
return ret;
}
int main()
{
scanf("%d%d%d",&n,&k,&l);
f[0][0][0]=1;
for (int i=1;i<=2*n+1;i++)
for (int j=0;j<=n;j++)
for (int x=0;x<=1;x++)
if (f[i-1][j][x])
{
if (j)
f[i][j-1][x]=(f[i][j-1][x]+1ll*f[i-1][j][x]*j)%mod;
if (i+j-1<2*n+x)
f[i][j+1][x]=(f[i][j+1][x]+f[i-1][j][x])%mod;
if (j>=k&&!x)
f[i][j][1]=(f[i][j][1]+f[i-1][j][x])%mod;
}
fac=1;
for (int i=n+1;i<=2*n+1;i++)
fac=1ll*fac*i%mod;
ans=f[2*n+1][0][1];
ans=1ll*ans*fpw(2,n)%mod;
ans=1ll*ans*fpw(fac)%mod*l%mod;
printf("%d\n",ans);
return 0;
}
UPD: We fixed some mistakes and added another solution for D.
Aim of Q.C is just to make subset x = s[1...[s]-2] a perfect parenthesis sequence, with s[0] = '(' and s[|s|-1] = ')'. This is because if x is balanced, then all strict prefixes are gauranteed unbalanced, but still s[0]+x+s[n-1] will become balanced.
I thought the same but got WA on Test Case 6. What about yours?
See this comment. I too was closing brackets as soon as possible. But greedy approach should have been other way around (making brackets open first as much as possible). Refer this comment for better understanding : https://codeforces.net/blog/entry/66539?#comment-505352
I use a greedy approach , Let the first '(' match the last ')' ,and we just remove the first char and the last char ,then if the remaining string can be a Legal sequence , then it works,and also use greedy approach to replace '?',first we shoule cale the numebr of '(' in '?' ,then we should replace '?' with '(' First ,and the rest we replace with ')', Be careful with the illegal solution.
try this test case: 6 ??)?)) output: (()()) wa: :(
why output: (()()) is WA ? I think it is correct
It seems like my english is bad, I meaned that with this test, right answer would be (()()), and if your code gave :(, it would be considered as a wrong answer, sorry for my bad
OK , I think my approach will output the correct answer
Thanks for the fast editorial!
Can someone explain D — Serval and Rooted Tree more clear， sorry for my stupidness
For each non leaf node, we either have a max node or a min node. If we are at a max node, then we can assume our answer will come from the child with the highest upper bound. But if we are at a min node, then we need to add up all the upper bound. The upper bound at the leaves are 1 (meaning we take the 1st highest node of its subtree which is itself). For a min node with 2 leaf child, the upper bound is 2 (meaning we need 2 high value K's to maximize that node)
What do you mean, when you saying "upper bound". Is this a maximal number, what can be written in non leaf node? Can you explain idea in more detail, why we need upper bound for all nodes?
The upper bound on a node is the maximum value that can be achieved with optimal arrangement of it's subtree.
for each vertex, try to minimize the number of numbers which the number on this vertex must be less than (I mean '<'). Try to find this answer for all the vertices and the answer for the no.1 vertex will be used to make the final answer for this task, final answer is (number of leaves)-(answer for question I mentioned above for no.1 vertex). Hope you get it. how to get this idea: by seeing that the number on each vertex must be less than some numbers on other vertices, it depends on what type of restriction (min or max), try to minimize this number for all vertices to get better answer (bigger number for vertex no.1)
In pronlem E , we can check all rows and columns in a random order . In worst case , the expect number of queries is about 1020.
Can you post your code ? plz
I've just wrote one in here
Thanks for the editorial. I was trying to solve C by trying to maintain difference of 1 between number of open and closed brackets and greedily marking a '?' as '(' or ')'. Kept failing on pretest 6 and could see on Discord after contest that a few more were failing on that pretest.
I guess another intuition of why we can make as many '?' = '(' in the beginning is that there is no way it will make the sequence unbalanced as we can always have ')' at the later half of the sequence to balance it out. My solution, in contrast would have failed for case like "((?)))" as it would have changed the first '?' to ')'.
BTW Then I think there can't be an online solution to the problem ? Am I right ?
Thanks again !
I was facing the same problem but I still do not understand how closing brackets as soon as possible leads to failure in Testcase 6. Could you please explain your insights?
(??)
( ( ? ) )
Your code I guess will be assigning ? as ).
try this: ??)?))
Gives this output
(()()). Please take a look at my solution.a condition to maintain a valid sequence is make sure num of '(' >= num of ')' so )()( is fail for the first character when num of ')' is 1 and none of '(' character
Problem D and E are really nice! We need more div2 contests like this ;)
In the editorial for 1153E — Serval and Snake,
"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 998+10+10=1018 queries totally."
Where does the 998 comes from? Isn't it that in the worst case you will have to go through 999 columns?
Oh, you are right. It is 999. We've changed constraints several times and made a mistake in changing that number in the tutorial. Sorry for my mistake and thanks for your correction. Fixed now.
No worries~
I hardly understand anything from D's editorial :// ,
Can anyone explain : ,
1, What dp[i] means ? ,
2, What does "the number on i is one" mean when we dont know the specific 'x' ? ,
3, Why the answer is k + 1 — dp[1] ?
dp[i] means that the maximum number on node i is the dp[i]-th greatest number of leaves within subtree of i. Updated in the tutorial now and thanks for your questioning.
But can you please explain why this solution works ??
What is the proof behind the dp solution??
If you meet a max operation, then it is the minimum number of all dp values of its direct children. And if you meet a min operation, then it is the sum of dp values of its direct children.
dp[i] means that the maximum number on node i is the dp[i]-th smallest number of leaves within subtree of i.
according to ur comment, if dp[root] = 1, the maximum number on root node is the first smallest number of leaves which is 1. But the k+1-dp[root] gives k. We get a contradiction.
I think 'smallest' should be 'greatest', which makes sense
yes, you are right. Fixed and thanks.
I have added another solution so you can try to understand another one. :)
But how do you know where to place the values < x and the values >= x ?
Sorry for the mistakes, I've updated a new one.
thanks
Can you explain the min case of the second solution given in editorial of Problem D?
For all sons or children v of u, we number the first $$$f_{v}−1$$$ leaves in the 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\ is\ a\ son\ of\ u}f_v$$$. This is the optimal arrangement.
What is the intuition behind the first $$$f_{v}−1$$$ leaves?
What is the proof that this leads to optimal arrangement?
According to the optimal arrangement in the subtree of $$$v$$$ ($$$v$$$ represents all children of $$$u$$$), we know that the largest possible number written in node $$$v$$$ is $$$f_v$$$. And in a possible arrangement, the number written in node $$$u$$$ is the minimum of what the $$$f_v$$$-th leaf numbered in subtree of $$$v$$$. So our goal is to find an arrangement to make the number written in the $$$f_v$$$-th leaf as large as possible in each subtree of $$$v$$$. And bacause of the optimal arrangement in the subtree of $$$v$$$, we have to make sure that, for any two leaves $$$a$$$ and $$$b$$$, if $$$a$$$ numbered less than $$$b$$$ in $$$v$$$'s arrangement, $$$a$$$ should be numbered less than $$$b$$$ in $$$u$$$'s subtree, too. Let's consider how many numbers less than $$$f_v$$$ we can arrange first to make all $$$f_v$$$ as large as possible, so the answer is $$$\sum_{v\text{ is a son of }u} (f_v-1)$$$. And no matter how we arrange the next number, there will always be a $$$v$$$ that the $$$f_v$$$-th leaf in $$$v$$$'s subtree is numbered, and it becomes the minimum of what the $$$f_v$$$-th leaf numbered in subtree of $$$v$$$. So this is an optimal way to arrange the numbers.
And sorry for the mistake I written in the editorial, it is $$$\sum (f_v-1)$$$ instead of $$$\sum f_v$$$, I will fix it. :)
This was the most beautiful problem I have solved till nowrelated to graph traversals. Thank you.
The question still remains intact.
I got accepted and I'll share how I understood it,
Define $$$dp[u]$$$ as the minimum value to maximize node $$$u$$$. For example, if $$$dp[u] = 3$$$, you would need 3 values: $$$[k - 2, k - 1, k]$$$ to maximize node $$$i$$$.
The final answer is $$$k - dp[1] + 1$$$.
But how will you give the values to leaves in this case ??
This will seriously help me understand the problem
Any help will be appreciated
11
1 1 1 0 0 1 1 1 1 1 1
1 1 2 2 3 4 4 5 5 5
Why exactly do we need the +1?
k , k — 1, …… k — (dp[1] — 1) these are satisfied, the last is the ans, I don't konw if I got it, but it make sense.
How on God's green Earth is one supposed to get that intuition ?!? Dang. Are there any problems which are slightly less difficult, but are more intuitive that I should be trying? Cuz I've been trying to solve this for the better part of a couple of hours and I've got nowhere.
This is by far the simplest and most straighforward explanation I have found. Thanks.
great explaination!
You can refer link
this solution is easy to understand.
In Q C test case : 14 ((?)))(((??))) in this example we need to replace 2 ?'s with '(' and 1? with ')' with reference to the editorial, we should first add 2'(' to the string and then 1')' so ans =((()))(((()))) but in this case sequence s1...s6 is correct parenthesis.? Can anybody explain the editorial more clearly
We should check it whether a correct answer or not after we construct the possible answer.
So R u telling me to go for backtracking if the answer found is wrong. I am not getting how you are deciding that we should put ')' or '(' such that the complete sequence is correct but none of the prefixes.
The way they place the braces is the greedy way that should give the correct answer. If this greedy way doesn't give the correct answer, there is no way you can place the braces right.
Can someone tell me how to find the bus route in O(1)? (for Problem A)
time = s + ( ( (t-s+d-1)/d ) * d );
Yeah, I saw it in some sources but I don't understand how it works.
t-s is the duration between arrival time and initial time. But the bus need not come at the arrival time exactly. So, we add d to this time in order to get any time after arrival. Now we need to find the number of trips within the duration t-s+d.
In order to find it, we subtract 1 form t-s+d because we don't need any trips in the last minute. So, we get number of trips=(t-s+d-1)/d. Each trip takes d time. Finally, time will be = s + ( ( (t-s+d-1)/d ) * d )
For problem A, can someone explain , how to come up with this? time = s + ( ( (t-s+d-1)/d ) * d );
Also, is it not possible to come up to this using aritmetic progression??
Because I tried to do this:
but this gives wrong ans..
Let $$$time$$$ be the minimal time you need to wait for a bus.
If $$$s\geqslant t$$$, then $$$time=s$$$. Else, you need to wait $$$x$$$ more seconds until the next bus comes. So basically, you have $$$time=s+x$$$.
Of course $$$time\geqslant t$$$ so $$$s+x\geqslant t$$$. Moreover, you get on the bus right when the bus comes, so $$$x$$$ is divided by $$$d$$$. The problem become: Find the smallest $$$x$$$ satisfies that $$$s+x\geqslant t$$$ and $$$x$$$ is divided by $$$d$$$.
Now we can write $$$x$$$ as $$$y\times d$$$ where $$$y$$$ is an integer. Condition $$$s+x\geqslant t$$$ can be written as $$$s+y\times d\geqslant t$$$, or $$$y\geqslant \dfrac{t-s}{d}$$$. We need to find the minimum $$$y$$$ that satisfies that condition. Here, $$$|\dfrac{t-s+d-1}{d}|$$$ is the answer (let $$$a$$$ be a real number, $$$|a|$$$ is the maximum integer that smaller than $$$a$$$), and when you save the result of the operation
(t-s+d-1)/dto an integer variable, it gets the same result.can you explan why we have -1 there?
Some mathematical stuff I don't even know man. But it's true :))
Got my mistake.
The string (()(())()) is different from the one given in the test case, and can't be formed from (???(???(? as the second last element (s[n-2]) is different in your solution and we can only change "?" and not the "(" and ")".
Can someone explain with example the approach for D ?
Is ques D is related to some standard problem which I should solve first? because I feel many people did solve this ques in very less time and almost all have applied same approach.
I feel the same way.
I solved it in contest and don't remember seeing any similar problem. I started brainstorming and analyzing random trees I drew on paper and eventually saw the pattern.
Could you help me? how you come to the recognize the pattern? Like not the solution I am asking, but how did you able to connect the dots in order to get the pattern?
Okay, I will try to explain my thought process. The maximum query looked like it would be pretty straightforward, so I only thought about the minimum query. Idea one (Wrong): If I want the minimum of 2 children, then the max should be in one and max-1 should be in another. I drew a sample where this failed. Idea two (Failed): Make some sort of dp to find out which of the children is the one I keep. I couldn't think of anything with this approach. Idea three (Success): Look carefully at sample 3, and try drawing a few similar ones, but with more levels. Say N is the number of leaves. I saw that when a node keeps the minimum value of its children, it looses the values of all other children. Say you have 3 children, the value on this node can not be N or N-1, but it can be N-2. This led to the idea: If a node keeps the minimum, it looses all the values of its children, except the smallest one (loosing K values means the answer can't be higher than N-K). So you keep track of which values the children lose, and keep the smallest one (Number of lost numbers — 1). Now for the max query: You want to lose the minimum possible (to get the highest possible result), so you keep the child which loses the minimum. Link to my submission: https://codeforces.net/contest/1153/submission/52704203
Best Explanation, Thank You.
I understood your maximum's logic (also that dfs in your code returns the values lost) but I still don't have any clue on the minimum part. Can you please explain a little more ? I worked out examples and saw that it works, but why ?
When you ask for the minimum in a node, you lose the values of all its children (plus all the values the children lost) except for the smallest one. I explained as best as I could... If you have any specific question I can try to answer it. Good luck!
it really helped.
Best explanation for this problem.
What is the intuition behind problem D?
I understood it and have written a blog on it
https://codeforces.net/blog/entry/66541
Hope it helps
Thanks for the effort but it's not clear to me yet. Sorry :)
Which part ? I updated it by adding image check it now
Thanks!
Am I the only one who thinks that the editorial needs more explanation?
For which problem? :)
Problem B.
For any $$$h_{i,j}$$$, it is limited by three views — the top view, the left view and the front view. We just set $$$h_{i,j}$$$ as the minimum among these three limitations.
Problem D
You can refer link
this solution is easy to understand.
Can you explain the min case of the second solution given in editorial of Problem D?
For all sons or children v of u, we number the first $$$f_{v}−1$$$ leaves in the 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\ is\ a\ son\ of\ u}f_v$$$. This is the optimal arrangement.
What is the proof of this?
**Problem D : Serval and Rooted Tree **.
Can also be done in this way . for each node X keep a pair (maximum possible order of X,no of leaves subtree rooted at X has).
Order of X means if we sort values at leaves in the subtree rooted at X then let that sorted sequnce be it be L1,L2 ..,Li ...Lk then Order of x is maximum possible index .
Lets call this tuple (maximum possible order of X,no of leaves subtree rooted at X has) as (ff,ss).
if node X is of **max ** type maximum then X.ss is total leaves in subtree rooted at X i.e. X.ss=($$$\sum\limits_{}^{all child} C.ss$$$ ) where C represent child.
Ans X.ff is maximum possible order that will be X.ff=max(X.ss-(C.ss-C.ff)) i.e. X.ff=X.ss+max(C.ff-C.ss)) for all C that are child of X.
if node X is of **min ** type maximum then X.ss is total leaves in subtree rooted at X i.e. X.ss=($$$\sum\limits_{}^{all child} C.ss$$$ ) where C represent child.
Ans X.ff is maximum possible order that will be X.ff=($$$\sum\limits_{}^{all child} (C.ff -1)$$$ ) + 1.
code :
code_link
Thanks it helped!!
Thanks, i have one doubt why you did summation in last 3rd line??
There is a place in question C that I don't want to understand. According to the meaning of the problem, first fill in the required'(', then fill in the required')'. In this case, there is only one filling method. I don't know how to prove that only this filling method is available.I hope someone can help me.
There are many solutions. We just use this method to construct one possible answer. :)
Thank you for your reply. Since there are many solutions, why can one of them be used to judge the feasibility?
The method I given is the optimal way to find an answer. If the answer it found is invalid, there will be no solution exists. :)
What is test case 5 in problem D ?
silly bugs T^T
Just when you thought asking EXACTLY 2019 queries for E was fuckin' genius...
How did you manage to do that?
First 1000 queries to check each column. If head and tail are at the same column, I check 999 rows (if there are only one odd answer (for head), it means that the tail is at the 1000'th column). And next I use binary search (2x10) to find exact positions. In total it's 1000+999+10+10=2019 queries
Haha nice! That’s pretty funny.
For div 2 c the second example test case given- 10 (???(???(?
is ()()()()()->(1)+(1)+(1)+(1)+(1) not a solution? why?
As the problem states, all prefixes of the final string, except the final string itself, should not be valid. Since () is a valid parenthesis sequence, ()()()()(), is not a valid solution.
Please read the statement.
()is a strict prefix of()()()()(), and according to the problem, it should not be a correct parenthesis sequence.I have seen problems similar to C before with parentheses checking. I would like to practice more of those .. can anyone link me to similar problems please ?
https://www.codechef.com/problems/COMPILER http://www.spoj.com/problems/ANARC09A/ http://codeforces.net/contest/5/problem/C This will surely help you.
There are many bracket problems on cf,I think they are very common...Here is one that is more challenging: 380C - Сережа и скобочки
There is one main important fact about a correct bracket sequence: if you treat
( = 1and) = -1, then the total sum must be0, and every prefix sum must be>= 0.In problem D 1. why are we taking sum of dp values in case of min operation. 2. why are we taking min values in case of max operation.
I think Problem F can be solved directly by calculus in $$$O(n\log n)$$$.
Let
(Which means the probability that a random segment cross point x.)
Then
(Which means the probability that a at least k random segment in n cross point x)
We just need to calculate:
We can solve it in $$$O(n\log n)$$$.
I implement it in $$$O(n^2)$$$ though...
UPD: I can't solve it in $$$O(n\log n)$$$ but $$$O(n\log^2 n)$$$. It's about polynomial interpolation so very brute.
UPD2: It can be solved in $$$O(n\log n)$$$ now. See at here.
Oh, by FFT. For it's 998244353.
Oh, So nice.
Where's your Bob.
how to cal f(x) in O(n^2) ?
That's quite easy. We first reform $$$f(x)$$$ to $$$\sum\limits_{i = 0}^n a_i p(x)^i$$$.
It's $$$O(n^2)$$$.
Then we replace $$$p(x)$$$ with $$${2x(l - x) \over l^2}$$$.
It's $$$O(n^2)$$$.
got it, thx~
Can you explain more about how to solve $$$\int_0^l f(x)dx$$$ in $$$O(n\log n)$$$?
Sorry about that. My mistake. Now I can only solve it in $$$O(n\log^2n)$$$
By polynomial interpolation. It's very brute.
I can solve it in $$$O(n\log n)$$$ now.
Let $$$l = 1$$$, it doesn't matter.
We reform $$$f(x)$$$ to $$$f(x)=\sum\limits_{i = 0}^n a_ip(x)^i$$$.
We now only need to calculate $$$\int_0^1 p(x)^i dx$$$. $$$p(x) = 2x(1-x)$$$.
So it will be $$$\int_0^1 x^i(1-x)^i dx = {i!^2 \over (1+2i)!}$$$.
I don't know why but now it can be solved in $$$O(n\log n)$$$. (I get this by wolfram...)
So anyone knows why: $$$\int_0^1 x^i(1-x)^i dx = {i!^2 \over (1+2i)!}$$$?
Aw, It's Beta function!
And it seems like:
Thank you so much!
Can you share some problems of this kind?
https://atcoder.jp/contests/agc032/tasks/agc032_f
Here you go.
Can someone explain the problem C, I have tried understanding it, but didnt worked out.
So the problem is the same as asking to recover (if possible) a sequence of parentheses that is balance but any proper prefix is not balanced. The sequence of parenthesis is balanced if and only if: there's equal
(as), and for any prefix there's no more(than). Saying that the sequence of parentheses is balanced but any proper prefix it's not actually implies that the number of(is more than the number of)for any proper prefix... that's the main idea :)okay, here is my understanding. let me know whether is correct or not
P(1,L), 1<=L<=N, is balance if it contains equal number of ('s and )'
and we have to balance the P, such that there should be only one solution for L, that is L=N.
and we have to replace ? with )'s or ('s to satisfy the above contraint. right ?
Yes
Problem B has another cute solution (at least I had it accepted, break me if you dare!) -- if
t[i][j] = 1(we don't care about the 0 case obviously), then the number of bricks we put ismin(b[i], a[j])(basically, the minimum of the front and left view corresponding to the brick).That's what I submitted, too. You don't even need to store the t_ij, you can output this min as you read a 1, or 0 when you read a 0.
Ditto. If there were impossible arrangements, this might fail, but since it's guaranteed the given heights will be possible, this minimum approach should always work.
[please ignore earlier posted message, I confused node id and value filled in]
Read the statement carefully please. :) The numbers written in the middle of the nodes are their indices, and the numbers written on the top are the numbers written in the nodes.
I have looked at all of the solutions of D but all of them are too cryptic. I can't understand none of them at all. All these subindicies and sums are very, very confusing and I can't understand why do they pop up. Can someone please instead of saying "Do x to solve" try to explain why do x to solve? What is the intuition behind those indicies? Why this and not that?
Can someone explain how to do a binary search in problem E ,for example, after finding a row how to choose the two points ?
Can you please explain what is wrong with this submission: https://codeforces.net/contest/1153/submission/52760960 When I run it locally I get the correct answer for the second test case.
There are $$$n-1$$$ edges in a tree but you tried to read an $$$n$$$-th edge.
Thanks!
Why in problem F we add both f[i-1][j][1] and f[i-1][j][0] to f[i][j][1] (the first case in solution placing P at the ith position)
Sorry for this typo, we just add $$$f(i-1,j,0)$$$ to $$$f(i,j,1)$$$. The editorial is fixed. :)
Thanks
Can I get Some upvotes ;)
Are there any problems similar to problem D for practice ?
Can anyone explain how this solution of D by Max.D. works ?
It would be nice if the problem statement explicitly says if the interacter is adaptive, just saying.
Can anyone explain to me what's wrong with my submission for the interactive problem E. The checker seems to be giving me an invalid answer given the mentioned input. Can anyone take a look if there's some issue? https://codeforces.net/contest/1153/submission/53116004 (check the diagnostic message for Test Case #3)
Why is it so hard to explain D?
I rember participating in that contest, and tried today again to solve it. With ablsolutly no success. Then did read the tutorial...still understand like nothing. Did read again all comments in this thread...but have still no clue else that is dp ...somehow.
What I especially don't understand: How can we recursively make a statement about a subtree when the value clearly depends on which numbers are used in the siblings' subtrees?
For Problem D Serval and Rooted Tree.
Finding the number of numbers for a vertex from which the number on the vertex must be less than. Vertices are two types max and min. 1)if the vertex is a min vertex then it has to be less than all its child except one child whose value it would take. Here if the vertex has x children then it has to be smaller than dpv+dp[c1]+dp[c2]+dp[c3]+...+dp[cx]; X-1 because it would take the value of one of it's child. 2)If the vertex is a max vertex then it has to be the maximum values among all its child. Here if the vertex has x children then it would give priority to the child which is smaller than minimum number of values dp[v]=min(dp[c1],dp[c2],dp[c3],dp[c4],....,dp[cx]); here min operation in max vertex because it would select the most optimal child and since this child is having a value greater than other children so the value of the vertex would also be greater than other children.
I have a solution to problem E without any binary search!
First, for columns:
First, we do sliding window query: we query a rectangle of size $$$n \times n/2$$$, and slide it from left to right. If the head and tail are at different columns, then we can find those columns when the sliding window experiences a change in parity. This takes $$$n-n/2=n/2$$$ queries for column. Similarly for rows, so it takes $$$n$$$ queries in total.
Now if they are in the same row/column, they must be in different column/row. So just query each cell of that column/row: $$$n$$$ more queries. Hence we find the common row/column.
Now, in $$$2n$$$ queries, we have found out the rows and columns. Now all that remains is to try all possible $$$2^{2}$$$ operations, so that we complete the entire interaction in $$$2n+4$$$ queries! A new record!!
You can see that my program doesn't cross 2004 queries 103719211
Thanks a lot for your solution.
I doubt that if one of the points is in column $$$1$$$ while the other is in column $$$n/2+1$$$, you solution can't find the column (the parity is always odd).
However, following your hint, I found a solution with an upper bound in about $$$n+2\log(n)$$$. If the two points are in different columns, there will always be an odd reply in your sliding. Once we find an odd reply, we know there is exactly one point within the rectangle, and binary search works.
So we can implement your method first for columns, if no odd reply found, then they are in the same column. Do it for rows, and we must receive an odd reply.
To find the second point, for example, if we know they are in different columns, and we can do binary search in either column $$$1$$$ to $$$c_1-1$$$, or $$$c_1+1$$$ to $$$n$$$, whichever has odd reply.
To estimate the upper bound, the worst case is that we didn't get anything from column queries. So they are in the same column. The binary search for the first point takes $$$2\log(n)$$$. In principle, the second one requires one $$$\log(n)$$$ for rows, but if the two points are far apart, the row queries end a lot earlier; and if they lie close together, and at the last rows, the last binary search is almost nothing.
Here is my submission 103914149
I was trying to solve problem D, and not being able to solve it, I came to search for the solution here. But I found no intuitive or clear solution either in the editorial, or in the comments for people with unicellular brains like me. I looked at a few solution codes, and finally solved the problem. So I decided to attempt to write a simpler explanation than what's already here for problem D.
Let us define $$$dp_i$$$ as the minimum number of leaves in the subtree of node $$$i$$$ that we have to consider to get the maximum possible value at node $$$i$$$. In other words, say, if $$$dp_i = 2$$$, then we have to consider at least $$$2$$$ leaves as the possibility of containing the number which will be stored in node $$$i$$$. Which means, we can narrow down the number of necessary leaves to consider as the answer for node $$$i$$$ as $$$2$$$. So, if $$$dp_1=p$$$, then our final answer will be, (choosing greedily), the $$$p$$$-th largest possible number to be assigned to a leaf in the tree. So, say, there are $$$k$$$ leaves in the tree, our final answer will be $$$k-p+1$$$.
Now that we know what exactly we have to compute, let us move on to how we will compute it.
Let $$$choice_i=1$$$ if node $$$i$$$ has max written on it, and $$$0$$$ if node $$$i$$$ has min written on it.
Case 1 (MAX): If $$$choice_i=1$$$, then we can choose the child of node $$$i$$$ which has the least number of necessary leaves in its subtree. We can, thus, narrow down the answer as much as is possible to be done by node $$$i$$$. Thus, if $$$choice_i=1$$$, $$$dp_i=min(dp_{child_i})$$$.
Case 2 (MIN): If $$$choice_i=0$$$, then we do not have an option of narrowing down the number of necessary leaves at node $$$i$$$. We must consider all the necessary leaves of all children of node $$$i$$$ to compute the number of necessary leaves for node $$$i$$$. Thus, if $$$choice_i=0$$$, $$$dp_i=\sum dp_{child_i}$$$.
If node $$$i$$$ is a leaf, we do not have to consider $$$choice_i$$$ as it does not have any children. Thus, if node $$$i$$$ is a leaf, $$$dp_i=1$$$.
Thus, we can summarize the solution as:
- if node $$$i$$$ is a leaf, $$$dp_i=1$$$.
- if $$$choice_i=0$$$, $$$dp_i=\sum dp_{child_i}$$$.
- if $$$choice_i=1$$$, $$$dp_i=min(dp_{child_i})$$$.
$$$answer=k-dp_1+1$$$.
C++ solution
Problem D is a simpler version of this question.
Problem E is just a simpler version of this question.
In the other question you have to search for two points, in which atleast one bit in binary of their index number differs, here we have to search for two points, in which atleast one of their x and y coordinate differ. In each query in both questions, we query over some search space, and we get to know whether 1 point lies in search space or if 0/2 points lie in the search space.
Problem F can be solved in $$$O(n)$$$. First, notice that for segment $$$[0,1]$$$, the probability that point $$$x$$$ is covered by at least $$$k$$$ subsegments is
Second, notice that
So the final answer is