Here you will find solutions of many problems on spoj. If you want solution of some problem which is not listed in blog or have doubt regarding any spoj problem (which i have solved) or any programming concept (data structure) you can mail me @ raj.nishant360@gmail.com

And my humble request to you all that don't copy the code only try to understand the logic and algorithm behind the code. I have started this because if you tried as hard as you can and still can't find any solution to the problem then you can refer to this.
You can read my answer how to start competitive programming CLICK HERE

Sunday, October 18, 2015

PATULJCI-Snow White and the N dwarfs

Snow White and the N dwarfs

Given below code is for patuljci spoj or snow white and the N dwarfs spoj .

Hint:- source( http://hsin.hr/ )

For now, forget about the problem we are solving.

Suppose we had a sequence of integers and an algorithm like this:

while there are different numbers in the sequence
    select any two different numbers from the sequence
        and erase them

For example if the sequence were:
1 2 3 1 2 3 2 3
the algorithm could have done this:
1 2 3 1 2 3 2 3 --> 3 1 2 3 2 3 -> 1 3 2 3 -> 3 3
Note that we could also end up with other sequences if we selected pairs in a different way.

Let candidate be the number that is left in a sequence (3 in the example above).
Let count be the number of numbers left in a sequence (2 in the example above).

The cool thing about the algorithm is that if there is a number that appears more than N/2 times in the sequence it must end up as a candidate no matter the way we select pairs. Intuitively, we don't have enough other numbers to kill all of the candidate numbers. So we can choose our own way to select pairs. Let's do it recursively like this.

1) Split the sequence S in two halves L and R.
2) Run the recursive algorithm on sequence L to get L.candidate and L.count
3) Run the recursive algorithm on sequence R to get R.candidate and R.count
4) Kill the remaining pairs among L.count + R.count numbers that are left.
The step #4 can be done very efficiently like this:

if L.candidate == R.candidate
    S.candidate = L.candidate
    S.count = L.count + R.count
else
    if L.count > R.count
        S.candidate = L.candidate
        S.count = L.count - R.count
    else
        S.candidate = R.candidate
        S.count = R.count - L.count
    end
end

So, we can use this idea to build the interval tree, every node containing info (candidate and count) about the sub-sequence it represents. We can also query the interval tree to get candidate number for any interval [A, B]. Then we can use binary search to count the number of appearances of the candidate number in the interval and determine if the picture is pretty or not.




/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 18 October 2015 (Sunday) 17:10
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009
template<class T>
class segmentTree{
public:
    segmentTree(){
        height = 1;
        left_most = 1<<height;
        right_most = (left_most<<1) - 1; 
        tree = new T[right_most];
    }
    segmentTree(int s){ 
        size=s;
        height = ceil(log2(s));
        left_most = 1<<height;
        right_most = (left_most<<1) - 1;
        tree = new T[right_most+9];
    }
    void init(T * arr){
        build(arr);
    }
    void Update(int pos , T val){
        point_update(1 , left_most , right_most , left_most+pos , val);
    }
    void Update(int l , int r , T val){
        range_update(1 , left_most , right_most , left_most+l , left_most+r , val);
    }
    T Query(int pos){
        return point_query(1 , left_most , right_most , left_most+pos);
    }
    T Query(int l ,int r){
        return range_query(1 , left_most , right_most , left_most+l , left_most+r);
    }
private:
    T *tree;
    int size , left_most , right_most , height;
    void build(T * arr){
        for(int i = 0 ; i < size ; i++)
            tree[left_most+i] = arr[i];
        initalize(1 , left_most , right_most); 
    }
    void initalize(int root , int left_most , int right_most){
        if(left_most == right_most) return;
        int mid = (left_most + right_most)>>1 , l_child = (root<<1)  , r_child = (root<<1)+1;
        tree[root].split(tree[l_child] , tree[r_child]);
        initalize(l_child , left_most , mid);
        initalize(r_child , mid+1 , right_most);
        tree[root].merge(tree[l_child] , tree[r_child]);
    }
    void point_update(int root , int left_most , int right_most , int pos , T val){
        if(left_most == right_most && root == pos) { tree[root].update(val); return ;}
        int mid = (left_most + right_most)>>1 , l_child = root<<1 , r_child = (root<<1)+1;
        tree[root].split(tree[l_child] , tree[r_child]);
        if(pos <= mid) point_update(l_child , left_most , mid , pos , val);
        else point_update(r_child , mid+1 , right_most , pos , val);
        tree[root].merge(tree[l_child] , tree[r_child]);
    }
    void range_update(int root , int left_most , int right_most , int l , int r , T val){
        if(l <= left_most && r >= right_most){ tree[root].update(val);return;}
        int mid = (left_most + right_most)>>1 , l_child = root<<1 , r_child = (root<<1)+1;
        tree[root].split(tree[l_child] , tree[r_child]);
        if(l <= mid) range_update(l_child , left_most , mid, l , r , val);
        if(r > mid) range_update(r_child , mid+1 , right_most , l , r , val);
        tree[root].merge(tree[l_child] , tree[r_child]);
    }
    T range_query(int root , int left_most ,int right_most ,int l , int r){
        if( l <= left_most && r >= right_most )
            return tree[root];
        int mid = (left_most + right_most)>>1 , l_child = root<<1 , r_child = (root<<1)+1;
        tree[root].split(tree[l_child] , tree[r_child]);
        T l_node  , r_node , temp;
        if(l <= mid) l_node = range_query(l_child , left_most , mid , l , r );
        if(r > mid) r_node = range_query(r_child , mid+1 , right_most , l , r );
        tree[root].merge(tree[l_child] , tree[r_child]);
        temp.merge(l_node , r_node);
        return temp;
    }
    T point_query(int root , int left_most , int right_most , int pos){
        if(left_most == right_most && root == pos) return tree[root];
        int mid = (left_most + right_most)>>1 , l_child = root<<1 , r_child = (root<<1)+1;
        T temp;
        tree[root].split(tree[l_child] , tree[r_child]);
        if(pos <= mid) temp = point_query(l_child , left_most , mid , pos);
        else temp = point_query(r_child , mid+1 , right_most , pos);
        tree[root].merge(tree[l_child] , tree[r_child]);
        return temp;
    }
};
class node{
public:
    int count , number;
    void merge(node &l , node &r){
        if(l.number == r.number){
            count = l.count + r.count;
            number = l.number;
        } else {
            if( l.count > r.count ){
                count = l.count - r.count;
                number = l.number;
            } else{
                count = r.count - l.count;
                number = r.number;
            }
        }
    }
    void split(node &a , node &b){
    }
    void update(node &a){
    }
    node(){
        count = 0  , number = 0;
    }
    node(int num){
        count = 1;
        number = num;
    }
};
node arr[300009];
vector<int> Index[100009];
int main(){
    int n , c;
    scanf("%d%d",&n , &c);
    int temp;
    for(int i = 0; i < n ; i++){
        scanf("%d",&temp);
        Index[temp].pb(i);
        arr[i] = node(temp);
    }
    segmentTree<node> s(n);
    s.init(arr);
    int q , l , r;
    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&l,&r);
        l-- , r--;
        int num = s.Query(l , r).number;
        int count = upper_bound(Index[num].begin() , Index[num].end() , r) - lower_bound(Index[num].begin() , Index[num].end() , l);
        int req = r - l +1;
        if(count*2 > req){
            printf("yes %d\n", num);
        } else
            printf("no\n");
    }
    return 0;
} 

No comments:

Post a Comment

Your comment is valuable to us