awoo's blog

By awoo, history, 3 years ago, translation, In English

1644A - Doors and Keys

Idea: BledDest

Tutorial
Solution (awoo)

1644B - Anti-Fibonacci Permutation

Idea: BledDest

Tutorial
Solution (Neon)

1644C - Increase Subarray Sums

Idea: BledDest

Tutorial
Solution (awoo)

1644D - Cross Coloring

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1644E - Expand the Path

Idea: BledDest

Tutorial
Solution (awoo)

1644F - Basis

Idea: BledDest

Tutorial
  • Vote: I like it
  • +54
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Approach of D problem was great

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In problem D why we process the queries backward?

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

    When you process backwards, the query is equivalent to "color all squares in this row and column which are not yet colored". This way, each square will be colored at most once. So now your answer will be $$$k$$$ raised to some power(which is actually the number of queries where at least one square was colored).

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I processed all the queries forwards but ended up getting WA, but I am unable to understand how is there a difference between processing it forwards or backwards? Even if we are doing it forwards then, yes it might be possible that some square is getting colored more than once but in the end I am counting the different number of colors for all the squares so that shouldn't make a difference.

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

        For each query you want to determine something that happens in the future — in the later queries. So to tell something about query $$$i$$$, you have to first process queries $$$i+1$$$..$$$q$$$. That is exactly the same as going backwards over queries: you first determine the status of the query, then add the information about it to some data structure.

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

looks legit

upd. already fixed

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

Can anyone help why is this giving me TLE for D 147473308 ?

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

    You have initialized arrays visr and visc of size n and m respectively. Hence your time complexity is O(t*(n+m)) or larger, which in the worst case will be 2*1e9 since there is no limit on sum of m,n over all test cases.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Woah! I was facing the same issue. I would've never figured this out without your comment.

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

Can anyone please explain problem E?

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

No need for FFT in problem since we need only sum of those Stirling's number and this can be done in O(i): Since S(i,j) = sum(1<=t<=j) C(j,t) * t^i * (-1)^(j+t) / j! we have:
S(i,1)+S(i,2)+..+S(i,k) = sum(1<=j<=k,1<=t<=j)( t^i * (-1)^(j-t)/((j-t)! * t!) ).
Let d = j-t, then ans = sum(1<=t<=k,0<=d<=k-t)( (t^i/t!)*((-1)^d / d!) ) iterate over t and sum(0<=d<=k-t) ((-1)^d / d!) can be precomputed

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

    I really like this formula. It is elegant and works under any prime modulo. Thank you for sharing it!

    Here's a more detailed explanation and another way to look at it: Let $$$n \geq 1$$$ be a fixed integer.
    As in tutorial, let $$$p_i = \frac{(-1)^i}{i!}$$$ and $$$q_j = \frac{j^n}{j!}$$$.
    Then $$$S(n, k) = \sum\limits_{i+j=k} p_i \cdot q_j$$$.

    Consider a matrix $$$M$$$ in which $$$M_{i, j} = p_i \cdot q_j$$$ for $$$0 \leq i, j \leq n$$$.
    Then $$$S(n, k)$$$ is the sum of entries on the antidiagonal $$$i+j = k$$$.

    Suppose we want to find $$$S(n, 0) + S(n, 1) + ... S(n, k)$$$ for some $$$k$$$.
    That is to sum the entries above the antidiagonal $$$i+j=k$$$.
    We can sum these values column by column.
    For a fixed column $$$j$$$, the sum is $$$q_j \cdot \sum\limits_{i=0}^{k-j} p_i$$$.
    Thus, $$$S(n, 0) + S(n, 1) + ... S(n, k) = \sum\limits_{j=0}^{k} q_j \cdot \sum\limits_{i=0}^{k-j} p_i$$$.

    To compute this efficiently, note that $$$\sum\limits_{i=0}^{k-j} p_i$$$ is just the sum over a prefix of $$$p$$$.

    My implementation: https://codeforces.net/contest/1644/submission/148117254

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

    I have a question, though. To compute $$$S(i,1)+S(i,2)+...+S(i,k)$$$, the formula requires to find $$$t^i$$$ over $$$t=0,1,...,k$$$. Can this be computed (or precomputed) in $$$O(i)$$$?

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

      Oh I get it.
      We can use linear sieve to find all primes $$$p$$$ and compute $$$p^i$$$.
      For a composite $$$x = a \cdot b$$$, compute $$$x^i$$$ as $$$a^i \cdot b^i$$$.
      This is $$$O(k \log i / \log k) = O(i)$$$

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

C can be done with 2D DP. My submission is linked below 147347109

Note that I only used the custom "getbigger" function instead of the max function because the max function was being annoying for me.

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

Here are two alternate solutions for F. (Neither one uses any prior knowledge about the Stirling numbers.)

Simple no-FFT solution
EGF+ODE solution
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, why is the answer equal to k to the power of valid queries that have at least one cell belong to them? I am unable to understand. Why is "to the power"?

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In problem D, why TLE with vector(int) and AC with vector(bool) , time complexity doesn't change. AC code with bool,
TLE code with vector

UPD: People already answered this in Announcement for this contest

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

As for problem F, I think the solution described in the tutorial is in $$$O(n\sqrt{n}\log n)$$$ time complexity, because we have $$$O(\sqrt{n})$$$ $$$\lceil\frac{n}{i}\rceil$$$ s, and calculating each of them takes $$$O(n\log n)$$$. But the solution of F says it takes $$$O(n\log^2n)$$$, am I wrong or the tutorial made a mistake? Can anyone help me?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The polynomial describing $$$A_i$$$ has $$$\min(i, k) + 1$$$ terms, so the complexity of calculating $$$A_i$$$ is $$$O(i \log i)$$$ and the total complexity is $$$\sum \limits_{i = 1}^n O(\frac n i \log \frac n i) = O(n \log^2 n)$$$.

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I am doing question D the same way, but getting a wrong answer. I have used a set to store the rows and columns and then proceed with the maximum size among the two. Can anyone help me out, please? Link for my solution: https://codeforces.net/contest/1644/submission/155271519

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

My submission for problem D. https://codeforces.net/contest/1644/submission/157867234 Anybody please tell me where and why the code fails