PRCS16D - Editorial

bit
editorial
medium
offline
prcs16d
proc2016

#1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

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 imes 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 imes \sqrt{N} imes \log N + Q imes \sqrt{k} imes \log N).