Tuesday, 2 February 2016

fun with competitve programming

GCD

hi friends today I will discuss about GCD actual implementations in competitive programing .I have been facing lot of problems so here i though to make a note of the implementation of GCD.

GCD(Greatest Common Divisor) is best solved by Euclid algorithm.
gcd(a,b)=gcd(b,r) where a=bt+r;

how??

gcd(a,b)=>gcd(bt+r,b)
now bt is divisible by b,so the common division must depend on r.

code in C

#include<stdio.h>
int main()
{
    int b=4,a=6;//a>b
    while(b)
    {
        int f=a%b;
        a=b;
        b=f;
    }
    printf("%d\n",a);
    return 0;
}

faster code in C

#include<stdio.h>
int main()
{
    int b=10,a=25;//a>b
    while(b)
    {
        b^=a^=b^=a%=b;
    }
    printf("%d\n",a);
    return 0;
}

both the codes looks different but are same as the second code uses xor, as xor has a special property of swapping the elements..(interesting application right!!)

implementation of gcd

Q)Suppose that you have two sets of people of cardinalities m,n and you want to divide them into teams of k people with every team being composed of people of only one of the original two sets.

So then what you have to do .. find the gcd of the two numbers that will be k the maximum length a team can be divided as k divides both m and n.
example

m=4,n=6

"*" and "0" represents team members in the set.

{* * * *} ,{0 0 0 0 0 0}
{* *},{* *},{0 0},{0 0},{0 0},

Q)Suppose there are two set of team of size n,m .First team consists of boys and another girls . Now on the ith day you invite (i%n)th boy and(i%m)th girl for dinner.If either of them is "happy" the other one will become "happy" and the state of happiness stays even after meeting.You are given some of the girls or boys are already in "happy" state.
So you have to find if all the boys and girls have achieved the state of happiness or not.

So brute force will be O(n*m) because there is only n*m number of pairs possible.

Now suppose this input.
n=2 m=4
already happy state of boys -> 1st boy(0th index)
already happy state of girls -> none

i= 0 1 2 3 4 5 6 7 8 9(assuming i(day) state from 0)
b=0 1 0 1 0 1 0 1 0   (i%n)
g=0 1 2 3 0 1 2 3 0   (i%m)
    ^    ^    ^    ^    ^
happy states..

output :NO

Now suppose this input.
n=4 m=5
already happy state of boys -> 1st boy(0th index)
already happy state of girls -> none

i= 0 1 2 3 4 5 6 7 8 9(assuming i(day) state from 0)
b=0 1 2 3 0 1 2 3 0 1 0 1 2 3 0 1 2 3 0 1
g=0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
    ^          ^ ^       ^ ^ ^ ^    ^ ^ ^ ^ ^ ^ ^
OUTPUT :YES

now O(n+m) solution

find gcd of n,m =k
and now store h[i%k]=1
then loop through 0to k if h[loop variable]=0 then NO else YES..

how??

suppose n=4 ,m=6

g= 0 1
n= 0 1
      2 3

m=0 1
     2 3
     4 5

so if 0th and 1st position is "1" then the OUTPUT is YES else NO.

code

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

int gcd(int a,int b)
{//a>b
    while(b)
        b^=a^=b^=a%=b;
    return a;
}
int main(int argc, char const *argv[])
{
 int n,m,a[1000]={0},x,x1,k;
 scanf("%d %d",&n,&m);
 k=gcd(max(n,m),min(n,m));
 scanf("%d",&x);
 for(int i=0;i<x;i++)
 {
  scanf("%d",&x1);
  a[x1%k]=1;
 }
 scanf("%d",&x);
 for(int i=0;i<x;i++)
 {
  scanf("%d",&x1);
  a[x1%k]=1;
 }
 for(int j=0;j<k;j++)
  if(a[j]==0)
  {
   printf("NO\n");
   return 0;
  }
 printf("YES\n");
 return 0;
}

input file

100 50

30 50 54 7 8 59 60 61 62 63 64 15 16 18 19 20 22 73 27 79 83 86 87 89 42 93 94 45 46 97 98

20 1 2 3 5 6 17 21 24 25 26 28 30 31 32 34 35 38 40 41 49

output
YES

input file

2 3
0
1 0

output
YES

input file

2 4
1 0
1 2

output
NO

Friday, 15 January 2016

bug hunt in c++

look through this code snippet

did you know:

#include<bits/stdc++.h>
void fo(){};

int main()
{
fo();
return 0;
}

is correct!! notice the ";" mark.

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"

Monday, 24 August 2015

acm-icpc regionals amritapuri 2014

Kiwi Number

The New Zealand government is super-excited about the Cricket World Cup 2015 happening in their country. Hence, it has decided to conduct a census on cricket to find out how many people are interested in the sport, etc.
The statistics obtained are given to us as a range of numbers from A to B (inclusive). In these statistics, the government is interested in some particular numbers called "Kiwi Numbers".
A number is called a Kiwi Number if it has a prime number of distinct factors. A prime number N has exactly two divisors, 1 and N.
Can you help the government by calculating the number of Kiwi numbers in the given range?
Input:
The first line contains the number of test cases T.
Each of the next T lines contains two space separated numbers A and B.
Output:
For each test case, output the required answer on a separate line.
Constaints:
1 <= T <= 100
2 <= A <= B <= 1000000000
B - A <= 200000
Sample Input:
3
2 10
100 100
578 720
Sample Output:
6
0
23
Explanation:
For the first case, the Kiwi numbers are 2, 3, 4, 5, 7, 9.

explainantion

to solve this u need to know segmented sieve of Eratosthenes ....
solve this spoj question for detail...

http://www.spoj.com/problems/PRIME1/

solution

#include<bits/stdc++.h>
int a[10000]={0};
int main()
{
    a[1]=1;
    a[0]=1;
    for(int i=6;i<=100;i+=6)
    {
        if(a[i-1]==0)
            for(int j=(i-1)*(i-1);j<=10000;j+=(i-1))
                a[j]=1;
        if(a[i+1]==0)
            for(int j=(i+1)*(i+1);j<=10000;j+=(i+1))
                a[j]=1;        
    }
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        int b[200005]={0},z=0;
        scanf("%d %d",&n,&m);
        int x=sqrt(m);
        for(int i=2;i<=x;i++)
        {
            int k=n/i;
            k=k*i;
            if(k<n)k+=i;
            int sq=i*i;
            for(;k<=m;k+=i)
            {
                if(k<sq)continue;
                if(k==sq)b[k-n]++;
                else b[k-n]+=2;
            }
        }
        for(int i=0;i<=m-n;i++)
        {  
            b[i]+=2;
            if(b[i]==2 || b[i]==3)z++;
            if(a[b[i]]==0 && b[i]%2!=0 && b[i]%3!=0)
                z++;
        }
        printf("%d\n",z);
    }
    return 0;
}

Dhonis Bowlers

The Indian team is known for their strong batting and sloppy bowling. The captain M.S. Dhoni is concerned about this issue. He wants to address this by pairing up bowlers who have good economy rates.

He has all the bowlers' economy rates as integers. Unfortunately, these are T20 figures and to convert them to ODI format, he wants to pair up bowlers in such a way that the sum of the economy rates of two bowlers, modulo M, is always less than or equal to X.

Given the economy rates, M and X, can you tell him how many such ordered pairs are possible?

Note: The pair of bowlers chosen by him can be the same. Yeah, Dhoni has won a cup in all limited over formats, but he definitely needs to sharpen his math skills.

Input:

The first line contains the number of test cases T. Each test case contains N, M and X on the first line, followed by N space separated integers A[1..N] on the second line.

Output:

Output T lines, containing the answer for the corresponding test case.

Constraints:

1 <= T <= 10

1 <= N <= 100000

0 <= X < M <= 100000

0 <= A[i] <= 1000000000

Sample Input:

3 5 3

1 2 3

4 7 4

31 12 11 17

Sample Output:

Explanation:

For the first example, the valid pairs are (1, 1), (1, 2), (2, 1), (2, 3), (3, 2), (3, 3).

my solution

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,x,a[300000]={0},c,window[300000]={0};
        long long sum=0;
        scanf("%d %d %d",&n,&m,&x);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&c);
            a[c%m]++;
        }
        window[0]=a[0];
        for(int i=1;i<m;i++)
            window[i]=window[i-1]+a[i];
        for(int i=m;i<=m+x;i++)
            window[i]=window[i-1];
        for(int i=0;i<m;i++)
        {
            if(x>=i)
            sum+=a[i]*(window[x-i]);
            sum+=a[i]*(window[m+x-i]-window[m-i-1]);
        }
        printf("%lld\n",sum );
    }
    return 0;
}

Sunday, 23 August 2015

MY SKETCHES....

hi friends its a very different post not relates to computer science field but a brief display of my hobby...

i thought why dont i share my knowledge with u all and even u will start creating fine arts.... so my friends today no tutorial as such but a brief demonstration of my works... hope u like and enjoy watch please do comment and share....