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 ?

https://codeforces.net/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.net/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.

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

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

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.

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.

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

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.net/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.net/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.net/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.net/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.net/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)

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; }

https://codeforces.net/contest/1385/submission/87201950 can anyone explain why my code giving tle for problem D. it is similar to editorial solution.

Can anyone tell what is this code wrong for solution of Problem B? I iterate from left to right and take all integers in permutation1 until the first integer of permutation1 appears again. Then I do the same for second interger. But it throws wrong ans.

I am WA on test case 2 for E. I have used the same topo sort approach. Where am I getting wrong? 87207905

Detailed editorials with appropriate proofs and implementations on my YT channel

Editorial for problem C: https://youtu.be/vjRHaZb16bU
Editorial for problem D: https://youtu.be/9gVpnosPKec
Editorial for problem E: https://youtu.be/yn6ZPaqwlso

Enjoy watching!!

If anyone need, Detail Explanation(not a video tutorial) for D Here

If anyone is interested in rerooting and DP on trees method to solve Problem F: here is my submission :) 87210583

Can anyone help me out with this solution for C — Make it good? Link to solution. It is giving correct solution on test 2 on my local machine, but wrong answer on the site. I changed Language from GNU C++14 to GNU C++17(64), it passed a few more test cases but again it gave Wrong answer. Can anyone tell me why this is happening? Thank you.

de

Can someone explain why this wont pass third test case for problem B? 87097426

somebody please explain me the tc 3 of Problem D :: 8 bbaaddcc

how the ans is 5.

Thanks in adv

В задаче Е опечатка в разборе. В Третьем слове вместо «если» написали «ели»

Can i get a author's testcase, which doesn't fit completely in CodeForces tasks set of testcases? (for example, the 2nd testcase from task F)

Is rating updated ??
I participated the contest but then I had to go somewhere else, so i leaved the contest without single submission.
So is this some kind of feature of codeforces to not involve registered but not participated contestant in rating changes?

Can someone explain how the complexity of the 4 th solution is (nlog(n)) ?

For 1385F - Removing Leaves, there exists a O(n) solution based on rerooting of trees concept.

Check this out : 87161106

i am kinda having hard time understanding B . can anyone plz explain the problem and tutorial to me . thanx in adv.!!!!!

Is there any iterative way to solve problem D?

using unordered_set in Problem B. gives WA. why?

Hi Guys, I couldn't solve question E during the contest.So I thought to give it a try after reading the editorial. I have implemented recursive method of topological sorting before , so i tried to do it by iterative method, but somehow i couldn't get the logic right .

This is the case on which my code fails 3 3 1 1 2 1 1 3 1 3 2

Here is the my code : https://codeforces.net/contest/1385/submission/87232399

Can somebody help.

IN Codeforces Round #656 (Div. 3) Question C If I use the logic: grp=2; if(n>2) for(int i=n-3;i>=0;i--) { if(a[i]>a[i-1]&&a[i-1]<a[i-2]) break; grp+=1; } cout<<grp<<endl;

How is the logic wrong?? Can anyone give me a corner case?