chokudai's blog

AtCoder Beginner Contest 245 Announcement
By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 245.

We are looking forward to your participation!

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

Comments Comments (41)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Who didn't copy-paste D?

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

    from where?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it -6 Vote: I do not like it

      I didnt solve it and I assumed ppl copy-pasted it because it felt impl-heavy

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

        I didn't think it was impl-heavy. Notice you can determine the coefficient of $$$B_i, 0 \leq i \leq m$$$ from C[i] / A[0];

        Spoiler
        → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

I spent only 6 mins on F, but struggled to solve problem D, like when you get WA on pretest 2 on div2A.

Spoiler
→ Reply
»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

anybody else did dp on reversed compressed scc graph in F?

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

    I did lol.

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

    I did node coloring. (white unprocessed, grey in-process, black processed)

    A cycle is detected if a grey node is visited before being colored black.

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

    I did remove leafs until there are not more leafs. All remaining vertex lead into circles.

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

    Me too

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve c ?

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

    I used multi-source BFS. It could have been done by DP as well.

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

    Maintain the max two numbers the previous position x[] can have. First element can be a[0] or b[0] Then iterate x[], and foreach position check if you can use a[i] or b[i], taking into account which values on the previous position where possible.

    You end up with 0, 1 or 2 possible values for the last position. If 0, then ans=No.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve H?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried FFT on D but failed. Is it precision error? Submission Anyway I got AC with a naive approach. There's no way a problem D in ABC would need FFT.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way to extract the index of the min value of an array in a range in O(log(n)) rather that just the value? (with segment tree or otherwise — I am not very comfortable with seg tree yet)

I needed that to solve E.

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

    You can make from each element a pair<value,index>, then sort this. First element in this list is min value, and has its index next to it.

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

      No I mean dynamically. I have to change the value of elems to 'delete' them by assigning to a large val then keep querying for the min in a range.

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

        Not sure how exactly that works.

        In E, I maintained a multiset of witdhts of chocklates that fit into some with of a box.

        Then iterated the boxes sorted by length, and putting all chocklates that fit into the box by length into above multiset.

        Then take one choclate out of the multiset, and put it into the current box. For this, we choose the choclate from the multiset with the biggest with. (which is first if putting negative with into the multiset)

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

          I use Python so I guess multiset wasn't an option for me. I'll have to learn C++ too it seems.

          Thanks anyway.

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

    Note that if we sorted boxes and chocolates in ascending order of their widths then their lengths, and started processing boxes one by one in ascending order, we can find that among the first chocolates that have widths $$$\le$$$ the current box it is best to assign the chocolate having the maximum length that can fit into the current box (if exists).

    The reason is that all those chocolates will fit into the next boxes in terms of width, so the idea is to choose the one that will increase our chance of succeeding later in terms of length by getting rid of the maximum we can choose.

    A multiset with upper/lower bound operations is sufficient here, where we can maintain a pointer for chocolates and when we move to the next box keep incrementing the chocolates pointer while adding the respective chocolate lengths to the multiset until we either reach a length greater than the current box or exceed the $$$n$$$ boundary.

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

      Thank you.

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

      the editorial sorts the overall list of boxes and chocolates in descending order of (width, length) but the argument looked similar .

      Is there any name for such greedy proof's ?

      → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Nvm

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with the question polynomial division for this contest ? The question was fairly easy don't know why I am getting RE as a verdict although there doesn't seem to be any .Here's my code CODE LINK . Thanks in advance.

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

    If A0=0 you divide by 0 I think.

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

      In the question it is given that A0 is not zero.Check the question .

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

        That's An not A0. A0 is the constant term.

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

          " Here, each coefficient of A(x) and B(x) is an integer whose absolute value is at most 100, and the leading coefficients are not 0. " It's stated the coefficients are not 0 , sorry I didn't get it.

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

            Leading coefficients just mean An and Bm not every coefficient.

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

              okay, thanks for the clarification, language for the problem should have been better, although it did strike to me that it was written "leading coefficients" instead of "coefficients" anyway thanks for your help.

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

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

                  Yes , I had seen that , it's just that I thought every coefficient is greater than 0 so I wrote the code with A[0] because you see it was written leading coefficients which misled me . Thanks anyway .

                  → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Can check out my video editorials of D,E and F if you have any doubt

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I think Problem E is a very nice practice for greedy algorithm, where you should choose different strategies of sorting at different stages.

At first sight of problem F, I realized that the well known algorithm of finding out all strongly connected components should work, but made some small mistakes during the implementation, and finally got accepted within the last 5 minutes.

In my opinion, problem E and F are really great for my level. I have a big chance to solve them, but still not that easy. Thanks again to the problem writers.

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

    I completely agree. Combined with the short statements, i always learn something new from ABC, especially D/E/F

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem G?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For H, why the answer for M equal to the product of F(pi, qi, K, N)?

→ Reply