code with chinmay.c: September 2015

Friday 11 September 2015

mastering c++(2)

extending little more concept about loop

sometimes we dont want to allot new memory so we can use this approach

#include<bits/stdc++.h>
int main()
{
    for(auto i:{1,2,3,4,5,6})
        printf("%d\n",i);
    return 0;
}

now pointer stuff

pointer to : *p
reference of: &p

suppose

int i=1;
so,
int *p=&i;

means p points to the memory address where i is stored....

int p=&i;

means p has the memory address of "i" so whatever changes u will do in p will directly effect i..

assume it like its same as two remote of a same tv.

pointer even does the same task but in that it points to the index of the number it is addressed... like int *p=&a[5]; even when we write int *p=a(is an integer array);it points to the first element... its same as int *p=&a[0];

int *p=nullptr
nullptr is to make a pointer null ...
it is mostly used when the non linear data structure is used like queue, linked list,vector,maps etc
to mark the end of node...

summing up in a program

#include<bits/stdc++.h>
typedef struct $
{
    int value;
    struct $ *pointer;
}fun;
void play(fun a,fun *ax,fun &axx)
{
    int i=a.value;
    int j=ax->value;
    int k=axx.value;
    printf("%d %d %d\n",i,j,k);
    printf("------------\n");
    printf("%d\n",a.pointer->value);
    printf("%d\n",a.pointer->pointer->value );
    printf("------------\n");
    printf("%d\n",ax->pointer->value );
}
int main()
{
    fun *a=new fun[1];
    fun *ax=new fun[1];
    fun axx;
    a[0].value=12;
    ax[0].value=13;
    axx.value=45;
    a[0].pointer=&ax[0];
    ax[0].pointer=&axx;
    axx.pointer=nullptr;
    play(*a,ax,axx);
    return 0;
}

at first i initialized the memory for a and ax in heap and axx in stack memory
after that assigned value to the variables

after that i made use of the pointers to point to each other a->ax->axx

and call the fun function which shows a clear difference of reference and pointer

take a pen and paper and try to break and check if u got the concept if not comment me... its very important u get to pointers concept thoroughtly and play with it and try new variations than only u can master its use...

Sunday 6 September 2015

acm icpc amritapuri regional 2009

XOR SUM

Given an array of N numbers, we wish to choose a contiguous sub-sequence of the array, so that the bitwise XOR of all chosen numbers is maximum. Bitwise XOR is defined as follows: every bit in the answer is obtained by applying XOR logic on the corresponding bits of the set of numbers. For example 7, 8 and 5 are XORed as follows,

Numbers in binary:  0111  1000  0101  -----  1010

So the answer is 10 (in decimal). The same answer can be obtained in C/C++/Java by using the XOR operator as 7^8^5.

Input

The first line contains the number of test cases T. The first line of each test-case contains one integer, N (size of the array). The next N lines of each test-case contain integers denoting the elements of the array.

Constraints:

1 $\le$ T $\le$ 10
1 $\le$ N $\le$ 100, 000
All input integers will be non-negative and fit into 32 bit signed integer.

Output

For each test case, output a single line containing the maximum sum that can be obtained.

Sample Input

5  3  7  7  7  0

5  3  8  2  6  4

Sample Output

implmentation of tries (source quora by lalit kundu -iiit hyderabad)

I will be writing in this post about Tries and the concept widely used in bit manipulation kind of problems. We'll see 2-3 problems which trie is helpful. First we see what a trie is. Trie can store information about keys/numbers/strings compactly in a tree. Tries consists of nodes, where each node stores a character/bit. We can insert new strings/numbers accordingly.

Source: Wikipedia.

But we will be dealing with numbers here, and particularly in binary bits. We'll see as we solve problems.

Problem1: Given an array of integers, we have to find two elements whose XOR is maximum.

Solution: Suppose we have a data structure in which can satisfy two types of queries: 1. Insert a number X 2. Given a Y, find maximum XOR of Y with all numbers that have been inserted till now. If we have this data structure, we'll insert integers as we go, and with query of 2nd type we'll find the maximum XOR.

So, we trace the path of the number we have to insert, we don't have to draw the existing path again. Insertion of an N length key takes O(N) which is log2(MAX) where MAX is the maximum number to be inserted in trie, because there are at maximum log2(MAX) binary bits in a number. This way we store all the data about all the numbers inserted into trie till now. Now, for query of type 2: Let's say our number Y is b1,b2...bn, where b1,b2.. are binary bits. We start from b1. Now for the XOR to be maximum, we'll try to make most significant bit 1 after taking XOR. So, if b1 is 0, we'll need a 1 and vice versa. In the trie, we go to the required bit side. If favorable option is not there, we'll go other side.

Doing this all over for i=1 to n, we'll get the maximum XOR possible.

Problem2: Given an array of integers, find the subarray with maximum XOR.

Solution: Let's say F(L,R) is XOR of subarray from L to R. Here we use the property that F(L,R)=F(1,R) XOR F(1,L-1). How? Let's say our subarray with maximum XOR ended at position i. Now, we need to maximise F(L,i) ie. F(1,i) XOR F(1,L-1) where L<=i. Suppose, we inserted F(1,L-1) in our trie for all L<=i, then it's just problem1.

ans=0

pre=0

Trie.insert(0)

for i=1 to N:

pre = pre XOR a[i]

Trie.insert(pre)

ans=max(ans, Trie.query(pre))

print ans

SOLUTION

#include<bits/stdc++.h>
#include<complex>
using namespace std;
#define ll long long
typedef pair<ll,ll> pp;
typedef vector<pair<ll,ll> > vpp;
ll min(ll a,ll b)
{
    return(a<b)?a:b;
}
ll max(ll a,ll b)
{
    return(a>b)?a:b;
}
typedef struct $
{
    struct $ *left;
    struct $ *right;
}ss;
void insert(ss *head,ll a,ll count)
{
    if(count ==-1)return;
    if((a>>count)&1)
    {
        if(head->right==NULL)
        {
            head->right=(ss *)malloc(sizeof(ss));
            head->right->right=NULL;
            head->right->left=NULL;
        }
        insert(head->right,a,count-1);
    }
    else
    {
        if(head->left==NULL)
        {
            head->left=(ss *)malloc(sizeof(ss));
            head->left->right=NULL;
            head->left->left=NULL;
        }
        insert(head->left,a,count-1);
    }
}
void recieve(ss *head,ll a,ll count,ll &num)
{
    if(count==-1)return;
    if((a>>count)&1)
    {
        if(head->left!=NULL)
            recieve(head->left,a,--count,num);
        else
        {
            num+=(ll)pow(2,count);
            recieve(head->right,a,--count,num);
        }
    }
    else
    {
        if(head->right!=NULL)
        {
            num+=(ll)pow(2,count);
            recieve(head->right,a,--count,num);
        }
        else
            recieve(head->left,a,--count,num);
    }
}
int main()
{
    ll t,n,num,a[400005],prefix[400005]={0},ma=0;
    scanf("%lld",&t);
    while(t--)
    {
        ma=0;
        scanf("%lld",&n);
        for(ll i=0;i<n;i++)
            scanf("%lld",a+i);
        ss *x=(ss *)malloc(sizeof(ss));
        insert(x,0,31);
        for(ll i=1;i<=n;i++)
        {
            prefix[i]=prefix[i-1]^a[i-1];
            insert(x,prefix[i],31);
            num=0;
            recieve(x,prefix[i],31,num);
            ma=max(ma,num^prefix[i]);
        }
        printf("%lld\n",ma );
    }
    return 0;
}

Wednesday 2 September 2015

mastering c++ (1)

hi friends in this tutorial we will learn some of the cool stuffs on c++.

first initialization stuffs..

#include<bits/stdc++.h>
#include<complex>
using namespace std;
int main()
{
    double d=2.2;
    int i=7;
    d=d+i;
    i=d*i;
    double ddd{2.3};
    complex<double>z=1;
    complex<double>z2{1,2};
    complex<double>z3={1,2};
    vector<int>v{1,2,3,4,5};
    int id{2};
    auto bd=true;                //a bool
    auto cd='x';                //a char
    auto idd=123;                 //an int
    auto dd=1.2;                 //a double
    auto zd=sqrt(12);             //power type whatever z returns
    cout << i << "\n" << d << "\n" << ddd << "\n" << z << "\n" << z2 << "\n" << z3 << "\n" << v[0] << "\n" << id << "\n" << bd << "\n" << cd << "\n" << idd << "\n" << dd << "\n" << zd << "\n" ;
    return 0;
}

theory
complex is a class defined in complex.h file it has all the function for executing complex nunmbers such as trignometric,power,exponential,hyperbolic functions...

auto
when u dont know exactly what is the type of the variable u will recieve then use auto ..
as soon as u declare a type auto it searches for its type using "template aurgument dectection" auto keyword just serve the purpose it doesnot necessarily do the task...

#include<bits/stdc++.h>
#include<complex>
using namespace std;
auto f()->decltype(1+2)
{
    return sizeof(f);
}
int main()
{
    cout<<f()<<'\n';
    return 0;
}

decltype is use to provide the type to a function here (1+2) was in int so returned value is 4

constants

const ->promises that it will not change the value
constexpr->evaluated at compile time and the value assigned must also be const

to understand look the following the code snippet.

#include<bits/stdc++.h>
#include<complex>
using namespace std;
int main()
{
    const int d=17;
    int i=2;
    constexpr int l1=d;
    const int w1=d;
    cout<<l1<<'\n'<<w1<<'\n';
    l1=2;
    w1=3; 
    return 0;
}

#include<bits/stdc++.h>
#include<complex>
using namespace std;
int main()
{
    const int d=17;
    int i=2;
    constexpr int l1=d;
    constexpr int l2=i;
    const int w1=d;
    const int w2=i;
    cout<< l1<<'\n'<<l2<<'\n'<<w1<<'\n'<<w2; 
    return 0;
}

notice this error shown in compile time and no error for "const"

#include<bits/stdc++.h>
#include<complex>
using namespace std;
constexpr double square(double x){return x;}
int main()
{
    cout<<square(2);
    cout<<square(3);
    return 0;
}

here u may confuse that the function is a constexpr but still it is accepting a variable input but the fact is that this function is immutable means u cannot inherit this function nor modify it... something like final keyword in java...

compile using c++14 in ubuntu

The current GCC in the ubuntu repository doesn’t support the C++14 standard. To use the C++14 install the GCC has to be updated manually. It can be found in the Ubuntu Toolchain PPA. After this, the C++ compiler can be updated. The following commands show how to add the repository and install the compiler:

root$sudo add-apt-repository ppa:ubuntu-toolchain-r/test

root$sudo apt-get update

root$sudo apt-get install g++-4.9

check whether g++-4.9 is installed..

root$g++-4.9

now check which version is there in your pc

root$sudo ln -f -s /usr/bin/g++-4.9 /usr/bin/g++

now check the version

root$g++ -v

you must see something like

thats means its done :) now compile your file using.

root$g++ -std=c++14 code.cpp

"code.cpp type your file name"

code with chinmay.c