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

×

DOTIT - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: DOlaBMOon
Tester: Hussain
Editorialist: Taranpreet Singh

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Fast Fourier Transformation for polynomial Multiplication and Square root Decomposition.

PROBLEM:

Given two array $A$ and $B$ of length $N$, Answer $Q$ queries of the form.
- Given three integers x, y and l, print sum $\sum^{l-1}*0 A*{x+i}*B_{y+i}$

SUPER QUICK EXPLANATION

  • Divide $B$ (or $A$, as per our choice) into blocks of length $L$. Calculate for every block, Reverse it and multiply with array $A$ (considering both $A$ and blocks as polynomial). This,way, we get dot product of $A[i\dots i+L-1]$ and block. let this be stored in F[block number][Index in array A].
  • After doing this, answer queries, of length less than L using brute force, and remaining by jumping over blocks in $O(1)$ time, by adding for every block i, F[i][position of pointer in $A$, if pointer in $B$ has reached start of block i]. Border blocks can be handled brutely.

EXPLANATION

Beware, long (and probably scary) editorial ahead. You have been warned.

First of all, Let us consider a problem Where we are given two arrays and we need to perform dot product.

I know you all are smart enough to do this in $O(N)$ time, But let us say I am too weak to do it. I just know about polynomials.

I represent $A$ and $B$ each as polynomials, So, how can we find out dot product of $A$ and $B$ using some property of polynomials. We know that if $C$ is product of $A$ and $B$, then

$C[i] = \sum A[j]*B[i-j]$ $\forall$ $0 \leq j \leq i$

But this does not help us directly, Because we need to calculate $\sum A[j]*B[j]$ $\forall$ $1 \leq j \leq n$, which Multiplies A[i] with B[i], not B[n-j+1]. Isn't there anything we can do so that we can convert required sum to polynomial multiplication? Give it a try and if you still can't figure it out, See Hidden box.

View Content

This way, If we can multiply polynomials efficiently, we can find dot product of two arrays in same time. We all know we can multiply polynomials efficiently using Fast Fourior Transformations in $O(N*logN)$ time (I know I'm too slow than you guys, who did this in $O(N)$). I am not going into details of FFT, otherwise we would be leaving the territory of this problem, but you can read more about it from CLRS, here and here (Possibly the simplest explanation).

So, Returning to our original problem, how can we utilize above information? We can use Square root Decomposition.

The idea is to Divide one of the array (Suppose $B$) into blocks of length L, and for every block, we reverse the block, lets call it BL, and multiply it with $A$. If we call this product polynomial C, we can prove that $C[i+L] = A[i\dots i+L-1]* BL$.

We see that after reversing, $C[i+L]$ will constitute $\sum A[i+j]*RB[L+1-j]$ which is same as $\sum A[i+j]*B[j]$ $\forall 0 \leq j \leq L-1$. Let us store this results in an array, say PRE[Block Count][N].

I know above paragraph may sound incomprehensible to beginners with polynomials in CP, so read more about polynomials representations here as well as in CLRS book link mentioned above.

Let us assign $PRE[block][i] = C[i+L]$. Don't worry about Time complexity, which i have explained at the end.

Now, we can say that $PRE[i][j]$ represent dot product of Block i and $A[j \dots j+L-1]$.

If you have understood this, Give a try to answering queries, as we generally do using square root decomposition.

For queries where both endpoints of a query lies in same block, we calculate it in naive manner. Otherwise, Our query is of form, starting partial (or complete) block followed by a number of complete blocks and then a partial (or complete) ending block. For start and end block, we can calculate answer naively and using the PRE table, we can answer dot product queries for each block.

The only thing which I suspect, might confuse is, that for every block, we have $N$ results stored in PRE array, which one to use.

We just need to observe that suppose we have a query x,, and length. we see that every element in array $A$ will have a corresponding element in $B$. we just need to find this corresponding element for starting position of every block. Give it a try (I know you are saying, why this guy doesn't tell anything straight, but that's how we all learn.) and as usual, refer our secret box if help needed.

View Content

So, this conclude our another long editorial. Oh wait, Time complexity analysis is still left.

TIME COMPLEXITY

For Pre-computation, we do FFT multiplication of arrays of size N and B for every block, giving $O(C*((N+B)*log(N+B)))$ time if $C$ means number of block and $B$ is size of blocks.

For every query, We never make more that $O(B)$ iterations for start and ending blocks and $O(C)$ iterations for middle blocks, Thus, giving Time Complexity per query $O(B+C)$ Since $C = \lceil N/B \rceil$. This become $O(B+N/B)$.

Overall Complexity becomes $O(N/B*((N+B)*log(N+B))+Q*(B+(N/B)))$.

Choice for $B$: Usually, choosing $B$ around $\sqrt N$ works, but in this particular problem, pre-computation part involves FFT, which, apart from extra Log factor, includes a heavy constant, so, we might reduce Number of block, so reduce Number of FFTs performed. Setter uses $15*\sqrt N$

This way, Overall complexity Comes down to $O(\sqrt N * (Q+N*logN))$.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 25 Sep '18, 02:18

taran_1407's gravatar image

5★taran_1407
3.9k2387
accept rate: 22%

edited 27 Sep '18, 15:15

admin's gravatar image

0★admin ♦♦
19.7k350498541


this solution solves it in just 9 lines.

link

answered 28 Sep '18, 23:34

vipin_bhardwaj's gravatar image

5★vipin_bhardwaj
2378
accept rate: 10%

1

Because of 4x time limit + numpy being allowed.
Relevant post: link

(29 Sep '18, 17:13) meooow ♦6★

@titin_ I found this quite useful: Resource

link

answered 04 Oct '18, 15:52

viv_nitp's gravatar image

5★viv_nitp
182
accept rate: 0%

Any resource for FFT?

link

answered 04 Oct '18, 14:38

titin_'s gravatar image

4★titin_
133
accept rate: 0%

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:

×1,237
×647
×331
×288
×68
×5

question asked: 25 Sep '18, 02:18

question was seen: 497 times

last updated: 04 Oct '18, 15:52