### jtnydv25's blog

By jtnydv25, history, 7 months ago, ,

Random flips

Let $h_n(r) = \displaystyle \sum_{i=1}^{n} i^r$.

$h_n(r), h_m(r)$ can be computed for all $1 \leq r \leq 2k$ for both $n, m$ in $O(k^2)$ 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}})$

• +73

 » 7 months ago, # |   -30 from where do you learn the meaths of problem 1. the maths it complicated and i hates probability and expectations.problem2 is good one.
 » 7 months ago, # |   -30 but none is for my level. i like algorithmic problems and hate maths. huh!