×

SUMQ - Editorial

Author: Vipul Sharma
Tester: Prateek Gupta
Editorialist: Oleksandr Kulkov

MEDIUM

None

PROBLEM:

You are given three arrays $A$, $B$ and $C$. You have to sum up $(A_i+B_j)(B_j+C_k)$ for all $i$, $j$, $k$ such that $A_i \leq B_j \geq C_k$.

QUICK EXPLANATION:

Over all $B_j$'s, sum up $\left(\sum\limits_{A_i \leq B_j}(A_i+B_j)\right)\times\left(\sum\limits_{C_k \geq B_j}(B_j+C_k)\right)$.

EXPLANATION:

Let's bruteforce $B_j$. If we fix some $j$, then we can choose $A_i \leq B_j$ and $C_k \geq B_j$ independently. Let's sort $A$ in ascending order and $C$ in descending order. Then suitable $A_i$ as well as suitable $C_k$ will form prefix of $A$ and $C$ correspondingly which size can be found by binary search. Let the sizes of these prefixes will be $k_1$ and $k_2$. Then from triples with this $B_j$ we will have contribution of $\sum\limits_{i=1}^{k_1}\sum\limits_{k=1}^{k_2}(A_i+B_j)(B_j+C_k)=\sum\limits_{i=1}^{k_1}(A_i+B_j)\left(k_2 B_j+\sum\limits_{k=1}^{k_2}C_k\right)=\left(k_1 B_j+\sum\limits_{i=1}^{k_1}A_i\right)\times \left(k_2 B_j+\sum\limits_{k=1}^{k_2}C_k\right)$ which can be quickly calculated using prefix sums. Thus we have $O(n \log n)$ solution.

We can optimize this solution to $\mathcal{O}(n)$ by making the following observation. Let us sort the $B$ in increasing order. The values of $k_1$ and $k_2$ can only increase when we go from left to right in the array $B$. This technique's standard name is "two pointers" approach.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution will be updated soon.
Tester's solution will be updated soon.

RELATED PROBLEMS:

This question is marked "community wiki".

2★melfice
51213
accept rate: 0%

17.6k347489517

 0 In Explanation part , why are we considering Ck≥Bj instead Bj≥Ck. answered 13 Jul '17, 22:45 1 accept rate: 0%
 0 can someone explain it in an understandable manner?? answered 14 Jul '17, 22:44 1●1 accept rate: 0% See the second answer in the below link....I have directly discussed the implementation. https://discuss.codechef.com/questions/101196/can-anyone-help-me-with-sumq-from-june17?page=1#101255 (15 Jul '17, 17:55)
 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:

×12,790
×2,044
×148
×4

question asked: 13 Jun '17, 03:12

question was seen: 765 times

last updated: 15 Jul '17, 17:56