fanache99's blog

By fanache99, history, 10 months ago, In English

Can anybody post their solution to problem G?

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

»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Neither I, nor my teammates could solve it:(

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

How to solve A, H?

  • »
    »
    10 months ago, # ^ |
    Rev. 5   Vote: I like it +26 Vote: I do not like it

    H: Let's say $$$g(a) = \displaystyle \prod_{i=1}^{q} (a_i + i) + \sum a_i 2^{i-1}$$$

    Call the frequency sequence of $$$a$$$ to be the sequence $$$f$$$, where $$$f_i$$$ is the frequency of $$$i$$$ in $$$a$$$. We'll prove that for some frequency sequence $$$f$$$ with all values < $$$q$$$, the sum of $$$g(a)$$$ over all permutations $$$a$$$ with frequency sequence $$$f$$$ is $$$0$$$ and hence, it is enough to just consider arrays with all values same to solve the problem.

    To find the sum, we can consider all values different and divide by $$$\prod f_i!$$$.

    $$$ \displaystyle \sum_{\sigma} \prod_{i=1}^{q} (a_{\sigma_i} + i)$$$ = $$$\displaystyle \sum_{S \subseteq [q]} \prod_{i \in S} i \prod_{j \notin S} a_{\sigma_j} $$$

    = $$$\displaystyle \sum_{S \subseteq [q]} \left( \prod_{i \in S} i \right) \left( \sum_{\sigma} \prod_{j \notin S} a_{\sigma_j} \right) $$$

    = $$$\displaystyle \sum_{S \subseteq [q]} \left( \prod_{i \in S} i \right) \left( F_{q-|S|} |S|! (q-|S|)! \right)$$$, where $$$F_i$$$ is sum of $$$a$$$ taken $$$i$$$ at a time.

    Now, we can iterate on $$$|S|$$$. And our sum becomes:

    $$$\displaystyle \sum_{k=0}^{q} F_{q-k} k! (q-k)! \sum_{S \subset q, |S| = k} \prod_{i \in S} i $$$

    The final summand is sum taken $$$k$$$ at a time from $$${1, 2, \ldots q}$$$, which is non-zero only for $$$k=0$$$ and $$$k=q-1$$$, as $$$(x+1)(x+2) \ldots (x+q) = x^q - x$$$.

    So, our sum becomes $$$F_q 0! q! - F_1 (q-1)! 1! = F_1$$$ = sum of the array $$$a$$$.

    Also, $$$\displaystyle \sum_{\sigma} \sum_{i=1}^{q} a_i 2^{i - 1} = \sum_{i} a_i (2^0 + \ldots 2^{q-1}) (q-1)! = F_1 (2^q-1) (q-1)! = -F_1$$$

    So, the total sum becomes $$$0$$$ for any $$$f$$$ with all values < $$$q$$$.

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

      It actually suffices to consider only the cyclic rotations of a particular string, rather than all permutations. Consider the polynomial $$$P(x) = \displaystyle\prod_{i=1}^{q} (a_i + i + x)$$$. Then, summed over cyclic rotations of the string, the first term is $$$\sum_{x=0}^{q-1} P(x)$$$. Now,

      $$$\displaystyle\sum_{x=0}^{q-1} x^k = \begin{cases} q-1 & q-1 \mid k \text{ and } k > 0 \\ 0 & \text{else} \end{cases}$$$

      $$$P(x)$$$ has degree $$$q$$$, so for $$$q > 2$$$, only the $$$x^{q-1}$$$ term has nonzero value. In particular, the value of the sum is $$$(q-1) \sum_{i=1}^{q} a_i + i = (q-1) \sum_{i=1}^{q} a_i$$$. The rest of the proof is essentially the same.

      (For $$$q=2$$$, we can directly analyze $$$g(ab)$$$ versus $$$g(ba)$$$.)

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

Problem G goes like that:

It's easy to see if a subseq&=0, in every bit there will be a number equaling to 0.

we used inclusion-exclusion principle. Let $$$f_x$$$ be the number of $$$a_i$$$ that includes bitset $$$x$$$, which is easy to get with FMT.

The answer for $$$i$$$ is $$$\sum_{x} (-1)^{popcnt(x)} \binom{f_x}{i}$$$, with FFT we can calculate it in $$$O(n\log n)$$$.

By the way, How to solve H and J?

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

    J: We can find the expected value of max(0, bacteria inside — bacteria outside) for one petri-dish and multiply by $$$n$$$.

    Let $$$x$$$ be the bacteria inside and $$$y$$$ outside. We have a simple process. We go from $$$(x, y) \rightarrow (x, y+1)$$$ with probability $$$y/(x+y)$$$ and $$$(x +1, y)$$$ with probability $$$x / (x + y)$$$.

    Initially we have $$$(x, y) = (1, n - 1)$$$. Say in $$$r$$$ minutes $$$a$$$ bacteria were added inside and $$$r-a$$$ outside. The probability of this happening is:

    $$$ \displaystyle \dfrac{\binom{r}{a} (n-1) n \ldots (n-1 + r - a - 1) a!}{n (n + 1) \ldots (n + r)} = \dfrac{\binom{n - 2 + r - a}{r - a}}{\binom{n - 1 + r}{r}}$$$.

    So, the value after $$$r$$$ minutes is $$$\displaystyle \sum_{a} \dfrac{\binom{n - 2 + r - a}{r - a}}{\binom{n - 1 + r}{r}} \max(0, 2a - n - r + 2)$$$.

    We can store prefix sums of $$$\binom{n-2+i}{i}$$$ and $$$i \binom{n-2+i}{i}$$$ (or use hockey stick identity) to find the answer for each $$$r$$$ in $$$O(1)$$$

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

    UPD: Sorry I didn't realize that jtnydv25 had posted the solution above :(

    H: The main observation is if the multiset of the digits $$$A = { a_1, a_2, \cdots, a_q }$$$ contains two different numbers, the sum of luckiness over all permutations of these digits will be equal to zero. So you only need to take all numbers with equal digits and add them to the answer. In the contest, I simply guessed the conclusion and used a brute force solution to verify it.

    Proof: Note that $$$X = \sum_{\sigma} \prod_{i=1}^q (a_{\sigma(i)} + i) = \sum_{S \subseteq A} f(A) f(S \setminus A) \cdot \left([z^{q-|A|}] \prod_{i=1}^q (z+i)\right) \cdot \prod_{z \in A} z$$$, where $$$f(A)$$$ equals to the number of the permutations of the multiset $$$A$$$ (i.e. $$$f(A) = \binom{|A|}{c_0,c_1,\cdots,c_{n-1}}$$$ ). Since $$$q$$$ is prime, the polynomial $$$\prod_{i=1}^q (z+i) \equiv z^q - z \pmod q$$$, so we have $$$X = f(S)f(\varnothing) \prod_{z \in S} z - \sum_{z \in S} f({z})f(S \setminus {z})\cdot z $$$. For the first term, $$$f(S) = \binom{q}{c_0,\cdots,c_{n-1}} \equiv 0 \pmod q$$$ since the $$$S$$$ contains at least two different numbers. For the second term, note that $$$\sum_{i=0}^{q-1} 2^i = 2^q - 1 \equiv 1 \pmod q$$$, so the overall sum equals to $$$0$$$.

    By the way, I don't think this task is suitable for a contest. It's more like a work based on the existing proof, and I didn't do anything in the contest except guess the conclusion...

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

    and how to do that with fft?

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

      Let $$$N = 2^n$$$ and $$$g_j = \sum_{x | f_x = j} (-1)^{\text{popcnt}(x)}$$$. This gives us $$$b_i = \sum_j \frac{g_j j!}{i! (j - i)!}$$$.

      Using sequences $$$A_k = g_k k!$$$ and $$$B_k = \frac{1}{(N - k)!}$$$, we have $$$(A \star B)_{N+i} = \sum_j A_j B_{N + i - j} = \sum_j g_j j! \frac{1}{(j - i)!} = i! b_i$$$

      (Intuitively, $$$B' = \sum_j \frac{1}{j!} x^{-j}$$$ multiplied by $$$x^N$$$ gives the polynomial $$$B$$$.)

»
10 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Is there any simple way to solve A?

My ugly approach is to use a union-find structure to maintain the current component of ants, and the whole process needs a linked list or something similar to compress the vertices of degree $$$2$$$. But it contains so many corner cases and details that it's a nightmare to implement it.

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

    You can use the same approach but with sqrt decomposition on queries. It becomes relatively easy to implement.

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

It was quite confusing that two of us knew that in problem J it suffices to find a matching which maximizes sum of squares of edge lengths. In the end we came up with some solution finding a good cross composed of two lines in $$$O(n\log{n}\log(precision))$$$, but we were kinda trying to finish other problems.