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

general
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

21

don’t fix the precisions, then try it will be AC i was also fixing precision but it not accepted
then i removed and it got accepted , but don’t know why they said … print answer till maximum 8 decimal places

22

thanks bro

1 Like
23

Lol, it got accepted without precision just by printing. I got almost 10 WA due to this :expressionless:
Why did this happen though? I believe setprecision would give us the accurate decimal up to 8 places.

1 Like
24

you can see this

1 Like