chokudai's blog

AtCoder Beginner Contest 240 Announcement
By chokudai, history, 2 years ago, In English

We will hold AtCoder Beginner Contest 240.

We are looking forward to your participation!

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

Comments Comments (29)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

Could G be done using NTT? I tried using the same but got WA on later test cases. It didn't time out for most cases though.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I think it's just some complicated combinatorics.

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

    I submitted using atcoder::convolution and it got WA on 3 tests (AC on the rest). Seems weird.

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

    Same question here. AC 57 tests and failed 3 tests. While NTT on half of the polynomial got AC.

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

    I think NTT doesn't work for really big cases because the largest $$$2^n$$$th root of unity you can make in the finite field of order $$$998244353$$$ is $$$2^{23} < 10^7$$$. So then the NTT just calculates nonsense.

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

Well the round was good itself but because of fucking poor government in Iran and power outage I couldn't submit around 50 minutes :(

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

How to solve G?I think there is a simple formula but I can't find it.

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

    Here's the link to editorial (Japanese). I guess you can just read the math formulas. Link

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

Why my solution of E got WA ? I have read the editorial but cannot find the mistake :(

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

    We want the value of leaf of a subtree be consecutive.

        1
   / \
  2   3
 / \ 
4   5

    We want vertex 4 and 5 {(1, 1) and (2, 2)} or {(2, 2) and (3, 3)} but not {(1, 1) and (3, 3)}.

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

    tho i may be wrong i think what happens is that when u mark all leaves with num, num, you end up with the parent having a range larger than it should be. for example, because you dont mark leaves in dfs order, if a parent has children 2, 3, 5 that are all leaves, it may mark 2 as (1,1), 2 as (2,2), and 5 as (4,4), thus including leaf node marked (3,3) in the process.

    EDIT: oops someone beat me to it lol

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

In Problem E, I understood that the upper bound is the number of leaves and got accepted with a simple DFS. But I also tried it with BFS but it gives WA. Can anyone point out my mistake ? Submission

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

how to use dp in c i have written recursive one but unable to write dp got tle in 6 cases

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

    Let dp[i] be the set of position that we can reach when moving i steps. Initially, dp[0] = {0}. for i != 0, we iterate over dp[i-1]. Let P be some value in dp[i-1], we add P + a[i] and P + b[i] to set dp[i]. The answer is to find if X is in dp[n]. Submission

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

I fucked up in F coz my dumb ass thought that if xi is positive then taking all yi in sum will always give maximum for concave parabola

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

    Oh, I think I made this assumption too, but my solution got AC.

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

      Actually, I think implementing it this way is correct: the other alternative, taking 0 x_i's, is either not a global maximum, in which case it's safe to ignore, or it is already considered in the previous iteration. If x_{i-1} is positive, taking 0 x_i's is equivalent to taking y_{i-1} x_{i-1}'s. If x_{i-1} is negative, taking y_{i-1} x_{i-1}'s would be found by binary/ternary search.

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

Can someone explain what Problem E is asking ?? I find it hard to understand !!

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

    I think it is part of that problem to translate the formulars into some meaningful.

    From my point of view we can output all segements as l[i]=r[i]=1, that would satisfiy all conditions and would obviously minimize the max used value.

    Unfortunatly the editorial does not cover that part.

    Can somebody explain?

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

      Let u and v be two nodes, and they are not in each others subtree. Then intersection of [L_v, R_v] and [L_u, R_u] should be empty set. So (1,1) is wrong.

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

    the first condition is really just saying for two nodes i and j, Li,Ri must be completely inside or intersect with Lj,Rj if j is an ancestor of i

    the second one says their L and R values must not intersect if i and j are in different subtrees

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

Can someone prove or give me some intuition to why the following holds for a $$$\geq$$$ b $$$\geq$$$ c:

$$$ \sum_{i=0}^c {a \choose b-i}{c \choose i} = {a+c \choose b} $$$

Used for problem G from today I think, as explained in editorial.

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

    Both are the coeff of x^b in (1+x)^(a+c)

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

    You can think of the left term as a two-step process in which, you want to select $$$b$$$ elements from two sets. First, you choose $$$i$$$ element from $$$c$$$ then you choosing $$$b-i$$$ from $$$a$$$. This is equivalent to choosing $$$b$$$ directly from $$$a+c$$$ (it has a one-to-one mapping to the above two-step process)

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

There is an alternative answer to Problem F that does not require ternary search and just simple math. https://atcoder.jp/contests/abc240/submissions/29629051

→ Reply