ONBRIDGE – Online Bridge Searching

Category : Graph, Bridges
Problem Link : ONBRIDGE

Problem Description: Given a empty undirected graph with n nodes. Then a list of m edges, output the number of bridges in the graph after adding each edge.

Solution:
Normally, We can calculate bridges in a graph in O(n+m). But for each each edge, we can not do the following.In that case complexity will be O(n+m) * m, which is large.
To solve this problem We should know about Biconnected Component(BCC)\

To know about BCC, I can refer https://en.wikipedia.org/wiki/Biconnected_component
But simply, BCC is a collection of nodes, Where there are more than one path from any node to another node.In other words, a bcc doesn’t contain any bridges. They are simply cycles.

Again, What is Connected Components?
Connected Components is a set of nodes, where there is atleast a path from each node to other node.
I think these definition is enough to understand the solution.

Claim: In a undirected graph, A connected components forms a tree where nodes are BCC.(Think ? )

We are going to add edges one by one and calculate the bridges.

Lets add a-b edge:
Three case may occur.

Case 1.

a and b in same BCC. like adding a edge between 2 and 3.
because this two nodes are already in same bcc, this doesn’t add any bridge or reduces # of bridges.

Case 2.

if a and b are in two different connected component.
This edge is a bridge edge because adding this edge decreases the number of connected components.
bridges get increased by 1.
Now we need to merge this two connected components according to their respective size. This ensures O(1) running time.
Let’s see an example:

without loss of generality, Lets assume a is in small connected component. What we need to do is make a as a root of his connected component. This is done going towards its parent ans reversing the link.
Finally Link a to b.

Case 3.

If a and b is in same connected component. So there is a cycle formed in the tree. So we need to traverse the cycle and compress all the nodes in a BCC.

Lets see an example:

So all the tree edges in this components were bridges earlier. So we cancel them out.
This is done by finding the lca then traverse trough all the nodes on the path. Make them in the same bcc.

Here is The solution:

My code :

#include<bits/stdc++.h>
using namespace std;

const int N = 5e4+4;
int n,bridge,m;
int bcc[N],comp[N], link[N],SZ[N];
void init()
{
    for(int i = 0;i < n; i ++ ){
        bcc[i] = comp[i] = i;   // BCC and CC of a node, Initially all are isolate.
        link[i] = -1;           // Link to the parent in a CC
        SZ[i] = 1;              // Size of a CC 
    }
    bridge = 0;
}
// Output the BCC of a node
int getBCC(int a)
{
    if(a==-1)return -1;
    if(bcc[a]==a) return a;
    else return bcc[a] = getBCC(bcc[a]);
}
// Output the root of the component where a is.
int getCOMP(int a)
{
    if(comp[a]==a) return a;
    else return comp[a] = getCOMP(comp[a]);
}
// Merging two path, a->lca, b->lca.
int cs = 0, vis[N];
void MergePath(int a,int b)
{
    cs++;
    a = getBCC(a);
    b = getBCC(b);
    vector<int> va,vb;
    int lca = -1;
    while(1) {
        if(a!=-1) {
            a = getBCC(a);
            va.push_back(a);
            if(vis[a] == cs) {
                lca = a;
                break;
            }
            vis[a] = cs;
            a = link[a];
        }
        if(b!=-1) {
            b = getBCC(b);
            vb.push_back(b);
            if(vis[b]==cs) {
                lca = b;
                break;
            }
            vis[b] = cs;
            b = link[b];
        }
    }
    for(int i = 0;i < va.size();i  ++) {
        bcc[va[i]] = lca;   // Compressing in same BCC
        if(va[i]==lca) break;
        bridge --;
    }
    for(int i = 0;i < vb.size() ; i ++ ) {
        bcc[vb[i]] = lca;   // Compressing in same BCC
        if(vb[i]==lca) break;
        bridge --;
    }

}

// This reverses the edge of a to root of the connected component
void MakeRoot(int a)
{
    int root = a,child = -1;
    while(a!=-1) {
        int p = getBCC(link[a]);
        link[a] = child;
        comp[a] = root;
        child = a;
        a = p;
    }
    SZ[root] = SZ[child];
}


void addEdge(int a,int b)
{
    a = getBCC(a), b= getBCC(b);
    if(a==b) return;   // Case 1

    int u = getCOMP(a), v = getCOMP(b);
    if(u!=v) {      // Case 2
        bridge ++;
        if(SZ[u] > SZ[v]) {
            swap(a,b);
            swap(u,v);
        }
        MakeRoot(a);
        link[a] = comp[a] = b;
        SZ[v] += SZ[a];
    }
    else MergePath(a,b);    // Case 3
}
int main()
{

    int t;
    cin >> t;
    while(t--) {
        cin >> n >> m;
        init();
        for(int i= 0;i < m; i ++ ) {
            int a,b;
            scanf("%d %d",&a,&b);
            addEdge(a,b);
            printf("%d\n",bridge);
        }
    }
    return 0;
}

Principal of Inclusion-Exclusion

Problem Link : Problem 1
Simple Problem: One of the basic applications of Principal of Inclusion-Exclusion (PIE) .

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const int N= 16;
int a[N];

int main()
{
      Dii(n,k);
      forn(i,k) Si(a[i]);
      Long ans =0 ;
      forn(i,1<<k){
            Long p = 1, cnt = 0;
            forn(j,k) {
                  if(i&1<<j) {
                        cnt ++;
                        Long g = gcd(p,a[j]);
                        p = p * a[j] /g;
                  }
                  
            }
            if(cnt) {
                  if(cnt % 2) ans += n/p;
                  else ans -= n/p;
            }
        
      }
      printf("%lld\n", n - ans);
      return 0;
}

The time-complexity can slightly improved if we delete a number such that it has a divisor already in the list. With this We can shrink the size of the SET.

 
#include <bits/stdc++.h>
using namespace std;
 
/*------- Constants---- */
 
#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
 
/*************************** END OF TEMPLATE ****************************/
 
const int N = 1001;
bool vis[20];
int a[N];
 
int main()
{
      Dii(n,k);
      forn(i,k) Si(a[i]);
      sort(a,a+k);
      vector<int> I;
      forn(i,k) I.pb(a[i]);
      I.resize(unique(all(I)) - I.begin());
      
      for(int i = 0; i< I.Sz; i++ ) {
            for(int j = i+1 ; j < I.Sz; j ++) {
                  if(I[j] % I[i] == 0 ) vis[j] = 1;
            }
      }
      vector<int> S;
      for(int i = 0; i < I.Sz;i ++ ) {
            if(vis[i] == 0 )S.pb(I[i]);
      }
      Long ans= 0;
      forn(i,1<<S.Sz){
            Long p = 1, cnt = 0;
            double d = 1;
            forn(j,S.Sz) {
                  if(i&1<<j) {
                        cnt ++;
                        Long g = gcd(p,S[j]);
                        p = p * S[j] /g;
                        d = d * S[j] /g;
                  }
                  
            }
            if(cnt && d <= n + EPS) {
                  if(cnt % 2) ans += n/p;
                  else ans -= n/p;
            }
            
      }
      printf("%lld\n", n - ans);
      return 0;
} 

Problem 2 : HDU – 2204
Solution:
Maximum value of K = 60 , as 2^60> 1e18;
The number of primes <= 60 , 17
So, We need to calculate as follows, How many numbers is in form p^2, p^3,….

Now when calculating # of perfect square, and # of perfect cube , we overcount , some numbers are counted twice. What are they, Number in form p^6, as this number is in form (p^3)^2, and in form (p^2)^3, Thus the PIE apples.

So we need to subtract overcount .

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/

const int N = 60;
vector<int> Prime;
bool vis[N];

void seive()
{
      for(int i= 2;i < 60 ; i ++ ) {
            if(vis[i]==0) {
                  Prime.pb(i);
                  for(int j = 2 * i ; j < 60; j += i ) vis[j] = 1;
            }
      }
}


Long ans;
Long n;

void dfs(int M,  int ind , int p)
{
      if(M >60 || (1LL << M ) > n) return;
      if(ind == Prime.Sz) {
            if(M!=1) {
                  ans += ((int) (pow(n, 1./M) ) - 1)  * p;
            }
            return;
      }
      dfs(M * Prime[ind] , ind+1,-p);
      dfs(M , ind+1, p);
}
int main()
{
      seive();
      
      while(scanf("%lld",&n)==1) {
            ans=1;
            dfs(1,0,-1);
            
            printf("%lld\n", ans);
      }
      return 0;
}

Again This code can be re-written by using bit mask technique

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/

const int N = 60;
vector<int> Prime;
bool vis[N];

void seive()
{
      for(int i= 2;i < 60 ; i ++ ) {
            if(vis[i]==0) {
                  Prime.pb(i);
                  for(int j = 2 * i ; j < 60; j += i ) vis[j] = 1;
            }
      }
}


Long ans;
Long n;

int main()
{
      seive();
      
      while(scanf("%lld",&n)==1) {
            ans=1;
            for(int i  = 1;i < 1<< Prime.Sz; i ++) {
                  int k = 1 , cnt = 0;
                  bool flag = 1;
                  for(int j = 0; j < Prime.Sz; j ++ ) {
                        if( i & 1<< j  )
                        {
                              k *= Prime[j];
                              if( k > 60 ) {
                                    flag=  0;
                              }
                              cnt ++;
                        }
                  }
                  if(flag) {
                        ans += ((int) (pow(n,1./k) + EPS )-1) * ((cnt&1) ? 1 : -1);
                        //db(ans);
                  }
            }
            
            
            
            printf("%lld\n", ans);
      }
      return 0;
}

SPOJ – CERC07B – Strange Billboard

Category: BitMask, Brute force
Link: Link

Discussion: For each possible configuration of the first row, We can determine the next row, then the following. Thus building the structure

//
//  main.cpp
//  CERC07B - Strange Billboard
//
//  Created by Repon Macbook on 12/11/15.
//  Copyright © 2015 Repon Macbook. All rights reserved.
//
/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/

const int N = 17;
char x[N][N];
int ar[N];
int temp[N];


int main()
{
      int n,m;
      
      while(scanf("%d%d",&n,&m)==2 ){
            if(n+m==0) return 0;
            forn(i,n) scanf("%s",x[i]);
            forn(i,n){
                  int o = 0;
                  forn(j,m) if(x[i][j]=='X') o |= (1<<j);
                  ar[i] = o;
            }
            int iM = 1e8;
            bool flag = 0;
            forn(i,1<< m ) {
                  forn(k,n) temp[k]= ar[k];
                  int cnt = 0;
                  forn(j,m) {
                        if(i & (1<<j)){
                              temp[0] ^= (1<<j);
                              if(j+1<m) temp[0] ^= (1<<(j+1));
                              if(j-1>=0) temp[0] ^= (1<<(j-1));
                              temp[1] ^= (1<<j);
                              cnt ++;
                        }
                  }
                  for(int i = 1; i< n; i ++ ){
                        for(int j = 0; j< m ;j ++ ) {
                              if(temp[i-1] & 1<<j ) {
                                    temp[i] ^= (1<<j);
                                    if(j+1<m) temp[i] ^= (1<<(j+1));
                                    if(j-1>=0) temp[i] ^= (1<<(j-1));
                                    temp[i+1] ^= (1<<j);
                                    cnt ++;
                              }
                        }
                  }
                  if(temp[n-1] == 0 ) {
                        iM = min(iM, cnt );
                        flag = 1;
                  }
            }
            if(flag) printf("You have to tap %d tiles.\n",iM);
            else printf("Damaged billboard.\n");
            
      }
      
      return 0;
}

SPOJ – XMAX

Link : Problem
Discussion: From Stack Exchange

Let the “length” of a number be the number of digits needed to write it out in binary, excluding any leading zeros. Equivalently, the length of a number is the position of the leading 11 bit in its binary representation.

Clearly, if all the input numbers had a different length, the problem would have a trivial solution: just iterate over the input numbers in decreasing order by length, choosing each number if and only if XORing it with the maximum so far increases the maximum, i.e. if and only if its leading bit is not set in the current maximum.

Since this is an algorithmic question, let me provide some pseudo-code to illustrate the algorithm I just described:

# Find maximum XOR of input, assuming that all input numbers have
# different length:

let max = 0
for each number n in input (sorted in descending order by length):
    if max < (max XOR n): let max = (max XOR n)

(To see why this algorithm works, first observe that each bit in a binary number is “worth” more than all the lower bits combined, so we clearly want to work from top down, first optimizing the highest bits, no matter what this does to the lower bits.

Now assume that we’ve already considered all the input number longer than kk bits, and determined the maximum value the bits higher than kk can have in their XOR, and that we’re now considering whether to XOR a kk-bit number — which, by assumption above, is the only kk-bit number in the input — into the maximum or not. We cannot change the bits above the kk-th bit by doing so, but we can always ensure that the kk-th bit in the result is set, by XORing the current input number into the result if and only if the kk-th bit of the result so far is not yet set. Further, ensuring that the kk-th bit is set is clearly more important that anything that may happen to the lower bits as a side effect, so we may ignore those bits for now.)

The tricky part is when the input may contain multiple numbers with the same length, since then it’s not obvious which of them we should choose to include in the XOR. What we’d like to do is reduce the input list into an equivalent form that doesn’t contain more than one number of the same length.

Conveniently, this is exactly what Gaussian elimination does: it transforms a list of vectors into another list of vectors which have strictly decreasing length, as defined above (that is, into a list which is in echelon form), but which still spans the same linear subspace.

The reason this linear algebra algorithm is relevant here is that binary numbers satisfy the axioms of a vector space over the finite field of two elements, a.k.a. GF(2), with the numbers viewed as vectors of bits, and with XOR as the vector addition operation. (We also need a scalar multiplication operation to satisfy the axioms, but that’s trivial, since the only scalars in GF(2) are 11 and 00.)

The linear subspace spanned by a set of bit vectors (i.e. binary numbers) over GF(2) is then simply the set of vectors obtainable by XORing a subset of them. Thus, if we can use Gaussian elimination to convert our input list into another one, which spans the same subspace, we can solve the problem using this other list and know that it gives the same solution as for the original problem.

Thus, we need to implement Gaussian elimination over GF(2). Fortunately, this turns out to be very simple (in fact, much simpler than doing it for ordinary vectors of real numbers):

Find the maximum length kk of the (remaining) inputs, and at least one input having that length. Set this input aside.

XOR all other inputs of length kk with the input set aside in step 1: their length will now become less than kk.

Repeat from step 1, until all remaining inputs have length 00 (and can therefore be discarded).

The inputs set aside during successive iterations of step 1 above will form the new input list. (Conveniently, they will already be in decreasing order by length.)

A useful optimization is to separate the inputs into a number of “buckets” (i.e. variable-length lists) by their length: this makes finding the maximum length, and all inputs having that length, very easy and efficient.

Here’s some pseudo-code again:

# Preliminary phase: split numbers into buckets by length
for each number x in input:
    let k = length of x
    if k > 0: add x to bucket k

# Gaussian elimination:
for each bucket (in decreasing order by k):
    if this bucket is empty: skip rest of loop
    let x = arbitrary (e.g. first) number in this bucket
    remove x from this bucket
    add x to modified input list

    for each remaining number y in this bucket:
        remove y from this bucket
        let z = y XOR x
        let k = length of z
        if k > 0: add z to bucket k

Then just apply the maximum-finding algorithm given above to the modified input list.

(Ps. It’s also possible to find the subset of input numbers giving the maximum XOR using this algorithm: for each modified input number, you just need to somehow keep track of which original input numbers it was XORed from. This is basically the same algorithm as using Gaussian elimination to find a matrix inverse, just adapted to bit vectors.)

Here is my implementation:

/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const int N = 1e5+5;
Long a[N];

int b(Long a)
{
      for(int j = 63; j >=0 ; j --) {
            if(a & (1LL<<j)) {
                  return j;
            }
      }
      return -1;
}
int main()
{
      
      Di(n);
      forn(i,n) {
            Si(a[i]);
      }
      vector<Long> S[100];
      forn(i,n) {
            S[b(a[i])].pb(a[i]);
      }
      vector<Long> A;
      for(int i = 63; i >=0 ; i-- ) {
            if(S[i].Sz) {
                  A.pb(S[i][0]);
                  for(int j= 1; j < S[i].Sz ; j ++ ) {
                        Long u = S[i][0] ^ S[i][j];
                        S[b(u)].pb(u);
                  }
            }
      }
      Long ans = 0;
      for(auto a: A) {
            if((ans ^ a) > ans ) ans = ans ^ a;
      }

      printf("%lld\n", ans );
      return 0;
}

2D BIT

2d bit is easier to code,
For 1d bit, query(x) return the sum of all the elements which index is <= x, index starting from 1
For 2d bit , query(x,y) return the sum of all the elements of the rectangle (1,1) to (x,y)

Practice Problem:Matsum

/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */
 
#include <bits/stdc++.h>
using namespace std;
 
/*------- Constants---- */
 
#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
 
/*************************** END OF TEMPLATE ****************************/
const int N = 2013;
Long bit[N][N];
int a[N][N];
void update(int x,int y,int val)
{
    for(int i= x; i< N ; i += i&-i) {
        for(int j = y; j < N; j += j&-j) {
            bit[i][j] += val;
        }
    }
}
Long query(int x,int y)
{
    Long r = 0;
    for(int i = x; i> 0; i-= i&-i ) {
        for(int j = y; j > 0; j-= j&-j ) {
            r += bit[i][j];
        }
    }
    return r;
}
char s[5];
int main()
{
 
    Di(t);
    while(t--){
        Di(n);
        forn(i,n+1) forn(j,n+1) bit[i][j] = 0 , a[i][j] = 0;
        while(scanf("%s",s)) {
            if(strcmp(s,"END") == 0 ) break;
            if(strcmp(s,"SET") == 0) {
                Diii(x,y,u);
                x++,y++;
                update(x,y,u - a[x][y]);
                a[x][y] = u;
            }
            if(strcmp(s,"SUM") == 0){
                Dii(x1,y1);
                Dii(x2,y2);
                x1 ++ ,y1 ++;
                x2 ++, y2 ++;
                printf("%lld\n", query(x2,y2) - query(x2,y1-1) - query(x1-1,y2) + query(x1-1,y1-1));
            }
        }
    }
}

SPOJ – CCOST

Discussion:
The First Intution that comes to mind after reading the problem is 2D BIT but if you see the memory requirement , you will be able to figure it out that the problem is not for 2D BIT. The problem can be solved by 1D BIT only.
Store all the Tree Updates and all the queries and sort both of them w.r.t to y cordinate. Mantain an BIT for the x-cordinate ( compress the Array to it’s Rank to maximum size of 10^5 instead of 10^7). Now Update the BIT and process the query simultaneously like this:
Now,For a particular y co-ordinate,
-> if it is updating a tree co-ordinate,then update(x,v)
-> if y is a query then query(x2) – query(x1), Range query

/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
template <class T> inline T bigmod(T p,T e,T M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return (T)ret;}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const int N = 5e5+5;
struct Event{
      int y,type,x1,x2,val;
      Event(int y,int type,int x1,int x2,int val):y(y),type(type),x1(x1),x2(x2) ,val(val){};
};
bool cmp(Event a,Event b)
{
      if(a.y==b.y){
            return a.type < b.type;
      }
      else return a.y<b.y;
}
Long bit[N];
void update(int x,int val)
{
      while(x<N) {
            bit[x]+=val;x+=x&-x;
      }
}
Long query(int x)
{
      Long r = 0;
      while(x>0)r+=bit[x],x-=x&-x;
      return r;
}

vector<Event> E;
vector<int> o;
int qq[N][2];
Long oo[N], ans[N];
int main()
{
      Di(t);
      while(t--) {
            Di(n);
            forn(i,n){
                  Diii(x,y,v);
                  o.pb(x);
                  E.pb(Event(y,0,x,-1,v));
            }
            Di(q);
            int cnt = 0;
            forn(i,q ){
                  Dii(x1,y1);
                  Dii(x2,y2);
                  o.pb(x2);
                  o.pb(x1-1);
                  
                  E.pb(Event(y1-1,1,x1-1,x2,cnt++));
                  E.pb(Event(y2,1,x1-1,x2,cnt++));
                  
            }
            sort(all(o));
            o.resize(unique(all(o)) - o.begin());
            sort(all(E),cmp);
            for(int i=0;i<E.Sz;i++){
                  Event it=E[i];
                  if(it.type==0) {
                        int  x1=lower_bound(o.begin(), o.end(), E[i].x1) - o.begin() + 1;
                        update(x1,E[i].val);
                  }
                  else {
                        int x2 = lower_bound(o.begin(), o.end(), E[i].x2) - o.begin() + 1;
                        int x1 = lower_bound(o.begin(), o.end(), E[i].x1) - o.begin() + 1;
                        oo[it.val] = query(x2)- query(x1);
                  }
                  
            }
             cnt = 0;
            forn(i,q){
                  ans[i] = oo[cnt+1] - oo[cnt];
                  cnt+=2;
            }
            forn(i,q) printf("%lld\n", ans[i]);
            E.clear();
            o.clear();
            ms(bit,0);
      }
      return 0;
}

TPCPPLAR – Popular SPOJ

Problem Link: Link
Problem Statement:

Given a directed graph G , N vertices and M arcs.
A node X called “acessible” to Y if there is a path from X to Y
A node X called “popular” if every node Y in V fulfill one of two conditions :
1. X is acessible to Y
2. Y is acessible to X
The Problem : Given graph G, count the number of popular node.

Discussion:

First , The given graph can form cycle, So we calculate SCC, and construct a new graph connecting the SCC.
In the new graph , we do following

Topological sort

Later in the text comparison A < B means that vertex A stands before vertex B in topological order.
Now let's notice that for vertex V an edge that connects vertices V1  V doesn’t influence on the fact whether V is popular. Let’s remove all such edges and see whether there exists a vertex V1  V that has zero input degree, if so — V is not popular, otherwise it is.

When Processing the vertex as topsort, We keep two things, the number of vertex in the right that has zero incoming edge and the number of vertex in the left that has zero outgoing edge. When processing a vertex , we add the incoming edge to the vertex and after the process, we delete all the outgoing edge of the vertex.

/*
 
 *************************
 Id  : Matrix.code
 Task: TPCPPLAR - Popular
 Date: 23 OCT-2015
 
 **************************
 
 */

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
template <class T> inline T bigmod(T p,T e,T M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return (T)ret;}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
void IN(){    freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);}

/*************************** END OF TEMPLATE ****************************/
const int N = 150005;
vi G[N],R[N], D[N] , top, C[N] , nodes[N] , RD[N];
bool vis[N];
int color[N];
int in[N],out[N];
int Pos[N] , a1[N] , a2[N] ;

void dfs1(int u)
{
      vis[u]=1;
      for(auto a: G[u]){
            if(vis[a] == 0 ) dfs1(a);
      }
      top.pb(u);
}
void dfs2(int u,int col)
{
      nodes[col].pb(u);
      color[u] = col;
      for(auto a: R[u]) {
            if(color[a] < 0 ) dfs2(a,col);
      }
}

void dfs3(int u)
{
      vis[u]=1;
      for(auto a: D[u]){
            if(vis[a] == 0 ) dfs3(a);
      }
      top.pb(u);
}



int main()
{
      Dii(n,m);
      forn(i,m){
            Dii(u,v);
            G[u].pb(v);
            R[v].pb(u);
      }
      ms(vis,0);
      top.clear();
      for(int i=1;i<=n;i++) {
            if(vis[i] == 0 ) {
                  dfs1(i);
            }
      }
      reverse(all(top));
      ms(color,-1);
      int col = 0;
      for(auto a : top ) {
            if(color[a] < 0 ) {
                  dfs2(a,col++);
            }
      }

      // Construction of new graph
      for(int i=1;i<=n;i++) {
            for(auto p : G[i] ){
                  if(color[i] != color[p]) {
                        D[color[i]].pb(color[p]);
                        RD[color[p]].pb(color[i]);
                        in[color[p]] ++;
                        out[color[i]] ++;
                  }
            }
      }
      // All the edge need to be unique, otherwise we can update indegree and outdegree for the same edge
      for(int i=0;i<col;i++) {
            sort(all(D[i]));
            D[i].resize(unique(all(D[i])) - D[i].begin());
            sort(all(RD[i]));
            RD[i].resize(unique(all(RD[i])) - RD[i].begin());
      }

      // Top-sort
      ms(vis,0);
      top.clear();
      for(int i=0;i < col; i ++ ) {
            if(vis[i] == 0 ) {
                  dfs3(i);
            }
      }
      reverse(all(top));
      int Lz= 0, Rz = 0; // The two value to keep
      for(int i = 0;i< col; i ++ ) if(in[i] == 0 ) Rz++;
      vi Ans;
      for(auto i: top ) {
            if(in[i]==0) Rz--;
            for(auto a: RD[i]) {
                  if(out[a] == 0 ) Lz--;
                  out[a] ++;
            }
            if(Lz || Rz ) {
                  
            }
            else {
                  for(auto a: nodes[ i]) Ans.pb(a);
            }
            for(auto a: D[i]) {
                  in[a] --;
                  if(in[a] == 0 ) Rz++;
                  out[i] --;
            }
            if(out[i] ==0 ) Lz ++;
      }
      cout<< Ans.Sz<<endl;
      sort(all(Ans));
      for(auto a : Ans) printf("%d " , a) ;
      
      
      return 0;
}

Spoj – DQUERY

Spoj : DQUERY
Problem Link : http://www.spoj.com/problems/DQUERY/
Method : Segment Tree/ MO’s Algorithm

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT                     1000006
#define ll                      long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define FOR(i,n)                for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define inf                     1<<30
#define lc                      ((n)<<1)
#define rc                      ((n)<<1 |1)
#define debug(x)                cout <<#x<<" -> " << x << endl;


/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
      ll ret = 1;
      for(; e > 0; e >>= 1){
            if(e & 1) ret = (ret * p) % M;
            p = (p * p) % M;
      } return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/


int iAr[LMT], A[LMT];
vector<ii> Q[LMT];
int cnt[LMT];
int nxt[LMT];
int T[3*LMT];

void build(int n,int b,int e)
{
      if(b==e) {
            T[n] = A[b];
            return;
      }
      int mid = (b+e)/2;
      build(lc, b, mid) ;
      build(rc, mid+1, e);
      T[n] = T[lc] + T[rc];
}

int query(int n,int b,int e, int i , int j)
{
      if(b>j || e < i ) return 0;
      if(b>= i && e <= j  ) return T[n];
      
      int mid = (b+e)/2;
      return query(lc, b, mid, i , j) + query(rc, mid +1 ,  e, i , j);
}

void upd( int n,int b,int e,int pos)
{
      if(b==e && b == pos ) {
            A[pos] = 1;
            T[n] = 1;
            return;
      }
      int mid = (b+e)/2;
      if(pos <= mid ) upd(lc, b, mid, pos);
      else upd(rc, mid+1, e, pos);
      T[n] = T[lc] + T[rc];
}
int iAns[LMT];

int main()
{
      
      
      int n;
      sc(n);
      for(int i = 1; i <= n ; i ++ ) {
            sc(iAr[i]);
            if(cnt[iAr[i]] > 0 ) {
                  A[i] = 0;
                  nxt[cnt[iAr[i]]] = i ;
                  cnt[iAr[i]] = i;
            }
            else {
                  A[i] = 1;
                  cnt[iAr[i] ] = i ;
            }
            
            
      }
      //for(int i  =1 ; i<= n ;i ++ ) printf("%d %d\n" , i , nxt[i]);
      build(1,1,n);
      
      int q , a ,b ;
      sc(q);
      for(int i  = 0 ;i < q; i ++ ) {
            sc(a);sc(b);
            Q[a].push_back(mp(b, i));
      }
      
      for(int i = 1 ; i <= n ; i ++ ) {
            for(int j = 0 ;j < Q[i].size() ; j ++ ) {
                  int R = Q[i][j].first;
                  int p = query(1, 1, n, i, R);
                  iAns[Q[i][j].second] = p;
            }
            if(nxt[i] >0 ) upd(1, 1, n, nxt[i]);
            
      }
      
      for(int i = 0;i < q; i ++ ) {
            printf("%d\n", iAns[i]);
      }
      
}

Counting How Many Numbers In a Range With Specific Property

Intended Problem : LightOj 1140
The problem Asks to output The number of 0’s to be write in range [A,B] inclusive,,,

Okay, The strategy to solve this kind of problem is Simple , Function…

Let F(N) -> be a function which returns the number of 0’s in range [1,N] .( we keep 0 as a special case.)
Then The number of 0’s in range [A,B] = F[B] – F[A-1]

Now only problem remains how to calculate values of F(N) efficiently…

Let string y = "decimal representation of N"
y = "101" if N  = 101

We iterate through the y..
The first digit -> 1
So we can place [0,1] , not more than that.
We declare a variable upto = Which far I can go in this given condition. The condition will be see soon,,

So , ->>> We put 0 in the first position. Go to the next digit..
Can you tell ,which digits I can place in 2nd position ???
0 ?
Not exactly … As We started from 0, and whatever I put in the 2nd position ,It will remain smaller Than N..
This is the condition…. So I need a comparator to tell me whether The I can [0,9] or to the certain limit..
This is done using a bool variable …

low = (low || d < y[i]-'0')

if low == true: d in range [0,9]
else d in range[0,y[i]-'0']

This value is proceded to the next stage..

Again ,One more information is needed to to be propagated. That is Is The number is valid..
Like Putting 0 in the first place doesn’t make any valid representation of the Number…
So we wipe out this chances…
Putting A variable…. prv0
This value is true if we placed valid digits [1,9] in some left digits.
and false otherwise.

Again , We need a counter function, That counts ,how many number can be created if we place d in the i’th place…
This is simple ….

N = 167
how many Number can be created which is <= N && starts with 1 .... this is 68 [100,167]
how many Number can be created which is <= N && starts with 0 .... this is 68 [000,99]

Is it clear ???

Now The solution:::

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT				100
#define ll				long long
#define ull				unsigned long long
#define MOD				1000000007
#define MEMSET_INF		63
#define MEM_VAL			1061109567
#define FOR(i,n)			for( int i=0 ; i < n ; i++ )
#define mp(i,j)			make_pair(i,j)
#define lop(i,a,b)		for( int i = (a) ; i < (b) ; i++)
#define pb(a)			push_back((a))
#define gc				getchar_unlocked
#define PI				acos(-1.0)
#define inf				1<<30
#define lc				((n)<<1)
#define rc				((n)<<1 |1)
#define msg(x)			cout<<x<<endl;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(ll &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
	ll ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/


string y;
ll dp[11][2][2];

ll cnt ( int inx, int low, int prv0)
{
	if(prv0 == 0) return 0;
	ll r = 0 ;
	for (int i = inx ;  i < y.length() ; i ++ ) {
		r = 10 * r + (low ? 9 : y[i]-'0');
	}
	return r+1;
}


ll cal(int inx , int low , int prv0)
{
	if(inx == y.length()) return 0;

	if(dp[inx][low][prv0] !=-1 ) return dp[inx][low][prv0];
	
	int up = (low ? 9 : y[inx]-'0');
	
	ll r = 0;
	for (int d = 0 ; d <= up ; d ++ ) {

		r += cal(inx+1, (low || (d < y[inx]-'0')) , prv0 || d);

		if(d == 0) r += cnt (inx+1, (low || (d < y[inx]-'0')) , prv0 || d);
	}
	return dp[inx][low][prv0] = r;
}

int main()
{
	ll tc ,cs =0 ;
	ll a , b ;
	sc(tc);
	while (tc -- ) {
		sc(a);
		sc(b);
		ms(dp, -1);
		ll k1 = 0;
		if(a-1>=0 )
		{
			ll p = a-1;
			y.clear();
			while(p){
				y.push_back(p%10+'0');
				p/=10;
			}
			reverse(y.begin(), y.end());
			k1 = cal(0,0,0);
		}
		ll p = b;
		y.clear();
		while (p) {
			y.push_back(p%10+'0'); p/=10;
		}
		reverse(y.begin(), y.end());
		ms(dp, -1);
		ll k2 = cal(0, 0, 0);
		if(a == 0) k2 ++;
		printf("Case %lld: %lld\n" ,++cs, k2 - k1);
	}
	return 0;
}

In my code, call function is the main generator, helper cnt function ..
Using DP , avoids same calculation..
This occurs as overlapping sub-problems..

N = 489
cal(0,0,0)
-> cal(1,1,0) , Put 0 in the 1st place
-> cal(1,1,1) ,Put 1 in the first place
-> cal(1,1,1),Put 2 in the first Place
-> cal(1,1,1) ,Put 3 in the first place
-> cal(1,0,1) ,Put 4 in the first Place

So we memoize the result and write a recursive dp solution.
We just needed to store The value for 0 , we place a condition on d , then add to it

Second Problem : SPOJ MDIGITS
The only change is that we will need to store all the digits, not for only 0’s

Here is The code:

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT                     15
#define ll                      long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define FOR(i,n)                for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define inf                     1<<30
#define lc                      ((n)<<1)
#define rc                      ((n)<<1 |1)

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
	ll ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/

string y;
struct W  {
	int A[10];
	W(){ms(A, 0);}
	void show(){
		FOR(i, 10) printf("%5d" , A[i]);
		printf("\n");
	}
};

W dp[20][2][2];
W EMPTY;
bool vis[20][2][2];

int cnt( int index , int low , int ZERO)
{
	
	if(ZERO == 0) return 0;
	
	int sum = 0 ;
	
	for (int i = index ; i < y.length() ; i ++ ) {
		
		sum = 10 * sum + (low ? 9 : y[i] -'0');
		
	}
	
	return sum + 1;
}

W cal(int index , int low, int ZERO)
{
	
	if(index == y.length() ) return EMPTY;
	
	if(vis[index][low][ZERO] ) return dp[index][low][ZERO];

	W r;
	
	int upTo = (low ? 9: y[index] - '0');

	for (int d = 0 ; d <= upTo ; d ++ ) {
		
		W t = cal(index + 1 , low || d < y[index] -'0' , ZERO || d) ;

		int h =cnt (index + 1, low || d < y[index] -'0' , ZERO || d );
		
		for (int i = 0; i < 10 ; i ++ ) r.A[i] += t.A[i];
		
		r.A[d] += h ;
	}
	vis[index][low][ZERO] = true;
	return dp[index][low][ZERO] = r;
}



int main(void){
	
	for(int a, b; scanf("%d %d", &a, &b) == 2 && (a || b); ){

		if(a>b) swap(a, b);
		ms(dp, 0);
		ms(vis, false);
		y = to_string(a-1);
		W k = cal(0, 0, 0);
		ms(dp, 0);
		ms(vis , false);
		y  = to_string(b);
		W k2  = cal(0 , 0, 0);

				
		for (int i = 0; i < 10; i ++ ) {
			if(i) printf(" ");
			printf("%d",k2.A[i] - k.A[i]);
		}
		printf("\n");
		
	}
	return 0;
}

Another Example :
Given A range [A,B],
Digit Product of a number if the multiplication of all the digits of a number ,
DigitProduct(123) = 1 * 2 * 3 = 6
DigitProduct(1021) = 1 * 0 * 2 * 1 = 0

So you need to summation all the DigitProducts in the range [A,B]

Try To figure it out ??

LightOj – 1396 – Palindromic Numbers (III) , Spoj Pallin

Approach : Greedy , String ,Pallindrome ..

Abridge Statement : Given A string (|s| <= 10^5 ) , You Have to output minimum possible palindromic number which is greater than the given number.

Idea :
1. For a pallindrome String , if we fix the first half , then last half is already selected...
2. To find the minimum possible pallindrome, We first check , if the given string mirrored about it's middle position than it creates bigger pallindrome or not.
S = "123312"
If we mirror the first half , then it creates , 123321 , which is greater than the given string
So this case we can handle.
Now if S= 12312 , This will create 12321 , which is bigger than the given string ,,

I think you understood how to handle odd & even length ...

3. If The mirrored String is small Then we need to derive some method

Let's look S = 1567
What's its next Pallindrome : 1661 ...
How ???

Ok if we update the most significant digit, then It will create bigger pallindrome , No doubt, but not always the minimum possible . To find the minimum possible, We need to update the least significant digits... As I said , The first half determines the second half, So the least updating Position is the middle element.

How to find this pivot element ??
This is easy . in 0 based index, Its index = (len - 1) /2;

so ,we start from the least significant digit to most significant digit,,

Ok , we want to update the least significant digit, Increase its value by 1, Now
Case 1 : if the digit is 9, then We update it to 0, carry to make 1 ,for the later significant digit
Case 2: If the digit is not 9 , increase it by 1 , and note its position(pos ) ,,.


To build The output string,

 
for all i < pos : 
        out[i] = out[len-1-i]  = str[i]
out[pos] = out[len-1-pos] = str[i] + 1;
for i = pos + 1 to i < len -1 - pos  :
       out[i] = '0';

Is everyThing done ??
Not really.
Two special case :
1 :

 
 If |S| = 1 ,: 
       if(S[0] < 9) : out[0] = S[0]+1;
       else :
             out[0] = '1'; out[1]='1'

2. If all the digits are 9,
Think . 999,
What should be the answer. 1001

Think this case and you will get it..

Complete Solution :

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT				100005
#define ll				long long
#define ull				unsigned long long
#define mod				1000000007
#define MEMSET_INF		63
#define MEM_VAL			1061109567
#define FOR(i,n)			for( int i=0 ; i < n ; i++ )
#define mp(i,j)			make_pair(i,j)
#define lop(i,a,b)		for( int i = (a) ; i < (b) ; i++)
#define pb(a)			push_back((a))
#define gc				getchar_unlocked
#define PI				acos(-1.0)
#define inf				1<<30
#define lc				((n)<<1)
#define rc				((n)<<1 |1)
#define msg(x)			cout<<x<<endl;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
	ll ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/


char str[LMT];
char out[LMT];

int main()
{
	
	
	int tc,cs = 0;
	sc(tc);
	while (tc -- ) {
		
		scanf("%s",str);
		int len = 0 ;
		bool flag = true;
		
		for( ; str[len] ; len ++ ){
			if( str[len] !='9') {
				flag = false;
			}
		}
		
		printf("Case %d: ",++cs);
		
		if(len == 1) {
			if(str[0] <'9' )printf("%c\n" ,str[0] +  1);
			else printf("11\n");
			continue;
		}
		
		if(flag == true ){
			printf("1");
			for(int i = 1; i < len ; i ++) printf("0");
			printf("1\n");
			continue;
		}
		else {
			
			out[len] = '\0';
			
			bool isbig=true , iseq = 1;
			for(int i = (len - 1)/2 ; i >=0  ;i -- ){
				if(str[i]!= str[len-1-i]) {
					isbig = str[i] > str[len-1-i];
					iseq = 0;
					break;
				}
				if(str[i] != str[len - 1 - i ]) iseq = 0;
			}
			
			if(isbig && iseq == 0) {
				for(int i = 0 ; i <= (len - 1)/2 ;i ++ ) out[i] = out[len-1-i] = str[i];
				printf("%s\n",out);
				continue;
			}
			
			
			int ink , pos = 0;
			for(int i = (len-1)/2 ; i >=0 ; i -- ) {
				
				if( str[i] !='9') {
					ink = str[i] +1 ;
					pos = i ;
					flag = true;
					break;
				}
			}
			
			
			
			for(int i = 0 ; i < pos ; i ++ ) out[i] = out[len-1-i] = str[i];
			out[pos]= out[len -1 - pos]  = ink;
			for(int i = pos + 1; i < len -1 - pos ; i ++ ) out[i] = '0';
			
			printf("%s\n",out);
			
		}
		
	}
	return 0;
}