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;
} 

PLD-Palindromes

Palindromes

Given below code is for pld spoj or palindromes spoj.

Hint :- Simple implementation of Rolling Hash.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 15 September 2015 (Tuesday) 00:19
===================================================*/
#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
#define base 1223
ll prime[30009] , fh[30009] , bh[30009];
void prime_power(int n){
    prime[0] = 1;
    for(int i = 1 ; i <= n + 5 ; i++)
        prime[i] = (prime[i-1]*base)%mod;
}
void Hash(string &s , int n){
    for(int i = 1, j = n ; i<= n ;j--, i++){
        fh[i] = (fh[i-1] + s[i-1]*prime[i])%mod;
        bh[j] = (bh[j+1] + s[j-1]*prime[i])%mod;
    }
}
int count_palindromic_substring(string &s , int k){
    int n = s.size();
    int count = 0;
    int flag = 1;
    for(int i = k , j = 0 ,p_pow = n-k ; i<= n ;p_pow-=2 , j++,i++){
        ll hs1 , hs2;
        if(p_pow>=0){
            hs1 = (fh[i] - fh[j] + mod)%mod;
            hs1 = (hs1*prime[p_pow])%mod;
            hs2 = (bh[j+1] - bh[i+1] + mod)%mod;
        } else{
            hs2 = (bh[j+1] - bh[i+1] + mod)%mod;
            hs2 = (hs2*prime[abs(p_pow)])%mod;
            hs1 = (fh[i] - fh[j] + mod)%mod;
        }
        if(hs1 == hs2)
            count++;
    }
    return count;
}
int main(){
    
    string s ;
    int k;
    cin>>k>>s;
    prime_power(s.size());
    Hash(s , s.size());
    cout<<count_palindromic_substring(s , k)<<endl;
    return 0;
}

TESSER-Finding the Tesserect

Finding the Tesserect

Given below c++ code is for TESSER spoj or Finding the tesserect spoj.

Hint:- Use hashing or suffix array to find pattern in difference string.

#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
ULL hash[100009];
#define MU 123
void preHash(char str[] , int n)
{
    hash[n] = 0;
    for(int i = n-1 ; i>=0 ; i--)
        hash[i] = hash[i+1]*MU + str[i] - 65;
}
void solve(char str[] ,char pattern[] , int n , int m)
{
    ULL phv = 0;//hash value for pattern strings
    ULL multiplier = 1;
    for(int i = m-1 ; i>=0 ; i--){
        phv = phv*MU + pattern[i] - 65;
        multiplier = multiplier*MU;
    }
    preHash(str , n);
    int flag = 0;
    for(int i = 0 ; i < n - m + 1 ; i++)
        if(hash[i] - multiplier*hash[i+m] == phv)
        {
            flag = 1;
            break;
        }
    if(flag)
        printf("YES\n");
    else
        printf("NO\n");
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int arr[n+9];
        for(int i=0 ; i < n ; i++)
            scanf("%d",&arr[i]);
        char str[n+9];
        for(int i = 1 ; i < n ; i++)
            if(arr[i] == arr[i-1])
                str[i-1] = 'E';
            else if(arr[i] > arr[i-1])
                str[i-1] = 'G';
            else
                str[i-1] = 'L';
        n--;
        char pattern[n+9];
        scanf("%s",pattern);
        int m = strlen(pattern);
        solve(str , pattern , n , m);
    }
    return 0;
}

NAJPF-Pattern Find

Pattern Find

given below code is for NAJPF spoj or Pattern Find spoj.

Hint:- Use hashing for string and find pattern (very basic)

#include <bits/stdc++.h>
using namespace std;
#define MU 123
#define ULL unsigned long long
ULL hash[1000009];
void preHash(char str[] , int n)
{
    hash[n] = 0;
    for(int i = n-1 , j = 1 ; i>=0 ; i-- , j++){
        hash[i] = hash[i+1]*MU + str[i] - 97;
    }
}
void solve(char text[] , char pattern[] , int p , int t){
    ULL p_hash = 0 , check , pre = 1;
    for(int i = p-1 ; i>=0 ; i--){
        p_hash = p_hash*MU + pattern[i] - 97;
        pre = pre*MU;
    }
    check = p_hash;
    vector<int> v;
    int flag = 0;
    preHash(text , t);
    for(int i = 0; i < t - p + 1 ; i++ )
        if(hash[i] - pre*hash[i+p] == check){
            flag++;
            v.push_back(i+1);
        }
    if(flag == 0)
        printf("Not Found\n");
    else
    {
        printf("%d\n",flag);
        for(int i = 0 ; i < flag ; i++)
            printf("%d ",v[i]);
        printf("\n");
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        char text[1000009] ,  pattern[1000009];
        scanf("%s%s",text , pattern);
        int n , m ;
        n = strlen(text);
        m = strlen(pattern);
        solve(text , pattern , m , n);
    }
    return 0;
}

GSSQUNCE-Sequence

Sequence

below given code is for gssqunce spoj or sequence spoj.

easy one ... no need of explanation here only check if number is repeated more then twice then it can not form sequence .

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <sstream>
#include <fstream>
#include <climits>
#include <ctime>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int main()
{
 int t;
 scanf("%d",&t);;
 while(t--)
 {
  int n;
  scanf("%d",&n);
  int a[60000],flag=1;
  map<int ,int>mp;
  map<int ,int >::iterator t;
  for(int i=0;i<n;i++)
   scanf("%d",&a[i]),mp[a[i]]+=1;
  for(t=mp.begin();t!=mp.end();t++)
   if((*t).second >2){
    flag=0;
    break;}
  if(flag==0 || n==1)
   printf("NO\n");
  else
   printf("YES\n");
 }
 return 0;
}