Can someone provide me the code for solving this spoj problem spo.com/problems/FREQUENT . What I am basically trying to do is :
Using segment trees, declare the tree as such pair<int,int> tree[4*max][3] where tree[node][0] = (maximum occuring element, count of its occurence in the range's left part) tree[node][2] = (maximum occuring element, count of its occurence in the range's right part) tree[node][1] = (maximum occurencing element, count of its ocuurence in the whole range comparing it with left and right parts)
The leaf nodes will have [(0,0), (a[i],1), (0,0)] where i is the case where l==r in the construct function of the segment tree. For the rest, tree[node][1] can be easily found. For tree[node][1], we'll compare tree[2*node][1] and tree[2*node+1][0] and similarly for tree[node][2] we'll compare tree[2*node+1][1] and tree[2*node][2].
I have just started solving problems based on segment trees but unable to code this. However, i coded but that seems to be a bad one. Can someone please help!!!
Stuck on this!! Please..
My idea is similar to yours: For each node in the tree, keep max consecutive equal elements from left, right and total. Then the rest is just case analysis.
Code: FREQUENT
With the input
Should return 2, no? Your code return 1
"You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order."
What if the array isn't non-decreased? I mean, if we don't have a non-decreased array, how can we solve this problem?
Ahh beautiful.
Given array is in non-decreasing order. So you can replace array a = {1 1 1 2 2 3 3 3 3} by another array b = {3 0 0 2 0 4 0 0 0}. Also remember indices of first equal elements. Build an RMQ (range maximum query) or a segment tree over array an b to answer for maximum element on subarray. Use some magic for very left and very right element and OK.
My idea : In each node of segment tree (corresponding to interval [l,r]) we keep track 3 information : (Max_Frequent,Value_have_maxFrequent), (Frequent_of_a[l],a[l] ~ leftmost element), (Frequent_of_a[r],a[r] ~ rightmost element).
(Because the sequence is non decrease so at most one element of [l,r] can lie on both left son (aka [l,(l+r)/2]) and right son on segment tree, so we must keep track left most and rightmost element of each interval for the case this element exist)
The main problem is how to combine two son LEFT [l,(l+r)/2] and RIGHT [(l+r)/2+1,r], other function is similar to normal segment tree. It's easy but have some special case.
You can see my code at : FREQUENT . Accepted.
Sorry for my bad English.
line 36 to 39 in ur code are in if condition because if that is true, it means all elements in that node's range are same and thus we only need to update the M value. Is it?
Yes. If all elements are equal, we will easy combine two sons.
All special cases when divide [l,r] to two son are :
1 2 3 4 | 5 6 7 8 (general case, a.r.x!=b.l.x)
1 1 1 1 | 1 1 1 1 (all elements are equal)
1 1 2 2 | 2 3 4 5 (a.r.x==b.l.x)
1 2 3 3 | 3 3 3 3 (a.r.x==b.r.x)
and
1 1 2 2 | 2 2 3 3 (a.r.y+b.l.y > max(a.M.y,b.M.y))
Is there any solution to solve it in o(nlogn) if the array isn't in non-decreasing order?
This is actually quite a well-researched problem, Wikipedia lists here the best algorithms known for solving this. Only N * sqrt(N) algorithms are known.