Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Before contest

Codeforces Round #623 (Div. 1, based on VK Cup 2019-2020 - Elimination Round, Engine)

23:11:31

Register now »

Codeforces Round #623 (Div. 1, based on VK Cup 2019-2020 - Elimination Round, Engine)

23:11:31

Register now »

*has extra registration

Before contest

Codeforces Round #623 (Div. 2, based on VK Cup 2019-2020 - Elimination Round, Engine)

23:11:30

Register now »

Codeforces Round #623 (Div. 2, based on VK Cup 2019-2020 - Elimination Round, Engine)

23:11:30

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3404 |

3 | TLE | 3356 |

4 | apiadu | 3351 |

5 | mnbvmar | 3281 |

6 | LHiC | 3276 |

7 | Um_nik | 3268 |

8 | 300iq | 3267 |

9 | yosupo | 3249 |

10 | ainta | 3226 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 168 |

5 | vovuh | 167 |

6 | pikmike | 166 |

7 | ko_osaga | 161 |

8 | Um_nik | 160 |

9 | Petr | 154 |

10 | McDic | 152 |

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:

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,

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

So, we have to find:

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 :

Now,

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

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

Say we need to solve a recurrence of the form :

Here, *f* is an arbitrary function which can be computed in *O*(1). An example of such a problem is 553E - Kyoya and Train. The tutorial gives a solution in .

I recently saw a similar problem in codechef may long SERSUM, where I used another technique which I had thought of when I saw the prior problem. In this post I explain this very simple and intuitive sqrt decomposition solution, running in which works in almost the same time as solution because of a very low constant. Here goes:

Let us divide into blocks of size say *K*, giving us a total of ⌈ *N* / *K*⌉ blocks. Block *t* consists of [(*t* - 1)*K*, *tK* - 1]

Let .

Let *C*_{t} = *A*_{t}*B*.

When processing the block *t* + 1 we assume that we know *C*_{t}, which is computed when block *t* has been completely processed. So, we compute *C*_{t} a total of times using FFT in time .

Consider some *n* between [*tK*, (*t* + 1)*K* - 1]. Then,

.

Clearly, the right part can be calculated in *O*(*K*), and we have an extra time of *O*(*NK*) because of this part.

Overall complexity = , which is minimized taking , and overall complexity is .

An optimization:

Note that the right part can be computed with only one mod operation if we use m2 = m * m, and keep subtracting m2 when the total sum exceeds it. Eventually we take total sum modulo m. This is a very common technique, which we use in matrix multiplication as well.

This means that we should use a block size even greater than for better results, because of a huge constant difference in the two parts. (Computing *C*_{t} using FFT, and computing the remaining sum in *O*(*k*) using brute force iteration with the optimization above.) Just as an example, for *N* = 10^{5}, and *m* = 10^{9} + 7 (which is a bad mod value for FFT problems), the best performance comes when you take *K* ≈ 6 × 10^{3}. For this input size it runs in about 2 seconds, which is pretty good.

Hello Codeforces Community!!!

I invite you all to take part in Hackerearth's March Easy contest.The contest will be held on 1st March,2018 at 22:00 IST.

Problems have been set by allcodeAC and tested by trytolearn and me.

You will be given 5 algorithmic problems to solve in 3 hours. Partial scoring will be used (you get points for passing each test case). Although the contest is targeted towards beginners, we hope even experienced problem-solvers find one or two problems to be interesting. The contest is rated and prizes will be awarded to the top 3 beginners(i.e. Programmers with a rating of 1600 or less before the challenge starts).

Good luck and have fun.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/22/2020 19:53:30 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|