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-
-
Store the required data in node, and then build a typical segment tree.
-
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.
-
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-
- 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.
- How to correctly solve it, in light of the reply quoted above.
Thanks in advance 
