code with chinmay.c: c plus plus

Showing posts with label c plus plus. Show all posts

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...

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