chokudai's blog

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

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

Who didn't copy-paste D?

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

    from where?

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

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

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

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

    I did lol.

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

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

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

    Me too

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

how to solve c ?

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

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

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

How to solve H?

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

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

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

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

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

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

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

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

      Thank you.

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

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

can any body tell my mistake in problem D? Only 1 testcase failed while all other worked submission

»
3 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Nvm

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

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

    If A0=0 you divide by 0 I think.

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

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

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

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

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

            Leading coefficients just mean An and Bm not every coefficient.

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

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

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

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

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

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

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

my code for E is failing 7 test cases , could anyone give me a test case where it is failing or point out what's wrong with my code code link

edit : please don't mind this comment i found my mistake

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

How to solve Problem G?

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

I want to ask after_contest_001.txt on C.

I use DisjointSet to detect the connection about whether is there a path from left to right ?

here is my submission

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

    4 1 100 99 96 95 1 97 98 2

    I made a mistake on connection and DP, directed graph

    the pic

»
7 weeks 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)?