Unofficial Editorials November Long Challenge (Part 2)

editorial
,
81

Here is my very first AC submission - https://www.codechef.com/viewsolution/16282523 (there are a lot of optimizations, the most crucial is adding fast input-output(-0.5 seconds and building this SQRT-decomposition tree layer-by-layer, in that case, there will no many memory-jumps). I didn’t want to write it, cause solution couldn’t be understandable. The biggest problem is enumeration of buckets in the 2nd, 3rd, …, imagine that you write segment tree, but not for 2 childrens, for arbitrary K > 2. About POLY, do you know what is the convex-hull trick?

1 Like
82

@taran_1407,

I’ve replaced that line, let we have sqrt(N) buckets. For every pair let’s calculate production between them, totally there will be sqrt(N) * sqrt(N) = N such productions. And if we have a query for L and R from different buckets, let K = [sqrt(N)], idx(L) = [L / K], idx® = [R / K], let’s take the production F[idx(L)+1]F[idx(L)+2]…*F[idx®-1] if idx(L) != idx®

83

I have already tried writing a segtree for more than two children in past, successfully written it too, but didn’t feel that it was worth the effort at that time, to say the truth.

And yes, i know about convex hull trick, but wasn’t able to generalise it for non-linear functions (got 30 points).

I too have built sqrt buckets layer by layer to avoid memory complications. (upto x layers … x i define myself using a formula on N) avoiding creating extra layers, but with magic = 4 instead of 8.

Having a nice time with ur solution. Your solution is understandsble, thanks for writing it that way.

84

The only thing that’s had caused me a confusion was ur MUL array. I expected it to give MLE, but i was wrong there, it didn’t. :slight_smile:

Now I’m crystal clear about implementation. Will soon implement it, possibly tonight.

Thanks again for coming up with such a unique solution.

PS: Nice use of iterative Segtree to reduce iteration count. :stuck_out_tongue:

85

Great…

Its just that i haven’t worked with fenwick tree, because segtree usually serve the purpose.

86

I too used segment tree, but my approach is kind of a standard one. Just save positions of maximum left and the right element which is < R and merge the segments.

https://www.codechef.com/viewsolution/16163632

1 Like
87

I divide the problem in three subtasks. general is the function of third subtask. i take out all the prime from p. I precalculate those prime power 10e6. then I build the dp array with the leftovers and calculate mmi. afterwards i check for the common prime powers seperately.

88

@taran_1407 I do not understand the factpowsum array part

89

Can you explain a little bit more

90

Well, consider given array 2, 4, 1, 8 (taking powers of two to simplify my example).

let P be 32, so that the prime factor of P is 2.

FactPowSum array wiil be 0 1 3 3 6

It is just the sum array of array 1 2 0 3 ( which denote largest powers of 2 which divide ith number)

Read about sum arrays from http://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/

Hope that helps

91

Well, I tried doing everything… converting vector to array…making euclidean iterative… still can not get to pass that 9th test case… any help would be appreciated…-Link to solution

1 Like
92

Use 1 based indexing everywhere. Or use approach in editorial- thats the only way :frowning:

93

I have used the approach in editorial (given above)…
I don’t get how 1-based indexing would help??

94

Try using bit shift instead of dividing. and instead of % 64 use & 63

95

He meant the Official Editorial. The Complexity is larger this way. You can also refer to this DS

96

thanks for sharing such a great solution :slight_smile:

i understand it but unable to implement it! I have first created sqrt(N) blocks and then for each blocks another sqrt(N) …(as mentioned) but facing problem on how to map them to appropriate index during query. can you please explain a little bit how did you map indices in the inner levels ?

97

Guess, I need to use the DS you described.
Also, could you please explain a little about the cal function written in your LVGFT code. How are you finding m1,m2? You could explain in LVGFT editorial…

98

@kush2327 - Even I dont know why 1 based indexing helps, except that the codes using those did 9th test case in 3.6-3.9 seconds. Someone said that its because “Less “%” operations are performed this way” but I dont know how correct it is.

99

@taran_1407 for the 20 points as explained above in SEGPROD QUESTION in case when we calculate an prefix product array and 0 comes then all the subarrays gets zero in which that element comes and in that case SIGFPE AND WA definitely comes . PLZZ Explain your approach for 20 points first i am not gettting it THAT PREFIX PART PORTION AND THEN prefixprodarr[Ri]/pparr[Li-1] i n case 0 comes we cant do this i am right or wrong plzz clarify

100

First thing, I would request you to share your solution link along with query. It will help me understanding the problem u are facing in a better way.

Second thing, For first subtask, we are given P is a prime and all A[i] between 0 to P-1. This implies gcd(A[i], P) = 1 for all elements of given array, Ryt??.

From here, i am using the fact that we are required to output the product modulo P. Here, i am using modular multiplicative inverse to solve our problem.

1 Like