awoo's blog

Educational Codeforces Round 105 Editorial
By awoo, history, 7 weeks ago, translation, In English

1494A - ABC String

Idea: BledDest

Tutorial
Solution (Neon)

1494B - Berland Crossword

Idea: Neon

Tutorial
Solution (awoo)

1494C - 1D Sokoban

Idea: adedalic

Tutorial
Solution (awoo)

1494D - Dogeforces

Idea: Neon

Tutorial
Solution (Neon)

1494E - A-Z Graph

Idea: adedalic

Tutorial
Solution (adedalic)

1494F - Delete The Edges

Idea: BledDest

Tutorial
Solution (BledDest)
 
 
 
 
  • Vote: I like it
  • +78
  • Vote: I do not like it

Comments Comments (71)
»
7 weeks ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Good contest and editorial!

→ Reply
»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

First time I will reach Pupil

→ Reply
»
7 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Thanks for EaRly editorials.

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

    It was a very fast Editorial Indeed. Anyhow, I loved the round. Thanks to authors !

    → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the editorial and codes!

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally the editorial :)

→ Reply
»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Can anyone please help me understand why my approach to B is wrong? I have basically done a recursive backtrack since the possibilities are very small. 108948906

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

    Your approach paints black twice on the same cell for this case 2 0 0 1 2.

    0 0 1 1
0 0 0 1

    At some point, Your array will become this. And It falsely identified it as correct solution.

    Modified code

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

    In this case , your code may first fill the top row just as the green line (n-1 case), then fill the rightmost column just as the blue line (n-1 case). However, the top-rightmost cell (in red circle) is covered twice , which is incorrect .

    when L=0,U=n-1,R=n,D=0 ,your code will output "YES" but the correct answer is "NO" .

    (Sorry for my poor English :P)

    → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank for the (early?) editorials. I love the contest , especially problem D & E .

→ Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem B

The easiest solution And I Get AC

108991755

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried C using binary search but I am getting a TLE, I iterated through all the special positions and calculated the total number of boxes at special positions if we stacked all the boxes before the ith position and the last stacked box is at the ith position and added the untouched boxes at special position which are to the right of the ith position My submission. Could someone help with this please.

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

    I did the same thing. Maybe looking at my solution would help.

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

      I wanted to know the reasoning behind the TLE.

      → Reply
  • »
    »
    7 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    Hey tyagsa .I replaced find to the map.I have gone AC 109024868. I'm think find works in O (N)

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

      Can you briefly explain the naive algorithm mentioned in q? I am not even able to understand that :((

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

        We cannot move boxes that are in negative positions to positive ones because we cannot pull boxes on ourselves.

        So. we will solve for positive and similarly for negative, we add the results and print it! We can iterate to which position we will pull the boxes (the boxes to this position will be sequential). Is this position always a special position because it makes no sense to pull after a special position ?. binsearch will find how many boxes will stand consequtevely and again, binsearch will find how many consequtevely boxes are on superpositions and add suf [i + 1] to the answer, which is equal to the number of boxes that we have not moved but they are on special positions.

        P.S. Sorry for bad English 109027439

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

          thanks a lot :)

          → Reply
        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          i did the same thing as you at first got WA Here.

          After reading your code i did a little change of lowerbound(checking if the value at the position we found with lowerbound is strictly greater than the value at out current special index and then decrease if strictly greater) to upperbound in the first binary search and got AC Here.

          Can u help me in finding my mistake

          [UPD: found mistake (accessing the end of array in some cases)]

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

            Hey, your mistake in 2 point.

            1)after first lower_bound -> (if(p[j] > sp[i]) j--;) i replaced it by if(p[j] == sp[i]) j++; think why?

            2) and in second lower bound instead sp[i]-j i do sp[i]-j + 1. because we have j boxes, not j + 1

            109054593 check it

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              Thank you. For highlighting these points, especially point 2 but in point 1 i think i was accessing the nth element in somecases. which was giving some garbage.(did this and got AC)

              Appreciate your time and effor in correcting me. Thank You.

              → Reply
    • »
      »
      »
      7 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thank you very much! never looked at the find function while debugging, will keep this in mind next time.

      → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the blazing fast editorial !

→ Reply
»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Complexity calculation of problem D did not seem so trivial to me. Can anyone explain the complexity of the model solution?

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

    The time complexity is $$$O(n^{3})$$$

    First of all let's find an upper bound on the number of vertices in the graph, that is, an upper bound on $$$k$$$, in terms of $$$n$$$.

    I claim that the maximum number of vertices is $$$2n$$$. We can prove it by induction on depth (maximum distance from root to a leaf) of the tree. (Its really easy induction, you can try it yourself or lemme know in reply if you run into some trouble).

    Now for each node which is not a leaf, let's observe what happens in the recursive function $$$calc()$$$ in the editorial code. The $$$O(n^{2})$$$ for loop is executed exactly once. Then a linear number of recursive calls for its children. So, if we sum up for all non-leaf nodes, ee have $$$nO(n^{2}+n)$$$ operations over all non-leaf nodes. Which gives us a time complexity of $$$O(n^{3})$$$.

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

      Great explanation!

      Another way to visualise the maximum possible number of vertices is this: Start with the root. For the current list of leaf-nodes, what would be the worst possible split? If there are $$$X$$$ leaves, it would be a two-way split of $$$X-1$$$ and $$$1$$$. The right list cannot be split further, and we assume a similar split for the left one. This would lead to $$$N$$$ leaves and $$$N - 1$$$ non-leaves (supervisors), giving us an upper bound of ~$$$2N$$$.

      Why does this splitting yield maximum nodes? For each split you make, you gain a supervisor. For $$$N$$$ leaves, you can make a maximum of $$$N-1$$$ splits, and hence you can gain a maximum of $$$N-1$$$ supervisors.

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

      Edit: ignore this comment.

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

        Actually you are wrong in saying that each pair of nodes can be compared no more than $$$O(\log_2 n)$$$ times, for here you assume that the maximum number of levels is $$$O(\log_2 n)$$$, which is false, because if you look at the example provided by svince in the comment above, you will see that his tree has $$$n$$$ levels, so the bottom two leaves will be compared $$$n$$$ times here.

        → Reply
    • »
      »
      »
      7 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Edit: nvm made a mistake assuming the number of levels.

      The time complexity is actually $$$O(n^{2}\log_2{n})$$$. Given a level in the tree, let the number of nodes in that level be $$$m$$$ and the number of leaf descendants for each node be $$$l_{j}$$$ where $$$1 \leq j \leq m$$$. Notice $$$\sum_{j=1}^{m} l_{j} = n$$$ and that the time complexity for processing the entire level is $$$O(\sum_{j=1}^{m} l_{j}^{2})$$$. This implies that the time complexity for the level is $$$O(n^{2})$$$ and the overall time complexity is $$$O(n^{2}\log_2{n})$$$ because the maximum levels in the tree is $$$\log_2{n}$$$.

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

        if you see the above comment, I provided an example where the level of the tree is not $$$\log n$$$

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

          I don't think that example justifies that for loops would run $$$\mathcal O(n^2)$$$ in the worst case. Since, that example claims that at each $$$n$$$ level you would split $$$x - 1$$$ and $$$1$$$ but the inner for loop would run only once for all $$$x - 1$$$ nodes due to the break statement and $$$x - 1$$$ times for the last node in the worst case. Summing up, the runtime of that example would be $$$\mathcal O(n^2)$$$.

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

            I never said that the example justifies that the loop runs for $$$O(n^{2})$$$ in the worst case. I said that it is a counter-example to the assumption that there are atmost $$$\log n$$$ levels.

            So unless you have a proof that the complexity is indeed $$$O(n^{2} \log n)$$$, your comment below means nothing to me.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it -11 Vote: I do not like it

              I never said that the example justifies that the loop runs for $$$O(n^2)$$$ in the worst case.

              Yes. You never said that. But your claim on algorithm's runtime $$$\mathcal O(n^3)$$$ implies that the loop would run $$$n^2$$$ times in the worst case. Unbeknownst to you, you made two people to feel wrong about the time complexity which is right.

              In summary, the algorithm's runtime is not $$$O(n^3)$$$.

              So unless you have a proof that the complexity is indeed O(n2logn), your comment below means nothing to me

              The proof would be writing a paragraph for me. But I already proved it can't be $$$O(n^3)$$$.

              Then a linear number of recursive calls for its children. So, if we sum up for all non-leaf nodes, ee have $$$nO(n^2+n)$$$ operations over all non-leaf nodes.

              You're mistaken the depth would be $$$n$$$ but it's the number of nodes at the last level or leaf nodes. Since you mentioned it's trivial to see the number of nodes of the tree is $$$2n$$$ which implies it's a binary tree. And depth should be $$$log_2n$$$. Thus, it's $$$log_2nO(n^2 + n)$$$.

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

                Ok, you are so wrong here in the last paragraph that I won't even bother correcting you. Have a nice day, and don't reply.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                    Vote: I like it -11 Vote: I do not like it

                  Nope. I wasn't wrong. If you meant to split $$$\frac x 2, 1, 1, 1, 1... 1$$$ at each level it would be $$$log_2n$$$ recursive calls to the child nodes with $$$O(n^2log_2n)$$$ runtime else you meant to split $$$x - 1, 1$$$ at each level. Yeah it would be linear number of recursive calls to the child nodes as you said. But I disproved the runtime of for loop wouldn't be $$$O(n^2)$$$ in that case. I still don't see why you're claiming the runtime is $$$O(n^3)$$$ in the worst case.

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

        You're right. It is $$$\mathcal O(n^2logn)$$$.

        → Reply
  • »
    »
    7 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    Actually, it's $$$\Theta(n^2)$$$ overall. Here's a precise estimation:

    • It's easy to prove by induction that every subtree contains strictly more leaf nodes than interior nodes. Thus there are at most $$$n-1$$$ interior nodes.
    • Everything outside of calc is obviously $$$\Theta(n^2)$$$, and dominated by reading the input.
    • The function calc is called exactly once for each subtree, and hence at most $$$2n - 1$$$ times. In that call, ls contains each leaf in that subtree exactly once, and ch grows up to a size equal to the number of children of that subtree's root.
    • The only action in calc which isn't $$$O(n)$$$ per call to calc (and hence $$$O(n^2)$$$ overall) is the nested for loops. Totaled over every call to calc, the inner for-loop is run at most once for each pair $$$(L, C)$$$ where $$$L$$$ is a leaf node and $$$C$$$ is a child of some ancestor of $$$L$$$. Thus, this inner loop runs at most $$$n \times (2n - 2)$$$ times, which is also $$$O(n^2)$$$ overall.
    → Reply
»
7 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Alternative solution for problem D (109027989)

Process pairs of nodes $$$(a, b)$$$ in increasing order of weight $$$w$$$. Consider the highest ancestors of $$$a$$$ and $$$b$$$. If they are equal, skip that pair. If one of them has weight $$$w$$$, connect it to the other ancestor. Otherwise, create a new node with weight $$$w$$$ and connect it to both the ancestors.

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, I tried choosing the biggest number out of the 4, reduced its value to 0 and then correspondingly decreased the adjacent numbers by 1 if required (decreased both adjacent numbers by 1 if the chosen number is n or decreased the maximum of the adjacent numbers by 1 if it is n-1). Then, I checked if any number is negative (answer is NO) or all numbers are equal to 0 (answer is YES).

Keep repeating all the above steps until you get an answer.

I got a wrong answer for this approach. Can anyone explain why this is incorrect?

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Regarding dynamic connectivity for problem F with larger constraints: All of the necessary information to answer the relevant connectivity queries in $$$O(1)$$$ is easy to calculate while building a DFS tree. (For each back-edge leading to $$$c$$$, which DFS-child of $$$c$$$ is its other side a descendant of? For each DFS-child of $$$c$$$, is there a back-edge to some ancestor of $$$c$$$ in that subtree? Is $$$c$$$ the root?) The reasoning is basically the same as for the famous classical algorithms for finding bridges and articulation points.

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the problem F with n,m <= 2 * 10^5

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

@awoo in your editorial in problem C, both of these vectors are not used at all correct? would you mind removing this line if so?

    vector<int> c(n), res;
→ Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Whoops, sure, they were used for a slow solution and I forgot to remove them.

    → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F was beautiful.

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

solution of ABC String using python(easy to understand)--> https://codeforces.com/contest/1494/submission/109052454

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please help me find why i'm getting wrong ans on B . My approach is i try to fill the corners first

https://codeforces.com/contest/1494/submission/109065708

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what is wrong in my code? https://codeforces.com/contest/1494/submission/109073464

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone elaborate editorial for F? I can't quite understand meaning behind solution.

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how bit-masking working here and why are we taking & upto 8 only

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

    Well, we used bit masking here for generating all possible combination of 3 variables( considering you are referring to Problem A). 2^3 = 8. So A can be replaced with ( or ). similarly B and C. Now we just need to check with a current choice, we are able to make a valid string or not. It is a clear brute force. I have used a similar approach to Problem B also submission.

    → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a DP solution for C? The tags mention Dp as well. I up-solved it using Binary Search. If anyone solved using dp, please do share it. Would love to know the dp approach.

→ Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone tell me why (problem B) for test cases 2 1 1 2 2 answer is YES? should it not be NO? nevermind got it :)

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can D solved with heaps , I tried to solve it with heaps but it fails ans the checker comment doesn't make any sense to me ! can anyone help me figure it out . 108993423

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain solution of question B?

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

    The code may seem complicated because it uses bit-wise operations and bit masking But it's pretty simple, it tries every single combination of colors that can occur on the edges (there are only 16 possibilities), and checks if they can satisfy the requirements. If none do it just outputs "NO".

    If the code is what confused you, don't worry about it. You can just write it with simple if else statements, he just wrote it more practically.

    If you want to understand what his code does just research bit-wise operations and bit masking on google, they're not complicated at all. Cheers.

    → Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I can't seem to find what's wrong with my implementation for question C, it's basically the same as the editorial, but I'm getting WA on test 2 on the 78th case.

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

    I am also facing the same verdict. My code : 110020481

    I am unable to find any corner case against my submission

    → Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem-> 1494C - 1D Sokoban
Submission-> 110472885

Basically, as written in the tutorial, I used binary search(upper_bound) to find the next upper limit.

Can someone find the mistake in the code ;_;

→ Reply