damn_me's blog

Spoj problem FREQUENT
By damn_me, 10 years ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    With the input

    6 1
1 3 2 1 4 5
1 6
0

    Should return 2, no? Your code return 1

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      "You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order."

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ahh beautiful.

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like 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))

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any solution to solve it in o(nlogn) if the array isn't in non-decreasing order?

→ Reply