SMARKET - Editorial

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

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 :stuck_out_tongue:

See my solution - CodeChef: Practical coding for everyone

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? :smiley:

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