×

# PRCS16D - Editorial

Author: Parth Mittal
Tester: Satyam Kumar
Editorialist: Parth Mittal

MEDIUM

# PREREQUISITES:

Binary Indexed Tree, Offline Algorithms

# PROBLEM:

You are given two arrays, $A$ and $B$, both of size $N$. You are given $Q$ queries of the form $(i, j, k)$. Where for each query, you have to find the cardinality of the multiset $S(i,j,k) = \{A_p \cdot B_q | i \leq p,q \leq j, A_p \cdot B_q ≤ k\}$.

# EXPLANATION:

Note that we're looking for pairs $(p, q)$, such that $p\times q \leq k$. This implies that at least one of $p$ or $q$ is $\leq \sqrt{k}$. This gives us an algorithm to answer a single query:

ans = -(elements in A <= root(k)) * (elements in B <= root(k))
for i = 1 to root(k):
ans += (elements in A = i) * (elements in B <= K / i)


Note that setting $ans$ to $0$ in the beginning will lead to some over-counting, which the current value eliminates.
How do we answer the sub-queries we generate? They can be handled by a Binary Indexed Tree. Note that a segment tree will not work here because of high constant factor.
How do we extend to multiple queries? We can use Mo's algorithm.
Overall runtime is $O(Q\times \sqrt{N}\times \log N + Q\times \sqrt{k}\times \log N)$.

This question is marked "community wiki".

263
accept rate: 25%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,680
×2,595
×371
×69
×21
×1

question asked: 12 Oct '16, 23:01

question was seen: 452 times

last updated: 02 Jan '17, 19:17