Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

fanache99's blog

[OpenCup] Grand Prix of Grushevka
By fanache99, history, 2 years ago, In English

Can anybody post their solution to problem G?

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

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

Neither I, nor my teammates could solve it:(

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

How to solve A, H?

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

    H: Let's say

    Unable to parse markup [type=CF_MATHJAX]

    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

    Unable to parse markup [type=CF_MATHJAX]

    .

    Unable to parse markup [type=CF_MATHJAX]

    =

    Unable to parse markup [type=CF_MATHJAX]

    =

    Unable to parse markup [type=CF_MATHJAX]

    =

    Unable to parse markup [type=CF_MATHJAX]

    , where $$$F_i$$$ is sum of $$$a$$$ taken $$$i$$$ at a time.

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

    Unable to parse markup [type=CF_MATHJAX]

    The final summand is sum taken $$$k$$$ at a time from

    Unable to parse markup [type=CF_MATHJAX]

    , which is non-zero only for $$$k=0$$$ and

    Unable to parse markup [type=CF_MATHJAX]

    , as

    Unable to parse markup [type=CF_MATHJAX]

    .

    So, our sum becomes

    Unable to parse markup [type=CF_MATHJAX]

    = sum of the array $$$a$$$.

    Also,

    Unable to parse markup [type=CF_MATHJAX]

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

    → Reply
    • »
      »
      »
      2 years 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)$$$.)

      → Reply
»
2 years 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

Unable to parse markup [type=CF_MATHJAX]

, with FFT we can calculate it in $$$O(n\log n)$$$.

By the way, How to solve H and J?

→ Reply
  • »
    »
    2 years 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

    Unable to parse markup [type=CF_MATHJAX]

    with probability

    Unable to parse markup [type=CF_MATHJAX]

    and

    Unable to parse markup [type=CF_MATHJAX]

    with probability

    Unable to parse markup [type=CF_MATHJAX]

    .

    Initially we have

    Unable to parse markup [type=CF_MATHJAX]

    . Say in $$$r$$$ minutes $$$a$$$ bacteria were added inside and

    Unable to parse markup [type=CF_MATHJAX]

    outside. The probability of this happening is:

    Unable to parse markup [type=CF_MATHJAX]

    .

    So, the value after $$$r$$$ minutes is

    Unable to parse markup [type=CF_MATHJAX]

    .

    We can store prefix sums of

    Unable to parse markup [type=CF_MATHJAX]

    and

    Unable to parse markup [type=CF_MATHJAX]

    (or use hockey stick identity) to find the answer for each $$$r$$$ in $$$O(1)$$$
    → Reply
  • »
    »
    2 years 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

    Unable to parse markup [type=CF_MATHJAX]

    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

    Unable to parse markup [type=CF_MATHJAX]

    , where $$$f(A)$$$ equals to the number of the permutations of the multiset $$$A$$$ (i.e.

    Unable to parse markup [type=CF_MATHJAX]

    ). Since $$$q$$$ is prime, the polynomial

    Unable to parse markup [type=CF_MATHJAX]

    , so we have

    Unable to parse markup [type=CF_MATHJAX]

    . For the first term,

    Unable to parse markup [type=CF_MATHJAX]

    since the $$$S$$$ contains at least two different numbers. For the second term, note that

    Unable to parse markup [type=CF_MATHJAX]

    , 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...

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

    and how to do that with fft?

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

      Let

      Unable to parse markup [type=CF_MATHJAX]

      and

      Unable to parse markup [type=CF_MATHJAX]

      . This gives us

      Unable to parse markup [type=CF_MATHJAX]

      .

      Using sequences

      Unable to parse markup [type=CF_MATHJAX]

      and

      Unable to parse markup [type=CF_MATHJAX]

      , we have

      Unable to parse markup [type=CF_MATHJAX]

      (Intuitively,

      Unable to parse markup [type=CF_MATHJAX]

      multiplied by $$$x^N$$$ gives the polynomial $$$B$$$.)
      → Reply
»
2 years 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.

→ Reply
  • »
    »
    2 years 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.

    → Reply
»
2 years 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

Unable to parse markup [type=CF_MATHJAX]

, but we were kinda trying to finish other problems.
→ Reply