You are not logged in. Please login at www.codechef.com to post your questions!

×

PRCS16D - Editorial

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\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".

asked 12 Oct '16, 23:01

rounaqwl66's gravatar image

2★rounaqwl66
263
accept rate: 25%

edited 02 Jan '17, 19:17

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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