I solved this using only Mo’s Algorithm → solution
Mo’s Algorithm tutorial by Anudeep Nekkanti → tutorial
I tried doing this using the segment tree, stored the sorted values of the range at each node and then tried searching, still getting TLE in second subtask. Can anyone please tell the reason,i couldnt find the mistake…
https://www.codechef.com/viewsolution/13307321
@narendra1897 in log(n) approach like in first solution array B is nothing but comulative frequency of numbers suppose A[]={1,2,3} so B={1,1,1} A[]={1,1,1}so B[]=(1,2,3} in next case B[]={length of block}
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?
1 Like
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!
7 Likes
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 .