xiaowuc1's blog

By xiaowuc1, 4 years ago, In English

Hi all,

The final contest of the 2019-2020 USACO season will be running from March 27th to March 30th. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

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

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +79 Vote: I do not like it

Now that we all have to deal with corona, is Bessie the Cow quarantined from the statements or not?

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Hello! Does anybody know if the contest is over yet?

»
4 years ago, # |
Rev. 2   Vote: I like it +76 Vote: I do not like it

Platinum:

Sprinklers2
Exercise
Circus

Screencast of finishing the season perfectly

Upd: codes

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    (Circus) How to determine the possibility of swapping u and v? I couldn't figure out any solution with polynomial time complexity.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it +18 Vote: I do not like it

      If we use dfs order, there are two cases. If $$$u\neq lca(u,v) \neq v$$$, then we can swap $$$u$$$ and $$$v$$$ if $$$d(u, v) \leq \text{number of removed nodes}$$$. Otherwise, (assume $$$lca(u, v)=u$$$) we need to consider nodes with $$$\text{degree} \geq 3$$$ (any node in path $$$u, v$$$ or the closest one from $$$u$$$ such that $$$depth(lca(u, w)) < depth(u) $$$).

      The simplest form of saying it, we can swap u and v if we can arrange it like so:

      u --- 0 --- v
            |
            0
      

      0 represents an empty node.

»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    What's the time complexity for exercise(platinum)? The with function is like $$$O((n/z)^2)$$$.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it +8 Vote: I do not like it

      Time complexity is $$$(n/z)^2$$$ summed over all prime powers $$$z$$$. This is less than $$$\sum_{i=1}^n\left(\frac{n}{i}\right)^2$$$ which equals to $$$\frac{n^2\pi^2}6$$$ when $$$n$$$ goes to infinity. Hence it is indeed $$$O(n^2)$$$ . I was told there exists $$$O(n\cdot\text{poly}\log)$$$ solution too.

      P.S. It seems the system also let $$$O(n^{2+\epsilon})$$$ solutions pass. The given optimization on modulo is probably needed in this case.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        How to do in $$$O(n\cdot \text{poly log})$$$? (I assume it requires division?)

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it +25 Vote: I do not like it

          Yes it needs division. I read it from Elegia's blog here(in Chinese). I can try to do some explanation.

          Basically we are still trying to find the number of permutations of length $$$n$$$ containing at least one cycle whose length is a multiple of $$$p^k$$$ for each $$$p$$$ and $$$k$$$.

          With some tough generating function manipulation, we can get the number of permutation of length $$$n$$$ , containing no cycles whose length is a multiple of $$$L$$$. It is $$$\frac{n!(L-1)(2L-1)\cdots(kL-1)}{k!L^k}$$$, where $$$k=\lfloor\frac nL\rfloor$$$. We can get the answer we are seeking easily with this.

          Since we are doing everything modulo $$$M-1$$$, we can get answer for each prime power divisor $$$q^t$$$ of $$$M-1$$$ and combine them with Chinese Remainder Theorem. It's almost the same as finding $$$\binom{n}{k}\bmod M-1$$$, just write each number in the form $$$q^a\cdot b$$$, where $$$\gcd (q,b)=1$$$. From here we actually have a $$$O(n\cdot\text{poly}\log)$$$ solution already.

          The blog did some further optimizing and analyzing to get complexity $$$O(n\log\log n+\frac{n}{\log n}\log M)$$$ (the latter part comes from factorization of $$$M$$$ I think, because we need to find only prime divisors $$$\le n$$$).

          To be honest if this is the intended solution I won't like this problem at all :)

»
4 years ago, # |
  Vote: I like it +73 Vote: I do not like it

Here are my detailed solutions to the first 2 problems of the Platinum division:

Problem 1. Sprinklers 2: Return of the Alfalfa.
Problem 2. Exercise.