Big Integer Implementation

// Big Integer Implementation

#include "bits/stdc++.h"
using namespace std;
#define pb                       push_back
#define all(v)                   v.begin(),v.end()
// Excluding leading zeroes
string roundzero(string x){
    string ans="";
    int flag=1;
    if(x[0]-'0'!=0) flag=0;
    int i;
    for(i=0;i<x.length()-1 && flag==1;i++){
        if(x[i]-'0'!=0) flag=0;
    }
    for(int j=i;j<x.length();j++){
        ans.pb(x[j]);
    }
    return ans;
}
// To find greater of two string
int greater1(string x,string y){
   int i=0;
   while(x[i]==y[i] && i<x.size()){
    i++;
   }
   if(i==x.size()) return -1;
   if(x[i]-'0'>y[i]-'0') return 1;
   else return 0;
}
// To make strings of equal length
vector<string> equallength(string x,string y){
    //if(x.size()==y.size()) return;
    if(x.size()>y.size()){
        string temp1=x,temp2=y;
        reverse(all(temp1));
        reverse(all(temp2));
        int u=x.size()-y.size();
        while(u--){
            temp2.pb('0');
        }
        reverse(all(temp1));
        reverse(all(temp2));
        x=temp1;
        y=temp2;
    }
    if(y.size()>x.size()){
        string temp1=x,temp2=y;
        reverse(all(temp1));
        reverse(all(temp2));
        int u=y.size()-x.size();
        while(u--){
            temp1.pb('0');
        }
        reverse(all(temp1));
        reverse(all(temp2));
        x=temp1;
        y=temp2;
    }
    vector<string> ans;
    ans.pb(x);
    ans.pb(y);
    return ans;
}
//ADD
string add(string x,string y){
       string ans="";
       vector<string> el=equallength(x,y);
       x=el[0];
       y=el[1];
       int carry=0;
       for(int i=x.size()-1;i>=0;i--){
           //cout<<(((x[i]-'0')+(y[i]-'0')+carry)%10)<<endl;
         int ans1=(((x[i]-'0')+(y[i]-'0')+carry)%10);
         ans.pb((char)(ans1+48));
         carry=(x[i]-'0'+y[i]-'0'+carry)/10;
       }
    if(carry!=0)
    ans.pb((char)(carry+48));
    reverse(all(ans));
    return ans;
}
//SUBTRACT
string subtract(string x,string y){
    string ans="";
    vector<string> el=equallength(x,y);
    x=el[0];
    y=el[1];
    //cout<<x<<" "<<y<<endl;
    int flag=greater1(x,y);
    //cout<<flag<<endl;
        if(!flag)
        {
            string temp=x;
            x=y;
            y=temp;
        }
        for(int i=x.size()-1;i>=0;i--){
            if(x[i]-y[i]>=0){
                ans.pb((char)(48+x[i]-y[i]));
            }
            else{
              int r=i-1;
              while(x[r]=='0') r--;
              x[r]=x[r]-1;
              for(int k=r+1;k<i;k++){
                x[k]='9';
              }
              int p=10+(x[i]-'0');
              int q=y[i]-'0';
              ans.pb((char)(48+(p-q)));
            }
            //cout<<x<<" "<<y<<" "<<ans<<endl;
        }
    reverse(all(ans));
    return ans;

}
//MULTIPLY
string multiply(string x,string y){
   string ans="";
   for(int i=y.size()-1;i>=0;i--){
    string temp="";
    int e=y.size()-1-i;;
    while(e--) temp.pb('0');
    int p=y[i]-'0';
    int carry=0;
    //cout<<y[i]<<" ";
    for(int j=x.size()-1;j>=0;j--){
        //cout<<x[i]<<" ";
        int q=x[j]-'0';
        int y=((p*q)+carry)%10;
        carry=((p*q)+carry)/10;
        cout<<carry<<" ";
        temp.pb((char)(y+48));
    }
    if(carry!=0)temp.pb((char)(carry+48));
    reverse(all(temp));
    cout<<temp<<endl;
   // cout<<temp<<endl;
    if(ans==""){
        ans=temp;
    }
    else{
        vector<string> el=equallength(temp,ans);
        temp=el[0],ans=el[1];
        ans=add(temp,ans);
    }
   }
   return ans;
}
//DIVIDE  uses repeated subtraction ;;may lead to TLE
vector<string> divide(string x,string y){
     vector<string> ans;
     vector<string> el=equallength(x,y);
     x=el[0];
     y=el[1];
     string qui="",rem="";
   
     if(greater1(x,y)==0) {
             qui.pb('0');
             for(int i=0;i<x.length();i++){
                 rem.pb(x[i]);
             }
     }
     else{
         long long w=0;
         string divid=x;
         string divis=y;
         while(greater1(divid,divis)){
             divid=subtract(divid,divis);
             w++;
         }
         while(w){
             qui.pb((char)(48+(w%10)));
             w/=10;
         }
         reverse(all(qui));
         for(int i=0;i<divid.length();i++){
             rem.pb(divid[i]);
         }
     }
     ans.pb(qui);
     cout<<roundzero(rem)<<endl;
     rem=roundzero(rem);
     ans.pb(rem);
     return ans;
}
//Main
int main(){
   string x,y;
   cin>>x>>y;
   vector<string> ans=divide(x,y);
   cout<<ans[0]<<" "<<ans[1]<<endl;
return 0;
}

Link To Clipboard

VISITING ADJACENT NODES IN GRID

                (x-1,y-1)---------> (x-1,y)-----------> (x-1,y+1)
                  .                        .                          .       
                (x,y-1)                 (x,y)                   (x,y+1)  
                  .                        .                          .       
                (x+1,y-1)<----------(x+1,y)<---------   (x+1,y+1)
                  .                        .                          .


 Hectic Process to validate each point adjacent and jump onto that
 Same process to be done 8 times..

 Hence,
 We make two arrays to store the order of x,y components (delta)

         dx={-1,-1,-1,0,+1,+1,+1,0}
         dy={-1,0,+1,+1,+1,0,-1,-1}


    FOR i=0 -> 8
       validate(x+dx[i],y+dy[i])
       process(x+dx[i],y+dy[i])

REAL STL CHALLENGE !!

The Best STL Problem !!

Email Aliases : http://codeforces.com/problemset/problem/589/A

Implementation :

#include "bits/stdc++.h"
#define pb                       push_back
#define FOR(i,n,m)               for(int i=0;i<n;i+=m)
using namespace std;
map<string,vector<string> > m;
int main(){
  map<string,vector<string> > :: iterator it;
  int n;
  cin>>n;
  vector<string> v,v1;
  FOR(i,n,1){
      string temp,s,e;
      cin>>temp;
      v.pb(temp);
      FOR(i,temp.size(),1){
          if(isalpha(temp[i])){
              s.pb(tolower(temp[i]));
          }
          else{
              s.pb(temp[i]);
          }
      }
      //cout<<s<<endl;
      int flag=0;
      int flag1=0;
      if(s[s.size()-1]=='m' && s[s.size()-2]=='o' && s[s.size()-3]=='c' && s[s.size()-4]=='.' && s[s.size()-5]=='l' && s[s.size()-6]=='i' && s[s.size()-7]=='a' && s[s.size()-8]=='m' && s[s.size()-9]=='b' && s[s.size()-10]=='@')
     {

         flag=1;
         FOR(i,s.size(),1){

          if(s[i]=='.'){
              continue;
          }
          else if(s[i]=='+'){
              while(s[i]!='@') i++;
              e.pb(s[i]);
          }
          else{
              e.pb(s[i]);
          }
          if(s[i]=='@' ) break;
      }
     }
     if(flag){
       string d="bmail.com";
       e=e+d;
       it=m.find(e);
       if(it!=m.end()){
         m[it->first].pb(temp);
       }
       else{
        m[e].pb(temp);
       }
     }
      else{
       it=m.find(s);
       if(it!=m.end()){
         m[it->first].pb(temp);
       }
       else{
        m[s].pb(temp);
       }
      }
  }
  vector<string> :: iterator g;
  cout<<m.size()<<endl;
  for(it=m.begin();it!=m.end();it++){
    cout<<it->second.size()<<" ";
    for(g=it->second.begin();g!=it->second.end();g++){
        cout<<*g<<" ";
    }
    cout<<endl;
  }
return 0;
}

TCS CODEVITA 2015

Teaming up with Akshay Goel (Team Algomonks) , Cleared TCS CodeVita 2015 

Round#1 with Rank #238 Score : 3.73 

Round#2 with Rank #75 Score : 2.79

SPOJ UPDATE :

Newly Framed Question !!
             http://www.spoj.com/problems/UJ01/

GOOGLE CODE JAM ROUND 1C

ALMOST HAD MY CHANCES
Solved two problems but wasn't enough !!
Ranked #1288 with 44 points

Problem 1 : http://ideone.com/x7zhjI

Problem 2 : http://ideone.com/sFkXLf

:)

GOOGLE CODE JAM ( QUALIFICATION ROUND ) 2015

CLEARED THE QUALIFICATION ROUND WITH 34 POINTS :)

Code:

Problem 1 :  http://ideone.com/AeXJ1H   (17 points )

Problem 4 : http://ideone.com/tIIaw3 ( 8 points )

Problem 2 :http://ideone.com/ONjN4L ( 9 points )  Could not solve !!!

Interesting Problem : To Find nth NON-FIBONACCI NUMBER

First Few Non-Fibonacci nos. are : 4,6,7,9,10,11,12..........................

This is very similar to generating fibonacci numbers.Initialize your loop with the 3 initial fibonacci numbers a=1,b=1,c=2.Now , whenever this loop iterates, this tuple moves on to the next tuple of fibonacci numbers.(a=1,b=2,c=3).At every iteration, the number of non-fibonacci numbers jumped over is c-b+1.Keep adding this count as long as it is less than N. When this count exceeds N, it means that we just crossed the Nth Non-Fibonacci number on the numberLine. So if we move back the required numbers (the number by which count exceeds N), we will get the answer.

Complexity: O(log n)

              a=1 b=2 c=3

              while(n>0)

              {

               a=b;

               b=c;

               c=a+b;

               n-=(c-b-1);

              }

              n+=(c-b-1);

              ans=b+n;

CODEFORCES ROUND 297 Div. 2 ( Pasha and String )

Problem Link

Go Greedy!!!

Main Idea is that you go in any order , the swaps will not change.
Swap and Unswap totally depends on the total swap at that position

So , First just mark the swaps at each positon.

Then , sum them to get the total swaps at each position

Now if swap sum count is odd then swap otherwise not

This is one of the finest problem i had seen on greedy basic !!

Segment Tree Template

Structure of Each Node:

struct SegmentTreeNode {

//Information each node contains

void assignLeaf(int value) {
//Intialize each node

}

void merge(SegmentTreeNode& left, SegmentTreeNode& right) {
   //Logic to merge the node


}

int getValue() {
//returning the value queried
}
};

Template:

template<class T, class V>

class SegmentTree {

SegmentTreeNode* nodes;

int N;

public:

SegmentTree(T arr[], int N) {

this->N = N;

nodes = new SegmentTreeNode[getSegmentTreeSize(N)];

buildTree(arr, 1, 0, N-1);

}

~SegmentTree() {

delete[] nodes;

}

V getValue(int lo, int hi) {

SegmentTreeNode result = getValue(1, 0, N-1, lo, hi);

return result.getValue();

}

void update(int index, T value) {

update(1, 0, N-1, index, value);

}

private:

void buildTree(T arr[], int stIndex, int lo, int hi) {

if (lo == hi) {

nodes[stIndex].assignLeaf(arr[lo]);

return;

}

int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;

buildTree(arr, left, lo, mid);

buildTree(arr, right, mid + 1, hi);

nodes[stIndex].merge(nodes[left], nodes[right]);

}

SegmentTreeNode getValue(int stIndex, int left, int right, int lo, int hi) {

if (left == lo && right == hi)

return nodes[stIndex];

int mid = (left + right) / 2;

if (lo > mid)

return getValue(2*stIndex+1, mid+1, right, lo, hi);

if (hi <= mid)

return getValue(2*stIndex, left, mid, lo, hi);

SegmentTreeNode leftResult = getValue(2*stIndex, left, mid, lo, mid);

SegmentTreeNode rightResult = getValue(2*stIndex+1, mid+1, right, mid+1, hi);

SegmentTreeNode result;

result.merge(leftResult, rightResult);

return result;

}

int getSegmentTreeSize(int N) {

int size = 1;

for (; size < N; size <<= 1);

return size << 1;

}

void update(int stIndex, int lo, int hi, int index, T value) {

if (lo == hi) {

nodes[stIndex].assignLeaf(value);

return;

}

int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;

if (index <= mid)

update(left, lo, mid, index, value);

else

update(right, mid+1, hi, index, value);

nodes[stIndex].merge(nodes[left], nodes[right]);

}

};

Segment Tree Instance :

Segment Tree intialization

Segmenttree<int,int> s(a,n)

LUCAS THEOREM !

For nCk;
  nCk % p = ((a1Cb1)*(a2Cb2)*..............*(anCbn)) % p
where a1,a2,a3..... are digits in base-p representation of n &
where b1,b2,b3..... are digits in base-p representation of k. 

For nCr ;

No. of terms divisible in the nCk by a prime no. p may be equal to the :
        (a1+1)*(a2+1)*(a3+1).............. (am+1)   
where a1,a2,a3,...am are the digits in base p representaion (a1a2....am)base p 

Special case of this is the Odd numbers in nCk (i.e row of pascal triangle)


Link to problems:
1) http://www.spoj.com/problems/DUKKAR/
2) http://www.spoj.com/problems/HLP_RAMS/
3) http://www.spoj.com/problems/AJOB/

KALI LINUX : BACKTRACK REBORN

MOST ADVANCED PENETRATION DISTRIBUTIOON EVER!!!

Kali Linux is a Debian-derived Linux distribution designed for digital forensics and penetration testing. It is maintained and funded by Offensive Security Ltd. It was developed by Mati Aharoni and Devon Kearns of Offensive Security through the rewrite of BackTrack, their previous forensics Linux distribution.
Kali Linux is preinstalled with numerous penetration-testing programs, including nmap (a port scanner), Wireshark (apacket analyzer), John the Ripper (a password cracker), Aircracking (a software suite for penetration-testing wireless LANs), Burp suite and OWASP ZAP (both web application security scanners).

SPOJ PROBLEM 1029 : MATRIX SUMMATION (MATSUM)

Problem Link: http://www.spoj.com/problems/MATSUM/

Serously Hard to get an AC using segment tree!!

2-D Binary Indexed Tree/Fenwick Tree Problem
Just like 1-D BIT we have to go in both x as well as y co-ordinate axis

2-D BIT QUERIES FOR FENWICK TREE

update_query(x,y,MAX)
       while(x<=MAX)
       {
            ty = y;
           while(ty <= MAX)   //For each y of x
          {
              a[x][ty] += val;
              ty += (ty & -ty);
          }
          x += (x & -x);
      }

read_query(x,y) 
       sum=0;
       while(x!=0)
       {
          ty = y;
          while(ty!=0)
         {
            sum+=a[x][ty];
            ty-=(ty & -ty);
         }
        x-=(x & -x);
       }

To finally read queries:
          .  .   .  .  .  .  .  .  .  .  .
          .  .   (x1,y1). .  .  .  .  .  .
          .  .   .  .  .  .  .  .  .  .  .
          .  .   .  .  .  .  .(x2,y2) .  .

read_query(x2,y2)-read_query(x1-1,y2)-read_query(x2,y1-1)
+ read(x1-1,y1-1)  //same part subtracted twice 

Basic Exclusion and Inclusion Principle   

SHELL SCRIPT TO GREET YOU AS YOU LOG IN INTO THE SYSTEM :P

temph=`date | cut -c12-13`  //grep command could also be used
dat=`date +"%A %d in %B of %Y (%r)"`

if [ $temph -lt 12 ]
then
    mess="Good Morning $LOGNAME, Have nice day!"
fi

if [ $temph -gt 12 -a $temph -le 16 ]
then
    mess="Good Afternoon $LOGNAME"
fi

if [ $temph -gt 16 -a $temph -le 18 ]
then
    mess="Good Evening $LOGNAME"
fi

if which dialog > /dev/null                 //Parent Diectory
then
    dialog --backtitle "Linux"\
    --title "(-: Welcome to Linux :-)"\
    --infobox "\n$mess\nThis is $dat" 6 60
    echo -n "Press a key to continue. . ."
    read
    clear
else
    echo -e "$mess\nThis is $dat"
fi

SPOJ PROBLEM 6256 :INVERSION COUNT (INVCNT)

Problem link : http://www.spoj.com/problems/INVCNT/
 
Done it using Fenwick Tree !!!!

Took a time as well as resources to get through the logic...

Let array    A[5] =   2        3      8        6         1
                           
Let fenwick tree be F[maxvalue(a)=8]= 
0 0 0 0 0 0 0 0 0
So,
Inserting 2 in it ;  
0 1 0 0 0 0 0 0 0          count=0;
Inserting 3 in it ;
0 1 1 0 0 0 0 0 0          count=0;
Inserting 8 in it ;
0 1 1 0 0 0 0 0 1          count=0;
Inserting 6 in it ;
0 1 1 0 0 0 1 0 1          count=1;
Inserting 1 in it ;
1 1 1 0 0 0 1 0 1          count=1+4;

Basic logic is to get through that after inserting each number we have to count number of indexes marked with 1 after it ( That's what the problem says i<j  A[i]>A[j]  )
 Or Simply:
Sum of fenwick tree after number i.e. sum[num+1........MAX]

Don't forget to take tree size >=1e7  and total count of inversions as long long :P                                     

BEGINNING KERNEL PROGRAMMING.........

Prerequisites:
1.Linux System upgraded
2.Kernel installed in the system(Stable)
3.Could build cpp files (libncurses-dev package installed)

Basic Hello Kernel :

#include <linux/module.h> 
#include <linux/kernel.h>
#include <linux/init.h>
static int __init hello_init(void)
{
              printk(KERN_INFO "Hello, world 2\n");
              return 0;
}
static void __exit hello_exit(void)
{
               printk(KERN_INFO "Goodbye, world 2\n");
}
module_init(hello_init);
module_exit(hello_exit);


Make File:

obj−m += hello.o    //executable file which will be created after   making and loading kernel

all:
make −C /lib/modules/$(shell uname −r)/build M=$(PWD) modules
clean:
make −C /lib/modules/$(shell uname −r)/build M=$(PWD) clean


In the terminal ;  go to directory where modules are been generated
Then just write make
then write make install 
These commands just install down the kernel to bootloader of OS  :)

MAP STL BASED PROBLEMS

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

Cakewalk!!!

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

Nice Implementation of Map

SQUID PROXY SERVER INSTALLATION ( VIDEO CACHE SERVER ) 1....

Squid is a proxy server that caches Internet content closer to a requestor than its original point of origin. Squid supports caching of many different kinds of Web objects, including those accessed through HTTP and FTP. Caching frequently requested Web pages, media files and other content accelerates response time and reduces bandwidth congestion.

Especially to create in the Youtube video caching....
Prerequisites :=>  * System Requirements: 2 GB RAM ,1 TB HARDDISK
                   * 2 LAN Card
                   * Updated Linux System
  
STEP 1:    Create "fw.sh" in etc folder
           Change permissions to an executable file 
           Edit this file with script given below=>

.......................................................................................................................                

#!/bin/sh
# -----------------------------------------------------------

SQUID_SERVER="

192.168.2.1"

INTERNET="

eth1"

LAN_IN=&

amp;quot;eth0"

SQUID_PORT="

8080"


iptables -F
iptables -X
iptables -t nat -F
iptables -t nat -X
iptables -t mangle -F
iptables -t mangle -X
modprobe ip_conntrack
modprobe ip_conntrack_ftp
echo 1 &amp

;amp;amp;amp;amp;gt; /proc/sys/net/ipv4/ip_forward

iptables -P OUTPUT ACCEPT

iptables -A INPUT -i lo -j ACCEPT
iptables -A OUTPUT -o lo -j ACCEPT

iptables -A INPUT -i $INTERNET -m 

state --state ESTABLISHED,RELATED -j ACCEPT

iptables --table nat --append POSTROUTING

 --out-interface $INTERNET -j MASQUERADE
iptables --append FORWARD --in-interface $LAN_IN -j ACCEPT

iptables -A INPUT -i $LAN_IN -j ACCEPT
iptables -A OUTPUT -o $LAN_IN -j ACCEPT

iptables -t nat -A PREROUTING -i 

$LAN_IN -p tcp --dport 80 -j DNAT --to 

$SQUID_SERVER:$SQUID_PORT

iptables -t nat -A PREROUTING -i $INTERNET -p

 tcp --dport 80 -j REDIRECT --to-port $SQUID_PORT

iptables -A INPUT -j LOG

..........................................................................................................................

Make sure that connection  with internet has same name has  INTERNET in script and wlan connection as LAN_IN
Compile and execute the file

SPOJ PROBLEM 7757: Flowers Flourish From France MFLAR10

Problem Link: http://www.spoj.com/problems/MFLAR10/

Finally got one on tokenizing the string...

Used Strtok() function to tokenize the string..

And rest is simple :D

Just make first letters of each word either in uppercase or in lowercase and then just compare it out!!!

code :  http://pastebin.com/DGRC5WCU

HACKEREARTH JANUARY EASY CHALLENGE PROBLEM 4: LOVE FOR BINARY NUMBERS

24-Point Code : http://pastebin.com/CESvQA4E

Couldn't get through TLE!!

Net Resoucres:  http://discuss.codechef.com/questions/60505/the-hackerearth-january-easy-challenge

SPOJ PROBLEM 10575 : THE YELLOW BRICKS ROAD (YELBRICK)

Problem Link : http://www.spoj.com/problems/YELBRICK/

To minimize the number of cubes formed:

Vol of cube = (Vol of individual cuboids)/no of cubes 
It should be perfect cube...

Cubes could be formed when all sides of individual cuboids are divisble by same no. or the volume is perfect cube.

It could be thought of all sides of resultant cube must be equal(ofcourse)..

And we have to maximize the final volume(of all cubes) with minimum no of cubes . So , we must divide all sides by GCD( lowest no. which divides all the given nos. ) and then finally adding up the individual volumes..

Code: http://pastebin.com/UaScQUq8