I used Segment tree but got TLE in second Subtask. Please,someone tell why is it happening.
Here, is link to my code CodeChef: Practical coding for everyone
i am trying to traverse the array using MO’s and keeping track of frequency using segment tree.I don’t know what’s wrong with my code b/c i tried and run my code on many testcases but thr result are perfectly fine.Can anyone help me find bug in my code
link to solution->link text
This part “For each number x in the array, you can create a sorted list of indices where x appears. After that finding number of elements in the range [L,R], will require you to do two binary searches to find the smallest index ≥L and largest index ≤R”. What does it mean? Can someone please explain? I have created a segment tree where each node contains sorted scores from left to right of that segment. How do I compute the the correct number of elements between L and R? Thanks.
In the alternate view of problem-
Let us create another array B that denotes the lengths of the blocks of the array A. Number of elements in B will be equal to the number of blocks of the array A. For A=[20,10,10,7,7,7,10]the array B will be [1,3,2,1]
.
Should it not be [1,2,3,1]? Am I missing something?
I did everything in O(n+q) by pushing queries into a vector at location l and r and processing with line sweep
Credits to bluescorp for sharing a unique observation, we both had a O(Q*logN) algorithm ready before we communicated. My solution(AC 0.23s): CodeChef: Practical coding for everyone
Hi Guys!
Made a video editorial for this problem:
Stable Market - CodeChef April Long Challenge
Btw, I think is editorial is quite good, and it explains the approaches quite well.
Cheers!
Can someone explain the comments in code written by author @pkacprzak.
How did he decomposed query by calling (solve-strictly-inside8block) && (solve-left-boundary)
Thanks in advance !
Using MO’s algorithm and segment tree in O((N+Q)* ROOT(N) * LOG(N)) time ?
No, not using the MO’s algo, only segment tree with storing the nodes and the queries together.
I don’t know why you haven’t written about it yet
The solution is accepted using Segment tree where each node is storing the sorted list of elements in the range (this is basically a merge sort tree ). Make sure to use vectors while creating segment tree nodes and don’t pass vectors in function but instead pass their references. I got many TLE’s because of it.
My solution using Segment trees - Solution
I did everything in O(n+q) by pushing queries into a vector at location l and r and processing with line sweep
Credits to bluescorp for sharing a unique observation, we both had a O(Q*logN) algorithm ready before we communicated.
My solution(AC 0.23s): CodeChef: Practical coding for everyone
Do i get stars now?
i cant delete my comment so im doing this instead ;_;
get my solution on the first page plx XD
Yeah, seems like a typo.
given K = 2
Let say my bucket(which is completely lie in the range [L , R] ) contain values like this -
12 12 12 3 3 12 12 12 and after sorting the values in bucket are - 12 12 12 12 12 12 3 3
and from your above statement by doing binary search (in this bucket) , I have only 2 values which occur at least K (ie K = 2 )times , but answer should be 3 isn’t it ?
@rahulmysuru7 please help .
which array a ? given A or the array we make array B ?
also -
B will be [1,2,3,1] isn’t it or I did mistake ?
Can anyone provide \sqrt(n) log(n) solution using only SQRT decompostion not BIT.
u r not sorting the values, u are sorting the size of buckets, the size of buckets is 3,2,3 after sorting you get 2,3,3. now binary search will give you the answer(upper bound on k=1)
what do u mean by we are sorting size of buckets , all buckets are of root(n) except last (may be) .
Please explain with given Test case . using only SQRT .
8 5
20 10 10 10 7 7 7 10
2 6 2
3 6 2
3 6 3
3 8 3
3 8 1