Need help me in SPOJ Frequent.

Hi guys,

This time I need help with SPOJ Frequent . My code is here .

My Approach-

My attempt was to convert the problem into a simple RMQ by precomputing prefix, suffix, frequency and value of array elements We store ONLY the frequency array in segment tree. The algorithm is as-

  1. Store the required data in node, and then build a typical segment tree.

  2. For every range, check the following-

    a. For blocks of type {1,1,1,1,1,1,1} , we see that it is a single block. It will have the same prefix for all elements (which is the starting index of the block). For this, the answer is “r-l+1” (in code, l and r are denoted by a and b.)

    b. For blocks of type {1,1,1,2,2,2,2} , it is made up of 2 blocks. We simply use the formula ans = max(arr[a].suffix-a+1,b-arr[b].prefix+1);

    c. For any other block, we follow step 3.

  3. For any general case, we observe following-

Let array be {1,1,2,2,2,3,3,4,4,4} , and lets say our [l,r] are [4,9]. Our frequency array, which we stored in segment tree, is {1,2,1,2,3,1,2,1,2,3}.

Now, our range is [4,9] , for which our frequency array is {2,3,1,2,1,2}. Obviously, passing this straightaway will give us 3, which is wrong. But i thought that we can avoid this by “trimming”.

Notice the type of blocks here, it is- {2,2,3,3,4,4}. For blocks {2,2} and {4,4}, i again used pre-computation. I initialized answer as - “int ans=max(arr[a].suffix-a+1,b-arr[b].prefix+1);”. I used formula of 2.b to find actual length of such blocks. With the ends dealt with, I now pass off the following arguments to query function-

ans=max(ans,query(0,0,n-1,arr[a].suffix+1,arr[b].prefix-1,tree2,arr));

“l,r” have been replaced by “arr[a].suffix+1,arr[b].prefix-1” . I felt that since the corners are dealt with, we can be sure that now the frequency array will be of type {1,2…,a,1,2,…b}. Meaning the frequency array, for every block, will start for 1 and end at its frequency.

But apparently i am getting WA. I did search on forums, to come across-

however, i'm telling u a lot simpler approach that i follow (actually this is the most convenient way how u should solve problems with segment tree):-

at each node u r storing 1.max_freq(mf), 2.freq_of_leftmost_element(lf) ,3.rf

for leaf nodes(containg exactly 1 element):- mf=lf=rf=1
for any nonleaf node containing segment[l,r]:- m=floor[(l+r)/2]
mf= max{mf_of_lt_chld, mf_of_rt_chld , rf_of_lt_chld+lf_of_rt_chld(if exist when a[m]==a[m+1])}
lf =lf_of_lt_chld+lf_of_rt_chld(if exist when a[l]==a[m+1])
rf can be calculated in the same way

just defining the appropriate relation between parent node and child nodes for calculating the necessary informations, u can easily solve such problems using segment trees....if u go with some ad hoc ideas , u need to find new ideas for each and every problem though they are pretty similar problem......
using this concept, u can solve GSS1,GSS3,GSS5,BRCKTS,KGSS too.........

So my query is-

  1. At which test case is my code failing? At which part does my approach go wrong? I thought that taking care of corners of frequency array will allow me to do a simple RMQ on it, and get AC.
  2. How to correctly solve it, in light of the reply quoted above.

Thanks in advance :slight_smile:

Bro in segment tree you need 4*n(actually 2*2^(log(n)+1)) memory. I just changed line 56 to int tree2[4*n+4]; and it worked :slight_smile:

Link.

2 Likes

Thanks bro. I felt if tree needed more memory, i should get SIGSEV error…guess i cant trust that.

Can you believe i debugged it for 2 days before asking here? Now i feel like…WEW XD

Thanks bro :slight_smile:

i know that feel bro, these things just teach us lessons :smiley:

btw if you’re comfortable with linear recurrence and matrix exponentiation can you help in WW2 editorial’s setter’s explanation I asked it in comments here.

:slight_smile:

1 Like

I am sorry, i got too happy on getting AC, i forgot this Q has a second part.

Please explain the approach cited above. One where we store the left most element’s freq, rightmost element’s freq and maximum freq in each node. My solution is ad hoc, it doesnt exactly use “concept” of segment tree as parent node arent exactly related to child nodes.

I will appreciate if one of you can explain me that approach as well :slight_smile:

I havent dealt with matrix exponentiation yet dear, i am sorry :frowning:

Can’t comment word limit exceeded…

In that approach(i’d sugggest start thinking from bottom of seg tree(it’s like a recurrence))-> node has 3 values "max_freq", "max_freq_on_left"(including this node), "max_freq_on_right"… so for any node "max_fre" can be maximum of either left node’s "max_freq" OR same of right node OR if both left and right have same element ie. a[i]==a[i+1], then what ? Then it can be "max_freq_on_left"+"max_freq_on_right". Now why we add up these ? bcoz if number’s are same than there can be case like left segment {1,2,2,2} and right segment {1,1,1,1} so you see inspite of left having max_freq=3 we dont need it but we need it’s 'max_freq_on_left' giving us answer 1+4=5.

:smiley:

1 Like

Yup, i encountered this concept while solving GSS1. Got it the hard way tho (3 days of WA) XD

//