vovuh's blog

By vovuh, history, 3 weeks ago, In English,

All ideas belong to MikeMirzayanov.

1385A - Three Pairwise Maximums

Tutorial
Solution

1385B - Restore the Permutation by Merger

Tutorial
Solution

1385C - Make It Good

Tutorial
Solution

1385D - a-Good String

Tutorial
Solution

1385E - Directing Edges

Tutorial
Solution

1385F - Removing Leaves

Tutorial
Solution

1385G - Columns Swaps

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +157
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it -48 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    It should always be YES because if there exists an undirected edge where no matter the direction you choose, it creates a cycle, then that means there was a cycle in the graph to begin with which is a contradiction.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think u r right. I had a doubt that in ur statement that there was a cycle in the graph to begin with..... Can u please calrify this statement.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's simply this. Ignoring the undirected edges, if there is already a cycle in the graph, the answer is NO. Otherwise we can always specify directions for the undirected ones and get a YES.

»
3 weeks ago, # |
  Vote: I like it -36 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Only for last three questions.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    There's already Div.4, no need for Div.3 to be too easy,i think.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      'its too easy its too easy', maybe you come at school and start saying "haha guys its very easy math, i dont think math should be that easy at school"

      if you wanna solve hard and interesting problems then participate in div1, guys in div3 are studying, no need to belittle the value of their tasks

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I think the rating of some Div. 3 problems are assigned manually, it's mentioned in this blog.

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    It is rated and you'll get the result after system testing(no longer than a day).(Forgive my poor English)

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it +19 Vote: I do not like it

      Why would someone have to forgive your English? It's just a language to express your thoughts. This is not the first language of most of the people here. So, the possibility of making mistakes is too high. No one should ever bother about these kind of things.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        at least on this site, if you are to able to communicate, that should be pretty much it.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Hi, I see issues with your dfs function, but not sure if this is the cause of runtime error.

    1. You are not using the visited array to check if you have to perform the dfs on child nodes. You're only using the value of parent node. This suffices in case of trees, but for general graph you may get a cycle which your function is not figuring out.
    2. You are passing the set<int> recur by value, so you may end up using O(n^2) memory in the worst case. As this recur set will be copied for each function call. Pass the recur set by reference: set<int>& recur. If a child is completed but the parent is still there, you don't want the recur set to get cleared. Do recur.erase(node) on the last line of dfs instead. Detect Cycle in a Graph
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Pass string s by reference in your recursive function. Like string& s.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Thanks. Got it. Can you please explain why passing by reference does not give tle? and we should always use pass by reference or it was specific for some question?

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

            When a function is called, the arguments get copied, unless they are passed by reference. So here your string s, which can be of length 10^5, was being copied in each recursive function call. When we pass by reference the very big string does not get copied in each function call, only a reference to string s is being passed in each function call.

            When to use pass by reference, and when to use pass by value depends on what you want your code to do. Pass by reference vs value

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              What about this then? Edit: He just needed not to pass the whole string, it's feasible if we pass s/2 every round, even with pass by value.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I was dealing with the same problem, I noticed that many people have submitted kind of the same code as I wrote and got ac..but I was getting tle for no good reason.. but now after passing by reference it got accepted... here is my code which got ac.. and here is the one getting tle :/

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                maybe its because you were passing substrings.. and as per nilayjain said.. "very big string does not get coppied in each function call" your strings were getting smaller in each call, while mine was as big as the original one in the every call.. thats why i was having tle :(

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  It doesn't make sense to me why one would pass a value that does not change in a recursive function. I mean, just declaring it global makes it a lot sensible.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                ya.. maybe we should always declare large data structures globally, just to avoid these situations :/ and ya.. it still doesn't make any sense :/

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks ago, # ^ |
                    Vote: I like it -20 Vote: I do not like it

                  Global variable aren't a good practice, one should refrain from using them. They are the places where most of the bugs tend to reside. Pass by reference is the key!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  "Global variable aren't a good practice, one should refrain from using them. They are the places where most of the bugs tend to reside." ???????

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks ago, # ^ |
                  Rev. 2   Vote: I like it +6 Vote: I do not like it

                  Yes, you are right, it is a good idea to declare large structures globally, especially when you're using those structures in different functions. But this is not a rule of thumb, it all depends on situation. And if it is still not making sense, think about the complexity of the recursive function for 2 cases we are discussing above:

                  1. Passing the substring by value: complexity is = n + n / 2 + n / 4 + ... + 1 = 2 * n. (since you divide the string in 2 halves and then pass it)

                  2. Passing the full string by value for all recursive calls: complexity is = n + n + n ... (n times) = n^2. This is because even though your recursive function is taking lesser time n, n/2, n/4 etc, but copying the string still takes n time for each recursive call. This will be TLE for sure.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Thanks !! Got it :D

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks a lot.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks, Bro you really save the day!!:)

              I was stuck in the same too

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks for the help I was stuck with the same problem

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks that really helped a lot. I was stuck for hours at this.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can E be done throug BFS?nilayjain

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone else used binary search for C?87114284

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i did it

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I still didn't get the Binary Search approach, can you explain? Thanks

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        let's say $$$P(x)$$$ tells us whether by erasing the prefix of length $$$x$$$ the array becomes good (this is the subarray $$$[x+1\dots n]$$$). The key is that if $$$P(x) = true$$$, then $$$P(x+1) = true$$$. So, apply binary search to find the lowest $$$x$$$ such that $$$P(x) = true$$$. Now for a fixed $$$x$$$, to know if the array becomes good we do following:

        Let's say $$$L[i]$$$ tells us whether we can put all elements from left side of $$$i$$$ before $$$i$$$ in the array $$$C[]$$$ or not.

        $$$L[i] = \begin{cases}true & \ \text{ if } i = x+1\\L[i-1] \ \& \ A[i-1] < A[i] & \text{ if } i > x+1 \end{cases}$$$

        Let's say $R[i]$ tells us whether we can put all elements from right side of $$$i$$$ before $$$i$$$ in the array $$$C[]$$$ or not.

        $$$R[i] = \begin{cases}true & \ \text{ if } i = n\\R[i+1] \ \& \ A[i+1] < A[i] & \text{ if } i < n \end{cases}$$$

        Now, if there exists some $i \in [x+1\dots n]: L[i] = R[i] = true$, then $$$P(x) = true$$$; otherwise $$$P(x) = false$$$.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what was your approach for this question using binary search?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also did it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Look at this submission. Here $$$dp[i][j]$$$ is the minimum cost of make good the range starting at position $$$i$$$ having length $$$2^j$$$. The transitions are the same as recursive approach.

    $$$dp[i][j] = \min(dp[i][j-1] + \text{cost}(i + 2^{j-1}, i + 2^j-1), dp[i+2^{j-1}][j-1] + \text{cost}(i, i + 2^{j-1}-1))$$$

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for the reply. But I can't understand fully. Can you please explain how you are finding which character should come in the range I to 2^j-1 and what dp[0][I] means? And what does the j-i+1 in the cost function mean?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Let's say $$$k=\log_2 n$$$. Then, if the range is of length $$$2^p$$$, the character here must be $$$\text{'a'}+k-p-1$$$, cause each time we half the length of range, the character augments in 1. Now, the cost at some range is the amount of characters on the range that are different of the right character.

»
3 weeks ago, # |
Rev. 5   Vote: I like it +1 Vote: I do not like it

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)

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Approach the runtime of this problem in this way: For given string of length N and target of C-good string(C represents a generic character). We have 2 choices:

    Either we make the 1st half C-good and the 2nd half (C + 1) good, or we make the 1st half C + 1 good and the 2nd half C good. Let's denote T(N) as the runtime to solve length N. Then to solve the smaller subproblem it takes T(N / 2) time. It also takes O(N / 2) to count the cost of making half of the string all character C. So we have the following formula:

    T(N) = 2 * (T(N / 2) + O(N / 2)) = 2 * T(N / 2) + O(N).

    Applying the master theorem, the run time is O(N * logN). This is exactly the same with how we analyze merge sort's runtime.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      pefect!! can you please help me in one more thing?

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

      i had precalculated the count...

      isnt my solution O(n)?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        I think you are right. T(N) = 2 * T(N / 2) + O(1), which is O(N).

        The preprocessing takes O(26 * N), so it is O(N) in total. Nice work by the way to pre-compute costs!

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          T(N) = 2 * T(N / 2) + O(1) has O(N). not O(logN)..

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah, you are right, T(N) = a * T(N / b) + O(N^d), if a > b^d, T(N) = O(N^logb(a)) a = 2, b= 2, d = 0, so T(N) = O(N). I edited my comment.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You explained in a good manner.Thanks!

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can't we count the cost of making a substring into a letter in constant time by pre-calculating the cost to convert the string into in each letter. This will reduce time complexity to O(N) and 26*N needed for pre-calculation. Correct me if I am wrong. I know that O(N *logN) is actually smaller than O(26*N)

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think you are right. It is asymptotic[user:Shameek]ally better than O(N * logN). You can check out 87155344 by Shameek. He solved this problem by pre-computing costs.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it is similar for running the count function (L,R) for Log(n) time ..(i.e. for the number of level in rec tree) PS:correct me if I am wrong

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I did solve D using recursion. Actually, at each step, you will calculate which half of the string you need to make a 'c'-good string; but this doesn't mean that the half which will require the minimum number of changes will give the least total number of moves ultimately.

    Therefore, you need to call on both the halves and get the value of making these halves a 'c+1'-good string and finally you will compare the value in the whole of both these halves with each other and return the minimum value. So, all in all, you will be traversing the string twice (i.e 2n) and yeah the depth of recursion will be long n only.

    link to my solution in C++: https://codeforces.com/contest/1385/submission/87154630

    link to my solution in python: https://codeforces.com/contest/1385/submission/87147603

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    well input is based on indexing from 1 to N, where as vuvoh's code is reading input from 0 to N minus 1. like input will consider nodes 1, 2, 3, 4 but vuvoh's code will consider them as 0, 1, 2, 3 this is the reason he did x + 1 and y + 1 in output statements.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      so it is not necessary,right? thanks

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes , Not necessary but then u have to create adjacency list of "v+1" nodes as last node will be "v".

        You can check my solution for E : 87175293

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    We do not need to memoize because there is no overlapping subproblems. Simple recursion gives you O(N * logN) runtime already.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Why the complexity is O(NLogn)? It should be exponential. Can you please prove the complexity. Thanks in advance. PS: I read the prove using master's theorem. But is there any other way around to calculate it without using theorem.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can go descending by the recurrence, and see a pattern, then you can proof the pattern by using induction.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 7   Vote: I like it 0 Vote: I do not like it

    check these cases:

    4

    4

    4 3 3 4

    4

    4 3 3 2

    5

    4 3 3 3 3

    5

    4 3 3 3 5

    edit:- sorry for so many edits but testcases were coming in single line so i had to edit

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Difference between pass by reference and pass by value. Your same code I made the string as a pass by reference and got an AC. sub link. Pass by value creates copies each time in the recursion stack while pass by reference doesn't.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    unordered set does not preserve the order in which you insert the elements. In your case, your set could eliminate the duplicates, but didn't preserve the order.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe I'm wrong ...but that's why I used unordered sets...they are not sorted...and sets don't insert duplicate elements ,and as while printing the elements...they are printed in reverse order so i stored them in another unordered set and the result was as expected.You can check the code on your system. If it fails then my bad. If I'm wrong correct me,I'm still a newbie. Thanks

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i think u misunderstood me. see, in an unordered set A, if i insert [1,2,3,4,5,6,7,8,9] and now print the contents of A, the output wont be [1,2,3,4,5,6,7,8,9], it might me something like [5,6,3,1,4,...], the order of the elements stored in A is random.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah sorry,I googled it.I was not aware of this thing.Thanks:)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    binary search soln :- https://codeforces.com/contest/1385/submission/87194610

    explanation:- since we have to find the length of smallest prefix which we have to remove so that the remaining array satisfy the condition given in question we can binary search over the length of prefix if we found that after removing this length of prefix we can make array good we just have to set highlimit = middle(so that we can find smallest as if after removing prefix of length x we are getting good array so same will be for prefix of length greater than x) so now we can check for smallest prefix by this method........... sorry for bad english

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So, as we know, it should be possible to test in an O(n) complexity whether or not taking away a prefix of length k can work, simply by imitating the process. We also notice that, if we can achieve a "good" array by taking away a prefix of length k, we can also achieve a "good" array by taking away a prefix of length k+1. Therefore, we can apply binary search on k in the range of [0,n-1], and with an O(n) complexity of verification, we can solve the problem using binary search with O(nlogn) complexity.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Check the submissions, or the comments section already has multiple implementation of all problems

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did C with binary search. 87141880

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes using colors is pretty standard. You can check for the cycle while in the same dfs you do to construct the topological sort.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

»
3 weeks ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like 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]

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Did anyone solve G by 2-SAT ??

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I read 2-SAT :).

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

    I have done it using 2-SAT. Thanks.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain more? I was thinking of using 2-SAT as well but 2-SAT's assignment won't guarantee minimum number of columns swapped (afaik), how do you get around this?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That is actually not 2-SAT. You are making components for a vertex and it's complement and taking the component with smaller size. Please correct me if I am wrong.

      This is what I was doing-
      Consider each column as a node.
      If two nodes have same number in any row then one of them should be flipped, this gives us the relation of (x^y) which can be written as ((x or y) and (not x or not y)).
      If two nodes have same number in opposite rows then either both should be flipped or none should be flipped. So that gives not(x^y).

      not(x^y)
      not((not x and y) or (x and not y))
      ((not(not x and y)) and (not(x and not y))
      (x or not y) and (not x or y)

      Now both the conditions are reduced to CNF so maybe we can apply 2-SAT. I could not implement this idea and also problem requires that there should be minimum number of 1's in the answer. I am not sure how to do that either.

      I am not very good in 2-SAT so it is possible I might have missunderstood you. Please correct me if I am wrong.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is 2-SAT brother according to my understanding . Because For every column it has 2-states . either swap or no swap. So I took the other state as the complement. and then i am uniting those states. Making relations between states.

        https://en.wikipedia.org/wiki/2-satisfiability

        See this. I assume i did this only . Boolean satisfiability.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Complement in my sol means that it is a swap. So i have taken that states size as 1 and 0 otherwise.

        Otherwise if you are not satisfied , then I can't say. Because it is a new topic for me , I just read it today. But accroding to me this is 2 — SAT.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        I was thinking of same approach for optimizing number of 1's I was thinking to construct a graph with 12..n numbers as nodes and they are connected if a they share a column.I wanted to take each component of this graph and do 2SAT on all columns involved with the numbers of that component. They must have only 2 possible solution states so minimum can be taken.( Last part somehow made sense to me and i didn't prove it so not sure )

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah TopGun__ has done that. I was not sure about only 2 solution states but his solution does that and is correct. The assignment of values could have been done greedily. Thanks oly399 and TopGun__.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain Problem G. I am not able to understand the editorial.

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read the problem statement carefully.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is {1,3,2,4} good? No because you can't obtain a non decreasing sequence(the 2 will create the problem) So, remove prefix 1 from the array, increment the ans = (no of operations) by 1

    Now we have {3,2,4} Is it good? No, because again the '2' present in the middle will cause the problem (The c array will look like {3,2,4} or {3,4,2} or {4,2,3} or {4,3,2}

    Now remove prefix 3 from the array, increment the ans by 1. New ans = 2

    Now we have {3,2} Is it good? Yes, because we can obtain c as {2,3} which is a non-decreasing sequence.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, exactly this is my idea to find the element which causes the problems and that's the one which is surrounded by greater elements on both the side as in this case example 2 is surrounded by 3 and 4. But my solution fails for some test case which i can't figure out.Can you tell me any test case ?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Check the case for arr = {2,1,1,2} Your answer is 0 However answer should be 1 as {2,1,1,2} isn't good, but {1,1,2} is

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Pass string by reference.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why does not passing string by reference cause a TLE? Or in other words, how does passing string by reference optimize the time complexity?

      Does it decrease the constant in the Time Complexity expression? If yes, it would be kind of you to explain

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        If you don't pass the string by reference then the recursion call creates a whole copy of that string and takes O(n) time and that is the reason for TLE.

        And this is not only for string actually, but it holds for any type of argument.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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)?

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't pass string by value, pass by reference.

    N.B. Why are you passing an unnecessary 2D vector to function? And it is strange that you pass that vector by reference but pass string by value.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah i get it but then why my second submission got accepted there also I did not pass string by reference?

      and that 2D vector is prefix array to calculate the required number of changes between l to r

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I still got TLE using 2D prefix array. Guess yours was just a little faster to beat the time limit.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          i don't know what was happened with my code so yeah maybe it just a luck

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You accepted solution is also almost close to time limit. I think when you are using function directly then compiler has to perform some overhead computation to save calculated value and finally clear them which results in tle.

        And 200ms is not much time. You can't perform so many overhead computation in this time.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    string fk=ss will copy full string from ss to fk. It will happen on each iteration which will lead tle.

»
3 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Instead of doing this, u can find out whether graph contains cycle or not using Topological sort only (if the size of toposorted list != n then it contains cycle , answer is "NO") after this store position and mark all undirected edges from u to v if u is before v in toposorted order otherwise v to u .

    See : 87175293

»
3 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My video editorial for C and E.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, i used the similar logic but it fails for cases like {2,1,1,2}.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read the editorial carefully. You don't even explain your logic and expect others to find errors.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @Lazyc0d3r If you can't help, just keep quiet. I don't need your advice. :)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    5 2 1 1 3 2 what would be the answer for this testcase.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This mistake is very common, I made it too. You are passing arguments by value which is very costly when the function gets called recursively. Just change the string argument to string& a in count function and it should just work fine.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try string & a,not string a.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain where am I going wrong in E? https://codeforces.com/contest/1385/submission/87204598

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 6   Vote: I like it 0 Vote: I do not like it

    change vector<int> A(2*n),B,C; to vector<int> A(2*n),C; vector<int> B(n);

    change B.emplace_back(A[i]); to B[j]=A[i];

    because here: if( A[i] !=B[j] ) B vector at j index may overflow.Try again.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please explain it as well.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it +4 Vote: I do not like it

      Sure ^_^

      TL;DR: if you have calculated the maximum number of moves for the tree rooted at a vertex, find a formula to calculate it for its children.

      Let's notice, first of all, that if we choose a vertex $$$v$$$ and consider it as a root, then we can calculate the answer for that vertex: that is, we can find the maximum number of moves if at each move we remove $$$k$$$ leaves such that each leaf was a child of it's adjacent vertex for the graph rooted at vertex $$$v$$$. A point to note: in particular, this means that we never remove vertex $$$v$$$, as it never becomes a child of another vertex, as it is the root itself.

      Now another lemma: for a fixed rooted tree, the order of operations is not important. As long as there are leaves in the rooted tree (note again, that we don't count the root as a leaf), we can keep removing them, and any sequence of moves leads to the same number of moves.

      So for a given vertex, we can calculate this by DFS. Let's calculate it for vertex $$$1$$$.

      But we also maintain a map: $$$map<pair<int, int>, bool> ok$$$, which I define as $$$map[{v, par}]=true$$$ if in the tree, if $$$v$$$ is child of $$$par$$$, can we remove all children of $$$v$$$, hence making it possible for $$$v$$$ to be removed from $$$par$$$.

      We also store $$$count[v]$$$: number of direct children of $$$v$$$, each denoted by $$$u_i$$$, such that $$$ok[{u_i, v}]=1$$$

      Now let's say we have calculated the maximum number of moves $$$moves[v]$$$ in rooted tree $$$v$$$. How to do calculate $$$moves[u]$$$ for each child $$$u$$$ of $$$v$$$?

      Here's where re-rooting comes in. We have the recurrence relation

      $$$moves[v]=moves[par]-count[par]/k+(count[par]-ok[{v, par}])/k-c/k+(c+ok[{par, v}])/k$$$ where $$$c$$$ is the number of vertices adjoint to $$$v$$$, except $$$par$$$, such that $$$ok[{c, v}]=1$$$.

      The formula may look a bit involved but it is really intuitive so I recommend you to come up and prove it yourself. Lemme know if you have any doubts :)

      The answer is, of-course, the maximum over all $$$moves[v]$$$

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In E i am getting TLE in test case 7 with this code https://codeforces.com/contest/1385/submission/87209114. Can someone help me why i am getting TLE because when i declare the variables global, it is getting accepted.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

cntl=(r−l/2)−count(s[l…mid),c)+calc(mid,r,c+1)

In problem 1385D-Good String can anyone kindly explain me this expression? Why this is (r-l)/2 and why they have subtracted count(s[l..mid),c) from that?

Thank you.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1385/submission/87123118 can someone tell me a test case where my code fails? I tried to find one but it says "875th number differs" and I cant see that particular one to make changes to my code.

»
3 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Codeforces Nibba Starter Pack: - iS ThE cOnTesT RaTeD? - here hahaha haha upvote my memes, I memer - downvote comments in heaps cuz QUARANTINE - HaVe a LoOk At mY yOuTuBe chAnNeL

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

de

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please don't copy your whole code here, it might spoil the solution.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sry im new to codeforces

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        if you do want to do it, there is a part under the codeforces icon when you write your comment that supports spoilers.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

how the ans is 5.

Thanks in adv

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    aaaabbcd , total changes = 5
    aaaa bbcd , left half has all chars = 'a'
    aaaa bb cd , left half has all chars = 'b'
    aaaa bb c d , both halves are of length 1

    So this is a a-good-string with 5 changes

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Can anyone explain to me what is wrong in this code?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I can give you the generator's code. Note that you need to have testlib library locally to compile it.

    Spoiler
    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 4   Vote: I like it +3 Vote: I do not like it

      Thank you I just have some trouble with this line in solution:

      if (leaves[a].size() == leaves[b].size()) return a < b;

      I don't understand, why code without this line gives WA and with this line gives AC

      Can you explain?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        If two vertices have the same size of $$$leaves_v$$$ and you don't compare them by some other metric, it's undefined behavior. Standard set can't handle it (because can't compare which one is less than other) and you don't know what it will return, so it can lead to RE or WA easily. This is a pretty standard bug.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    If you participate without a single submission, you are considered to not participate in that contest. Simply, you won't gain nor lose any rating.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What if I participated in the contest and submitted a solution which got WA on the first testcase itself. So will that affect my rating?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for information.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting TLE for Problem E. I have tried optimising this code but not getting AC. My Submission: https://codeforces.com/contest/1385/submission/87226980 .

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Check this out : 87161106

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In B you are given a permutation of length n. Now the question is saying that they are merging the permutation of n with itself. So now you just have to find the original order of the permutation. Merging is done in such a way that the relative order is maintained in the merged permutation.

    Like for e.g- original permutation is 5 3 2 4 1 and the merged permutation is 5 3 5 2 4 3 2 1 4 1

    the answer to the question is simply 5 3 2 4 1 and you can see that the relative order is not distorted 3 if always coming after 5, 2 after 3 and soon.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is there any iterative way to solve problem D?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

using unordered_set in Problem B. gives WA. why?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com/contest/1385/submission/87232399

Can somebody help.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why i got WA in B with this submission ? 87147919

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    unordered_set stores the numbers in any order, it's not reliable for restoring the permutation.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I believe you wanted to write ((a[i]>a[i+1])&&(a[i+1]<a[i+2]))... And here is a test case 11 5 8 2 7 5 5 6 7 6 Your code gave the output 3 while the answer is 5...

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hello,Please tell me why my code is not getting submitted,ques C,make it good. link:https://codeforces.com/contest/1385/submission/87280302

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I guess you understood that we need to find the last index in the array such that the values to the right of it are greater and those to the left are smaller and are our answer will be that index, but the problem with your code is that the immediate value to the right of desired index might be equal to the value at that index and your code will in that case skip that position and give the wrong answer,

        I made some changes in your code, check this submission 87360403

        I just used a variable flag that will indicate that there are values to the right of current position that are greater than the value at current index, and if it is true and the value at current position is less than the value to the left of it then we have found our answer.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks...Are you connected in any social networking site like facebook,instagram. or r in in telegram so that we can discuss problems there.Please share those linkes if possible.Thank You

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I have sent you a personal message....

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, why the answer for this test case is not 5? 1, 2, 10, 7, 4, 3, 11, 10, 9, 7

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For G, after the contest, I found a different, possibly simpler, greedy algorithm.

  1. Start with an empty set of swaps (the result)
  2. Work out how many instances there are of each value in each row, and where they are.
  3. For each value in [1, n]:
    1. If there aren't a total of precisely two instances fail
    2. If there is one instance in each row then we are done
    3. If there are two instances in one then we can fix this by swapping either of the columns it occurs in. Swapping a column, however, will either cause a new value to be duplicated, or fix a duplication. If a new value is duplicated then we need to do a further swap to fix this. For each initial column work out the chain of swaps that will result.
    4. Work out the cost of each chain. The cost isn't simply the length, since some swaps will reverse swaps done in fixing previous duplications, in which case they reduce rather than increasing the cost.
    5. Take the cheaper chain, and apply all swaps in it to the rows. For each swap in the chain, if it wasn't previously in the result then add it. If it was then remove it.

I haven't proved that this always gives the best result, or worked out its theoretical performance, but my Python implementation of this passed all the tests well within the time limit.

See https://codeforces.com/contest/1385/submission/87241176

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

87210508

I seem to be getting an error for my solution of Problem F on some test of testcase 19 and can't seem to figure out where the error is. Can someone here help me out ? Thanks in advance

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

Please anyone explain me why my code of question 4 is resulting in TLE on testcase 3.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem A i calculated the minimum and double checked whether the solution is valid or not. during the constest did some work on pen and paper and felt like this will work can someone please explain my solution mathematically ? i know it sounds stupid asking someone to explain the solution i myself wrote but i just had the intuition that it might work now i want to understand mathematically why my solution worked! thanks in advance!



#include<bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; while(t--) { long long int x,y,z; cin>>x>>y>>z; long long int a,b,c; a=min(x,y); b=min(x,z); c=min(y,z); if(max(a,b)==x && max(a,c)==y && max(b,c)==z) { cout<<"YES"<<"\n"; cout<<a<<" "<<b<<" "<<c<<"\n"; } else { cout<<"NO"<<"\n"; } } }
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

vovuh Both solutions are the same while one is giving the wrong answer for problem F. Wrong Answer Accepted

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Those solutions are not exactly the same:

    In your WA solution, you call leaves[v].erase(leaf) and then s.erase(v)

    In your AC solution, you call s.erase(v) before you call leaves[v].erase(leaf), and since v points to s.begin(), the operation leaves[v].erase(leaf) will use a different value of v in your AC solution.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't get what difference does it make changing the order of execution of leaves[v].erase(leaf)

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        v is a pointer to the first value of s (s.begin()). If v was defined as v=s.begin(), rather than v=*s.begin(), then there would be no difference between the two solutions. But since v points to s.begin(), when you remove v from s, then call leaves[v].erase(leaf), the value of v here is different from the value of v in the previous line

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C

Submission 87154272 — I found the first minima starting from end of array. However getting Wrong answer on test case 2. Can anyone tell me where I am wrong? Any help will be really appreciated

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem basically asks you to find out if the array sorted in ascending or descending order, and your code does that. However, the new array c can be constructed by taking elements either from the beginning or the end of the array. So, if the original array looks like a pyramid [1, 2, 3, 4, 5, 4, 3, 2], the answer is still 0 because:

    b = [1, 2, 3, 4, 5, 4, 3, 2], c = [] b = [2, 3, 4, 5, 4, 3, 2], c = [1] b = [3, 4, 5, 4, 3, 2], c = [1, 2] b = [4, 5, 4, 3], c = [1, 2, 2] b = [4, 5, 4], c = [1, 2, 2, 3] b = [5, 4], c = [1, 2, 2, 3, 3, 4] b = [5], c = [1, 2, 2, 3, 3, 4, 4] b = [], c = [1, 2, 2, 3, 3, 4, 4, 5]

    but your code stops when it finds the pyramid head (element 5)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, Thank you for your answer. However, I am not finding the head but the minima from the end. The point where the numbers makes a V when plotted. We need to shed the numbers before the bottom most point in the V. If that point does not exist then my code returns 0.

      Example — 8, 1, 2, 3, 4, 3, 1

      Here [8, 1, 2] make a V. If we were to traverse from the end, 1 would be the point of minima

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Apologies, I was reading the code the other way. I debugged your code, and even though your logic is sound, but you're using continue prematurely. The issue lies here:

        if(n<=2){
            System.out.println("0");
            continue;
        }
        

        Since you're using continue before taking the input, the program is then reading the test case, but thinking it is a part of the next test case. To see it for yourself, try inputting the data line by line and you'll see what I mean, try the first 7 test cases and you'll see. To fix it you just need to move the continue to the line after taking the array input:

        if(n<=2){
            System.out.println("0");
        }
        int a[]=new int[n];
        for(int i=0;i<n;i++){
            a[i]=Sc.nextInt();
        }
        
        if(n <= 2)
            continue;
        

        Hope this helps!

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, Can you explain why the answer of this case is 2?

      1, 2, 10, 7, 4, 3, 11, 10, 9, 7

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think the answer should be 5 for this test case, not 2

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So I was trying problem D, in the first submission 87154198 I tried to loop over the string every time to count the number of characters, and that is probably a stupid thing to do. But I tried it again, 87258034 and basically I prepared an array beforehand that contains the sum of characters up to that point, and that made the backtracking O(1). I know that I'm doing a (26 * 131072) iterations per test case, but that's it. Everything else is O(1), but I'm thinking that the posted solution doesn't do a lot better. Does anyone have any ideas why is that? Any help is appreciated

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

task D. prefix sum solution. O(N*log(N))

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, how do we construct a topological sort of all the vertices of the graph, since we are doing the sorting only on the vertices which have directed edges, which doesn't account for the vertices which might not have even one directed edge specified?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome contest! (Although I managed to get only a few questions right...)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello! For problem C, I saw 'binary search' as a problem tag. If anyone here is able to produce a solution as to how one uses binary search to solve the problem, I will greatly appreciate it.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell why this code is not passing all the test cases,Ques C,Make it good.Link:https://codeforces.com/contest/1385/submission/87280302

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain the editorial of Problem G. I am not able to understand the editorial.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "Otherwise, let r1[i] be the number of row of the number i in the column c1[i] and r2[i] be the number of row of the number i in the column c2[i]. If r1[i]=r2[i] then it's obvious that at exactly one of these two columns should be swapped. The same, if r1[i]<>r2[i] then it's obvious that we either swap both of them or don't swap both of them."

    What does this statement means in the editorial?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I got a message that my code matches with another person's code and I commented on the page where you have to tell whether you have plagiarized or not and I still haven't got a response, so should I wait it out or should I mail them my queries...

I am new to this platform so I am unaware of the procedures. Help.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E was easily searchable, I think. A quick search on how to convert undirected graph to directed acyclic graph got me this result.

https://stackoverflow.com/q/45752331/7121746

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the editorial solution of problem C

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody elaborate on this part in F please:

				int leaf = *leaves[v].begin();
				g[leaf].erase(v);
				g[v].erase(leaf);
				st.erase(v);
				st.erase(leaf);
				leaves[v].erase(leaf);
				if (leaves[leaf].count(v)) leaves[leaf].erase(v);
				if (g[v].size() == 1) {
					int to = *g[v].begin();
					st.erase(to);
					leaves[to].insert(v);
					st.insert(to);
				}
				st.insert(v);
				st.insert(leaf)

Shouldn't we insert v when we are done removing all the k leaves? Also what is the part if(leaves[leaf].count(v)) for?

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone tell me why this solution passed for task D? I think this solution should have given TLE.Submission. PS: Complexity is O(NLogn). But can someone prove it without using master's theorem?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1385/submission/87268081 can anyone explain what this code get Memory limit exceeded on test 7 !!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This was my first contest and I don't have more than a week practicing in this page. I just wanted at least to complete the first problem but I didn't. Now, I have been watching the "tutorial" of A problem, and I keep don't understand why it says: "If y≠z then the answer is -1, because z is the overall maximum among all three integers a, b and c and it appears in two pairs (so it should appear at most twice among x, y and z). Otherwise, the answer exists and it can be x, x and z (it is easy to see that this triple fits well)".

Can someone explain me that?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F: http://codeforces.com/contest/1385/submission/87375086 wrong answer test case 20. I can't find my error.what's wrong in this. I used connect[] and leaf[] array for counting number of node connected with j node and number of leaf node connected with j node...help me..thank you

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my solution for problem D https://codeforces.com/contest/1385/submission/87450593 and its showing time limit error. Can anyone please tell me the mistake (I have used recursion as explained in tutorial).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the time complexity of Problem D not exponential but O(N * log N)?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Write the recurrence relation out. It will look a lot like merge-sort. T(n) = 2*T(n/2) + n

    This submission might help see the recursion better.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me in problem F. Why does the solution in the tutorial add the leaf again into the set st? I fell it to ensure that st doesn't become empty. Any other reasons for it?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Because the set with the custom comparator doesn't update the order of elements itself, you need to update it "manually". But during one move very few elements change so we can just remove them and then insert back with updated values.

»
3 weeks ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

vovuh The test cases are not good for Problem F. My code fails when I don't sort the nodes according to their number (integer representing the node id) when they have equal number of leaves, while it gets accepted when I sort them (according to id, when they have equal number of leaves).

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In directing edges question
5 5
0 2 1
1 1 5
1 5 4
0 5 2
1 3 5

if we do topological sort of all the directed edges we get
1 , 3 , 5 , 4
and after finding topological sort we check left index and right index and then assign the dirrection from left to right . in case of 0 2 1 two is not present in the topological sort list then how we assign the direction . Anyone help please

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D 88140376.Can someone help me out with time limit error? could someone please suggest some changes to the code. Thanks in advance.

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I have tried to make editorial for questions A-E . please have a look. Language :- Hindi

https://www.youtube.com/playlist?list=PLrT256hfFv5UWlctr-HughML5i0U-zFYy