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

jtnydv25's blog

By jtnydv25, history, 2 months ago, In English,

Hi, we are hosting a mirror contest of ICPC Asia-Kharagpur Regionals. The contest has just started and is available here.

The live updates of the onsite contest are available here

Read more »

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

By jtnydv25, history, 11 months ago, In English,

Contest link


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

Read more »

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

By jtnydv25, history, 21 month(s) ago, In English,

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 Ct = AtB.

When processing the block t + 1 we assume that we know Ct, which is computed when block t has been completely processed. So, we compute Ct 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 Ct using FFT, and computing the remaining sum in O(k) using brute force iteration with the optimization above.) Just as an example, for N = 105, and m = 109 + 7 (which is a bad mod value for FFT problems), the best performance comes when you take K ≈ 6 × 103. For this input size it runs in about 2 seconds, which is pretty good.

Read more »

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

By jtnydv25, history, 2 years ago, In English,

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.

Read more »

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