Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

jtnydv25's blog

By jtnydv25, history, 6 years ago, In English

Contest link


Random flips


Let hn(r)=ni=1ir.

hn(r),hm(r) can be computed for all 1r2k for both n,m in O(k2) using the recursion:

(n+1)^{r+1} - 1 = \displaystyle \sum_{i=1}^{r+1} \binom{r+1}{i} h_n(r + 1 - i)

Let P_{ij} be the probability that (i, j) has a 1 in it after all the operations.

By linearity of expectation, we have to find \displaystyle \sum_{i, j} P_{i,j}.

Let p_{i,j} be the probability that cell (i, j) is flipped in one such operation.

The total number of submatrices is \dfrac{n(n+1)}{2} \dfrac{m(m+1)}{2}.

The number of submatrices containing (i, j) is i(n-i+1)j(m-j+1)

So,

p_{ij} = \displaystyle \dfrac{4 i(n+1-i)j(m+1-j) }{nm(n+1)(m+1)}

Now, P_{i, j} = probability that this cell is flipped in odd number of operations:

= \displaystyle \sum_{r \text{ odd}} \binom{k}{r} p_{i,j}^r (1-p_{i,j})^{k-r}
= \dfrac{1 - (1-2p_{i, j}) ^ k}{2}

So, we have to find:

\displaystyle \sum_{i = 1}^{n} \sum_{j = 1}^{m} ( 1 - 2p_{i, j})^k
= \displaystyle \sum_{i = 1}^{n} \sum_{j = 1}^{m} \left ( 1 - \dfrac{8}{n(n+1)m(m+1)} i(n+1-i) j (m+1-j) \right)^k

Let t = - \dfrac{8}{n(n+1)m(m+1)}. Also, let f_n(i) = i (n + 1 - i) and expand using binomial theorem:

We have :

\displaystyle \sum_{r = 0}^{k} \binom{k}{r} t^r \displaystyle \sum_{i=1}^{n} \sum_{j=1}^{m} f_n(i)^r f_m(j)^r
= \displaystyle \sum_{r = 0}^{k} \left ( \binom{k}{r} t^r \left ( \displaystyle \sum_{i=1}^{n} f_n(i)^r \right) \left ( \sum_{j=1}^{m} f_m(j)^r \right) \right)

Now,

\displaystyle \sum_{i=1}^{n} f_n(i)^r = \displaystyle \sum_{i=1}^{n} i^r(n + 1 - i)^r
= \displaystyle \sum_{i=1}^{n} \sum_{j=0}^{r} \binom{r}{j} (-1)^j (n+1)^{r-j} i^{r+j}
= \displaystyle \sum_{j=0}^{r} \binom{r}{j} (-1)^j (n+1)^{r-j} \sum_{i=1}^{n} i^{r+j}
= \displaystyle \sum_{j=0}^{r} \binom{r}{j} (-1)^j (n+1)^{r-j} h_n(r + j)

Hence, \displaystyle \sum_{i=1}^{n} f_n(i)^r can be computed in O(r) = O(k).

Thus the original formula can be computed in O(k^2)


A forest of perpendiculars


We convert the problem into:

Given a value r, find the number of lines with distance \leq r from point q.

For this, consider a circle C with radius r centered at q. Consider two points A and B, both outside the circle C. The line passing through A and B has distance \leq r from q iff it intersects the circle C. Let F_A and G_A be the points of contacts of tangents drawn from A to the circle. Similarly define F_B and G_B.

We can prove that the line passing through points A and B intersects the circle C if and only if the line segments F_{A} G_{A} and F_{B}G_{B} do NOT intersect.

So, we need to draw 2 n tangents, and then draw n chords passing through the respective points of contacts, and count the number of intersections of these chords.

For this, sort the points by polar angles in O(n \log{n}) . Now we can count the number of intersections of line segments in O(n \log{n}), by iterating on the points.

Therefore, this question can be answered in O(n \log{n}).

Then we can just binary search to find the answer in complexity O(n \log{n} \log{\frac{R}{\epsilon}})

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

| Write comment?