We will hold AtCoder Beginner Contest 240.
- Contest URL: https://atcoder.jp/contests/abc240
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220220T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: Kodaman, leaf1415, YoshikaMiyafuji
- Tester: penguinman, physics0523
- Rated range: ~ 1999
- The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
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.
I think it's just some complicated combinatorics.
I submitted using
atcoder::convolutionand it got WA on 3 tests (AC on the rest). Seems weird.Same question here. AC 57 tests and failed 3 tests. While NTT on half of the polynomial got AC.
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.
Well the round was good itself but because of fucking poor government in Iran and power outage I couldn't submit around 50 minutes :(
How to solve G?I think there is a simple formula but I can't find it.
Here's the link to editorial (Japanese). I guess you can just read the math formulas. Link
Why my solution of E got WA ? I have read the editorial but cannot find the mistake :(
We want the value of leaf of a subtree be consecutive.
We want vertex 4 and 5 {(1, 1) and (2, 2)} or {(2, 2) and (3, 3)} but not {(1, 1) and (3, 3)}.
I see, Thanks！:D
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
Thanks anyway.
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
how to use dp in c i have written recursive one but unable to write dp got tle in 6 cases
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
AC Submission
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
Oh, I think I made this assumption too, but my solution got AC.
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.
Can someone explain what Problem E is asking ?? I find it hard to understand !!
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?
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.
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
Thank You Brother !
Can someone prove or give me some intuition to why the following holds for a $$$\geq$$$ b $$$\geq$$$ c:
Used for problem G from today I think, as explained in editorial.
Both are the coeff of x^b in (1+x)^(a+c)
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)
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