2
$\begingroup$

Given a string comprised solely of the characters $\text{a, b, c}$ we want to know the number of different $(i, j, k)$ triples such that $0 \leq i,j, k < n \text{ (here n denotes the length of the string)}$ satisfying the following two conditios :

$\bullet \text{ }s[i] = "a", s[j] ="b" \text{ and } s[k] = "c"$

$\bullet \text{ } (j + 1)^2 = (i+1)(k + 1) $

We consider such two tuples, $(i, j, k)$ and $(x, y, z)$ to be different only of $i \neq x$ or $j \neq y$ or $k \neq z$.

Example case and solution : The string $"ccaccbbbaccccca"$ with $n = 15$. There are two triplets that satisfy the given constraints, namely $(2, 5, 11)$ and $(8, 5, 3)$.

The second solution shows that $i$ is not necessarily less than $k$.


I know this is a programming question, but I'm more inclined to look for a mathematical approach that I currently seem to be missing. Since $n$ could be as large as $5 \cdot 10^5$ brute force is not feasible.

I've attempted coming by the solution by noticing that in order for $\sqrt{(i + 1)(k + 1) } = (j +1 ) \in \mathbb{N}$, $k +1$ should be of the form $(i + 1) \cdot \alpha^2$ or of the form $\frac{\alpha^2}{i + 1}$.

Hence, we would have to iterate and test in order to find the $ \alpha$ values that would satisfy our conditions. Later on, I found out by inspecting the process that the latter form covers all the solutions, multiple times, so I would only need to look for answers by using the second form.

This still led to a temporal complexity of $O(\sqrt{n} \cdot \sum_{k=1}^{n}\sqrt{k})$.


I've been at this for too many hours and I have no idea how to proceed. How would you solve this? I'm guessing $O(n)$ isn't possible but $O(n \log n)$ should probably do the trick.

$\endgroup$
  • $\begingroup$ Interesting exercise. Can you credit the source of this problem? Where did you encounter this? $\endgroup$ – D.W. May 19 '17 at 5:42
3
$\begingroup$

Let us shift all of your indices by $1$. The condition on the indices then becomes $j^2 = ik$. The number of factorizations of $j^2$ into $i \cdot k$ is at most $d(j)^2$, where $d(j)$ is the number of divisors of $j$. Therefore the total number of potential triples $(i,j,k)$ is at most $$ \sum_{j=1}^n d(j)^2 = O(n\log^3 n). $$ (For the estimate, see this question on Mathoverflow.) Note that the actual number of triples can also be bounded by $\sum_{j=1}^n d(j^2)$, which could be smaller (and it could be yet smaller even than this sum).

This means, at the very least, that if you know $n$ in advance, then you can make a list of $\tilde{O}(n)$ triples, and solve the problem in time $\tilde{O}(n)$. Using a sieve of Eratosthenes, you can likely also calculate the triples in $\tilde{O}(n)$; it might be worthwhile to store all primes at most $500,000$ ahead of time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.