13154 - Extreme XOR Sum (Observation, Precal )

- December 04, 2016


UVA 13154 - Extreme XOR Sum (Observation, Precal )

/// Story Behind This Problem!!
/// As problem pattern was similar to another problem which I had faced
/// recently on HackerRank( XOR MATRIX )
/// I easily figured out the pattern of NcR. Main Problem was with complexity!!
/// But, this problem luckily passed within 2 sec, as there was not strong pretests.
/// I heard after contest that complexity can be reduced to O( q*sqrt(n) ). I have no
/// proper idea of this Sqrt decomposition solution.
/// My solution is based on following idea:
/// 1. Observe the patten for different length.
/// 2. If ncr[ len ][ j ] is odd then include jth item of that len otherwise exclude.
/// 3. Now, As XOR follows cummulative property answer each xor sum of subsegment
///    containing odd values only on that len.


///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  Digit     0123456789012345678 ///
#define MX     10001
#define inf    2000000010
#define MD     1000000007
#define eps    1e-9
///===============================///

int dp[MX+1],ncr[2][MX+1];
vector<int>v[MX];

void Precal_Pattern() {
    for(int i=1; i<=10000; i++) {
        ncr[i&1][1]=1;
        v[i].pb(1);
        bool f=0;
        for(int j=2; j<=i; j++) {
            ncr[i&1][j]=( ncr[!(i&1)][j]+ncr[!(i&1)][j-1] )%2;
            if( ncr[i&1][j]==0  && !f )v[i].pb( j-1 ),f=1;
            if( ncr[i&1][j]  && f  )v[i].pb( j ),f=0;
        }
        ncr[i&1][i]=1;
        v[i].pb( i );
    }
}

int main() {
    int tc,cs=1,i,n,x,y,q;
    Precal_Pattern( );
    S(tc);
    while(tc--) {
        S(n);
        dp[0]=0;
        for(int i=1; i<=n; i++) {
            S(x);
            dp[i]=(dp[i-1]^x);
        }
        S(q);
        printf("Case %d:\n",cs++);
        while(q--) {
            S2(x,y);
            int g=(y-x+1);
            int sz=SZ( v[g] );
            int xr=0;
            for(int i=0; i<sz; i+=2) {
                int l=v[g][i];
                int r=v[g][i+1];
                xr^=( dp[ x+r ]^dp[ x+l-1 ] );
            }
            printf("%d\n",xr);
        }
    }
    return 0;
}