awoo's blog

By awoo, history, 4 years 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

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Good contest and editorial!

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

First time I will reach Pupil

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Thanks for EaRly editorials.

  • »
    »
    4 years 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 !

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally the editorial :)

»
4 years 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

  • »
    »
    4 years 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)

»
4 years 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 .

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

Problem B

The easiest solution And I Get AC

108991755

»
4 years 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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I wanted to know the reasoning behind the TLE.

  • »
    »
    4 years 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)

    • »
      »
      »
      4 years 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 :((

      • »
        »
        »
        »
        4 years 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

        • »
          »
          »
          »
          »
          4 years 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)]

          • »
            »
            »
            »
            »
            »
            4 years 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

            • »
              »
              »
              »
              »
              »
              »
              4 years 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.

    • »
      »
      »
      4 years 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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the blazing fast editorial !

»
4 years 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?

  • »
    »
    4 years 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})$$$.

    • »
      »
      »
      4 years 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.

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

      Edit: ignore this comment.

      • »
        »
        »
        »
        4 years 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.

    • »
      »
      »
      4 years 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}$$$.

      • »
        »
        »
        »
        4 years 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$$$

        • »
          »
          »
          »
          »
          4 years 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)$$$.

          • »
            »
            »
            »
            »
            »
            4 years 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.

            • »
              »
              »
              »
              »
              »
              »
              4 years 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)$$$.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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.

  • »
    »
    4 years 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.
»
4 years 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.

»
4 years 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?

»
4 years 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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years 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;
  • »
    »
    4 years 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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F was beautiful.

»
4 years 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.

»
4 years 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 :)

»
4 years 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.

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

It's coming 'tutorial is not available'!!