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

general
1

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.

2

@samarth2017 would u explain how u solved it using fft

3

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. :sweat_smile:

4

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) :slight_smile:

5

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.
Surely it had bigger values :sweat_smile:

6

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

7

Yeah I realized it later. I don’t know, why I did such an overkill :thinking:

8

Where is my solution wrong for Probability problem. My solution

9

@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
10

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

11

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

12

i have did this problem but not using trie , i am curries to know how you did with trie
can you explain your logic with a sample test please?

13

For me too . Giving precision gave me WA.

14

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

15

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

16

Ok Thanks again @samarth2017

17

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

18

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

19

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

20

Can you give me a link for the latter problem