World Codesprint 12 Hackerrank Editorial

general
,
1

Can Someone make a good editorial on World Codesprint 12 questions of hackerrank. Especially the “factorial array” question? Thanks in Advance.

2

FACTORIAL ARRAY

The thing to notice hear is 40 factorial has 9 zeroes at the end i.e it is divisible by 10^9. Hence, any factorial above this number will also be divisible by 10^9 (since it will always be a multiple of 40!)

since the operations are only of increment types, a bruteforce way of incrementing will require 40*n operations in worst case after which the elements will be zero.

ofcource, you can update the elements back to a smaller number, but only q times, hence 40*q at max for such numbers.

We build a segment tree on the array ad maintain a set which contains the indices of all the elements less than 40.

type 2 is simply a range sum query.

type 1:

to increment elements between l and r, we use lower bound on our set to find the first index greater than or equal to l which has value less than 40, and continue till the index exceeds r.

for each index, we update the segment tree with new factorial value also check if val>40 now, if it is, we remove this index from the set.

Type 3:

we update the element in the segment tree as usual and also see if the new value is less than 40 but old value wasn’t. in this case we insert this index to our set.

My Solution: https://www.hackerrank.com/contests/world-codesprint-12/challenges/factorial-array/submissions/code/1304466105

3

Thanks for Replying! what do we store in the segment tree, The values of A[i] or their factorials?

4

I’ve solved this problem using the concept of Lazy Propagation in Segment Tree.

First pre-compute the factorial up to 39 with modulo N i.e. 10^9 and for integer greater than 39 it’s factorial under modulo of N will be 0 so we will take advantage of that and store the factorial up to 39 in an array.

Now create the segment tree where each node of segment tree is an array of 40 integers given below

struct nod{
	int num[40];
};

Since each node of segment tree will have info of a range, we will keep info of number of integers equals to i where i<40 we do not need to store info about integers >=40(Since their factorial under modulo N is 0). This process is similar to Hashing.

We will also create a Lazy Tree which will keep info about lazy updates i.e. what to add to each elements in a range of that lazy node.

For query of Type 1: We will update the segment tree by checking the corresponding lazy tree node.
Let’s say value at node of lazy tree is 3 it means we have to add 3 to each elements of the array. In segment tree we will shift the array by 3 i.e A[i+3]=A[i] in corresponding range of segment tree. We will loose info about elements which will become >=40 after updates.

For query of type 3: We will do same as Type 1 by updating in range(r,r) and whole segment tree will gets updated according to that.

For query of type 2: Reach to the node of segment tree from which is in the range and updating all the nodes coming in the path according to the lazy tree and calculate the answer by simple mathematics i.e. (Factorial of I * Number of integers equal to I)%N for all I<40

Code:
link text

1 Like
5

Since we need to query for the sum of factorials, we store factorials in the segment tree.

6

Thanx for replyting! I can not get the core concept of your segTree. Can you please elaborate the part A[i+3] = A[i] ? It will be very nice of you if you make a video editorial on this.

7

It would be very nice if someone just make a video editorial on this question. Thanks in Advance!

8

just click the editorial tab for each problem

9

For all elements>=40, its factorial mod 10^9 will be zero. So the problem breaks down to maintaining the count of numbers from 1 to 39 in given range. We can do this by using square root decomposition or segment tree. I solved this problem using square root decomposition. Solution

10

‘A’ is an array of size 40 representing a node N of segment tree. Where A[i] is equals to number of integers equals to ‘i’ & i<40.If we’ve to add ‘k’ to each of the elements in the range of node N in original array then for this we will update the segment tree by shifting array ‘A’ by ‘k’ to right.Because the number of integers which were equals to ‘i’ will become equals to ‘i+k’ and we do not need to care about the integers ‘i+k’>=40.i.e. A[i+k]=A[i]

1 Like
11

Yeah! I got your point. Thanks

12

@j_s_r_r806 can you plz check what’s wrong with my code. I used same logic as yours and its coming right when I manually test it. but failing on hackerrank.
Here is the link https://ideone.com/EGxBdK