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

×

SEGPROD - Editorial

4
5

PROBLEM LINK:

Practice
Contest

Author: Denis Anischenko
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

None (though knowledge of sparse table may be helpful for understanding)

PROBLEM:

Given a non-changing array, answer queries of the form "? l r: what is $\prod\limits_{i=l}^{r} a_i$ modulo $P$ ($P$ is not necessarily prime)?" (subarray product query). The queries are online, and the constraints are so tight that an $O(1)$ per query solution is required.

QUICK EXPLANATION:

The intended solution does not utilize the fact that the query operation is product modulo $P$. The proposed data structure is capable of handling any associative operation query on subarray in $O(1)$ (online, provided that the array is not changing).

The idea of the intended data structured is somewhat similar to the idea of a sparse table: we will precompute the operation results on some subarrays of the array so that every input query subarray can be represented as a union of constant (at most 2) number of subarrays we already know the answer for. However, the difference with the classic sparse table (used for static RMQ problem) is that the given operation $\bigoplus$ is not idemptotent: $a\bigoplus a\neq a$ for the most of $a$'s, so the union we will use must be disjoint. The operation is also not invertible, so we can't use the prefix-sums approach.

For each $k=1,\ldots,\lceil \log_2 N\rceil$ consider all indices of the array that are divisible by $2^k$ as "pivots". Precompute the product on subarrays whose left or right bound is a "pivot", and that do not contain any other pivots.

Claim: for each $[l,r]$ query we can choose pivot element $2^k\cdot x$ in such way that we already precomputed the operation for some subarray with indices $[l, 2^k\cdot x)$, $[2^k\cdot x, r]$.

EXPLANATION:

Build the following data structure: for each $k=1,\ldots,\lceil \log_2 N\rceil$, for each $i=0,1,\ldots,N-1$ (we use $0$-indexation of the array) compute (we omit modulo $P$ for simplicity; assume that all integers are members of the ring $\mathbb{Z}_P$, with multiplication defined accordingly):

$A_{k,i}=\prod\limits_j a_j\text{ for }\left\lfloor\dfrac{i}{2^k}\right\rfloor\cdot 2^k\le j\le i$

$B_{k,i}=\prod\limits_j a_j \text{ for }i\le j \le \left\lceil\dfrac{i+1}{2^k}\right\rceil\cdot 2^k-1$

Here $\text{~}$ denotes bitwise negation, $\&$ denotes bitwise AND operation.

The meaning of the expressions is the following:

  1. $\left\lfloor\dfrac{i}{2^k}\right\rfloor\cdot 2^k$ is the largest number not exceeding $i$ that is divisible by $2^k$. Implementation-wise, this number $I$ is characterized by the property $I~\&~ 2^k=0$ ($\&$ denotes bitwise AND).

  2. $\left\lceil\dfrac{i+1}{2^k}\right\rceil\cdot 2^k-1$ is by one less than the smallest number more than $i$ that is divisible by $2^k$. Implementation-wise, this number $J$ is characterized by the property $J\& 2^k=2^k-1$ ($\&$ denotes bitwise AND).

Let's notice the following: suppose we have a query $[L, R], L\neq R$, and for selected $k$ the range of indices $[L+1, R]$ contains unique index $I$ divisible by $2^k$. Then

$$B_{k,L}\cdot A_{k,R}=\prod_{i=L}^R a_i$$

Indeed, if that index of the form $I=2^k\cdot x\in[L+1, R]$ exists and is unique, then, by the meaning of the corresponding expressions above:

$I=\left\lfloor\dfrac{R}{2^k}\right\rfloor\cdot 2^k$

$I=\left\lceil\dfrac{L+1}{2^k}\right\rceil\cdot 2^k$

And by definition of $B_{k,L}$ and $A_{k,R}$:

$$B_{k,L}\cdot A_{k,R}=\prod_{j=L}^I a_j \cdot \prod_{j=I-1}^R a_j=\prod_{j=L}^R a_j$$

Can we find the $k$ for which $I$ is unique? Surely, such $k$ exists because if for some $k$ there are $X>1$ indices divisible by $2^k$ in the range $[L+1,R]$, for $k+1$ there are $\dfrac{X}{2}$ such indices if $X$ is even and either $\left\lfloor\dfrac{X}{2}\right\rfloor$ or $\left\lceil\dfrac{X}{2}\right\rceil$ if $X$ is odd. Incrementing $k$ sufficient number of times we arrive to $X=1$.

It remains to notice that $k$ can be chosen as $k=\max\limits_l: 2^l\le L\oplus R$ ($\oplus$ denotes bitwise XOR).

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

Tester's solution can be found here.

RELATED PROBLEMS:

This question is marked "community wiki".

asked 13 Nov, 14:09

melfice's gravatar image

2★melfice
412
accept rate: 0%

edited 14 Nov, 19:29

admin's gravatar image

0★admin ♦♦
16.9k347485513


If you think of the array as a tree (chain), this is similar to centroid decomposition. Dividing the array(tree) into O(NlogN) subarrays(paths), in a way that any subarray can be represented as a concatenation of two of those O(NlogN) subarrays. If we append 1's to the array until its size becomes 2^k-1 and then perform the decomposition, the nodes at height 'h' will have 2^(k-1-h), (assuming root is at height 0) as the largest power of 2 that divides them. The LCA of two nodes l,r will be some number l<=i<=r of the form x*2^k as mentioned in the editorial. We need to decrease 'r' until it becomes a multiple of some power of 2 having power as large as possible. This is same as picking a '1' in 'r's binary representation and setting all bits to the right of it to '0'. But, the '1' we pick cannot be to the left of the first point of difference in the binary representations of l,r, because then 'r' would become less than 'l'. That is exactly what the largest set bit in (l XOR r) represents.

For example- Consider array of size 15, then 8 is the root with children 4 and 12 and so on. Consider the query from 5 to 7 and we get the required number by which splitting is done as 6. (their lca). Similar is the case with query 7 and 11 and lca as 8.

link

answered 15 Nov, 00:23

hemanth_1's gravatar image

6★hemanth_1
7808
accept rate: 20%

edited 2 days ago

likecs's gravatar image

6★likecs
3.1k736

1

nice explanation!

(2 days ago) likecs6★
1

What a great explanation man , thanks a ton!!

(yesterday) gagan86nagpal5★

can anyone give me the easy explaination as i am not understanding the editorial..

link

answered 2 days ago

soumik33's gravatar image

3★soumik33
111
accept rate: 0%

@soumik33 See here,we precompute the prefix product for all indices which are divisible by 2^k where k=1....logN So

We calulate prefix product for all subarrays from prevPivot+1 to currPrivot-1. And prefix product from currPivot to nextpivot - 1

So lets say for k=2: Indices:4,8,12,16,20,... So we calculate for following ranges: (1,3),(2,3),(3,3) (4,4),(4,5),(4,6),(4,7)

(5,7),(6,7),(7,7) (8,8),(8,9),(8,10),(8,11)

We do this for k=1..logN Now suppose a query: 1-6 (Here pivot are 2,4) So it can be (1-1)(2-3)(4-6)

(Here pivot is 4) Or (1-3)*(4-6) The second one takes only 1 multiplication

Consider another eg: Range 17:22 So (17:19)*(20:22)

Since we have precalculated for these results for all multiples of power of 2 it can be done in O(1).

note 20=4 * 5=(2^2)*5

So it means we have to choose such a number in the range which is multiple of some 2^k and k is maximum(as if not we have to do more than 1 multiplication)

So lets express 17:0b10001 22:10110 Exor result=111 So last set bit is 2 So pivot is multiple of 2^2

(Also note that there is only 1 multiple x for x*2^k as for x-1 it is less than L and for x+1 it is greater than R)

Proof for xor: See @hemanth_1 comment.Really nice explaination.

Hope this helps. Plz correct me if i am wrong.

link

answered 2 days ago

vivek_1998299's gravatar image

5★vivek_1998299
122
accept rate: 0%

edited 2 days ago

Hi vivek_1998299, I want to make this clear enough. Let's say we want to find I for (14,17) 14: 0b001110 17: 0b010001 XOR: 0b011111, HEre last bit set is at 4, hence 2^4 i.e. 16. Am i correct ?

(yesterday) gagan86nagpal5★

Yes correct

(yesterday) vivek_19982995★

In the editorial, there have been defined two numbers I and J with the properties: I&(2^k) =0 and j&(2^k) = 2^k-1 , can anyone give some examples by taking values of I , J and k to illustrate this property. Also in the Author's solution , Some different property is being used which seems to be fine

link

answered yesterday

gagan86nagpal's gravatar image

5★gagan86nagpal
6615
accept rate: 7%

@gagan86nagpal

It is same as i discussed in my comment. They have used to arrays A,B(2d arrays)

A(k,i) denotes product of all elements from largest value of 2^k * x (less than or equal to i) to i.So that value is floor(i/(2^k)) * 2^k (consider for i=5 ,k=2 so val=4,

for i=8,k=2. Val=8)

B(k,i) denotes product of all elements from i to (smallest value of 2^k * x which is just greater than i) - 1.That value is ceil((i+1)/2^k)*2^k (Consider i=5 k=2 so val=8 - 1=7

Consider i=8,k=2. So val=12 - 1 =11)

So as i said in prev comment : For k=2 and for i=4...N //for sake of confusion not considering from 1 (as 0 doesnt comes(1 based))

A(k,i)= [ (4,4), (4,5) , (4,6) , (4,7) , (8,8) , (8,9) ,.....]

B(k,i)= [ (4,7) , (5,7) , (6,7) , (7,7) , (8,11) , (9,11) ,...]

Hope this helps.

Plz correct me if i am wrong.

link

answered yesterday

vivek_1998299's gravatar image

5★vivek_1998299
122
accept rate: 0%

edited yesterday

Thanks for helping mate.I got the logic now , seems trivial now :p

(yesterday) gagan86nagpal5★

If anyone is finding the explanation a bit difficult to comprehend try this one

link

answered yesterday

adhyyan1252's gravatar image

6★adhyyan1252
825
accept rate: 8%

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,984
×828
×247
×13

question asked: 13 Nov, 14:09

question was seen: 794 times

last updated: yesterday