Unofficial Editorials November Long Challenge (Part 2)

editorial
,
21

Or you may try iterative version of gcd Extended.

22

I tried the iterative version also.
I think i should try that modulus part.
Thanks ,any more optimisations can be done?

23

I am amazed too.

1 Like
24

@taran_1407 I have asked a question for SEGPROD. It will be really helpful if you could help me debug my code and telling me where I am wrong.

25

I hope that would suffice. Else see fast solutions of other coders. (not mine though, it just passed on borderline :smiley: )

26

Thanx a lot!!
I did around 120 submissions and couldnt figure this thing.
Will always keep this in mind.

27

I also solved CSUBQ using seg tree. But my approach was a little bit different. It is easy to see that:
the number of subarrays with maximum array element in [L,R] is equal to difference of subarrays with all elements <=R and all elements < L. We can use 3 elements each in node to answer the 2 queries.

Here is a link to my solution. I use recursive seg tree and did not need any optimizations. I also added an additional variable in the node that stores size of node to make code simpler.

4 Likes
28

@jaideeppyne Yes, my solution is O(NLogN + QLogN). But I’ve submitted it in PYPY, it’s time limit is same as that of Python i.e. 5x that of C++. However, PYPY is significantly faster than Python. So, in the end, my solution passed just within the time limits.

29

Exactly what I did, except that I used 2 segment trees one for elements >= L and one for elements > R.

2 Likes
30

I tried solving CSUBQ little differently. For every index in the array i stored how many subarrays can be formed starting from that particular index and made a segment tree out of it.

Whenever i needed to update the array i made 6 cases to update the segment tree - if element smaller than ‘L’ replaces element in 1)range 2) greater than ‘R’; element in range replaces element 3)smaller than ‘L’ 4)greater than ‘R’ and element greater than ‘R’ replacing element 5)in range 6) smaller than ‘R’

For querying the range from x to y, i calculated how many subarrays are present in this range having starting point in x to y and i subtracted elements after y from the range accordingly.

To make the program easier i calculated next index greater than ‘R’ ,next index in range, previous index greater than ‘R’ and previous index in range for every element that is queried or updated.

The above solution works fine for first 3 subtasks but gave TLE for the last one although the complexity isn’t more than Qlogn. Can someone help me out here


[1]


  [1]: https://ideone.com/yDX2FD
31

I solved the SEGPROD problem using SQRT Decomposition and segment tree. Precomputed (each buckets product from range i to j, also precompute prefix and sufix of each bucket) out of query loop and answered each query in constant time. This approach had one flaw, that is, if L and R are both in same bucket, so I used segment tree for this case, and luckily it worked out.
Here is the link to my solution -


[1]


  [1]: https://www.codechef.com/viewsolution/16232677
1 Like
32

Why does my code give TLE for the first subtask? I did the same modular inverse approach.
https://www.codechef.com/viewsolution/16264031

EDIT: Precomputing the modular inverse worked :smiley:

33

@prakhar17252
I think u should precompute the modular multiplicative inverse for all elements of answer array.
Since size of array is only 10^6 so complexity 10^6(logN)
However in worst case of urs,complexity is O(210^7logN) which exceeds the Time limit

Hope your first subtask gets passed with this

1 Like
34

No need for square root decomposition to get 52 points (CSUBQ). :stuck_out_tongue:

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

3 Likes
35

can someone please tell me where else should i optimize my code, i tried so many times but couldnt get AC, getting TLE on the third subtask https://www.codechef.com/viewsolution/16231600

Thanks In Advance…

36

I have done everything you have done in SEGPROD but still didn’t get AC. I was getting TLE int task1 of of subtask3.
Can you suggest some changes which might fetch me an AC.

Link to my solution: https://www.codechef.com/viewsolution/16263438

37

I have done the exact same thing in SEGPROD, yet getting TLE in task #9 could someone please help me?

solution link: https://www.codechef.com/viewsolution/16254283

38

Thanks to both of u for sharing ur approach…

Though ur approach was nice, But to tell the truth, this is my first ever segtree non classical problem which i managed to solve. 2 segtree would be too much for first timers…

1 Like
39

That’s great

40

Great.
Often when queries are 10^7, pre calculation is vital