maroonrk's blog

AtCoder Regular Contest 177 Announcement
By maroonrk, history, 12 days ago, In English

We will hold AtCoder Regular Contest 177.

The point values will be 300-400-500-700-1000-1000.

We are looking forward to your participation!

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

May be this contest should be held on another day.

It's awful that having an "Earthquake" problem on exactly 12th May.

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    I feel sorry about it. I'm afraid didn't know the exact date of that earthquake...

    → Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For Earthquakes problem, I figured out that we need to solve it by considering connected components and that the ways to collapse could be only of the form LLL...RRR so I thought of calculating this using a stack. But, I am still confused how to merge the results for each components, can someone explain it?

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

    Let $$$F(i, t)$$$ be the probability of the entire $$$i$$$-th connected component collapsing before or at time $$$t$$$. Of course, at each time $$$t$$$ from $$$1$$$ to $$$N$$$, at most one connected component's probability can change.

    So, you can sweep over the time $$$t$$$ from $$$1$$$ to $$$N$$$, and maintain the product of $$$F(i, t)$$$ for all $$$i$$$. This can be done with a segment tree or just simply maintaining the product (to handle the case where there are zero values, just keep track of the number of zeros to avoid division by zero).

    → Reply
»
11 days ago, # |
  Vote: I like it +21 Vote: I do not like it

For problem E, we can use another type of sort to reduce the time complexity to $$$O(113TV+113N)$$$ where V is the max possible value of adding all the scores

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Today's problems were really enjoyable! (The jump from C to D was higher than I expected, though.)

Unfortunately, I wasted almost an hour trying to solve a misread version of problem D (which turned out to be much harder than the actual problem).... 😅

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I forgot to set my alarm, so I woke up after the contest ended, and lost 39 rating points :(

→ Reply
»
11 days ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

In problem E, if we let f[3]=2, f[4]=8, f[5]=113, what will the asymptotic behavior of f[n] be like?

By the way
→ Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    I have the result that there are $$$11219$$$ patterns to be considered for $$$6$$$ problems case. I ran the following C++ program for half an hour. In this case, the maximum point value was $$$30$$$.

    C++ Program

    Computing $$$f_7$$$ seems difficult. Did anyone try it?

    → Reply
»
11 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Sad feelings about today's problem D. I failed to solve it because I didn't believe it's possible for probability of a certain group to be 0 modulo 998244353. Lack of math knowledge led to correct solution failed two test cases :( But liked first 4 problems in general.

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Me too, I was almost solved the problem D during contest but keep getting 2 WA on in19 and in20. If I solved this, it would be the first time I entered top 200 in ARC.

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

    Is this (having 0 modulo 998244353) really likely to happen sometime or they handmade two testcases for this bug? Is the probability MOD/N?

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

      I guess problem-setters intentionally made one small and one large tests with such values. I wouldn't say it was a bug. It was more like: my (non-existing) math knowledge tells me that probabilities will never be zero modulo large prime number, so I won't even bother handling that case. The statement was wrong, obviously. Funny, but it was about just a couple more if-statements to be added, but for some reason I didn't try it during the contest. Painful, but very important lesson.

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

        Math knowledge tells us that products of non-zeros will be non-zero, not sums of non-zeros or products of anything. As I mention below, you shouldn't handle this just with a couple if-statements but with different representation.

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

          Unfortunately, math knowledge doesn't tell me anything if it's simply not here :(

          By a couple of if-statements I meant specifically handling zero-sums separately and not letting them to the product. Actually, the same idea is also suggested in the official AtCoder editorial. In my accepted code it literally looks like two-ish if-statements.

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

      In this case, when the result is a product of $$$G$$$ sums, then assuming the data is sufficiently mixed that the sums are uniformly distributed, the probability that none are zero is $$$(1-1/MOD)^G \approx 1-G/MOD$$$, so it's not very likely to turn out zero by coincidence.

      However, when the result is a product of sums, we should assume that it's possible. It doesn't even need extra special effort, the sums are 0 at the start! We can write code naturally to express the result as $$$0^k \cdot p$$$ with $$$p \neq 0$$$, and update $$$k$$$ and $$$p$$$ when a sum changes.

      Most of the time, the result is a product of very few variables, so we tend to calculate results by multiplying new values of those variables instead of always calculating their modular inverses. In that case, it can still end up zero, it's just not visible as a source of bugs.

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

        It doesn't even need extra special effort, the sums are 0 at the start!

        Unfortunelly, me (and I think) and other people who made this mistake printed 0 until all poles can actually fall, and then started calculating when we don't have any real 0 (the ones that are 0 without mod).

        Now I can see why this was just a lazy way solving this corner case.

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

          Well, actually the wrong assumption was that the sum of non-zero number of fractions $$$\frac{1}{2^{d_{i}}}$$$ modulo large prime number is never 0. This is why we handled zero number of addends separately. Not as lazy as it seems :)

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

            Us bro. It took me a lot of WA and RTE to figure out this case. Apparently people who directly bashed DS didn't had to handle to this case separately.

            → Reply
»
10 days ago, # |
  Vote: I like it -17 Vote: I do not like it

Why nobody is talking about question C? It was quite a jump from B to C

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

    Maybe because it only require to observe independence? there is not much we can discuss about.

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

    I guess you meant that problem B was easier than usual. Problem C wasn't difficult at all and required the only observation:

    Observation spoiler

    Implementation is quite straightforward and requires only graph theory basics:

    Implementation spoiler
    → Reply