Блог пользователя noomaK

Автор noomaK, история, 12 месяцев назад, По-английски

Yesterday IEEEXtreme 17.0 was held, and there are a lot of problems to upsolve, so let's discuss problems here.

If there is a problem that you can't solve, maybe ask here and someone will help!

I will start with this problem, Cool Sum, I couldn't get more than 50% points and the only thing that came up online while searching for similar problems is “Generating Functions”, help.

  • Проголосовать: нравится
  • +70
  • Проголосовать: не нравится

»
12 месяцев назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Can you make a PDF of the problemset? IEEEXtreme is famously very closed. I can't access the problem you want help with, it sounds cool.

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится +49 Проголосовать: не нравится

For Cool Sum, there's a "trick" for computing sums of binomial coefficients with step $$$k$$$:

Let's look at the binomial formula: $$$(1+X)^n = \sum_{i=0}^n \binom{n}{i}X^i$$$.

The "trick" is to consider $$$X$$$ as the $$$k$$$-th roots of unity. This is because they wrap around when multiplied to the $$$k$$$-th power.

In essence, for some $$$\omega$$$ where $$$\omega^k = 1$$$ you have that:

$$$(1 + \omega)^n = \sum_{i=0}^n \binom{n}{i}\omega^i = \sum_{i=[0:n:k]} \binom{n}{i} + \omega \sum_{i=[1:n:k]} \binom{n}{i} + \ldots + \omega^{k-1} \sum_{i=[k-1:n:k]} \binom{n}{i} $$$.

Here $$$[a:b:c]$$$ is the set of numbers starting from $$$a$$$ until $$$b$$$ with step $$$c$$$ (similar to Python notation of slices).

So, in essence, $$$(1 + \omega)^n = ans_0 + ans_1 \omega + \ldots + ans_{k-1} \omega^{k-1}$$$. In other words, it's the answer (seen as a polynomial) evaluated in $$$\omega$$$.

Now, the FFT/NTT step comes naturally: first, compute $$$(1 + \omega_i)^n$$$ for all $$$\omega_i$$$ $$$k$$$-th roots of unity. Then, interpolate the polynomial given these $$$k$$$ $$$(\omega_i, (1 + \omega_i)^n)$$$ pairs. Because the $$$\omega_i$$$ are roots of unity, the "interpolation" can, in fact, be achieved by simply applying the inverse DFT on the array given by $$$(1 + \omega_i)^n$$$.

»
12 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

did you manage to solve Rectangles and Polygon Cutting?. I wasn't able to solve both. It'd be great if you share your intuitions for these

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    For the Rectangles, you can create a graph where there is an edge between $$$i$$$ and $$$j$$$ if $$$i$$$ and $$$j$$$ are coprime, then you can iterate over the cliques in this graph and calculate the maximum sum of a clique.

    This seems to pass within the TL when you don't consider the elements that are coprime with everything else.

    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      True. But max independent set is NP hard. So I used a bitmask DP with time complexity O(2^25 * poly), considering the set of prime factors used below 100.

»
12 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Cool sum:

Very short solution: Answer is the coefficients of (1+x)^n.

More details: In FFT, the degrees are "cyclic", which means x^a * x^b = x^((a+b)%L), where L=2^k is the length of FFT. So even if n is very large, the degree of each term in (1+x)^n is taken modulo by 2^k.

a[0] = a[1] = 1; // a is initialized as (1+x)
FFT(a, L);
for (int i = 0; i < L; i++) a[i] = POWER(a[i], n);
FFT(a, L, -1);
  • »
    »
    12 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Actually, the answer is the coefficients of $$$(1 + X)^n \textbf{ mod } (X^k - 1)$$$, which happens to be exactly the ring under which DFT space works.

»
12 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Someone knows how to solve Dice?

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    The answer is the n-th coefficient of generating function $$$(D^1+D^2+...+D^k)/k$$$, where $$$D=(x^1+x^2+...+x^6)/6$$$ represents a single die. Simplify the formula and you will finally get something easy to calculate.

    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you please elaborate a bit more? I can only think of methods using FFT, which is too slow.

      • »
        »
        »
        »
        12 месяцев назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        $$$(D^1+\cdots+D^k)/k=\dfrac{D^1-D^{k+1}}{(1-D)k}$$$

        Continue on substituting with $$$D=\dfrac{x^1-x^7}{6(1-x)}$$$

        And finally you can get the n-th coefficient of the formula without FFT.

        • »
          »
          »
          »
          »
          12 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Got it, thanks! It is quite surprising that inverse part can be done in a way without involving complex methods.

        • »
          »
          »
          »
          »
          11 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Could you explain a bit more how you get the nth coefficient of that polynomial? I'm struggling with the division.

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can I get a hint for Powerful Strings?

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится -42 Проголосовать: не нравится

    It’s dp on aho corasick dp[length][node]

    for len=0....n
       for j=0....m
         for c = 0.....25
            int nx=nxt[j][c] 
            dp[len+1][nx]+=dp[len][j]*pw[cnt[nx]]
    

    with some optimizations.

    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится +31 Проголосовать: не нравится

      Elaborating on "some optimizations":

      Let's create matrix $$$A$$$, where $$$A[x, y] = \operatorname{pw}[\operatorname{cnt}[y]] * \operatorname{edges}[x, y]$$$, where $$$\operatorname{edges}[x, y]$$$ is a number of transitions in Aho-Corasick automaton from $$$x$$$ to $$$y$$$. Now answer is equal to the sum of coefficients $$$A^n[1, i]$$$.

      Let's denote the answer for given $$$n$$$ as $$$f[n]$$$, then $$$f[n]$$$ follows a linear recurrence of size $$$m$$$, where $$$m$$$ is a size of matrix $$$A$$$. Therefore, you can find first $$$2 \cdot m$$$ values of $$$f[n]$$$ with DP in time $$$O(m^2 \cdot 26)$$$, find the linear recurrence in $$$O(m^2)$$$ with Berlekamp-Massey, and after that you need to find $$$n$$$-th element of linear recurrence, which can be done in $$$O(m^2 \cdot \log N)$$$ with polynomial exponentiation, or even in $$$O(m \log m \log N)$$$ with FFT.

      • »
        »
        »
        »
        12 месяцев назад, # ^ |
          Проголосовать: нравится -25 Проголосовать: не нравится

        Why tf I’m getting these downvotes?

      • »
        »
        »
        »
        12 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        I tried doing that, but I keep getting only 40%, this is my code.

        I generated more than $$$2 \cdot m$$$ elements of the sequence then used Berlekamp-Massey, but I get WA on most cases.

        Can you please provide a link to your code, or tell me what's wrong with my approach?

        • »
          »
          »
          »
          »
          12 месяцев назад, # ^ |
            Проголосовать: нравится +16 Проголосовать: не нравится

          In line 137 it should be cnt[root] += 1;, not cnt[root] = 1;. It is not guaranteed that the input strings are distinct.

          • »
            »
            »
            »
            »
            »
            12 месяцев назад, # ^ |
              Проголосовать: нравится +13 Проголосовать: не нравится

            Thank you!! That was really stupid of me, I just got 100%.

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

For those wondering why you have 9 on cosinus peoblem. Try reading negative numbers incorrectly. First read the integer part(with minus), then read the fractional part(as positive number) and ADD them. So when you see -1.1 solve the problem for -1.0 + 0.1 = -0.9.

Upd: 0.9 -> -0.9, a typo

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    actually it doesn’t matter 0.9 or -0.9 because cos(-x) = cos(x)

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    No wonder. During the contest, I had already known that the test data is wrong. A lot of strong teams got the same 9 points, and our team's solution had been revised for a whole day :(

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    BTW, what was the solution?

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Rumors ?

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    The idea is simple Get every connected component using only "??" edges And now you can test every component alone. If someone in the component has an in degree edge "->" then the whole component fails to be the source other wise all of them are possible sources.

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Make a weighted tree, i.e., If a->b exists: add edge (a, b, 1), (b, a, -1) For a ?? b add edge (a, b, 0), (b, a, 0)

    For each node as root find the sum of weight of edge going away from root. If the sum is exactly equal to the number of edges a->b (form) then it is a possible source. Basically, you need to find sum of weight of edge for every node as root node. For this, you will do rerooting.

    Here's my accepted code:

    Code
»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

How to solve Theme Park?

I only managed to get 60 points by floyd-warshall, iterating over all edges as options, taking the best option, and if d = 2, take the best option after taking the one selected before.

This might be not the best answer, as maybe you can take two edges that are not the best, but their sum are the best. But I didn't know any better approximation

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    It is enough to consider only pairs of edges which have a common vertex (either starting or ending one), which leads to $$$O(n^3)$$$ solution.

    Why: let's say we have a pair of edges $$$(u \to v)$$$ and $$$(x \to y)$$$, then at least one of options $$$u := x$$$, $$$x := u$$$, $$$v := y$$$, $$$y := v$$$ is not worse. You can prove it by contradiction by writing down inequalities.

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

how i solve Rumors problem ?

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Make a weighted tree, i.e., If a->b exists: add edge (a, b, 1), (b, a, -1) For a ?? b add edge (a, b, 0), (b, a, 0)

    For each node as root find the sum of weight of edge going away from root. If the sum is exactly equal to the number of edges a->b (form) then it is a possible source. Basically, you need to find sum of weight of edge for every node as root node. For this, you will do rerooting.

    Here's my accepted code:

    Code
  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can erase all nodes you can reach from any node in a path where the first edge is directed (the -> edges). The answer are the remaining nodes. This is because, if a-> b, then obviously b can't be the source of the rumour. a, or an ancestor of a must be the source. Now, as b heard the rumour, all edges that the node b has should be directed from b, say b-> x for all edges b ?? x

    Why?

    Then, x heard the rumour and you can continue erasing nodes until there are only left nodes with ?? edges and no -> edges.

    My Code
»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve happy numbers and Labradoodle?

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For Labradoodle, you can solve it by brute forcing every prefix and suffix of the potential words, and checking for their existance using std::map or something like that then checking for ambiguity, if you're having a hard time implementing that you can check my code here.

    As for Happy Numbers, you need to know Digit DP before you can solve it, so you can try learning that then coming back to it.