faiyaz26's blog

By faiyaz26, 12 years ago, In English

for this problem: http://www.spoj.pl/problems/PATULJCI/

i have got some idea from this analysis by COCI. http://hsin.hr/coci/archive/2009_2010/contest3_solutions.zip

so far my implementation is with segment tree, then binary search.

here is my implementation which is getting WA:

/* Bismillahir Rahmanir Rahim */
/*Coder: Ahmad Faiyaz*/

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

# define FOR(i, a, b) for (int i=a; i<b; i++)
# define REP(i, a) FOR(i,0,a)

#define EPS 1e-11
#define inf ( 1LL << 31 ) - 1
#define LL long long

#define abs(x) (((x)< 0) ? (-(x)) : (x))
#define all(x) (x).begin(), (x).end()
#define ms(x, a) memset((x), (a), sizeof(x))

# define VI vector<int>
# define VS vector<string>
# define VC vector<char>

#define mp make_pair
#define pb push_back
#define sz(k) (int)(k).size()
#define FORIT(i,m) for(__typeof((m).begin()) i=(m).begin();i!=(m).end();i++)
#define pii pair<int,int>
using namespace std;
#define MAX 300005
struct node{
    int number,count;
};

int arr [MAX];
node tree [4*MAX];

vector <int> e [100005];

node combine(node l,node r){
    node ret;
    if(l.number == r.number){
        ret.number=l.number;
        ret.count= l.count+r.count;
    }
    else{
        if(l.count > r.count){
            ret.number= l.number;
            ret.count= l.count-r.count;
        }
        else{
            ret.number= r.number;
            ret.count= r.count-l.count;
        }
    }
    return ret;
}

node make (int val,int c){
    node ret;
    ret.count=c;
    ret.number=val;
    return ret;
}

void build(int node,int left,int right){
    if(left==right){
        tree[node]= make(arr[left],1);
        return;
    }

    int mid= (left+right)>>1;
    build(2*node,left,mid);
    build(2*node+1,mid+1,right);

    tree[node]= combine(tree[2*node],tree[2*node+1]);
    return;
}


node query(int node,int left,int right,int i,int j){
    if(left > j || right <i) return make(-1,-10000);
    if(left>= i && right<=j){
        return tree[node];
    }
    int mid= (left+right)/2;
    return combine(query(2*node,left,mid,i,j), query(2*node+1,mid+1,right,i,j));
}

int main(){
  //  freopen("in.txt","r",stdin);
  //  freopen("out.txt","w",stdout);
    int n,q,i,j;

    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
        e[arr[i]].pb(i);
    }
    build(1,0,n-1);
    scanf("%d",&q);
    while(q--){
        scanf("%d %d",&i,&j);
        node ret= query(1,0,n-1,i-1,j-1);
      //  cout<<ret.number<<" ";
        int cnt= upper_bound(all(e[ret.number]),j-1)-lower_bound(all(e[ret.number]),i-1);
        int elem= (j-i+1);

        if(2*cnt > elem){
            printf("yes %d\n",ret.number);
        }
        else{
            printf("no\n");
        }
    }

    return 0;
}

as far as i can see, i am doing same thing as told in the problem analysis!! but getting WA!! i have done checking with the official judge data, it seems that query function is not giving correct number for some range!! what to do?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Lets say we have array 3,3,3,1,1,2,2,2,1,1. In root when you are merging intervals (3,3,3,1,1) and (2,2,2,1,1), you say that most frequent value is 3 or 2, where it is 1. What I am saying is that you are looking only at most frequent value in some interval, but in fact, when combining two intervals, most frequent value can be value that is not most frequent in any of two intervals that you are merging. Am I making any sense ?

Also there is beautiful probabilistic solution to this problem.

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

    i have seen the probabilistic solution, but that will be not valid when c=100000.

    then what will be the way to solve this problem ?

    what i need to do during merging the intervals ?