maroonrk's blog

By maroonrk, history, 6 weeks ago, In English

We will hold AtCoder Grand Contest 060. This contest counts for GP30 scores, and it's the last contest of this season.

The point values will be 400-700-800-1000-1400-2200.

We are looking forward to your participation!

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

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

Is AGC060 equivalent to Xmas2022 ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    If you are referring to Xmascon 2022, no they are completely different.

»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Wow, Christmas Round.

»
5 weeks ago, # |
  Vote: I like it +78 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    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

»
5 weeks ago, # |
  Vote: I like it +110 Vote: I do not like it

The solution to F is quite similar to my solution to the recent PA problem.

Problem

My solution here.

But I didn't even try during the contest... sad...

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there another solution for C? I think the official solution is too hard to come up with.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +32 Vote: I do not like it

    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)$$$.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks! I'll try to understand it.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +39 Vote: I do not like 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:

      Find the probability that $$$U$$$ occurs in a random BFS queue before $$$V$$$.

      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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, how to understand the last part of the editorial, "This can eventually be reduced to the following problem"?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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|})$$$.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it
C in O(n log n) by hos.lyric