chokudai's blog

By chokudai, history, 2 months 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

»
2 months ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

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

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

Hope to get a good result!

»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Another Contest in Home quarantine :D

»
2 months 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??

  • »
    »
    2 months 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.

»
2 months 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

»
2 months ago, # |
Rev. 3   Vote: I like it -47 Vote: I do not like it

How to solve F, any hints ?

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

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -31 Vote: I do not like it

      Left the contest after an hour bro, asked this for upsolving

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

        This is no pretext. You can be held accountable for using unfair means in the court of law.

»
2 months 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

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it -27 Vote: I do not like it

    how did you solve? can you give topic's name of c,d,e...please?

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

      Contest isn't over...

    • »
      »
      »
      2 months 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!

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

      You can do E using Priority Queues.

      • »
        »
        »
        »
        2 months 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.

»
2 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Anyone please explain solution to problem F.

  • »
    »
    2 months 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.

  • »
    »
    2 months 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$$$.

    • »
      »
      »
      2 months 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.

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        7 weeks 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.

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

      Awesome explanation thanks

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

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

  • »
    »
    2 months 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
    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months 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.

      • »
        »
        »
        »
        2 months 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.

»
2 months 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).

  • »
    »
    2 months 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...

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months 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

          • »
            »
            »
            »
            »
            »
            2 months 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.

            • »
              »
              »
              »
              »
              »
              »
              2 months 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)

            • »
              »
              »
              »
              »
              »
              »
              2 months 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]!$$$

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months 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)$$$

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months 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!$$$

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months 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)!$$$

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

                  I think you meant

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

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

                  gupta_samarth yes, of course you're right

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

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

              My Submission

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months 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.

    • »
      »
      »
      2 months 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

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months 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 =(

          • »
            »
            »
            »
            »
            »
            2 months 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!

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

            can you explain the rerooting solution

            thanks

            • »
              »
              »
              »
              »
              »
              »
              2 months 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.

        • »
          »
          »
          »
          »
          2 months 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]!} . \ ...) $$$
»
2 months 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.

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it +39 Vote: I do not like it

I am just going to leave this here.

Problem F

  • »
    »
    2 months 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)

    • »
      »
      »
      2 months 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.

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

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

    • »
      »
      »
      2 months 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.

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

        can you provide code?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Sure
    • »
      »
      »
      2 months 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.

  • »
    »
    2 months 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 :'(

»
2 months 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.

  • »
    »
    2 months 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.

  • »
    »
    2 months 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

  • »
    »
    2 months 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.

»
2 months 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?

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

    Hint: Tree Dp

  • »
    »
    2 months 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

»
2 months 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 ?

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
2 months 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.

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

    That's what I did, took me 40 mins.

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

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

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

    d: brute force e: sort, greedy

  • »
    »
    2 months 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.

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

      can you explain e in more detail?

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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.

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

      for D: implemented using bfs code But still getting TLE

      • »
        »
        »
        »
        2 months 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

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

          still getting TLE code

          • »
            »
            »
            »
            »
            »
            2 months 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]]++;
            
      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        You can use Dijkstra's algorithm for sparse graphs :

        https://cp-algorithms.com/graph/dijkstra_sparse.html

        basically using normal dijkstra, using priority queue / set to extract min node. Complexity will be O(V^2log(V) + EVlog(V) )

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

      Can you explain your dp solution for E ?

    • »
      »
      »
      2 months 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

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

        Can you explain ur modification ?

        • »
          »
          »
          »
          »
          2 months 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.

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

      I don't think you need bfs also. Just use the idea of floyd warshall algorithm and prove that the shorter path will only consists of the X and Y vertices only. So instead of iterating k from 1 to n , you just use k as X and Y only. mat[i][j]=mat[i][x]+mat[x][y]+mat[y][j] if mat[i][x]+mat[x][y]+mat[y][j] < mat[i][j].

  • »
    »
    2 months 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.

»
2 months 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 :(

»
2 months 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.

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

    Answer is simply k-(maximum distance between two adjacent houses).

    code

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

      Why is tha true? I pondered for like 10 minutes to try and find an O(n) solution and just gave up and coded N BFS searches haha.

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

        You see it's a circle and to travel all the houses you are basically not gonna traverse an arc of the circle.

        Being greedy you want that arc to be of maximum length, that is why we subtract maximum arc length.

        Hope that helps

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

    https://atcoder.jp/contests/abc160/submissions/11292835 Runs in quadratic time for D. Can it be improved?

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

      why this solution has time complexity O(N)?

      I think that's O(N^2) with two for loop

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

For E I first considered the approach: Put all colored apples in a vector and sort by their value (and maintain their type as the second value in this pair). Also put colorless apples in a priority queue. Then for each apple in this vector, if its value is better than the biggest one in the priority queue and you can still get apples of this type, get it, otherwise get the top of the priority queue.

But this idea could be hacked using the following input:

2 2 2 2 2
10 2
9 1
5 1

Because array would be like 10 9 2 1 and red apple with value 2 would be replaced with colorless apple with value 5.

So then I considered getting best colored ones (in that case 10 and 9) while colorless weren't worth it and then replacing what's left with colorless from smallest to biggest value (in this case, 5 would replace blue apple with value 1), but this approach failed =(.

So what's wrong with this last idea?

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

Time to go to Codechef, #Quarantine

»
2 months 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!

»
2 months 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]++;
            }
}
  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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.

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

    You mustn't count it twice

    • »
      »
      »
      2 months 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.

»
2 months 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

  • »
    »
    2 months 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.

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

    Thanks a lot. I finally understood solution to problem E after reading your explanation!

»
2 months 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.

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

    Why do they divide?I don't understand it

  • »
    »
    2 months 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.
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      It is multinomial coefficient formula

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

How to solve D?

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

    You can build graph and run one BFS for each node and get minimum distances (this is possible because $$$ N \leq 2*10^{3} $$$ so you can do $$$O(N^{2})$$$. Then brute force each pair (i, j) and sum $$$1$$$ to k-th answer, where $$$k = dist[i][j]$$$.

  • »
    »
    2 months 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.

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

So,How to slove the problem F?

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

so,how to solve the problem F?post

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

My linear solution for problem C:

This code finds longest interval and subtracts from k.

max = arr[0] + (k - arr[n - 1]);

for(int i = 0; i < n - 1; i++){
    max = max < arr[i + 1] - arr[i] ? arr[i + 1] - arr[i] : max;
}

printf("%lld", k - max);
»
2 months 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?

»
2 months 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
  • »
    »
    2 months 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';
    }
    
    • »
      »
      »
      2 months 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.

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

      A slight modification can bring down space usage. We can avoid using the 2d array s by directly incrementing corresponding index in t.

      Maximum distance is only N-1, not N^2. So, T's size can just be linear instead of quadratic.

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

        You are right. I didn't notice it in the contest. Thanks!

»
2 months 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.

  • »
    »
    2 months 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]

    • »
      »
      »
      2 months 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?

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

    The biggest N is 500000 but your array is A[20000]. I am not sure but I think this is the problem.

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

plz anyone explain the concept of problem-c?

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

    Imagine that there are houses on one side of a circular road. Let's call those houses A, B, C, D, E, F, G. You want to traverse all of the houses. You can traverse clockwise or anti-clockwise and the problem wants you to calculate the distance of the shortest path. You can start from any house it doesn't matter. Don't forget that this road is circular so house A comes after house G.

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

    Here is my linear solution if you want to take a look.

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

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

can anyone explain question f?

»
2 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Just stay at your home and start coding, better for you & your family and your society, it may be a chance for you to increase your problem solving skills

I HOPE EVERYONE TO HAVE SAFE LIFE.

»
2 months 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?

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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!

»
2 months 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

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

»
2 months 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!

  • »
    »
    2 months 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.com/blog/entry/75262?#comment-594252

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

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

»
2 months 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

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

for problem d the editorial provided has this formula min{|j −i|, |X −i|+ 1+|j −Y |, |Y − i| + 1 + |j − X|}. for the computing the shortest distance between vertex i and j. even if we don't use the second part of the formula which is "|Y − i| + 1 + |j − X|" the computed ans will always be the shortest path between the vertex i,j. i used similar concept and got accepted. can anyone explain me why the second part of the formula is not used or maybe the test cases provided would be too weak???

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

can anyone tell about the problem b what is it asked?

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

can anyone please explain me what is the logic behind problem C. I can not understand the logic of this problem. Help someone.

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

    The problem 'Find the minimum distance that needs to be traveled' is equal to subtract the maximum distance between two adjacent houses from K.

    • You shoud think about how to calculate the distance between the first house and last one.