We will hold AtCoder Grand Contest 060. This contest counts for GP30 scores, and it's the last contest of this season.
- Contest URL: https://atcoder.jp/contests/agc060
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20221225T2100&p1=248
- Duration: 180 minutes
- Number of Tasks: 6
- Writer: maroonrk
- Tester: HIR180, satashun
- Rated range: 1200 -
The point values will be 400-700-800-1000-1400-2200.
We are looking forward to your participation!
Is AGC060 equivalent to Xmas2022 ?
If you are referring to Xmascon 2022, no they are completely different.
Wow, Christmas Round.
For C, $$$N^2 \log 998244353$$$ is not a model solution, but I set the TL so that such solutions can also pass. I'm sorry that some (not many, but some) solutions got TL with that complexity. I'll be more careful when setting constraints in the future.
Small tips: use the const keyword for the mod. There's a solution that turns into AC with this change.
Recently I copied Gauss from our library. It was much slower than expected. It was taking modulo as an argument and I was initially passing 1e9+7 there. When I hardcoded it, it sped up 5 times!!! I was expecting some speedup indeed, but definitely not by such a huge factor
The solution to F is quite similar to my solution to the recent PA problem.
You are given $$$n$$$ vertices with weight $$$a_1, a_2, \dots, a_n$$$, there are $$$\gcd(a_i, a_j)$$$ edges between the vertex $$$i$$$ and $$$j$$$. Compute the number of spanning trees.
My solution here.
But I didn't even try during the contest... sad...
How to solve C?
Is there another solution for C? I think the official solution is too hard to come up with.
Here's my solution:
Instead of considering permutations of size $$$2^n-1$$$, consider $$$2^n-1$$$ random real numbers between $$$0$$$ and $$$1$$$. The root doesn't matter at all(you can see that by noticing that, when looking at permutations, it's always $$$1$$$), so we can remove it to solve the problem on $$$2$$$ independent trees.
Let $$$P_i(x)$$$ be the probability that a tree with depth $$$i$$$ is heap-like if the value of node $$$V$$$ is $$$x$$$, up to constant factors(because in the end we'll only care about the ratio of 2 values of this polynomial). We can start with $$$P_{N-B}(x)=x^{2^{N-B}-2}$$$, and then to calculate $$$P_{i+1}(x)$$$ from $$$P_i(x)$$$, if the value of the root of the tree with depth $$$i+1$$$ is equal to $$$u$$$, then the probability that the left subtree is heap-like(up to constant factors) can easily be seen to be $$$u^{2^i-1}$$$, and to find the probability that the right subtree is heap-like, notice that we're just scaling down the problem from $$$0$$$ to $$$1$$$ to from $$$0$$$ to $$$u$$$, so the probability is $$$P_i(\frac{x}{u}) \cdot u^{2^i-2}$$$. So, $$$P_{i+1}(x)=\int_x^1 u^{2^{i+1}-3} \cdot P_i(\frac{x}{u}) du$$$. Notice that all nonzero coefficients of all $$$P_i(x)$$$ will be in positions $$$x^{2^j-2}$$$ for some natural number $$$j \leq i$$$, so we can calculate all nonzero coefficients of the polynomial $$$P_{i+1}$$$ from the nonzero coefficients of the polynomial $$$P_i$$$ in $$$O(i)$$$, which allows us to calculate all nonzero coefficients of $$$P_{N-1}$$$ in $$$O(N^2)$$$.
Similarly, let $$$Q_i(x)$$$ be the probability that a tree with depth $$$i$$$ is heap-like if the value of node $$$U$$$ is $$$x$$$. We can calculate $$$Q_{N-1}$$$ in the same way as $$$P_{N-1}$$$. Now, the answer is $$$\frac{\int_0^1 P_{N-1}(x) \cdot (\int_0^x Q_{N-1}(y) dy) dx}{\int_0^1 P_{N-1}(x) \cdot (\int_0^1 Q_{N-1}(y) dy) dx}$$$. The numerator can be calculated in $$$O(N^2$$$ $$$log$$$ $$$MOD)$$$, while the denominator can be calculated in $$$O(N$$$ $$$log$$$ $$$MOD)$$$.
Thanks! I'll try to understand it.
My solution is here.
The first question we concerned about is how to generate a heap "step by step"? Given a heap-like permutation, let's enumerate the value from $$$1$$$ to $$$n$$$, push its occuring position into a queue, and we can get a BFS order of this heap. With this observation we can turn the original problem into this:
It's easy to find that $$$U$$$ is on the left-most chain while $$$V$$$ is on the right-most chain of the heap. When performing BFS, we only concerned about how far we've step on these two chains. So, a ideal DP state appears: $$$f(u,v)$$$ representing the probability that the event "$$$u$$$ (on the left-most chain) occurs and $$$v$$$ (on the right-most chain) occurs, but $$$2u,2v+1$$$ don't" happens. Transformation is also apparent, $$$f(2u,v)\overset{+}{\longleftarrow}pf(u,v)$$$ and $$$f(u,2v+1)\overset{+}{\longleftarrow}(1-p)f(u,v)$$$, where $$$p$$$ is the probability that "when $$$u,v$$$ occur in a queue but $$$2u,2v+1$$$ don't, $$$2u$$$ occurs first during the subsequent BFS processing".
Our last task is to find $$$p$$$. We can get hint from sample 2, guessing $$$p=\frac{s_{2u}}{s_{2u}+s_{2v+1}}$$$, where $$$s_x$$$ is the size of subtree rooted at $$$x$$$.
Here is a proof. Let $$$S$$$ be the node set of subtree rooted at $$$2u$$$ and $$$T$$$ be the node set of subtree rooted at $$$2v+1$$$. $$$S\cup T$$$ is generated from $$${1,2,\cdots,n}$$$ in some way but we don't care it. What we care about is that known $$$S\cup T=U$$$, how to generate $$$S$$$ and $$$T$$$. Since two subtrees can't affect each other, we can simply choose $$$|S|$$$ elements from $$$U$$$ as $$$S$$$, and $$$T=U\setminus S$$$. But what it means? We know that $$$p_{2u}=\min S$$$ and $$$p_{2v+1}=\min T$$$, so the key is where $$$x=\min U$$$ goes! That is to say, when $$$x\in S$$$, $$$2u$$$ occurs first; when $$$x\in T$$$ otherwise, $$$2v+1$$$ goess first. What's the probability that a particular element is chosen into $$$S$$$? $$$\frac{|S|}{|S|+|T|}$$$ of course, that is the answer.
With $$$f(u,v)$$$, answer can be calculated by enumerate the situation $$$u\gets U$$$, $$$v\gets{\text{some node upper than }V}$$$. The calculation can be done in $$$\mathcal O(n^2\log P)$$$ or $$$\mathcal O(n^2)$$$.
Submission: https://atcoder.jp/contests/agc060/submissions/37547686
For D, how to understand the last part of the editorial, "This can eventually be reduced to the following problem"?
Let $$$a = \lbrace a_1 \dots a_{|a|} \rbrace \pod{a_i \in [n - 1]}$$$, then $$$f(a) = n! (a_1 - 0)!^{-1} (a_2 - a_1)!^{-1} \dots (n - a_{|a|})!^{-1}$$$.
Consider a directed graph with $$$n + 1$$$ vertices; the value of edge $$$u \to v$$$ is $$$(v - u)!^{-1} \pod{u < v}$$$. The value of a path is defined as the product of value of the edges of the path. Let $$$g(n)$$$ be the sum of value of all paths from $$$0$$$ to $$$n$$$.
Consider $$$a$$$ as a path from $$$0$$$ to $$$n$$$, then we have that $$$f(a)$$$ is equal to the value of path $$$a$$$ multiplied by $$$n!$$$. And $$$\sum_{c \subset a} f(a)$$$ is the sum of the value of all paths that contain the vertices in $$$c$$$, also multiplied by $$$n!$$$. We can divide a path into several parts ($$$0 \to c_1 \to \dots \to c_{|c|} \to n$$$). Then $$$\sum_{c \subset a} f(a) = n! \cdot g(c_1 - 0) g(c_2 - c_1) \dots g(n - c_{|c|})$$$.
I also couldn't get it for a long time. The problem I had was that you can do inclusion-exclusion over sets where you do put the $$$<$$$ signs into and then the solution is pretty much the same except at the end you need to sum over all possible "merges" of a sequence(like for [2,3,1] you sum over [2,3,1], [5,1], [2,4], [6]) which looks unsolvable.
Had to read the beginning carefully again to understand it.
The quadratic part of the official solution is as follows: create two vectors of numbers $$$P=(2^{N-1}-1, 2^{N-2}-1, \ldots, 2^{N-A}-1)$$$ and $$$Q=(2^{N-1}-1, \ldots, 2^{N-B}-1)$$$. Then repeat this step $$$B$$$ times: remove the last number $$$x$$$ from $$$Q$$$, subtract $$$x$$$ from every number in $$$Q$$$, add $$$x$$$ to every number in $$$P$$$, add $$$x$$$ to $$$P$$$. Find the product of all the numbers in $$$P$$$ and $$$Q$$$.
Let's look at the numbers that are still currently in $$$Q$$$, those that were moved from $$$Q$$$ to $$$P$$$ and those in $$$P$$$ separately.
The first group is pretty simple: it's a prefix of sequence $$$S = 1, 3, 7, \ldots, 2^k-1, \ldots$$$ times some power of 2. The pattern for the second group is a bit more tricky: the first number is a number from $$$S$$$. The rest of them is a "dot product" of a prefix of $$$S$$$ and some consecutive powers of 2. All in all it's a bit tedious but we can find the products of these numbers in linear time.
has a pretty simple formula: after $$$i$$$-th step the product we need is $$$\prod_{j=1}^A{(2^{N-j}+2^{N-B+i}-2)}$$$. So the idea is just to come up with a polynomial and then evaluate it at $$$N$$$ points, which would usually take $$$O(N \log^2 N)$$$ time(both for constructing it as a product of $$$N$$$ monomials and multipoint evaluation), but can be done in $$$O(N \log N)$$$ here!
Let's start with the polynomial $$$(x+1)(x+2)\ldots(x+2^k)$$$. Surprisingly(to me) its coefficients can be found in linear time thanks to something called q-binomial theorem(just reverse the coefficients). Then it's easy to find $$$(x+2^s)(x+2^{s+1})\ldots(x+2^{s+k})$$$ by multiplying each term by some power of 2. We can also change the variable from $$$x$$$ to $$$2^{N-B} x - 2$$$ again by similar manipulations and Taylor shift in $$$O(n \log n)$$$.
This gives us the polynomial we need. All that's left is to evaluate it at $$$x=1,2,4,\ldots,2^B$$$ which can be done in $$$O(N \log N)$$$ with Chirp Z-transform.