Solutions to the last two problems of 3 Address Code Finals

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	SecondThread	150
7	-is-this-fft-	150
9	pajenegod	145
10	BledDest	144

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}})$$$

jtnydv25's blog