9 / 23
Oct 2010

yes, i've used segment tree too........
but before i go into details of my solution, answer my following queries:-

1.you seemed to be new to the use of segment tree, because segment tree is not intended to store those index values of the range, rather they can be easily mapped with the node no. whenever you are going to traverse the tree......
am i right?

2.what do you mean by that?

how is it feasible?

3.you effectively store only the maximum of the range at each node.....then there is no possibility that you can combine the left_child and right_child to generate the necessary information for the parent node...how have you done that?
(i think one needs atleast 3 things to be stored at each node)

reply me soon.....

in case the array is -1 -1 1 1 1 1 3 10 10 10
then i make my segment tree is made in the following fashion
node1 has 0 5 9 4 (this implies that node 1 has starting range 0 and its left child ends at 5 and the range of this node ends at 9 and max frequency in this range is 4)
node2 has 0 1 5 4
node3 has 6 6 9 3
node4 has 0 -1 1 2
node5 has 2 -1 5 4
node6 has 6 -1 6 1
node7 has 7 -1 9 3

it seems u have not used segment tree(atleast as far as i know, this is not the standard way a segment tree should be formed)..
in segment tree, if the parent node is holding the information abut the range [l,r], then left_child should keep [l,m] and right_child [m+1,r].......... where m = floor((l+r)/2)

{{0,1,2},{2,5,4},{6,6,1},{7,9,3}}
this is what i pass to the segment tree as my array not the original array

now,I got ur idea little bit (but i still dont understand how u ve written qry)......
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.........

hope, this will help u....... smile

1 month later

I getting time limit exceeded for this code can anyone pls help

#include <iostream>
using namespace std;
struct node
{
	int lf,mf,rf;
};
node ar[300000];
int max1(int a,int b,int c)
{
	if(a>b)
		b=a;
	if(c>b)
		b=c;
	return b;
}
void insert(int a[],int start,int end,int node)
{
	if(start==end)
	{
		ar[node].lf=1;
		ar[node].mf=1;
		ar[node].rf=1;
	}
	else
	{
		insert(a,start,(start+end)/2,2*node);
		insert(a,(start+end)/2+1,end,2*node+1);
		int m=(start+end)/2;
		if(a[m]==a[m+1])
			ar[node].mf=max1(ar[2*node].mf,ar[2*node+1].mf,ar[2*node].rf+ar[2*node+1].lf);
		else
			ar[node].mf=(ar[2*node].mf>ar[2*node+1].mf?ar[2*node].mf:ar[2*node+1].mf);
		if(a[start]==a[m+1])
			ar[node].lf=ar[2*node+1].lf+ar[2*node].lf;
		else
			ar[node].lf=ar[2*node].lf;
		if(a[m]==a[end])
			ar[node].rf=ar[2*node+1].rf+ar[2*node].rf;
		else
			ar[node].rf=ar[2*node+1].rf;
	}
}
int query(int a[],int start,int end,int i,int j,int node)
{
	int p1, p2;
	if (i > end || j < start)
		return -1;
	if (start >= i && end <= j)
		return ar[node].mf;
	p1 = query(a,start,(start+end)/2,i,j,2*node);
	p2 = query(a,(start+end)/2+1,end,i,j,2*node+1);
	if (p1 == -1)
		return p2;
	if (p2 == -1)
		return p1;
	if(p1>p2)
		return p1;
	else
		return p2;
}
int main()
{
	while(1)
	{
		int n,q;
		cin>>n;
		if(n==0)
			break;
		int a[n];
		cin>>q;
		for(int i=0;i<n;i++)
			cin>>a[i];
		insert(a,0,n-1,1);
		int t1,t2,f;
		for(int i=0;i<q;i++)
		{
			cin>>t1>>t2;
			f=query(a,0,n-1,t1-1,t2-1,1);
			if(f!=-1)
				cout<<f<<endl;
		}
	}
}

First of all use the code tags to put the code. The first post has it, so it should be obvious how to do that. Your code is very hard to read and because of that you're making it difficult for people to help you.

I didn't check the program logic, just tried to analyse the complexity itself. I think that it's correctly implemented O(N*log(N)) and I think that's the right complexity for this problem. The recursive calls also don't seem to loop for any ranges.

The constant can be reduced though. I think the recursive calls could be removed from insert function, but that's probably not the problem. What is eating a lot of time here, and maybe causes TLE, are the arithmetic operations. You have a lot of "x*2" and "x/2" expressions. Try changing all of them to "x<>1" respectively. If you haven't heard of them, those are bitwise shifts. You can read more about them on the net. When you're multiplying or dividing by a power of 2, you can always express that with a shift and it will be much faster.

If that doesn't help, I guess you should try a different approach. For example: merging equal values into single blocks with data about the size or range:
{-1,-1,-1,2,2,2,2} => {(-1,3),(2,4)}
{-1,-1,-1,2,2,2,2} => {(-1,0,3),(2,3,7)}

It will be harder to implement and I don't think that's necessary here, but I don't have other ideas at the moment.

The program from first post seems very similar and it was getting WA, so maybe you have some looping problem that I missed. Maybe somebody else will find something more.

3 months later

My implementation is very similar with yeduguru... except what the querry functions returns . Any way im getting Tle also... im not getting what is the reason. I got RTE when my array size was [200020]... But if the input size is 100000 at it best then the number of maximum nodes is 2*100000-1. So it shud have not given RTE. I increased it to 300000 then Tle !!!! . NY suggestion highly appreciated !!!

1 year later

dipto very nice explaination. but i want to ask one thing, left most element ? what exactly do you mean by that ?

should it be max frequency in the left array ? (i mean lf) ? please correct me.

thanks.

lf is the frequency of the left most element in a segment.
for example, if a segment looks like [1,1,1,2,5,5,9]
then, lf = frequency of 1 i.e. 3

please let me know if you still have any doubt.

dipto, seriously your these 2 posts make me to do GSS1, GSS3, FREQUENT in 2 days only. smile wow.... thanks alot.. trying to do GSS5.. but i think it is a little bit tuff...

6 months later

Hello everyone. I am solving this problem and I get WA. I use a different approach that any of you talk about in this post. I tried a looot of testcases and they were all incorect. Please check my code. Thanks:)

#include <cstdio>
#include <algorithm>
using namespace std;
struct val {
    int f, l;
};
struct n {
    int v, c;
};
n tree[ 600000 ];
val array[ 300000 ];
int A[ 200000 ];
void init( int node, int i, int j ) {
    if ( i == j ) {
        tree[ node ] = ( ( n ) { A[ i ], 1 } );
    }
    else {
        init( node * 2, i, ( i + j ) / 2 );
        init( node * 2 + 1, ( i + j ) / 2 + 1, j );
        int v1 = tree[ node * 2 ].v, v2 = tree[ node * 2 + 1 ].v, c1 = tree[ node * 2 ].c, c2 = tree[ node * 2 + 1 ].c;
        if ( array[ v1 ].l > ( i + j ) / 2 ) {
            if ( array[ v1 ].l > j ) {
                c1 += j - ( i + j ) / 2;
            }
            else {
                c1 += array[ v1 ].l - ( i + j ) / 2;
            }
        }
        if ( array[ v2 ].f <= ( i + j ) / 2 ) {
            if ( array[ v2 ].f < i ) {
                c2 += ( i + j ) / 2 - i + 1;
            }
            else {
                c2 += ( i + j ) / 2 + 1 - array[ v2 ].f; 
            }
        }
        if ( c1 > c2 ) {
            tree[ node ] = ( ( n ) { v1, c1 } );
        }
        else {
            tree[ node ] = ( ( n ) { v2, c2 } );
        }
    }
}
n query( int node, int a, int b, int l, int r ) {
    if ( a > b || a > r || b < l ) {
        return ( ( n ) { -1, 0 } );
    }
    else if ( a >= l && b <= r ) {
        return tree[ node ];
    }
    n p1 = query( node * 2, a, ( a + b ) / 2, l, r );
    n p2 = query( node * 2 + 1, ( a + b ) / 2 + 1, b, l, r );
    if ( p1.v == -1 ) {
        return p2;
    }
    if ( p2.v == -1 ) {
        return p1;
    }
    if ( array[ p1.v ].l > ( a + b ) / 2 ) {
        if ( array[ p1.v ].l > b ) {
            p1.c += b - ( a + b ) / 2;
        }
        else {
            p1.c += array[ p1.v ].l - ( a + b ) / 2;
        }
    }
    if ( array[ p2.v ].f <= ( a + b ) / 2 ) {
        if ( array[ p2.v ].f < a ) {
            p2.c += ( a + b ) / 2 - a + 1;
        }
        else {
            p2.c += ( a + b ) / 2 + 1 - array[ p2.v ].f;
        }
    }
    if ( p1.c > p2.c ) {
        return p1;
    }
    else {
        return p2;
    }
}
int main() {
    int i, j, N, Q, l, r;
    while ( 1 ) {
        scanf( "%d", &N );
        if ( N == 0 ) {
            return 0;
        }
        scanf( "%d", &Q );
        for ( i = 0; i <= 250000; ++i ) {
            array[ i ] = ( ( val ) { 1000000, -1 } );
        }
        for ( i = 0; i < N; ++i ) {
            scanf( "%d", A + i );
            A[ i ] += 100001;
            array[ A[ i ] ].f = min( array[ A[ i ] ].f, i );
            array[ A[ i ] ].l = max( array[ A[ i ] ].l, i );
        }
        init( 1, 0, N - 1 );
        for ( i = 0; i < Q; ++i ) {
            scanf( "%d%d", &l, &r );
            printf( "%d\n", query( 1, 0, N - 1, l - 1, r - 1 ).c );
        }
    }
}
16 days later

Hi can someone provide me with some edge case, and few more test case. My solution run fine for many test cases still it is giving wrong answer.
Thanks

There are not really any special test cases here. You should be able to brute force generate many test cases as the constraints are simple.

1 year later

EDIT:got it.i thought there was only one test case.
@dipto,
I used exactly same concept as you have explained above.
But i am getting WA.Can you look into it?

removed code
5 years later

class JustNode{
public:
pair<int,int> freqR,freqL;
int freqMax;

void specifyNode(JustNode &leftNode,JustNode &rightNode){
freqL.first = leftNode.freqL.first;
freqL.second = leftNode.freqL.second;
freqR.first = rightNode.freqR.first;
freqR.second = rightNode.freqR.second;
freqMax = max(leftNode.freqMax,rightNode.freqMax);
if(leftNode.freqR.first==rightNode.freqL.first){
if(freqL.first==leftNode.freqR.first){
freqL.second = leftNode.freqR.second + rightNode.freqL.second;
}
if(freqR.first==leftNode.freqR.first){
freqR.second = leftNode.freqR.second + rightNode.freqL.second;
}
freqMax = max(freqMax,leftNode.freqR.second + rightNode.freqL.second);
}freqMax= max(max(freqMax,freqL.second),freqR.second);
}

   void setValue(int value){
       freqMax = 1;
       freqR.first = value;
       freqR.second = 1;
       freqL.first = value;
       freqL.second = 1;
   }

};
Can anyone explain to what’s wrong with my code,
I have used segment tree to get max frequency. Each node in my segment tree will contain

1.left most limits frequency and rightmost limit frequency and max frequency.
When I tested with test cases I’m getting the correct output. I don’t know where I went wrong. Please help me.
Thanks in advance.

3 months later

Pls help me finding the error in this code
I have taken this link2 as reference
I am getting correct answer while running it in the terminal while spoj throws me wa
Thank you in advance

#include<bits/stdc++.h>
    using namespace std;
    #define inf 100005
    #define ll long long
    ll a[inf],f[inf],st[4*inf];
    ll n,q;
    void build(ll pos,ll l,ll r)
    {
        if(l==r)
        {
            st[pos]=f[l];
            return;
        }
        ll mid=(l+r)>>1;
        build(2*pos+1,l,mid);
        build(2*pos+2,mid+1,r);
        st[pos]=max(st[pos*2+1],st[pos*2+2]);
    }
    ll RMQ(ll pos,ll l,ll r,ll ql,ll qr)
    {
        if(ql<=l&&r<=qr) return st[pos];
        if(qr<l||ql>r||ql>qr) return 0;
        ll mid=(l+r)>>1;
        return max(RMQ(2*pos+1,l,mid,ql,qr),RMQ(2*pos+2,mid+1,r,ql,qr));
    }
    ll maxOcc(ll l,ll r)
    {
        ll res;
        if(a[l]==a[r]) res=r-l+1;
        else{
        ll left=0,right=0;
        while(l>0 && l<=r && f[l]==f[l-1]) 
        {
            l++;
            left++;
        }
        while (r<n-1 && l<=r && f[r]==f[r+1])
        {
            r--;
            right++;
        }
        res=max(max(left,right),RMQ(0,0,n-1,l,r));
        }
        return res;
    }
    int main()
    {
        int eof;
        cin>>n>>q;
        unordered_map<ll,ll>map;
        for(ll i=0;i<n;i++) cin>>a[i],map[a[i]]++;
        for(ll i=0;i<n;i++) f[i]=map[a[i]];
        build(0,0,n-1);
        for(int i=0;i<q;i++)
        {
            ll x,y;
            cin>>x>>y;
            x--,y--;
            cout<<maxOcc(x,y)<<endl;
        }
        cin>>eof;
        if(eof==0) return 0;
    }