Unofficial Editorials November Long Challenge (Part 2)

editorial
,
61

One of the most unique and brilliant solution i have every heard, repeated application of sqrt decomposition to get query time O(1).

I would be glad to see ur submission. Thanks for sharing ur approach friend.

PS:if u r willing, i am recieving request for editorial of POLY, but wasn’t able to solve that one. If u r willing to share ur approach with me, that would be really helpful. Be assured, due credit will be given to u. If u urself want to write editorial, that would also be welcome. In case u r busy, no problem mate!!!

2 Likes
62

Thanks for this approach, I’m sure I can’t implement this. Looking forward to viewing your submission :smiley: Once again, thanks a lot buddy :slight_smile:

63

@eugalt, I’m not much in c++, but i thought lowerbound function uses binary search. Correct me if I’m wrong. :slight_smile:

64

Great editorial. But I am having difficulty in understanding square decomposition solution of CSUBQ, what is array found used for in your code ? @taran_1407

65

@taran_1407 There is lower_bound() function in the algorithms library which uses binary search on an iterator range. Here it’s a map/set method with the same name.

66

Hey Taran nice work man!! :wink:

67

Setter’s solution works in 2.5 sec holy shit :open_mouth: O_O

68

Oh by god… @vijju123

Well, I hope you convey this suggestion to admin. There should be proper testing in these three languages at least. No one should ever get undue advantage just because of a particular language.

Hope once again, This matter won’t go unnoticed.

69

Thanks mate!!

70

found[i][0] tells whether ith block contains atleast one value > R and found[i][1] tells whether ith block contains atleast one value >=L.

71

Happens, mate. You are not the first one for this, nor you will be the last. I too wasted nearly 12 submissions (WA Segment tree ones) on CSUBQ because of a variable mistake. Just changed variable and got AC.

72

May be U should try iterative versions of exponentation and mod Inverse, as they tend to be slightly faster.

73

Well, an algorithm is always simple to its writer. :slight_smile:

It would be a bit easier for me as well as other very helpful contributors to help u if u explain your logic a bit.

what does array arr do in your solution. It would help others to help u. :slight_smile:

74

I did only 30. :smiley:

75

Oops. My mistake :smiley:

76

@taran_1407 bro, it may be my immaturity in knowledge, since I have just gone through the MMI concept on GeeksforGeeks, but I can’t understand how will it give the desired answer in O(1)?

77

Well, Complexity of complete program will be O(Q*num) where num is number of prime factors of P.

78

Lemma: A number upto 10^9 can only have at most 10 distinct prime factors.

Proof: Try multiplying first 11 smallest prime numbers. The product exceeds 10^9, but P is <= 10^9. So, num <= 10.

79

@mgch

I might be wrong, but i guess this solution is going to get TLE because of “precalculated F[l+1] * F[l+2] * … * F[r-1]” as you mentioned. Bounds of this problem were so tight even to refuse O(QlogN) solutions to pass even after many optimisations.

And In case we try pre-computation like F[L+1][R-1] is going to give us MLE/TLE or both.

Can you please explain that part??

1 Like
80

I solved CSUBQ(after contest) using 2 Fenwick trees cuz i am no expert with segment tree and Fenwick seemed easy to implement with need of just handling the merge or break segment conditions with if else blocks.

So what i did is, maintained 2 maps for storing the index of consecutive blocks and the length of array from that index(array-1 is 1 when element is <= R ; array-2 is 1 when element is < L) .

I used Fenwick to store sum of segments from 1 to any index, thus on querying i’d do something like let a = --map.upperbound®, b= --map.upperbound(l)(i.e. decrement both upperbounds),
then ans = a - b;(mind me for the syntax her) after that, decremented the unnecessary part of segments

For a 1-query used lowerbound on both maps, accordingly merged or break the segments.

For a 2-query just used lowerbound on both maps, accordingly decremented the unnecessary part of segments and printed the answer .

My code would seem lengthy because i didn’t make any function for the merge or break part and cuz of the repeated if else blocks(sorry).

Here’s my solution.

PS : Upvote this if you like :slight_smile:

1 Like