chokudai's blog

By chokudai, history, 5 years ago, In English

We will hold AtCoder Beginner Contest 160.

We are looking forward to your participation!

  • Vote: I like it
  • +97
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

So why was the discuss about AtCoder written here?amazing!

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope to get a good result!

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Another Contest in Home quarantine :D

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

C001_scrambled for first test case. I am participating here for the first time. It throws RE.Can somebody help with the reason??

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

    Can you give link to submission?

    C001_scrambled should be sample test case, by the way.

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Either this is not one of my good days of programming or I don't know, i ussually do ABCD and now i can't do C

»
5 years ago, # |
Rev. 4   Vote: I like it -47 Vote: I do not like it

Edit: Please Ignore. I didn't realize the contest was still going on.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Dude the contest isn't over, don't discuss

»
5 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Very First time I solved Problem E myself in single attempt,Nice Contest! thanks for good contest

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it -27 Vote: I do not like it

    solution please?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Contest isn't over...

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      C is greedy, D is brute force and E is also greedy.

      Hope that helps!

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

      You can do E using Priority Queues.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        I'm always amazed how low-rated people seem to give the name of the data structure they used rather than any substantial insight to the solution.

»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Anyone please explain solution to problem F.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The base of the idea is like this.

    Let's suppose there are two edges connecting node (x,y) and node (x,z) and the node x is root. And let's define the number of the nodes belonging to the y-rooted subtree(subtree whose root node is y), as A, and the number of the nodes belonging to the z-rooted subtree, as B.

    Now we can count the number of the ways in which writing 1 on vertex y(or z) and writing each of the numbers 2 ~ A(or B) on the nodes of the y(or z)-rooted subtree. Let's define this number as C, D each.

    In short, the number of ways writing A numbers on the nodes of y-rooted tree is C, and the number of ways writing B numbers on the nodes of z-rooted tree is D.

    In this case, the number of ways writing (A+B+1) numbers on y-rooted tree, z-rooted tree, and the node x is C*D*(A+B)!/A!/B!(It contains combination).

    Sorry for many definition.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +26 Vote: I do not like it

    First: answer for given root is: $$$\frac{n!}{s_1s_2\ldots s_n}$$$, where $$$s_i$$$ is size of subtree rooted at $$$i$$$. Why? Because a permutation is valid iff value at any node is less than any other value in its subtree, probability of this holding for specific node $$$i$$$ is $$$\frac{1}{s_i}$$$ and those are all independent.

    Now run dfs from one fixed root and calculate for each vertex size of its subtree. For any vertex $$$v$$$ except for the root let's consider two parts of the tree splits to when edge between $$$v$$$ and its parent. If the root is inside $$$v$$$ subtree size of upper subtree with size $$$n - s_i$$$ will be included in calculating the result, otherwise lower subtree with $$$s_i$$$ will. Thus for each such node we want to multiply all answers in its subtree by $$$\frac{1}{n - s_i}$$$. The latter is equivalent to multiplying all values by $$$\frac{1}{n - s_i}$$$, and those in $$$v$$$ subtrees by $$$n - s_i$$$. To perform sequence of operations: multiply all values in a subtree by $$$x$$$, and at the end extract value from each node we can just: whenever we multiply all values in a subtree multiply the value at its root only, and at the end use basic dfs to calculate for each vertex product of values on path from root to this vertex.

    EDIT: to be precise: the formula I described includes dividing by size of root's subtree, while the solution divides by all except for the root. Thus we need to divide answer for all vertices $$$n$$$.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +7 Vote: I do not like it

      Can you give a more elaborate prove or some idea of how we get that formula.

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

      I got your point but i didn't understand how could you derive formula for answer for given root?

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

        The basic idea is : for any tree the number of possible arrangements are (n-1)! (as we have to keep the node with smallest value at root of this tree) but since for any subtree of this tree(lets say u) there are not sizeu! but dpu possible arrangements so the answer(i.e. (n-1)!) has to be divided by sizeu! and multiplied by by dpu. Thus we get the above formula dpv = (vsize-1)!*k where k is product of dpu/(sizeu!) for all u such that u is a child of v. It is slightly similar to how we calculate the number of arrangements in a list of numbers with duplicates.

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

      Awesome explanation thanks

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

Can anyone explain C problem statement was not clear to me ?

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it +7 Vote: I do not like it

    You have N cities around this lake and you can traverse it clockwise or anti-clockwise. You have to pass through every city and total distance travelled is sum of distances between every two cities in your path.

    In second sample, one city is in position 0 degrees ("north of the lake") and the last is in position 15. If you walked anti-clockwise (array is circular, remember), you could go from the 0-th city to the 2-th in 5 degress, because $$$(0 - 15) \ mod \ 20 = 5$$$.

    Solution.

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

      Does this means the given array is the co-ordinates of the i-th house if we plot on x-axis? Correct me if I am wrong.

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

        Nope. The array gives yous the distance in terms of the perimeter of the circle.

        Think of this sample:

        20 3
        0 5 15
        

        First house if in the top-most point of the circle, second house if 5 meters away (clockwise), then third house is 15 meters away (clockwise).

        Total perimeter is 20. So if you're in the first house and you travel 5 meters anti-clockwise, you get to the third house.

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

          Thank you. Problem statement was very confusing to me. Even there explanation for sample was not very clear to me. And at last I was suffocated by number of submissions.

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

        Yes, but just adding that you have to consider it as a loop at point K.

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

How to solve F? I can't even get close to a bruteforce solution of O(n*n).

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

    The O(N^2) solution is as follows:

    Root the tree at k. Now, we observe that this problem bijects to listing nodes in order such that all parents appear before their children. Let the number of ways to order nodes in the subtree of v be s[v]. We observe that through combinatorics, s[v] is the product of s[i] for all i that are children of v, multiplied by (stsize[v] — 1)!, divided by the product of s[i]!. The part with the factorials corresponds to the number of ways to order the different subtrees relative to each other. Thus, this can be solved in O(N) per root if we precompute the factorials and the multiplicative inverses.

    To speed up to O(N logN), a further idea is needed. (Hint: consider how to reroot the tree.)

    Edit: divide by the product of stsize[i], not s[i]. I'm a bit of an idiot...

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

      $$$O(n log n)$$$? Why. It can be quite easily in $$$O(n)$$$. I guess your $$$O(n log n)$$$ uses some data structure like HLD, which is way more harder to implement than simple DFS.

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

        Modular inverse is O(logM). The correct formulation of my complexity should be O(N logM), where M is 10^9 + 7.

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

          OK I forgot about this xD. My solution also works in $$$O(n log mod)$$$. We can of course precompute inverses of all numbers from $$$1$$$ to $$$n$$$ in linear time, so for "theoretical complexity" we can say it can be solved $$$O(n)$$$, but who would bother implementing it during the contest

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

            How does one compute inverse of numbers in linear time? I've never seen such an algorithm.

            Edit: apparently it's extended euclid and some dynamic programming idea. Yeah, I can see why no one would want to code it in contest time.

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

              That's one way, another is: if you want to compute inverse of $$$n$$$ numbers what you can do is: calculate their product, its inverse, products of numbers of each prefix and suffix. Inverse of one value is: inverse of product times product of all other, but all other is one suffix and one prefix so it's enough to calculate: inverse of product times suffix beginning one element after times prefix ending one element earlier.

              It works in $$$O(n + \log m)$$$

              (of course if you need such tricks to make your solution pass it means either model solution has better complexity, or time limit is insanely tight)

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

              I'm not sure how precomputing the inverses would help. We will possibly need to compute the inverse mod $$$M$$$ of $$$n!$$$, so with the dp approach we might need to compute all inverses from $$$1$$$ to $$$M-1$$$. (in above, $$$s[i]$$$ is a subtree size, $$$O(n)$$$, and we are dividing by $$$s[i]!$$$

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

                No. First we compute $$$n! \mod m$$$ which is simply product of $$$n$$$ numbers modulo $$$m$$$ which takes linear time, then calculate inverse of this one particular number which takes $$$O(\log m)$$$

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

                  Ok thanks, I got it. We are only doing inverses of $$$1!, 2!, \ldots n!$$$

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

                  If we want to calculate inverses of all factorials we can simplify this trick a little bit. Calculate $$$n!$$$, its inverse and iterate over $$$i$$$ from $$$n$$$ to $$$1$$$ and use identity $$$i!^{-1} = (i+1)^{-1}(i + 1)!$$$

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

                  I think you meant

                  $$$ i!^{-1} = (i+1)!^{-1}(i + 1) $$$

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

                  gupta_samarth yes, of course you're right

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

              Why not? I think can be quite easy to code.

              My Submission

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

                This formula at first seems totally out of the blue, but if you do remember/understand it, than OK, it can be easy to code.

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

      Could you please explain in a bit more detail s[v] is the product of s[i] for all i that are children of v, multiplied by (stsize[v] — 1)!, divided by the product of s[i]! ?

      I understand that $$$(stsize[v] — 1)!$$$ will give us permutations of relative subtrees, but doesn't it also count permutation of relative subtrees of different depths? Wouldn't that count bad permutations?

      Thanks

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

        That's why we divide by the product of s[i]!, to avoid further permuting the already permuted subtrees.

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

          So shouldn't it be divide by product of stsize[i]!? Still, I can't see how that works ;_;. I understand the solution and I managed to code the rerooting thing and get AC, but I don't understand the DP recurrence =(

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

            Yeah it's stsize[i]... I made a small mistake in the explanation. Thanks for pointing it out!

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

            can you explain the rerooting solution

            thanks

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
              Rev. 2   Vote: I like it +7 Vote: I do not like it

              Yea sure.

              You calculate $$$dp$$$ for one root (let's say 1). Then you do a DFS and each time you're going from node $$$u$$$ to node $$$v$$$, you want to reroot this tree, making $$$v$$$ its new root. So think like you're basically "rotating" this tree.

              So at first, you'll know that $$$ans[1] = dp[1]$$$, because you calculated $$$dp$$$ rooted at 1.

              So what changes? To calculate $$$dp[u]$$$, we use size of subtree rooted on $$$u$$$ and the size of all subtrees of its childs.

              So now $$$v$$$ is no longer a child of $$$u$$$, then $$$dp[u]$$$ will have to get rid of all of it's dependencies of $$$v$$$.

              Since

              $$$ dp[u] = (size[u]-1)! * (\frac{dp[v1]}{size[v1]!} . \frac{dp[v2]}{size[v2]!} . \ ...) $$$

              Then we have to multiply $$$dp[u]$$$ by $$$size[v]!$$$.

              Additionally, $$$size[u]$$$ will change because $$$v$$$ is not a child of $$$u$$$ anymore, so $$$size[u] = size[u] - size[v]$$$. But that means that our $$$dp$$$ changes too, so you'll have to divide $$$dp[u]$$$ by $$$(size[u] - 1)!$$$, recalculate $$$size[u]$$$ and multiply it again by $$$(size[u] - 1)!$$$

              These changes apply to $$$dp[v]$$$ too! Now $$$u$$$ is a child of $$$v$$$, so $$$size[v]$$$ increases by (the old) $$$size[u]$$$ and you have to recalculate $$$dp[v]$$$.

              This makes MUCH more sense if you draw it on your notebook.

              After recalculating $$$dp[u]$$$ and $$$dp[v]$$$, $$$ans[v] = dp[v]$$$, you call dfs recursively to child $$$v$$$ (now it's as if you didn't do any rerooting and you had just calculated everything rooted at $$$v$$$).

              After the recursive calls end (you're back at node $$$u$$$, you restore $$$dp[u]$$$, $$$dp[v]$$$, $$$size[u]$$$ and $$$size[v]$$$. You can do this part in a smart way or just use some auxiliary variables.

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

          OOOOO! Maybe I got it!

          Out of $$$size[v]!$$$ possible permutations for a child v of u, we have $$$dp[v]$$$ good ones. That means that there's a $$$\frac{dp[v]}{size[v]!}$$$ probability for a permutation to be good.

          So let $$$vi$$$ be the $$$i$$$-th child of $$$u$$$.

          So out of a total of $$$(size[u]-1)!$$$ possible permutations for ALL children of $$$u$$$, we have a probability of $$$\frac{dp[v1]}{size[v1]!}$$$ of it being a good permutation from subtree of child 1, $$$\frac{dp[v2]}{size[v2]!}$$$ of it being a good permutation from subtree of child 2 and so on.

          So

          $$$ dp[u] = (size[u]-1)! * (\frac{dp[v1]}{size[v1]!} . \frac{dp[v2]}{size[v2]!} . \ ...) $$$
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried to implement E with given ordering of the apples, noticed a minute before end that it would be more wise to reorder them by deliciousness.

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

    So we have to read the statement carefully, because the case which the order is not important usually uses sorting.

»
5 years ago, # |
  Vote: I like it +39 Vote: I do not like it

I am just going to leave this here.

Problem F

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

    At atcoder, it's kind of difficult to have new questions (at least in beginner contests)

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

      You can debate that a problem of this caliber (not an easy problem btw) shouldn't be repeated. However I can understand that the problem looks like it can get repeated accidentally just thought I'd mention it.

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

    Can you explain DP formula there? I can't get it...

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

      I didn't read the editorial however here is my solution.

      I am also too lazy to write any formulas but here is my solution.

      Let's assume that the tree is rooted so i need to calculate the number of topological sortings for this tree beginning at node 1 now let's assume that node $$$X$$$ has 1 child then $$$dp[X] = dp[child]$$$ i.e just append $$$X$$$ on the topological sorting of it's child. However in case $$$X$$$ has 2 children this means I have 2 arrays and I want to find the number of ways to merge them into one array such that the order of each array still stands meaning the $$$i-th$$$ number comes before the $$$(i+1)-th$$$ number array-wise, this can be done using stars and bars. this way I can merge any topological sorting with the current topolgical sorting of all previous children.

      After calculating $$$dp[X]$$$ for each node we calculate $$$dp2[X]$$$ for each node which is the answer for all the tree excluding the subtree rooted at $$$X$$$ this part should be pretty standard. then merge $$$dp[X]$$$ with $$$dp2[X]$$$ using stars and bars.

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

        can you provide code?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Sure
    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Suppose you have a rooted tree with $$$1$$$ as the root. Let $$$dp[x]$$$ equal the number of ways to distribute $$$|x|$$$ consecutive values on the subtree rooted at $$$x$$$, with the lowest value assigned to $$$x$$$. Then for leaves this equals 1, and we want $$$dp[1]$$$. If node $$$r$$$ has $$$k$$$ children $$$n_1,\ldots,n_k$$$, then think about first putting the lowest value at $$$r$$$, and then distributing the remaining $$$|r|-1$$$ values on the subtrees. A way to do this is to distribute values on each individual subtrees, and then "interleaving" these distributions. So you get the product $$$dp[n_1]dp[n_2]\cdots dp[n_k]$$$ times multinomial coefficient $$$C(|r|-1,[|n_1|,|n_2|,\ldots,|n_k|])$$$, where the multinomial coefficient gives the number of ways to interleave the distributions from different subtrees.

      Then for other roots, use re-rooting.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Damn, makes me miss CSAcademy: this kind of short statement problem was like lots of their other good quality problems :'(

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

Why this doesnt work ? https://atcoder.jp/contests/abc160/submissions/11310758

Insert all elements in a vector and sort.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Because coloring all the colorless apples red, before coloring any of them green is not always optimal.

    Ex.:

    2 1 2 2 2
    2 2
    1 1
    10 10
    

    The answer is 22, but your code gives 21.

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

    I didn't go through your whole code, but here is what I did.

    1. First sort A, B, C array in descending order.
    2. Make a new array(Let it be F) by taking the first X and first Y of B.
    3. Sort the new array F in descending order.
    4. Now try replacing the smallest element of F by the largest element of C.
    5. Do it until Del(Ci) — Del(Fj) > 0.(Why? Because If we replace now, our sum will decrease).

    Here is my simple implementation: Submission

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

    When you use a colorless apple you must decide which color it has to become based on which color has the worst apple who was being eaten before coloring this one(because that's the one you want to discard). If you mix all the apples you don't get to choose by this criteria and fail to reach maximum value.

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

What is an idea in task F? I don't get it? How to count it?

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

    Hint: Tree Dp

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

    Think, of a node N with two children X,Y

    You already know the size of the subtree on each child, and the number of ways you can label it.

    Since N is a parent of X,Y N should get the lowest number. And among the remaining you've to choose which are going to each child and multiply by the ways to label on each child.

    That will give you the solution for a particular root, use re-rooting after

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

Where will the editorials to the problems be posted ? Somewhere on Atcoder site or on codeforces ?

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

    A tab labelled "editorial" should show up on the AtCoder itself.

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

    See any of the past contest. You will get it.

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

Man, the re-rooting in F was tough. :(

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

For problem F, I think I can use dp to get the answer for $$$numberofways(root)$$$, for an assignment starting with "1" at some fixed root. The expression has a multinomial coefficient so worst case has a $$$\log n$$$ factor, for a total of $$$O(n\log n)$$$. Then I think the answer for a node adjacent to root can be obtained from the above answer, by changing some individual factors. It seems the total number of such changes as I change from node to node will equal the sum of degrees, so the answer should stay $$$O(n\log n)$$$. Can someone who solved it tell me if this is a good approach because I feel like it would take too long to implement.

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

can somebody tell me which topics are used in d and e

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

    d: brute force e: sort, greedy

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

    The key observation in D is that we cannot use Floyd-Warshal because it gives TLE, and then we implement BFS wich works better $$$O(n^2)$$$

    E is dynamic programming.

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

      can you explain E with dp solutions?

      In contest, I think dp too but I solved it greedy.

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

        I did read the problem now once again... and noticed that I still got it wrong.

        "You are going to eat X red apples and Y green apples." I took this as in first place we eat x+y red/green apples, then we eat anoter c ones, from which we can choose to color them red/green as long as there are some of them left.

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

      for D: implemented using bfs code But still getting TLE

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

        You should not use a vis[] array. Instead, push nodes to the queue whenever relax, ie whenever you found a new min distance to that node.

        for example see code

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

          still getting TLE code

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

            Ah, ok, it is the way you count the distances for every k. That makes it $$$O(n^3)$$$

            Note that the max distance between two nodes is n, so you can make and array of that size and run once throug the two-dimensional array. Basically you do then

            ans[dist[i][j]]++;
            
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Can you explain your dp solution for E ?

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

      For D, we can use Floyd Warshal with a little modification.
      https://atcoder.jp/contests/abc160/submissions/11317101
      E can be done with a greedy approach.
      https://atcoder.jp/contests/abc160/submissions/11318492

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

        Can you explain ur modification ?

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

          What Floyd Warshal does in every iteration is that it picks a vertex and for all pairs of points,it updates the shortest distance between them passing through the iteration point and thus after all iteration, the adjacency matrix will have the min distance between i,j.

          In our problem,we only have one other edge i.e x,y so, instead of taking iterations over all points, we only consider them through that edge and the main path. Thus,we only have 2 loops and one statement inside them instead of the third loop.
          I hope this helped.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    Nothing! simple observation.

    my_D (without any Bfs/Dfs) just simple HashMap you can use array too to store. for any (i,j) pair distance(k) will be k=min(abs(i-x)+abs(y-j)+1,abs(i-j)); just store it and finalyy print it.

    my_E just sort and pick TopMax x+y having constrain that you can't pick more than x from red and more than y from green apples respectively.

»
5 years ago, # |
Rev. 4   Vote: I like it +10 Vote: I do not like it

Brief Solutions:

  1. Simple check ---- O(1)

  2. The answer will 1000*(n/500)+5*((n%500)/5) ---- O(1)

  3. For every starting position i, the distance will be a[n-1]-a[i]+(i-1>=0?(k-a[n-1])+a[i-1]:0). Then take the minimum for all i — O(n)

  4. Form a graph, and then run bfs starting from each node. Then count the nodes at a distance k for every k. Since, every pair (i, j) appears twice, divide the answer by 2. Perhaps there exists a O(n) someone can explain. — O(n^2)

  5. First sort set A, B, C. Greedily take top x apples from set A, top y apples from set B and then atmost top (x+y) apples from set C. Sort them and take the top (x+y). — O(AlogA+BlogB+cLogC+(x+y)log(x+y))

  6. I couldn't solve myself :(

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

Can someone explain a O(n) solution for D? I think there exists a linear time solution.

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

Time to go to Codechef, #Quarantine

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

The editorial says there there is an O(N) solution for F.

However, if I am not mistaken, the computation of multiplicative inverse is needed, which is O(logN). Thus, shouldn't it be O(N logN) overall?

Edit: oops, I meant logM. Thanks to ahshafi for pointing out my mistake!

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

Why this approach doesn't work for D ( I got 5 WA )

for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int distance_direct_path = j - i, distance_bridge_path = abs(x - i) + abs(y - j) + 1;
                ans[min(distance_bridge_path, distance_direct_path)]++;
                if (distance_direct_path == distance_bridge_path)
                    ans[distance_direct_path]++;
            }
}
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are double counting when you check whether distance_direct_path is equal to distance_bridge_path. They are the same pair, and thus should only be counted once.

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

      You are right I got accepted but I dont understand isn't when distance_direct_path == distance_bridge_path in this case we have 2 differents shortest paths from i to j, so we need to count them both ?

      EDIT:

      My bad the answer is the number of pairs and not the number of paths.

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

    You mustn't count it twice

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

      Why we have 2 differents shortest paths, one direct path and the other path using the extra edge, so we need to count them both ?

      EDIT:

      My bad the answer is the number of pairs and not the number of paths.

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

Brief soln
A : Do it.

B : Greedy.

C : perimeter — longest interval length.

D : There might be more efficient ways, but for this problem size of input ($$$n = 2,000$$$) is small enough to run $$$n$$$ BFS and just add everything. This gives $$$O(n^2)$$$ algorithm.

E : Take $$$X$$$ best red and $$$Y$$$ best green. Now, from these, we can replace some of these to colorless ones to get better result. while we can improve (smallest in bag < largest colorless out of bag), we improve greedily. If we look at colorless one from biggest to smallest, we can easily maintain with priority queue. Code is easier than explaining. https://atcoder.jp/contests/abc160/submissions/11286026

F : We root the tree at 1 and solve for 1. Note that what we compute is actually number of permutations which does not violate order of tree. Consider some statement like this. If a subtree rooted at node 5 has (5, 6, 7, 8, 9), in the final permutation, 5 must be the first of subsequence (5, 6, 7, 8, 9) where order of 6,7,8,9 does not matter. If we throw any permutation at random, we have 1/5 chance sufficing this criterion. Observe that sufficing one statement does not change probability of sufficing another, so we compute answer for 1.
By DFS, we can compute $$$f(a, b)$$$ where $$$a$$$ is parent of $$$b$$$, $$$f(a, b)$$$ = number of nodes in subtree rooted at $$$b$$$. With this notation, we can write the answer above as $$$n!$$$ divided by some product of $$$f$$$s. When we change root to something adjacent of current node, note that exactly 2 edge changes it's 'direction'. We can compute all values in $$$O(n)$$$ dfs calls, but I implemented $$$f$$$ function with map so my solution is $$$O(n \log n)$$$. https://atcoder.jp/contests/abc160/submissions/11298787

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

    I think there is another O(n^2) solution not using BFS in problem D. We can figure out the shortest path from vertex A to vertex B (A<B) is among two cases: [A — B](the length of this path is B-A), [A — X — Y — B](the length of this path is abs(A-X)+abs(B-Y)+1). For each pair we can just compare these two numbers and find the length of the shortest path.

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

So here's how I solved F(got AC just after contest has ended) :(

Let as solve for a specific node x as root which has p children:

Let it's children be x1,x2,x3...,xp respectively. Let their subtree sizes be s1,s2,....sp respectively.

Obviously we have to distribute s1 numbers to subtree rooted at x1, s2 numbers to subtree rooted at x2,..... , sp numbers to subtree rooted at xp.

Thus we have the following recursive solution: solve(x)=solve(x1)*solve(x2)*....*solve(xp)* (NUMBER OF WAYS TO DISTRIBUTE n-1 NUMBERS TO SETS OF s1,s2,....,sp).

The last value is a simple combinatorics problem which is equal to (n-1)!/(s1! * s2! *....sp!).

The factorials can be precomputed and thus we can get the value for a particular root in O(n * log(n) ) time. (log term for doing modular inverse of factorials).

The values for remaining nodes can be found by re-rooting technique.

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

    Why do they divide?I don't understand it

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

    Your solution seems much simpler than others.Could you please again explain it with more details?specially the

    this part.
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      It is multinomial coefficient formula

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

How to solve D?

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

    You can calculate the distance for every pair of nodes in the graph with N BFS (for every node). After that, you will have a matrix dist of distances, where position [i][j] represents the distance from i to j.

    Then, you just count the number of times the k-th distance appears above the main diagonal of the matrix.

    vector<int> counter(n);
    
    for(int i=0; i<n; i++)
            for(int j=i+1; j<n; j++)
                counter[dist[i][j]]++;
    

    This solution is O(N²), which is enough for the restrictions.

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

So,How to slove the problem F?

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

so,how to solve the problem F?post

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Could anyone please link more problems like problem F (tree dp, rerooting)? Or could you please tell me where to find similar problems?

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

Problem D can be solved in $$$O(N)$$$.

Hint: use difference array and prefix sum.

Spoiler
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Oh, I only got an $$$O(n^2)$$$ solution using an algorithm like bucket sort. I didn't think about using difference array and prefix sum:(

    Perhaps my algorithm is easier to code, but its efficiency is very low...

    My code is below:

    #include <bits/stdc++.h>
    using namespace std;
    const int maxN=2005;int n,x,y,s[maxN][maxN],ans[maxN],t[maxN*maxN];
    int main() {cin>>n>>x>>y;
    	for (int i=1;i<n;i++)
    		for (int j=i+1;j<=n;j++) s[i][j]=min(j-i,abs(x-i)+1+abs(y-j));
    	for (int i=1;i<n;i++)
    		for (int j=i+1;j<=n;j++) t[s[i][j]]++;
    	for (int k=1;k<n;k++) cout<<t[k]<<'\n';
    }
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think this should the intended solution. Actually I coded exactly this $$$O(n^2)$$$ solution in contest. Here I'm just discussing a better solution after contest.

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

https://atcoder.jp/contests/abc160/submissions/11326931

This is my submission for problem C ,can anybody tell me why i am getting a runtime error on the testcases. I am new to programming ,please help.

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

    You're using an unitialized value, c, and accessing the array with it: C[c-1]

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

      My sample tests are running with it. They should also have a problem with c?Should I initialize c to some value?

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

I don't know why this approach doesn't work for E. ( I got 6 WA )

Here is my solution: https://atcoder.jp/contests/abc160/submissions/11367454

Is there anyone who save me?

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

    Check for overflow.You have declared sum as int try to change it to long long.

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

      Oh, I think I've seen accepted code with just integer sum but I was wrong. Thanks!

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

Any help for Task D. The editorial in AtCoder is in Japanese I think. And I am not able to understand that

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

    For each vertex perform a BFS and calculate the distance to each other node and update their counts.

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

    For International Readers: English editorial starts on page 7.

    for problem D: check editorial on page 10.

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

Can someone explain how we reach the formula in the editorial of problem F? Thanks in advance!

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

    Let $$$size[u]$$$ be the size of the subtree rooted at node $$$u$$$.

    Consider you're starting the process in node $$$u$$$. Then the number of answers for $$$u$$$ is the number of possible permutations of size $$$size[u]$$$ such that a child never comes before its parent in this permutation. Why is that? Because if we start at $$$u$$$. We write $$$1$$$ on it, then we go to its children, write first number between $$$2$$$ and $$$size[u]$$$ that hasn't been written yet and so on. So a child's number will never be smaller than its parents in this permutation.

    Now to get to the $$$dp$$$ formula, read this: https://codeforces.net/blog/entry/75262?#comment-594252

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

Supplementary editorial and sample codes for last 4 problems AtCoder ABC 160

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

There is another solution to E! I'll introduce another variable,N,and assume N,A,B,C,X,Y all have magnitude 1e5,to show time complexities.

Brute Force(the big idea)
Optimization 0
Optimization 1

Here's my code

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

E can be solved using ternary search as well.

Link