# Help needed in a question of ongoing contest CP IN 7 DAYS. CHEFAKE

I have solved this problem in O(N^2). So , I can surely say that either the constraints are wrong or the test cases are very weak. I just Want to know that is there a O(N) or O(NlogN) solution for this problem. If yes can you explain the approach.
. THIS is the link to the question . Thanks in Advance.

@samarth2017 would u explain how u solved it using fft

Exactly, even I spent a lot of time to come up with a O(N) or O(NLOGN) soln .But after the looking at the no of submissions, i tried N^2 and it passed.

I knew that I will not be able to think of an O(N) or O(NlogN) solution so I just took a chance with O(N^2)

Probabiltiy
Even in this problem, N^2 worked .
But I tried to solve it using a trie, but It failed on few cases.
As A[i] <= 10^7 , so i kept the highest bit as 30th.But it failed, so I kept increasing it, and it passed all the cases after changing it to 40.

It was a trivial question . YOU Just had to find the no. Of subarrays having sum less than equal to T . I Solved it in O(N) using 2 pointer

Yeah I realized it later. I donâ€™t know, why I did such an overkill

Where is my solution wrong for Probability problem. My solution

@dhruv788 I didnâ€™t know O(N^2) would work. You need to find count of distinct values of d[i] - d[j]. where d[i] are the indices where we have 1. Also 1 \leq d[i] \leq 10^5. Consider P(x) = \sum\limits_{i=1}^{k} x^{d[i]}, and Q(x) = \sum\limits_{i=1}^{k} x^{-d[i]}. k is number of ones. Now try to analyze P(x)*Q(x).
Time Complexity: O(N*log(N))
Have you solved the problem of finding distinct values of A[i] + A[j], where 1 \leq A[i] \leq 10^5?

1 Like

I tried to print the answer with various precisionsâ€¦ But it worked only when i just simply printed the answer without fixing the precision.

Can you give me a link to good resource to study trie. @samarth2017 @tamo11@yatin_yk08

i have did this problem but not using trie , i am curries to know how you did with trie

For me too . Giving precision gave me WA.

I think geeks for geeks is sufficient. Tries is a very basic concept but is a root for many advanced string algorithms.

@samarth2017 thanks for the reply man , But I havenâ€™t studied FFT yet , So I am not able to understand it. STILL Thanks

Ok Thanks again @samarth2017

Was the polynomial construction also not clear? The way I defined P(x) and Q(x).

Yes That is clear , I got the construction of the functions

We keep on adding prefix sums into the Trie, For a current index i, you need to find the no of value in the tree, with value >= (current_prefix_sum-t) so u can make a search operation for it.
considering x = (current_prefix_sum-t);
You can traverse from highest bit, (40) in my case, and whenever u have a non set bit in x
it means all the numbers in the trie with that bit set are greater than x, so we add it to our answer, and move towards the other directionâ€¦so it works like that.

Code

Can you give me a link for the latter problem