vovuh There's a typo in idea of E "Otherwise, the answer is always "YES".... Its not always YES.

Great contest with amazing set of questions, just a bit inclined towards DIV 2 rather than DIV 3.

Is it first time that ratings have been given to problems before the main testing ??

Great contest indeed and great editorial . . . learnt new things in this contest. . . Make more of these. Thanks

Was this test rated, if it was how much time will it take to update the ratings ?

Problem A was so deceptive. It appeared simple but I ended up spending so much time on it. Only managed to solve 3, but felt the problems were great.

https://codeforces.com/contest/1385/submission/87162089 can someone explain what is the error in this code for problem E ? I can't understand the diagnostics message

Anyone else used binary search for C?87114284

How to solve D in bottom up manner?? And/or Using iterative only??

For 1385E - Directing Edges, an alternative solution can be as described below with DFS, DSU.

Strategy: Creating edge from SMALLER value node to BIGGER value node

Observation: If the directed edges make any cycle, then there is no answer. Else, there is always an answer.

Solution Construction:

1. Make dsu components from directed edge list
2. If u and v both didn't participate in any directed edge, then make an edge from min(u,v) to max(u,v)

3. If u is a normal node and v is a node that participated in a direct edge, then always make edge from u to v

4. If u and v both participated in directed edges and both belong to separate dsu component, then make an edge u->v if root(u) < root(v), else v->u

5. If u and v both participated in directed edges and both belong to same dsu component, then make an edge u->v or v->u in such a way that no cycle occurs.

Solution: 87185374

(This strategy essentially behaves like the topsort solution from editorial. The editorial's cpp code's equivalent strategy is such that it tries to make edge from bigger value node to smaller value node)

I think problem D can add a modify operation — let $$$s_i\gets c$$$ ($$$c$$$ is a character).

Then we can use a segment tree to solve it.

Actually, the calc function in problem D's code is just like a pushup function in a segment tree.

i am still having difficulty for understanding complexity of prob D depth of recursion is log n

there are n possibilities if i am not wrong

e.g. aaaabbcd aaaabbdc aaaacdbb aaaadcbb the rest four with aaaa at the end... like we try all n possiblities but doesn the editorial do an additional step of counting at each step?

vovuh For problem F, the editorial states: We can notice that all leaves are indistinguishable for us. I think this is correct conceptually but do not know how to prove it. Can you share how you come up with this fact? When I first read this problem, I was thinking about the order of choosing different leaves to remove is going to have an impact on the final answer. Obviously this is not true.

I cant understand why problem E's solution needs to --x; --y;? Hoping for reply:)

https://codeforces.com/contest/1385/submission/87187974

anyone ? this python code is getting runtime error on 27th test (last one). i am new to python and have no idea why is this happening.

The Problem A stucked me for a hour.. Anyway I did it, but so slow.

Do we need to memoize in problem D i passed it using simple recursion.

why this can't apply on problem C. for(i=n-2;i>0;i--){ if((a[i]<a[i+1])&&(a[i]<a[i-1])){ break; } } cout<<i<<endl; Any test cases?

Can anyone help me for Problem D. I am getting TLE for Test Case 3. I have followed the approach similar to that given in editorial 87191656

https://codeforces.com/contest/1385/submission/87191814 can someone explain me....in which test case my code is failing...

For the problem B,my solution was perfect and the results were as expected when I tested it on my system...but everytime I submitted the solution,it failed the pretests but the same pretests ran perfectly on my system. Does anyone know why it happened?

how can one apply binary search in problem C, As it is written in tags ?????????????/

Why is the time limit for 1385E - Directing Edges 3 seconds and not the usual 2 or 1 seconds?

Shouldn't the editorial be the same as the tag given, for example, Problem C has the tag Binary Search whereas the explanation is pure implementation. I mean explain the approach that requires algorithms rather than intuitive ones.

Edit — Same goes for D no explanation for the DP approach

Editorial Answer is very good for C. But i implemented it using binary search.

If we think this question as a binary search question then according to me it is a very good binary search question.

Thats why i thought to share my idea.

If we consider f(x) as a boolean function that tells whether the array is good after xth index,then obviously f(x) will become a monotonic function by intution. As by intution we can see that if we take x1>x then for every x1 the array is good. So just find minimal value for x so that the array is good after index x and finally your answer will be n-(total elements in good array).

Hope this solution helps someone.

Did C with binary search. 87141880

What problems should I practice to solve D easily ? Any specific concepts ?

In problem E, is this a standard way of checking if there's a cycle in the directed graph? I did a quick google search and couldn't find such implementation.

I usually go about coloring the vertices and check if I revisit a vertex in current traversal.

Can anyone please tell me why I am getting wrong answer on test 2 for this solution of problem C http://codeforces.com/contest/1385/submission/87148563?? My idea is to find first element from the right such that it is surrounded by a larger element both on left side and right side. Then, we need to remove all the elements before it to make it a good array. Whats wrong in it?

I think D can be further optimised to O(N) by making a prefix array that stores count of a,b,c....z in any prefix. In this way the time of count function will drastically reduce to O(1). And final complexity will become exponential(logn) i.e 2^(logn) which is almost equivalent to O(n).

This way count(l,r,c) can be written as pre[r][c]-pre[l-1][c]

Did anyone solve G by 2-SAT ??

IN ques 1385C — Make It Good
eg .
1
4
1 3 2 4
soln:
step 1 : 3 2 4 c=[1]
step 2 : 2 4 c=[1 , 3]
step 3 : 2 c =[1 , 3 , 4]

the ans is 1 but A/C to this ques ans is 2 how?? please any one hep

Can anyone help me with the problem F(Removing Edges).I am new to graph problems and I am unable to understand the code given in while loop of the editorial

Why am I getting a TLE in D when I have used the same logic, and the code has same time complexity as mentioned in the tutorial?

It would be really kind of any one of you if you could help me out

My Submission : https://codeforces.com/contest/1385/submission/87198924

How to solve problem F if we can remove any k leaves at a time(i.e not only the leaves from a particular nodes but we can pick leaves from any node)?

why E's solution code will get MLE at test1 using Clang++17 while AC on g++17

Need help. I am getting TLE on testcase 3 for the problem D. I have tried similar approach but i am not sure why i am getting TLE. MySolution. Any help would be appreciated.

https://codeforces.com/contest/1385/submission/87155412

Can anyone Please explain why i am getting tle on test case 3 in question D? I have used recursion.

https://codeforces.com/contest/1385/submission/87198479

in the above submission, I just write both the parts separately which were included in minimum in the very first submission and this time I did not get the tle but I am unable to understand what was the problem

Problem D — Not able to understand what is causing TLE https://codeforces.com/contest/1385/submission/87200081

Anyone else solved E using analysis of DFS coloring states? (0 for not seen, 1 for discovered, 2 for visited)

My Solution:

Maintain a global vector of pairs for all the edges in the final solution

For every node, sort its edges in the following manner (directed edges comes before undirected)

Do a DFS starting from any node.

Color current node 1

While considering its neighbors:

A)If directed: (Standard methods used for detecting a cycle)

1) Check if the next node is colored 1; That implies a back edge is present, thus cycle formed

2) If the next node is colored 0, then recursively call DFS on it, push {current node, next node} as pair in edges

3) If the next node is colored 2, push {current node, next node} as pair in edges

B)If undirected:

1) Check if the next node is colored 1; implies a back edge would exist if {current node, next node} is considered an edge, thus convert it into a forward edge and push back {next node, current node} as an edge

2) Check if the next node is colored 0 (I might get a little sloppy with my explanation for this, so please bear with me :D)

Now I choose to always select {next node, current node} as my edge in this case due to the following:

Lemma: If I visit all the directed edges before undirected edges for a node, then conversion of all undirected edges to incoming directed edges for the current node {next node, current node}, will never result in the formation of a cycle

Proof:

If all undirected edges are converted into incoming edges. A cycle consisting of any pair these edges and the current node wouldn't be formed (as both edges are in the same direction). The same applies to all incoming directed edges.

Now for all outgoing directed edges, as per our sorting before we would have already visited these directed edges before encountering any undirected edge for our current node. Let's assume that along the path of the above outgoing directed edge, we reach a node 'u' and encounter an undirected edge linked to node 'v', which we convert into an incoming directed edge ('v' -> 'u'). Now if a cycle were to be formed using 'v', 'u', 'current node' and 'next node', then it wouldn't be possible as both of them are incoming edges ('v' -> 'u') & ('next node' -> 'current node').

Thus for all next nodes colored 0, we will choose the {next node, current node} as an edge.

3) If the next node is colored 2, we do nothing as we established above, it would already would have been treated as an edge {current node, next node} while we observed DFS for the next node (As its already been visited (colored 2)).

After visiting its neighbors, color the current node as 2 (visited and explored).

Finish DFS. Finally print edges.

My Solution: (https://codeforces.com/contest/1385/submission/87158004)

(Here I created a map of the managed undirected edges so as to only treat the edge for only one node, that implies in case of undirected edges, we wouldn't need to check if the next node is colored 2 as if it would, we would have already skipped past it, thus without checking for anything we can treat the undirected edge as an incoming directed edge)

For problem E-Directing Edges I am getting tle in 7th test case. https://codeforces.com/contest/1385/submission/87157571

First I have just checked that if for directed edges is there a cycle or not. If there is not a cycle then I used topological sort after that I assigned directions to undirected edges from left to right.

You can do F using Tree DP in 2 DFSes in $$$\mathcal O (n)$$$ time.

Arbitrarily root the tree.

Let $$$p(u)$$$ be $$$u$$$'s parent and $$$C(u)$$$ be the set of $$$u$$$'s children.
Let $$$\operatorname{in}(u)$$$ be the max number of moves we can do if we only consider the subtree of $$$u$$$.
Let $$$\operatorname{out}(u)$$$ be the max number of moves we can do if we remove the subtree of $$$u$$$.
Let $$$\operatorname{can}_i(u)$$$ be $$$1$$$ if we can remove all the nodes from the subtree of $$$u$$$, $$$0$$$ otherwise.
Let $$$\operatorname{can}_o(u)$$$ be $$$1$$$ if after deleting the subtree of $$$u$$$, we can remove all nodes except $$$u$$$'s parent, $$$0$$$ otherwise.
Let $$$\operatorname{cnt}_i(u)$$$ be the number of children $$$v$$$ of $$$u$$$ which we can turn into a leaf if we restrict ourselves to subtree of $$$v$$$.
Let $$$\operatorname{cnt}_o(u)$$$ be the number of nodes connected to $$$p(u)$$$ which we can turn into leaf after deleting the subtree of $$$u$$$.

Now, $$$\operatorname{in}(u) = \sum_{v \in C(u)} \operatorname{in}(v) + \left\lfloor \frac{\operatorname{cnt}_i(u)}k\right\rfloor$$$; $$$\operatorname{can}_i(u) = 1$$$ iff $$$\operatorname{cnt}_i(u) = \left\lvert C(u)\right\rvert$$$ and $$$k \mid \operatorname{cnt}_i(u)$$$; $$$\operatorname{cnt}_i(u) = \sum_{v \in C(u)} \operatorname{can}_i(u)$$$.
We can compute this in the first DFS.

$$$\operatorname{out}(u) = \operatorname{out}(p(u)) + \operatorname{in}(p(u)) - \operatorname{in}(u) - \left\lfloor \frac{\operatorname{cnt}_i(p(u))}k\right\rfloor + \left\lfloor \frac{\operatorname{cnt}_o(u)}{k}\right\rfloor$$$; $$$\operatorname{cnt}_o(u) = \operatorname{cnt}_i(p(u)) - \operatorname{can}_i(u) + \operatorname{can}_o(p(u))$$$; $$$\operatorname{can}_o(u)$$$ is $$$1$$$ iff $$$\operatorname{cnt}_o(u) + 1 = \deg(p(u))$$$ and $$$k\mid \operatorname{cnt}_o(u)$$$ which we can compute in the second DFS.

Now the answer will be $$$\max_{u}\left(\operatorname{in}(u) + \operatorname{out}(u) - \left\lfloor\frac{\operatorname{cnt}_i(u)}{k}\right\rfloor + \left\lfloor\frac{\operatorname{cnt}_i(u) + \operatorname{can}_o(u)}{k}\right\rfloor\right)$$$.

Code

Can you someone tell me why am I getting TLE for the 4th question (a-good string)? My solution is very similar to the editorial. Here's my submission Your text to link here...

My video editorial for C and E.

for Q.3- Make it good, can someone tell why this is an incorrect logic? Looking for a counterexample.

for(int i=1;i<=n-2;i++) { if(a[i]<a[i-1] && a[i]<a[i+1]) { c=i; }