Google Kickstart (previously APAC) 2017 Round A

Problem A
https://codejam.withgoogle.com/codejam/contest/8284486/dashboard#s=p0

Solution : http://ideone.com/lPWmS1

Approach : 

Let no, of dots be r rows and c columns. 

For side length=1  => No. of squares = (r-1)*(c-1)

For side length=2  => No. of squares=2*(r-2)*(c-2)

     Because all axis aligned can also be diagonally arranged atmost 1 way

For side length=3  => No. of squares=3*(r-3)*(c-3)

    Because all axis aligned can also be diagonally arranged atmost 2 way

      .

      .

      .

So on till side length=min(r,c)-1

Summing up all : we get 

          
S(n)=((r*(r-1))/2)^2-((r+c)*(r-1)*r*(2r-1))/6+(r*c*(r-1)*r)/2

      

     Modulo can be taken using modular inverse of 2 , 6 .

Problem B:
https://codejam.withgoogle.com/codejam/contest/dashboard?c=8284486#s=p1

Problem C:
https://codejam.withgoogle.com/codejam/contest/dashboard?c=8284486#s=p2

 

   

Interesting Segment Tree Problem

Link To Problem


Node Properties {

     no. of 4 in range (n_4)
     no. of 7 in range  (n_7)
     longest increasing subsequence length (n_i)
     longest decreasing subsequence length (n_d)

}


Node Updates {

   swap(n_4,n_7)
   swap(n_i,n_d)  
   // Due to the reason that i.e 44747  LIS = 4   LDS=2
       After Swap Operation      77474  LDS=2    LDS=4
}

Merge Node Updates{

     n4[parent]=n4[left]+n4[right]
     n7[parent]=n7[left]+n7[right]
     n_i=max(n_i+n7,n4+n_i,n_4+n_7)

}

Query{
   return n_i
}
    

GitHub : Setting Up and Connecting to Remote Directory

Github : Link To Dowload

1. Open the Git Shell (or Windows Powershell) 

2. Get into Directory you want to upload as your project
      ex.: C:/... or usr/...
3. CommandLine : git init
                  (intialize the git on directory)
                 git add . 
                  (add every item of your dir to server)
                 git commit -m "Your first message"
                  (commits the changes adopted) 
       
4. Create a new repository in github.com with all default settings.

5. At the top you'll see 'Quick Setup', make sure the 'HTTPS' button is selected and copy the address—this is the address of your repository on GitHub's servers.  

6. CommandLine : git remote add origin <URL FROM GITHUB>
                 
                 git push origin master


For Configuring Shell :
 git config --global user.name <YOUR USERNAME ON GITHUB>

For Proxy : 
 git config --global http.proxy http://proxyuser:proxypwd@proxy.server.com:8080




 

Theme Script for CodeBlocks Editor

Script file : Link

Step 1 :  Search For Application Data folder (for windows :                         C:\Users\gs\AppData\Roaming\CodeBlocks )
          AppData Folder may be hidden

Step 2 :  Open file "default.conf" and search for "<colour_sets>"

Step 3 :  Remove the part written in <colour_sets>...</colour_sets>
          and substitute the part written in it with part given in                 the link above.
          All These activities must be done with CodeBlocks IDE                     closed.

Step 4 :  Go to Editor Settings in IDE to set your custom theme.

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