1
$\begingroup$

How to calculate the number of n-tuples of positive integers, satisfying the property that for each adjacent elements in the tuple, the product of elements $A[i] \cdot A[i+1] \leq k$ where $1 \leq i \leq n$. For example, if $n = 2$ and $k = 2$, the answer is $3$ as $2$-tuples are $(1,1), (1,2), (2,1)$.

My Approach: I am trying to approach this problem with Inclusion-Exclusion principle. First, I will calculate all $n$-tuples with each element in the range $[1,k]$. This is $k^n$. Now I will consider all pairs $(a, b)$ where $1 \leq a \leq k$ and $1 \leq b \leq k$ and $a \cdot b > k$. Those pairs can be calculated easily. Now I will exclude those cases where at least one such pair occurs, then add cases where at least two such pairs occur and so on. But I am not sure how to do this.

$\endgroup$
5
  • 1
    $\begingroup$ The general exclusion-inclusion principle is quite complicated, $$| \bigcup_{i=1}^n A_i | = \sum_{i=1}^n |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j | - \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k | - ... + (-1)^{n-1} |\bigcap_{i=1}^n A_i |$$ $\endgroup$ Aug 10, 2021 at 12:12
  • 1
    $\begingroup$ Dynamic programming seems better suited, count the ones that end in $j$ and have length $l$ where $l$ goes from $1$ to $n$. Alternatively build the graph where two vertices are adjacent if thir product is at least $k$ and then raise its adjacency matrix to the $n'th$ and take sum of all terms. $\endgroup$
    – Asinomás
    Aug 10, 2021 at 12:12
  • $\begingroup$ @Yorch dynamic programming is not possible as 2 ≤ N ≤ 1000 and 1 ≤ k ≤ 10**9. I didn't get the alternative approach that you mentioned, could you please elaborate ? $\endgroup$
    – Mr Sukhe
    Aug 10, 2021 at 12:56
  • $\begingroup$ What is $P{}{}$? $\endgroup$
    – Asinomás
    Aug 10, 2021 at 12:57
  • $\begingroup$ Sorry, it's k. $\endgroup$
    – Mr Sukhe
    Aug 10, 2021 at 12:59

1 Answer 1

1
$\begingroup$

Consider the equivalence relation on $\{1,\dots, k\}$ given by $a\sim b$ if $\lfloor k/a \rfloor = \lfloor k/b \rfloor$.

Build the vector of pairs of ints that tells us for each equivalence class how many elements are in that class and what the value of $k/a$ is for its elements.

This can be done in time $\sqrt{k}$ with the hyperbola trick.

After we have built this vector we do a dp table with this vector.

In other words, for each length $l$ we find how many sequences end with an element in that particular equivalence class, of course we need to build prefix sum table for the previous column each time we want to get a new column.

Complexity is $\mathcal O (n \sqrt k)$ so should run fine.

$\endgroup$
2
  • $\begingroup$ I got your approach, and it seems to be working perfectly. Could you please elaborate the hyperbolic trick that you mentioned? I didn't get it completely. thanks $\endgroup$
    – Mr Sukhe
    Aug 11, 2021 at 4:33
  • 1
    $\begingroup$ It's basically the idea used here: en.wikipedia.org/wiki/Dirichlet_hyperbola_method . But the idea is just that in order to see how many elements have $\frac{k}{a} = x$ when $x\leq \sqrt{n}$ you can iterate through the values of $x$ and solve each one individually, and in order to find how many elements have $\frac{k}{a} = x$ with $x> \sqrt{n}$ you can just iterate over the values of $a$ where $a< \sqrt{n}$. Glad to help. $\endgroup$
    – Asinomás
    Aug 11, 2021 at 12:58

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.