noomaK's blog

IEEEXtreme 17.0 Problems Discussion
By noomaK, history, 7 months ago, In English

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.

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

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

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.

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it +49 Vote: I do not like it

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

→ Reply
»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    polygon cutting

    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
»
7 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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);
→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

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

      It should be $$$(1 + X)^n \textbf{ mod } (-1 + X^k)$$$ ?

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

        You are right. Fixed, thanks!

        → Reply
»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Someone knows how to solve Dice?

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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.

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

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

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

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

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

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

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

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

          → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I get a hint for Powerful Strings?

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it -42 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it -25 Vote: I do not like it

        Why tf I’m getting these downvotes?

        → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it +13 Vote: I do not like it

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

            → Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

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

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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 :(

    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    BTW, what was the solution?

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Rumors ?

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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
    → Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

how i solve Rumors problem ?

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

    How you can solve Rumors Problem

    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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
    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve happy numbers and Labradoodle?

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

    I need that answer too

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

    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.

    → Reply