Apple_Method's blog

By Apple_Method, 2 years ago, In English

Recently, while I have been working on setting problems for various competitions (including CerealCodes), I ran into a problem about how to compute PIE weights in $$$O(n^2)$$$.

Here's the problem:

Given values $$$count_k$$$ for all $$$k$$$ from $$$0, 1, \cdots, n$$$, if $$$count_k = \sum_{i = 0}^n \binom{k}{i}ans_i$$$, compute $$$ans_i$$$ for all $$$i$$$ from $$$0, 1, \cdots, n$$$. (You can probably see the applications of such a method when you are using PIE to solve a problem, hence why I would call these pie weights).

Now, we can develop a system of equations. From the premise of the problem, we have that

\begin{alignat*}{5} \binom{0}{0}ans_0 & {}+{} & \binom{0}{1}ans_1 & {}+{} & \cdots & {}+{} & \binom{0}{n}ans_n & {}={} & count_0 \newline \binom{1}{0}ans_0 & {}+{} & \binom{1}{1}ans_1 & {}+{} & \cdots & {}+{} & \binom{1}{n}ans_n & {}={} & count_1 \newline \cdots \newline \binom{n}{0}ans_0 & {}+{} & \binom{n}{1}ans_1 & {}+{} & \cdots & {}+{} & \binom{n}{n}ans_n & {}={} & count_n \end{alignat*}

Then, we can write

\begin{align} \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \newline 1 & 1 & 0 & \cdots & 0 \newline 1 & 2 & 1 & \cdots & 0 \newline \vdots & \vdots & \vdots & \ddots & \cdots \newline 1 & n & \frac{n(n-1)}{2} & \cdots & 1 \end{pmatrix} \begin{pmatrix} ans_0 \newline ans_1 \newline ans_2 \newline \vdots \newline ans_n \end{pmatrix} = \begin{pmatrix} count_0 \newline count_1 \newline count_2 \newline \vdots \newline ans_n \end{pmatrix} \end{align}

Thus, we can write

\begin{align} \begin{pmatrix} ans_0 \newline ans_1 \newline ans_2 \newline \vdots \newline ans_n \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \newline 1 & 1 & 0 & \cdots & 0 \newline 1 & 2 & 1 & \cdots & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline 1 & n & \frac{n(n-1)}{2} & \cdots & 1 \end{pmatrix}^{-1} \begin{pmatrix} count_0 \newline count_1 \newline count_2 \newline \vdots \newline ans_n \end{pmatrix} \end{align}

So it suffices to calculate

\begin{align} \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \newline 1 & 1 & 0 & \cdots & 0 \newline 1 & 2 & 1 & \cdots & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline 1 & n & \frac{n(n-1)}{2} & \cdots & 1 \end{pmatrix}^{-1} \end{align}

in $$$O(n^2)$$$ time.

To find this, let's break it down into its elementary row operations. Notice that because of pascal's identity, subtracting each row by the previous row will result in an extremely similar matrix. In fact, we can see that

\begin{align} \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \newline 1 & 1 & 0 & \cdots & 0 \newline 1 & 2 & 1 & \cdots & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline 1 & n & \frac{n(n-1)}{2} & \cdots & 1 \end{pmatrix}^{-1} = \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \newline -1 & 1 & 0 & \cdots & 0 & 0 \newline 0 & -1 & 1 & \cdots & 0 & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \newline 0 & 0 & 0 & \cdots & -1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \newline 0 & 1 & 0 & \cdots & 0 \newline 0 & 1 & 1 & \cdots & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline 0 & 1 & n-1 & \cdots & 1 \end{pmatrix}^{-1} \end{align}

Thus, we can break the desired matrix up into a bunch of elementary row operations the following way:

\begin{align} \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \newline 1 & 1 & 0 & \cdots & 0 \newline 1 & 2 & 1 & \cdots & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline 1 & n & \frac{n(n-1)}{2} & \cdots & 1 \end{pmatrix}^{-1} = \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \newline -1 & 1 & 0 & \cdots & 0 & 0 \newline 0 & -1 & 1 & \cdots & 0 & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \newline 0 & 0 & 0 & \cdots & -1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \newline 0 & 1 & 0 & \cdots & 0 \newline 0 & -1 & 1 & \cdots & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline 0 & 0 & 0 & \cdots & 1 \end{pmatrix} \cdots \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \newline 0 & 1 & 0 & \cdots & 0 & 0 \newline 0 & 0 & 1 & \cdots & 0 & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \newline 0 & 0 & 0 & \cdots & -1 & 1 \end{pmatrix} \end{align}

Now, we just need to optimize this to $$$O(n^2)$$$. Let $$$M_k$$$ be the product of the last $$$k$$$ matrices. Then, the following properties are satisfied:

The only cells that differ from the identity matrix are in the bottom-right most $$$k \times k$$$ submatrix.

If you remove the last row and the last column of $$$M_{k+1}$$$, the bottom-right most $$$k \times k$$$ submatrix is the same as the bottom-right most $$$k \times k$$$ submatrix of $$$M_k$$$.

Using these two observations, we can solve the problem: we can iterate over $$$k$$$: we will be storing the bottom-most $$$k \times k$$$ submatrix of $$$M_k$$$. Then, to compute $$$M_{k+1}$$$ from $$$M_k$$$, we just need to compute the last row. Because there are $$$O(1)$$$ transitions for each element within the last row, this takes $$$O(k)$$$ time, for a total of $$$O(n^2)$$$ time.

A sample code for this:

pie[0][0] = 1;
for(int i = 1; i < n; i++){
    pie[i][0] = sub(0, pie[i-1][0]);
    for(int j = 1; j <= i; j++) pie[i][j] = sub(pie[i-1][j-1], pie[i-1][j]);
}

In fact, the solution code to the CerealCodes problem Cereal Trees uses this idea.

Disclaimer: This is not the only solution; there is a much simpler solution by manipulating chooses to find the answer, but I thought this method was much cooler since it does not require any choose functions, just addition and subtraction, and can also be generalized further.

Full text and comments »

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

By Apple_Method, history, 3 years ago, In English

Hi codeforces!

A group of friends and I were recently working towards proposing a contest, since we had many ideas and one of my friends recently reached master. After figuring out most of the problems, we decided to propose the contest earlier today, but I encountered an interesting problem that I did not find a blog for, explaining the solution.

After my friend sent the invitation to coauthor the contest, I could see all of the problems that we had written so far, but I could not edit or create any new problems.

On my friend's screen, he could see the normal 5 bars which allows him to create problems:

However, on my screen, I can only see:

No matter what I do, it does not seem like I am able to propose a problem. For now, I have sent all of the information to my friends through discord and they have uploaded the problems, but it is super inconvenient and also very unproductive. Is this intentional (and if so, why would codeforces want to block me and not my friends), or is this a bug?

If it is a bug, I would appreciate it so much if it were fixed.

Note: this is not a complaint; the systems that the codeforces staff has been able to create is wonderful and much appreciated. Rather, this is an inquiry into why I do not have the ability to propose problems, as I have not found any other resources on codeforces that answer my question. If anyone can link a blog, that would also be excellent!

Full text and comments »

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

By Apple_Method, history, 4 years ago, In English

Hi everyone,

I was thinking about the following string problem:

You are given a string of length n, and q queries. Each query is a substring of the original string (s[l ... r]). For each query, you want to find the number of prefixes of the substring that are equal to a suffix. For example:

abcabc

2

1 3

1 5

For the first query, the answer should be 1, and the second query, the answer should be 2 (abcab == abcab, and ab == ab).

I haven't made much progress so far (I tried getting aho-corasick and suffix array to work, but I didn't find a way). Assuming $$$n \le 10^5$$$ and $$$q \le 10^5$$$, none of my ideas work.

Is there a solution to this problem, or is the lower bound on the time complexity $$$O(n^2+q)$$$ or $$$O(nq)$$$ (the best solutions i have found so far).

Because the problem has no source (I was thinking about problem ideas and stumbled upon this one) there might be no answer, but the problem seems so simple that there has to be one.

Excuse me if there are any mistakes here, as this is my first blog ever

Full text and comments »

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