GEOMMEAN - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Никита Лазарев
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Prefix-Sums

PROBLEM:

A famous student of AESC MSU, as you know, comes from Kostomuksha. Kostomuksha has a popular game called Doka.

The essence of Doka is as follows:

You are given an array A and an integer X. You want to calculate how many subarrays of this array have a geometric mean of X.

Formally, calculate the number of pairs of integers (L, R) such that 1 \leq L \leq R \leq N and
\sqrt[R-L+1]{A_L \cdot A_{L + 1} \cdot \ldots \cdot A_{R}} = X

EXPLANATION:

Let’s first try to simplify the expression:

\sqrt[R-L+1]{A_L \cdot A_{L + 1} \cdot \ldots \cdot A_{R}} = X \implies A_L \cdot A_{L + 1} \cdot \ldots \cdot A_{R} = X^{R-L+1}

Let X = p_1^{c_1} \cdot p_2^{c_2} \ldots p_k^{c_k}, where p_1 \ldots p_k are primes. Substituting this back, we have

A_L \cdot A_{L + 1} \cdot \ldots \cdot A_{R} = p_1^{(R-L+1) \cdot c_1} \cdot p_2^{(R-L+1) \cdot c_2} \ldots p_k^{(R-L+1) \cdot c_k}.

This suggests that we can deal with the powers of prime only to simplify our problem. Let us first factorize X, and then find the exponents of the prime factors of X for all A_i. If A_i has a prime factor which is not a prime factor of X, then this A_i can never be a part of a valid subarray. Hence we only need to find the exponents of prime factors of X. Let c_{i_j} denotes the exponent of p_i in A_j. Rewriting our condition back, we have

c_{i_L} + c_{i_{L+1}} + \ldots + c_{i_R} = (R-L+1) \cdot c_i, \forall i: 1 \leq i \leq k.
We can solve this problem using the prefix-sum technique. Let pre_{i_L} = \sum_{j = 1}^{L} c_{i_j}. So we have

pre_{i_R} - pre_{i_{L-1}} = (R - (L-1)) \cdot c_i \implies pre_{i_R} - R \cdot c_i = pre_{i_{L-1}} - (L-1)\cdot c_i.

In other words, we can maintain the values of pre_{i_j} - j \cdot c_i \forall i, j, and then we need to find out the number of pairs for which these values are equal for all i. So we have vectors corresponding to each index (with i^{th} element handling i^{th} prime) and we need to find out number of pairs for which these vectors are equal. This can be done using either hashing, or using map.

TIME COMPLEXITY:

To factorize X, we will require O(\sqrt{X}) time, and this will yield k = O(\log{X}) prime factors of X.
To find out exponents for each number, we will require O(N \cdot (\log{X} + \log{A_i})) time.
Using maps for these vectors, and finding number of pairs will require O(N \cdot \log{N} \cdot (\log{X} + \log{A_i})) time.

SOLUTION:

Editorialist’s Solution
Tester1’s Solution
Tester2’s Solution
Setter’s Solution

1 Like

A brute-force implementation worked!
Multiply using modulo K (where K is a >= 10 digit prime number, since X, Ai <= 10**9)
See Solution: 61364632 | CodeChef

I solved this problem as we are given product[l..r] = X ^ (r - l + 1) 
which can be written as : 
                         A[l]/x * A[l+1]/x * A[l+2]/x * ......A[r]/x = 1

So for the numbers now become B[i] = A[i] / x, and we need to calculate 
the number of subarrays  with product equal to 1. 
For that i did all the calculations wrt modulo P and it worked.  
Though it passed all the tests , but still Is it correct or it can fail
(working wrt p) in some cases ? 
3 Likes

I had a slightly weird solution by computing the prefix products and re-arranging the equation like so:
\dfrac{pre^r}{pre_{l-1}} = X^{r-l+1}
\dfrac{pre^r}{pre_{l-1}} = \dfrac{X^{r+1}}{X^l}
\dfrac{X^l}{pre_{l-1}} = \dfrac{X^{r+1}}{pre^r}

and then double hashing the values with 2 big primes.

Can you please share some tutorial for double hashing

Hey
Thanks for sharing your doubt.

Yes, your logic is correct. This question can be solved in this way also.

There are many subtleties in the editorial solution, far from being trivial.

See Tech Vineyard: Prefix sum vector & caching

I solved this problem as we are given product[l…r] = X ^ (r - l + 1) which can be written as :
A[l]/x * A[l+1]/x * A[l+2]/x * …A[r]/x = 1

This comment summarizes the idea behind it.

With exponent vectors which dimensions map to X prime factors, for X and each A[i], you can transform the multiplication by A[i] / division by X into sum/diff operations over vectors.