You are not logged in. Please login at www.codechef.com to post your questions!

×

CLTNGL - Editorial

PROBLEM LINK:

Practice
Contest

Author and Editorialist: Soumik Sarkar
Tester: Avijit Agarwal

DIFFICULTY:

HARD

PREREQUISITES:

Mobius inversion

PROBLEM:

There is a grid with $N$ equally spaced horizontal lines and $M$ equally spaced vertical lines. What is the expected number of grid points on the perimeter of a randomly chosen non-degenerate triangle with vertices at grid points.

EXPLANATION:

The problem asks for the expected number of grid points on the perimeter of a randomly chosen triangle which has non-zero area. Let's call these $good$ triangles. As each good triangle is equally likely, the answer is equal to the sum of grid points on the perimeter of all good triangles divided by the number of good triangles. $$ ans = \frac{good_{sum}}{good_{cnt}}$$

The number of grid points on the line segment joining $p_1=(x_1, y_1)$ and $p_2=(x_2, y_2)$ (including endpoints) minus one is given by $\gcd(|x_2-x_1|, |y_2 -y_1|)$. Let's denote this as $c(p_1, p_2)$ and assume we can get $c(p_1, p_2)$ for any pair of points in constant time. Clearly the number of grid points on the perimeter of a triangle with vertices at $p_1$, $p_2$ and $p_3$ is given by $c(p_1, p_2) + c(p_2, p_3) + c(p_3, p_1)$.

We can iterate over all triplets of points $(p_1, p_2, p_3)$, and for each triplet increment $good_{sum}$ and $good_{cnt}$ appropriately if the triplet forms a good triangle. This approach has complexity $\mathcal{O}(n^3m^3)$.

Improvement 1

To calculate the sum and count of good triangles, we can instead subtract proper values of $bad$ triangles from that of $all$ triangles.

$$ ans = \frac{good_{sum}}{good_{cnt}} = \frac{all_{sum} - bad_{sum}}{all_{cnt} - bad_{cnt}} $$

View Content

Then we have the answer as $$ans = \frac{\displaystyle 3mn \sum_{p_1} \sum_{p_2} c(p_1, p_2) - 6 \sum_{p_1} \sum_{p_2} c(p_1, p_2)^2}{\displaystyle n^3m^3 - 3 \sum_{p_1} \sum_{p_2} c(p_1, p_2) - nm}$$

Now $\displaystyle\sum_{p_1} \sum_{p_2} c(p_1, p_2)$ and $\displaystyle\sum_{p_1} \sum_{p_2} c(p_1, p_2)^2$ can be calculated by iterating over all pairs of points, so we are down to $\mathcal{O}(n^2m^2)$.

Improvement 2

Let's expand $\displaystyle\sum_{p_1} \sum_{p_2} c(p_1, p_2)$ as $\displaystyle\sum_{x_1=1}^n \sum_{y_1=1}^m \sum_{x_2=1}^n \sum_{y_2=1}^m \gcd(|x_2-x_1|, |y_2 -y_1|)$.
Considering the unique values of $|x_2-x_1|=i$ and $|y_2-y_1|=j$, we can say $$\begin{aligned} \sum_{p_1} \sum_{p_2} c(p_1, p_2) &=nm\gcd(0,0) + 2m\sum_{i=1}^{n-1}(n-i)\gcd(i, 0) + 2n\sum_{j=1}^{m-1}(m-j)\gcd(0, j) \\ &+ 4\sum_{i=1}^{n-1} \sum_{j=1}^{m-1} (n-i) (m-j)\gcd(i, j) \end{aligned}$$

A similar thing can be said for $\displaystyle\sum_{p_1} \sum_{p_2} c(p_1, p_2)^2$.

The first term in the expansion corresponds to cases of $p_1=p_2$ and can be calculated in constant time. The second and third terms deal with $p_1$ and $p_2$ on vertical and horizontal lines can be calculated in $\mathcal{O}(n + m)$, or even in constant time if one uses standard summation formulae. The last term requires $\mathcal{O}(nm)$.

Improvement 3

Here we focus on calculating $\displaystyle f_1(n, m) = \sum_{i=1}^n \sum_{j=1}^m (u-i) (v-j)\gcd(i, j)$ and $\displaystyle f_2(n, m) = \sum_{i=1}^n \sum_{j=1}^m (u-i) (v-j)\gcd(i, j)^2$.

Before proceeding further, I request you to go through this blog and this blog on multiplicative functions and Mobius inversion by Nisiyama_Suzune. I will be using identical notation as in the blog and the process used here is the same as described in the blog.

View Content

$$f_1(n, m) = \sum_{k=1}^n \left(uv \lfloor \frac{n}{k}\rfloor \lfloor \frac{m}{k}\rfloor -uk \lfloor \frac{n}{k}\rfloor s(\lfloor \frac{m}{k}\rfloor)-vk\ s( \lfloor \frac{n}{k}\rfloor) \lfloor \frac{m}{k}\rfloor + k^2s(\lfloor \frac{n}{k}\rfloor)s(\lfloor \frac{m}{k}\rfloor) \right) \sum_{d|k}\mu(d) \frac{k}{d}$$

Similarly we can say, $$f_2(n, m) = \sum_{k=1}^n \left(uv \lfloor \frac{n}{k}\rfloor \lfloor \frac{m}{k}\rfloor -uk \lfloor \frac{n}{k}\rfloor s(\lfloor \frac{m}{k}\rfloor)-vk\ s( \lfloor \frac{n}{k}\rfloor) \lfloor \frac{m}{k}\rfloor + k^2s(\lfloor \frac{n}{k}\rfloor)s(\lfloor \frac{m}{k}\rfloor) \right) \sum_{d|k}\mu(d) \frac{k^2}{d^2}$$

The function $\sum_{d|k}\mu(d) \frac{k}{d}$ is a multiplicative function which can be recognized as Euler's totient function $\varphi$. For a prime $p$, $\varphi(p^k) = p^k - p^{k-1}$. $\sum_{d|k}\mu(d) \frac{k^2}{d^2}$ is another multiplicative function, let's denote it by $\varphi_2$. Clearly $\varphi_2(p^k) = p^{2k} - p^{2k-2}$.
Both functions can be computed using a linear sieve as described in the above mentioned blog post.

The complexity of the solution is now $\mathcal{O}(n + m)$ which fits in the given time limit.

AUTHOR'S AND TESTER'S SOLUTION:

Author's solution can be found here
Tester's solution can be found here.

asked 16 Apr, 00:58

meooow's gravatar image

6★meooow ♦
6.6k617
accept rate: 49%

edited 20 Apr, 13:59

admin's gravatar image

0★admin ♦♦
19.0k348495533

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,487
×1,215
×52
×24
×3

question asked: 16 Apr, 00:58

question was seen: 190 times

last updated: 20 Apr, 13:59