atcoder_official's blog

By atcoder_official, history, 16 months ago, In English

We will hold Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309).

We are looking forward to your participation!

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

| Write comment?
»
16 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Yet another Well-known-in-China problem ... Well, perhaps not so well-known regarding the number of submissions, but the idea was probably pretty well-known.

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

I have no words to describe how bad the statement of problem C was. Is it so hard adding at least a small diagram which explains what is going on?

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

    The statement was short and simple according to me. I didn't feel like anything else was needed.

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

      I dont know maybe its just me but I found it quite confusing. What wasn't clear to me is that the whole lifecycle of a medicine starts always at day 1, I thought for 1 hour that it starts on day "i" so it didn't make any sense the output explanation. In my opinion this fact should have been stressed way better.

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

What is wrong in this submission of problem F?

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

Could someone help me in G ? I can't get the editorial's explanation

  • »
    »
    16 months ago, # ^ |
    Rev. 4   Vote: I like it +30 Vote: I do not like it

    Here is my non inclusion-exclusion solution.

    Suppose you have $$$N$$$ balls arranged in the top row and $$$N$$$ boxes arranged in the bottom row. Now you need to put $$$i$$$-th ball in $$$P_i$$$-th box such that $$$|P_i-i| \geq X$$$.

    So you can have $$$dp$$$ such that $$$dp[i][l][r][mask_1][mask_2]$$$ denotes the number of ways to distribute the first $$$i$$$ balls into first $$$i$$$ boxes such that

    • $$$l$$$ boxes in range $$$[1,i-X+1]$$$ are empty
    • $$$r$$$ balls in range $$$[1,i-X+1]$$$ have not been put into any box(to be clear we can only considering first $$$i$$$ boxes currently; these balls will be put in some later boxes)
    • $$$mask_1$$$ denotes the status of last $$$X-1$$$(range $$$[i-X+2,i]$$$) boxes(whether they are empty or not)
    • $$$mask_2$$$ denotes the status of last $$$X-1$$$(range $$$[i-X+2,i]$$$) balls(whether they have been put inside any box or not)

    Now for index $$$i+1$$$,

    • you have two options for $$$i+1$$$-th ball: either you put this ball in one of $$$l$$$ boxes in range $$$[1,i-X+1]$$$ or decide to put it in later boxes(in this case the status of this ball will get included in $$$mask_1$$$)
    • you have two options for $$$i+1$$$-th box: either you put one of the $$$r$$$ ball in range $$$[1,i-X+1]$$$ or decide to put some later ball in this box(in this case the status of this box will get included in $$$mask_2$$$)

    After each transition, you update $$$l$$$, $$$r$$$, $$$mask_1$$$ and $$$mask_2$$$

    So finally your answer is $$$dp[n][0][0][0][0]$$$

    Time complexity is $$$O(N^3 \cdot 4^X)$$$, with low constant factor.

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

      You can also note that $$$|l - r| < X$$$ must be true, which helps you reduce the time complexity to $$$O(N^2 \cdot X \cdot 4^X)$$$.

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

        Keeping $$$l$$$ in the state seems to be redundant, since the number of balls that haven't been placed is equal to the number of empty boxes.

        Assuming a bit is set in $$$mask_1$$$ when the box is empty, and in $$$mask_2$$$ when the ball is yet to be placed:

        $$$l = \text{popcount}(mask2) + r - \text{popcount}(mask1)$$$

        This reduces the complexity to $$$O(N^2 \cdot 4^X)$$$. (Code)

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

      In your Code why l is going till i-1 and not till i-x+1 as maximum number of empty boxes in range[1 , i-X+1] can be i-X+1.Can you please explain.

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

It seems, it is possible to solve $$$G$$$ using OEIS, and additionally write bruteforce to see, where to look on the site. For $$$X = 5$$$ an element of sequence depends on $$$43$$$ previous though.

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

    Yes, I did think of this way during contest, but could not figure out how to determine the recurrences since bruteforcing 43! (I thought 20 would be sufficient since for X = 3 it depended on previous 5 terms) permutations wasn't feasible. How exactly are you determining the recurrences ?

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

Enjoyed solving G.

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

    Could you share your approach? I am not getting the editorial's solution.

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

      My approach is same as the editorial. We are calulating the unban permuatations such that atleast $$$y$$$ indexes satisfy the condition $$$abs(P_i - i) < X$$$ for which we can do simple $$$dp[currentIndex][indexesTaken][maskOfIndexesTakenIn$$$ $$$(i - x + 1,i + x - 1)]$$$. For the remaining indexes we can just multiply it by $$$fact[n - y]$$$. After calculating we can just do inclusion exclusion and add our $$$answer * (-1) ^ y$$$ to the $$$final answer$$$.

      Code

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

Why this solution for F gives WA for 3 tests Link...

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

Implementing Problem D exactly as Editorial, still gives WA for 10 testcases. Any idea what is wrong with this?

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

    Your solution fails when $$$n_1 = 1$$$ or $$$n_2 = 1$$$ or both. Your max1 (or max2) variable will be equal to Integer.MIN_VALUE since max in your BFS will never get updated.

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

What is the "method of mirror images" in the editorial of H? Why can't we use the initial dp[i][j](=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1]) with some poly techniques instead of mirroring? Thanks.

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

    That's because of dp[i][0] and dp[i][M+1], which should be $$$0$$$. If you naively use polynomials, for example dp[i][0] gets (kinda) dp[i-1][-1]+dp[i-1][0]+dp[i-1][1], which does not evaluates to $$$0$$$, eventually destroying the whole polyonimal.

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

Can someone please explain how to build segment tree in F??

I have thought till the part of sorting the tuples and all but being a beginner at segment tree, I am unable to understand the editorial

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

    Maybe some example would help

    Assume that the boxes are already sorted by $$$h$$$ :

     1 2 7 
    2 4 6
    3 4 5
    4 5 6

    Consider we are now evaluating box 4. Now we want to check whether there's a box can be fit inside box 4

    By using the example above, we can see that box 3 can fits in the box 4

    How to do that?

    For each of the width, store the minimum depth of a box having that width. Let's store it in an array named $$$X$$$

    So in the example above, this array $$$X$$$ will look like this :

    1 2 3 4 5 6 7 ....
    0 7 0 5 0 0 0 ....
    

    We can now see thst when we evaluate box 4 (which has the width of 5), it's the same of finding minimum of $$$(X_1, X_2, X_3, X_4)$$$

    Then we check whether the minimum values is less than box 4's depth. If it is, then we can conclude that there's a box can be fit inside box 4

    And since we're gonna updating the $$$X$$$ values each time we evaluate new box and we can also need to find the minimum values of that array, then this task can be solved with segment tree

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

      Yeahhh, I got you.

      Thanks bro.

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

      Oh I forgot to mention that :

      • Initially all $$$X$$$'s value should be an arbitrarily large value so it won't be considered as minimum (the 0 I write in the example above is just for the better visualization)

      • Since the dimension of the box can reach $$$10^9$$$, make sure to have them compressed so it can be used as $$$X$$$'s indices

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

        yeah I figured and was trying to write up the code

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

Can someone plz tell why the ratings are not updated yet??

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

Any Hints for F?

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

I'm trying to solve F with a 2D fenwick tree.

First, rotate all the boxes to make $$$h_i\le w_i\le d_i$$$.

Then sort in ascending order of $$$h_i$$$. Do a compression on the second and third dimensions to make $$$1\le w_i, d_i\le N$$$.

For every $$$i$$$, first check the prefix sum of $$$(w_i-1, d_i-1)$$$. If the value is not zero, there must be at least one index $$$j<i$$$ such that $$$h_j<h_i$$$, $$$w_j<w_i$$$ and $$$d_j<d_i$$$ so we can print Yes (since we have sorted the boxes in ascending order of $$$h_i$$$, there is no need to check if $$$h_j<h_i$$$). Then update the fenwick tree to make $$$(w_i, d_i)=1$$$.

A typical implementation requires $$$\mathcal O(N^2)$$$ memory, but most of the $$$N\times N$$$ tree is always $$$0$$$, so we can reduce it to $$$\mathcal O(N\log^2 N)$$$ with a hash table (unordered_map).

The overall time complexity is $$$\mathcal O(N\log^2 N)$$$, which is expected to pass the task. But it got TLE on 11 of 64 cases. Why is that happening? my submission

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

    I'm not sure if this is the reason, but unordered_map has a big constant factor which is slowing your code down quite a lot. $$$O(n \log^2 n)$$$ is already quite heavy and it's not that surprising that significantly increasing the constant factor TLE's.

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

    Use gp_hash_table or some custom made faster hashtable.

    Submission after editing.

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

Alternative solution for E: Do a DFS, and keep a tag on how many generations of the most "promising" (i.e. it has the most generations currently available) are left to be used. When traversed to a certain node, attempt to use that node's insurance plan as the most "promising" one. This works because we only care about whether someone is insured, not how many insurances that cover them. Code