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

×

SUMQ - Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

MEDIUM

PREREQUISITES:

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

asked 13 Jun, 03:12

melfice's gravatar image

3★melfice
111
accept rate: 0%

edited 12 Jul, 00:24

admin's gravatar image

0★admin ♦♦
15.5k347484505


In Explanation part , why are we considering Ck≥Bj instead Bj≥Ck.

link

answered 13 Jul, 22:45

sierra101's gravatar image

2★sierra101
1
accept rate: 0%

can someone explain it in an understandable manner??

link

answered 14 Jul, 22:44

abhihacker02's gravatar image

4★abhihacker02
11
accept rate: 0%

edited 14 Jul, 22:45

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:55) siddharthp5383★
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:

×11,354
×1,812
×144
×4

question asked: 13 Jun, 03:12

question was seen: 397 times

last updated: 15 Jul, 17:56