Author Archives: Matrix.code

Git Hashes

Git sometimes does things like magic. But the magic it shows how it stores it information internally. Let’s discuss the fundamentals.

Okay, we have created an empty directory named git-internal and we initialised git in that directory. We can see the basic file structure inside .git folder which is the folder used by git to store all information.

Lets create a file main.go and modify so that after modification, the directory and content looks like this:

There is no change in .git directory so far. Let’s use git hash-object command to find out the SHA1 hash of main.go file using git hash-object main.go. git hash-object gives you the object id of a file, in our case main.go

Now, let’s add main.go file to git using git add main.go and see what has been changed in .git directory

If you notice then, you can see the SHA1 hash from the git hash-object main.go is used to denote a directory and a file. More specifically , first two character is used as a upper level directory, and the rest of 38 character is used to denote a file inside that directory. It’s a zlib compressed file which contains a header and the content of the file.

I suppose, this doesn’t answer clearly what is happening behind the curtain. So let’s dive into details.
In git, there is three kinds of objects

  • blobs
  • trees
  • commits

we have our main.go file. The process of generating the corresponding filename(in our case 99/fd8050e485c174e01c4e074041e41ae09bae59) and content of the file is as follows:

  • Git first constructs a header which starts by identifying the type of object — in this case, a blob. To that first part of the header, Git adds a space followed by the size in bytes of the content, and adding a final null byte
  • Git concatenates the header and the original content and then calculates the SHA-1 checksum of that new content. This SHA1 has is the same as git hash-object main.go output

Now that we know, how the SHA1 hash and the file name corresponding to that file is created. The content of that file is the zlib compressed version of value stored in store variable. To verify that, I have written a piece of code, that opens the file, decompresses using zlib format, and displays into terminal

Now this point, it should be clear that only the content of the file matters, the name or file permission doesn’t matter to this point at all. The file is just a zlib compressed data(header + file content). To prove this point, see the following picture:

Okay, now let’s create a commit and see what’s the status ? So, we run git commit -m "first commit" and let’s see what is changed in the object directory

Now, we see two new file created on this directory. So, we know 99/fd8050e485c174e01c4e074041e41ae09bae59 is correspond to the file main.go then what are the other files. To find out what is the type of object we can use git cat-file command. (Provide content or type and size information for repository objects)

So, we can see the other two types of objects in git. The tree type objects, basically holds the information

  • File permission
  • type of objects is has inside(blob/tree)
  • hash of the objects
  • name of the blob/tree(this is where, git knows about the existance of a file)

To generate the hash of the tree(b52e25f217248e21dec163465bd111bb6f723f0e)

We can see the format of the file, and how we generate these values.

For commit objects, we can see the same picture. Lets run this same thing for commit object file

Here we can see, the commit file 36/29dca9fc3a11108fcd229c8ed082ffa8761192 contains a header commit 197 and then information about tree, author, commiter, timestamp and commit message in zlib format.

The process to generate 40 byte hash and generate file content is exactly same, just the header and what information is included is different. 
store =  \0
Hash = SHA1(store)
file_name = Hash[0:2]/Hash[2:]
file_content = zlib_compressed(store)

Aside

Everyday Git

Git is the most popular version control system in modern tech world. The usage of version control system is to somehow manage all the versions of your work. Before going to the using of git, lets learn different version control system

  • Local version control: Limited to one computer, Store the difference between two versions in the disk in a special format. You can get any versioned file by adding the patch (Example: RCS)
  • Centralised version control: Many user, but only one server that contains the versioned file. Backwards is, single point of failure. If the server goes down, nobody can collaborate. If the file system crashes/ get corrupted and proper backup is not kept, then all the history loses except the snapshots stored in the users machine (Ex: CVS, Subversion, Perforce)
  • Distributed version control: Client check out recent version of files as well as all the history of the repository. These client copy is actually identical to the copy stored in the server. ( Git, Mercurial)

Git Philosophy :

  • Snapshots, Not difference: CVS, Subversion and other version control system stores a list of files, and the difference in each file for each version. Instead, Git thinks of its data more like a series of snapshots of a miniature filesystem. With Git, every time you commit, Git basically takes a picture of what all your files look like at that moment and stores a reference to that snapshot. To be efficient, if files have not changed, Git doesn’t store the file again, just a link to the previous identical file it has already stored.
Credit: Pro Git
  • Nearly every operation is local: As local machine is perfect replica of the git remote server, you can almost do many things when you are off network or out of VPN.
  • Data integrity: Everything is checksummed. Git preserve integrity by checking this sum. It uses SHA-1 hash to maintain and changes in file system.
  • Data Safety: If you commit something in git, it is very much impossible to lose that piece of data.
  • Three states: Modified, Staged, Commited

DP Recipe

  • Changing Parameter

    • Make the value of DP a new parameter and make one of the existing parameters the value of DP

    Problem: Brand New Problem
    Discussion: The official editorial describes the technique very well. Go through the official editorial here
    For Implementation see this.

    TLE Solution 
    /*
 * DATE : 2017-05-30
 * Algo : dp
*/
#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define Long                    long long
#define Ulong                   unsigned long long
#define FOR(I,A,B)              for(long long I = (A); I < (B) ; ++ I)
#define REP(i,n)                for( long long i=0 ; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define F                       first
#define S                       second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define in(x)                   input(x)
#define in2(x,y)                input(x), input(y)
#define in3(x,y,z)              input(x), input(y),input(z)
#define ins(x)                  scanf("%s",x)
#define ind(x)                  scanf("%lf",&x)
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
#define IO                      ios_base::sync_with_stdio(0);cin.tie(0)
#define READ                    freopen("/Users/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE                   freopen("/Users/matrixcode/Desktop/out.txt","w",stdout)

template<class T > void input(T &x){
    char c = getchar();x = 0;
    for(;(c<48 || c>57);c = getchar());
    for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}
}
inline long long bigmod(long long p,long long e,long long M){
    long long ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/***************************** END OF TEMPLATE *******************************/

const int N = 6e5+5;
char str[N];
int n,m;
int id = 0;
map<string,int> Map;
int getId(string s)
{
    if(Map.count(s)) return Map[s];
    return Map[s] = id++;
}
vector<int> num;
vector<int> v[11];

int dp[2][1<<15];

int pre[1<<15][15];
int calc(int idx)
{
    memset(dp,63,sizeof dp);
    dp[0][(1<<n)-1]=0;
    int nv= 0;
    for(int i=v[idx].size()-1;i>=0;i--){
        nv = nv ^1;
        int now = v[idx][i];
        for(int mask=0;mask < 1<<n; mask ++ ){
            dp[nv][mask] = dp[nv^1][mask];
            if(now < n && (mask & (1<< now)) == 0 ) {
                int cnt = pre[mask][now];
                dp[nv][mask] = min(dp[nv][mask], cnt + dp[nv^1][mask | (1<<now)]);
            }
        }
        //for(int j=0 ;j < 1<<n; j++) printf("dp[%d][%d] = %d\n",i,j,dp[nv][j]);
    }
    return dp[nv][0];
}
int main()
{

    in(n);
    for(int i=0;i<1<<n;i++){
        int cnt=0;
        for(int j=n-1;j>=0;j--){
            pre[i][j] = cnt;
            if(i&(1<<j)) cnt++;
        }
    }
    for(int i=0;i<n;i++){
        scanf("%s",str);
        num.push_back(getId(str));
    }
    in(m);
    for(int i=0;i<m;i++){
        int k;
        in(k);
        for(int j=0;j<k;j++){
            scanf("%s",str);
            v[i].push_back(getId(str));
        }
    }

    int sum = 1<<20;
    int id = -1;
    for(int i=0;i<m;i++){
        int v = calc(i);
        if(v < sum ) {
            sum = v;
            id = i;
        }
    }
    if(id==-1) printf("Brand new problem!\n");
    else {
        cout << id + 1<<endl;
        int p = n*(n-1)/2 - sum + 1;
        printf("[:");
        REP(i,p) printf("|");
        printf(":]\n");
    }
    return 0;
}
    Accepted Solution 
    /*
 * DATE : 2017-05-30
 * Algo : dp
*/
#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define Long                    long long
#define Ulong                   unsigned long long
#define FOR(I,A,B)              for(long long I = (A); I < (B) ; ++ I)
#define REP(i,n)                for( long long i=0 ; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define F                       first
#define S                       second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define in(x)                   input(x)
#define in2(x,y)                input(x), input(y)
#define in3(x,y,z)              input(x), input(y),input(z)
#define ins(x)                  scanf("%s",x)
#define ind(x)                  scanf("%lf",&x)
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
#define IO                      ios_base::sync_with_stdio(0);cin.tie(0)
#define READ                    freopen("/Users/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE                   freopen("/Users/matrixcode/Desktop/out.txt","w",stdout)

template<class T > void input(T &x){
    char c = getchar();x = 0;
    for(;(c<48 || c>57);c = getchar());
    for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}
}
inline long long bigmod(long long p,long long e,long long M){
    long long ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/***************************** END OF TEMPLATE *******************************/

const int N = 6e5+5;
char str[N];
int n,m;
int id = 0;
map<string,int> Map;
int getId(string s)
{
    if(Map.count(s)) return Map[s];
    return Map[s] = id++;
}
vector<int> num;
vector<int> v[11];

int pre[1<<15][15];
int Next[N][15];

int last[15];
int dp[1<<15][225];
int calc(int id)
{
    for(int i=0;i<n;i++) last[i]=1<<20;
    for(int i=int(v[id].size())-1;i>=0;i--){
        if(v[id][i]<n) last[v[id][i]] = i;
        for(int j=0;j<n;j++) Next[i][j] = last[j];
    }
    for(int i= 0;i <= n*(n-1)/2; i++ ) dp[0][i] = 1<<20;
    dp[0][0]=0;
    for(int i=1;i<1<<n;i++) {
        for(int j=0;j<=n*(n-1)/2;j++) {
            dp[i][j] = 1<<20;
            for(int k = 0;k < n ; k ++ ) {
                if(i&1<<k){
                    int added = pre[i][k];
                    int inv = j-added;
                    if(inv < 0) continue;
                    int pos = dp[i^(1<<k)][inv];
                    if(pos >= v[id].size()) continue;
                    int t = Next[pos][k];

                    dp[i][j] = min(dp[i][j], t+1);
                }
            }
        }
        //for(int j=0;j<=n*(n-1)/2;j++) printf("dp[%d][%d]= %d\n",i,j,dp[i][j]);
    }
    for(int i=0;i<=n*(n-1)/2;i++) {
        if(dp[(1<<n)-1][i] <= v[id].size()) return i;
    }
    return 1<<20;
}
int main()
{

    in(n);
    for(int i=0;i<1<<n;i++){
        int cnt=0;
        for(int j=n-1;j>=0;j--){
            pre[i][j] = cnt;
            if(i&(1<<j)) cnt++;
        }
    }
    for(int i=0;i<n;i++){
        scanf("%s",str);
        num.push_back(getId(str));
    }
    in(m);
    for(int i=0;i<m;i++){
        int k;
        in(k);
        for(int j=0;j<k;j++){
            scanf("%s",str);
            v[i].push_back(getId(str));
        }
    }
    int sum = 1<<20;
    int id = -1;
    for(int i=0;i<m;i++){
        int v = calc(i);
        if(v < sum ) {
            sum = v;
            id = i;
        }
    }
    if(id==-1) printf("Brand new problem!\n");
    else {
        cout << id + 1<<endl;
        int p = n*(n-1)/2 - sum + 1;
        printf("[:");
        REP(i,p) printf("|");
        printf(":]\n");
    }
    return 0;
}

    Something New Learned

    Data Structure:
    Problem Link: QCHEF
    My Solution:

     

    Click to See Code 
    //
//  main.cpp
//  QCHEF
//
//  Created by Matrix.code on 3/14/17.
//  Copyright © 2017 Matrix.code. All rights reserved.
//

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

#define Long                    long long
#define Ulong                   unsigned long long
#define FOR(I,A,B)              for(int I = (A); I < (B) ; ++ I)
#define REP(i,n)                for( int i=0 ; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define F                       first
#define S                       second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define in(x)                   input(x)
#define in2(x,y)                input(x), input(y)
#define in3(x,y,z)              input(x), input(y),input(z)
#define ins(x)                  scanf("%s",x)
#define ind(x)                  scanf("%lf",&x)
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
#define IO                      ios_base::sync_with_stdio(0);cin.tie(0)
#define READ                    freopen("/Users/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE                   freopen("/Users/matrixcode/Desktop/out.txt","w",stdout)

template<class T > void input(T &x){
   char c = getchar();x = 0;
   for(;(c<48 || c>57);c = getchar());
   for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;} } inline long long bigmod(long long p,long long e,long long M){    long long ret = 1;    for(; e > 0; e >>= 1){
      if(e & 1) ret = (ret * p) % M;
      p = (p * p) % M;
   } return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/***************************** END OF TEMPLATE *******************************/

const int N = 1e5+5;
const int RootN = 350;
int n,m,q;
int a[N];
int Beg[RootN] , End[RootN], Id[N] , dp[RootN][N], dp2[RootN][N];
int block;
int main()
{
   in3(n,m,q);
   REP(i,n) in(a[i]);
   block = 2*sqrt(n)+1;
   REP(i,n) {
      Id[i] = i/block;
      if(i%block==0){
         Beg[i/block] = i;
         End[i/block] = min(n-1, (Id[i]+1)*block-1);
      }
   }

   for(int i = 0;i <= Id[n-1] ; i++ ) {
      int Map[N]; ms(Map,-1);
      int iM = 0;
      for(int j = Beg[i] ; j < n ;j ++ ) {          if(Map[a[j]]>=0) {
            iM = max(iM, j - Map[a[j]] );
         } else Map[a[j]] = j;
         dp[i][j] = iM;
      }
   }

   for(int i=0;i<=Id[n-1]; i++ ){       int Map[N]; ms(Map,-1);       int iM = 0;       for(int j= End[i];  j>= 0; j--) {
         if(Map[a[j]]>=0) {
            iM = max(iM,  Map[a[j]] - j );
         } else Map[a[j]] = j;
         dp2[i][j] = iM;
      }
   }

   int x,y;

   int Map[N]; ms(Map,-1);
   while(q--) {
      in2(x,y); x--,y--;
      if(Id[x]== Id[y]) {
         int ans = 0;
         for(int i= x;i <=y;i++) {             if(Map[a[i]]>=0) {
               ans = max(ans, i - Map[a[i]] );
            }
            else Map[a[i]] = i;
         }
         for(int i=x;i<=y;i++){
            Map[a[i]] = -1;
         }
         printf("%d\n",ans);
      }
      else {
         int L = (x== Beg[Id[x]]) ? Id[x] : Id[x]+1;
         int R = (y== End[Id[y]]) ? Id[y] : Id[y]-1;
         int ans = 0;
         if(Beg[L] <= y) ans = max(ans, dp[L][y]);
         if(x <= End[R]) ans = max(ans, dp2[R][x]);

         vector<pair<int,int> > v;
         for(int i=x;i<Beg[L];i++)v.push_back(mp(a[i],i));
         for(int i=End[R]+1;i<=y;i++)v.push_back(mp(a[i],i));                        for(auto a: v) {             if(Map[a.F] >= 0) {
               ans = max(ans, a.S - Map[a.F]);
            }else Map[a.F] = a.S;
         }
         for(auto a: v) {
            Map[a.F] = -1;
         }
         printf("%d\n",ans);
      }
   }

   return 0;
}

     
    Problem Link: CUBTOWER

    My Solution:

    Click to See Code 
    //
//  main.cpp
//  CUBTOWER
//
//  Created by Matrix.code on 3/15/17.
//  Copyright © 2017 Matrix.code. All rights reserved.
//

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

#define Long                    long long
#define Ulong                   unsigned long long
#define FOR(I,A,B)              for(int I = (A); I < (B) ; ++ I)
#define REP(i,n)                for( int i=0 ; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define F                       first
#define S                       second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define in(x)                   input(x)
#define in2(x,y)                input(x), input(y)
#define in3(x,y,z)              input(x), input(y),input(z)
#define ins(x)                  scanf("%s",x)
#define ind(x)                  scanf("%lf",&x)
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
#define IO                      ios_base::sync_with_stdio(0);cin.tie(0)
#define READ                    freopen("/Users/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE                   freopen("/Users/matrixcode/Desktop/out.txt","w",stdout)

template<class T > void input(T &x){
   char c = getchar();x = 0;
   for(;(c<48 || c>57);c = getchar());
   for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}
}
inline long long bigmod(long long p,long long e,long long M){
   long long ret = 1;
   for(; e > 0; e >>= 1){
      if(e & 1) ret = (ret * p) % M;
      p = (p * p) % M;
   } return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/***************************** END OF TEMPLATE *******************************/

const int N = 2e5+5;
const int RootN= 350;
struct Event{
   int type;
   int l,r;
   int Time;
};

vector<Event> e[N];
int n,m,q;
long long BASE = 37 , mod = 1e9+7;
long long H(char s[])
{
   long long h =0;
   for(int i=0;s[i];i++) {
      h = (BASE * h + s[i]-'a' + 1 ) % mod;
   }
   return h;
}

long long value[N];
char str[N];
int len[N];
unordered_map<long long,int> Map;
vector<long long> NString[N];
int uniqueLen[N];
int TLen;
long long POW[N];
void append( int idx, char c)
{
   int v = c-'a' + 1;
   long long pre = NString[idx].size() ? NString[idx].back() : 0;
   NString[idx].push_back((v + BASE* pre ) % mod);
   int ptr = (int) NString[idx].size()-1;
   for(int i=0;i < TLen ;i ++) {
      int l = uniqueLen[i];
      if(l > ptr + 1) break;
      long long o = ((NString[idx][ptr] - POW[l] * (ptr - l>=0 ? NString[idx][ptr-l] : 0)) % mod + mod ) % mod;
      if(Map.count(o) && len[Map[o]] == l ) {
         e[Map[o]].push_back({0,idx,-1,-1});
      }
   }
}


int block;
int Beg[RootN] ,End[RootN], Sum1[RootN] , Sum2[RootN], id[N];
int Arr1[N] , Arr2[N];
long long Ans[N];


void update(int idx)
{
   Arr1[idx] ++;
   Sum1[id[idx]] ++;
   if(Arr2[idx] == 0) Arr2[idx]=1 , Sum2[id[idx]] ++;
}

long long Q1(int x,int y)
{
   long long ans = 0;
   if(id[x]==id[y]) {
      for(int i=x;i<=y;i++) {
         ans+= Arr1[i];
      }
      return ans;
   }
   int L = (x==Beg[id[x]]) ? id[x] : id[x]+1;
   int R = (x==End[id[y]]) ? id[y] : id[y]-1;
   
   for(int i=x;i<Beg[L];i++) ans += Arr1[i];
   for(int i=y;i>End[R];i--) ans += Arr1[i];
   for(int i=L;i<=R;i++) ans += Sum1[i];
   return ans;
   
   
}

long long Q2(int x,int y)
{
   
   long long ans = 0;
   if(id[x]==id[y]) {
      for(int i=x;i<=y;i++) {
         ans+= Arr2[i];
      }
      return ans;
   }
   
   int L = (x==Beg[id[x]]) ? id[x] : id[x]+1;
   int R = (x==End[id[y]]) ? id[y] : id[y]-1;
   
   for(int i=x;i<Beg[L];i++) ans += Arr2[i];
   for(int i=y;i>End[R];i--) ans += Arr2[i];
   for(int i=L;i<=R;i++) ans += Sum2[i];
   return ans;
}
void Process(int idx)
{
   for(auto a: e[idx]) {
      if(a.type == 0)  {
         update(a.l);
      }
      else if(a.type == 1) {
         Ans[a.Time] = Q2(a.l,a.r);
      }
      else if(a.type == 2) {
         Ans[a.Time] = Q1(a.l,a.r);
      }
   }
   for(int i=0;i<RootN;i++) Sum1[i] = Sum2[i] =0;
   for(auto a: e[idx]) {
      if(a.type == 0) {
         Arr1[a.l]=0;
         Arr2[a.l]=0;
      }
   }
}
int main()
{
   in3(n,m,q);
   POW[0]=1;
   for(int i=1;i < N;i ++) {
      POW[i] = (POW[i-1] * BASE ) % mod;
   }
   block = sqrt(n)+1;
   for(int i=0;i<n;i++){
      id[i] = i/block;
      if(i%block==0){
         Beg[id[i]] = i;
         End[id[i]] = min(n-1, (id[i] + 1) * block - 1) ;
      }
   }
   
   
   for(int i=0;i<m;i++){
      scanf("%s",str);
      reverse(str,str+strlen(str));
      value[i] = H(str);
      len[i] = strlen(str);
      Map[value[i]] = i;
      uniqueLen[i] = len[i];
   }
   sort(uniqueLen, uniqueLen + m);
   TLen = unique(uniqueLen, uniqueLen + m) - uniqueLen;
   
   
   int t,l,r,p;
   char ch;
   for(int i=0;i<q;i++) {
      scanf("%d",&t);
      if(t==0) {
         scanf("%d %c",&l,&ch);
         l--;
         append(l,ch);
      }
      else if(t==1) {
         scanf("%d %d %d",&l,&r,&p);
         l--,r--,p--;
         e[p].push_back({1,l,r,i});
      }
      else if(t==2) {
         scanf("%d %d %d",&l,&r,&p);
         l--,r--,p--;
         e[p].push_back({2,l,r,i});
      }
   }

   ms(Ans,-1);
   for(int i=0;i<m;i++) {
      Process(i);
   }
   for(int i= 0;i < q;i ++) if(Ans[i] >= 0)printf("%lld\n",Ans[i]);
   return 0;
}

    Uva Volume 1000-1099

    1000 – Airport Configuration

    1000 – Airport Configuration

    Discussion:

    Adhoc. Just Calculate cost for each configuration in O(n*n). Then sort and print the result. Beware of printing. There is only a space between “Configuration” and “Load”.

    Click to See Code 
    #include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define Long                    long long
#define Ulong                   unsigned long long
#define FOR(I,A,B)              for(int I = (A); I < (B) ; ++ I)
#define REP(i,n)                for( int i=0 ; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define F                       first
#define S                       second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define Si(x)                   scanf("%d",&x);
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
#define IO                      ios_base::sync_with_stdio(0);cin.tie(0)
#define READ                    freopen("/Users/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE                   freopen("/Users/matrixcode/Desktop/out.txt","w",stdout)

inline long long bigmod(long long p,long long e,long long M){
   long long ret = 1;
   for(; e > 0; e >>= 1){
      if(e & 1) ret = (ret * p) % M;
      p = (p * p) % M;
   } return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/***************************** END OF TEMPLATE *******************************/

const int N = 1001;
int A[30][30];
int a[30],b[30];
bool cmp(pair<int,int> a, pair<int,int> b)
{
   if(a.S==b.S)return a.F<b.F;
   return a.S<b.S;
}
int main()
{
   int n,p,v,d,k,con;
   while(scanf("%d",&n)==1 &&n) {
      memset(A,0,sizeof A);
      for(int i=1;i<=n;i++){
         scanf("%d %d",&p,&k);
         for(int j=0;j<k;j++){
            scanf("%d %d",&d,&v);
            A[p][d] = v;
         }
      }
      vector<pair<int,int> > v;
      while(scanf("%d",&con)==1 && con) {
         for(int i=1;i<=n;i++) { scanf("%d",&p);a[p] = i;}
         for(int i=1;i<=n;i++) { scanf("%d",&p);b[p] = i;}
         int ans = 0;
         for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) {
               int x = abs(a[i]-b[j]),y=1;
               ans += (x+1)*A[i][j];
            }
         }
         v.push_back(mp(con,ans));
      }
      sort(all(v),cmp);
      printf("Configuration Load\n");
      for(int i=0;i < v.size();i++) {
         printf("%5d         %d\n",v[i].F, v[i].S);
      }
   }
}
/*
3
1 2 2 10 3 15
2 1 3 10
3 2 1 12 2 20
100
1 2 3
2 3 1
2
2 3 1
3 2 1
0
2
1 1 2 100
2 1 1 200
1
1 2
1 2
2
1 2
2 1
0
0
*/

    1001 – Say Cheese

    1001 – Say Cheese

    Discussion:

    Think two terminal points as sphere of radius 0. Then we have some sphere, Our goal is to reach a sphere to another with minimal cost. Sounds like Dijkastra Algorithm.
    What are the edges?
    We can go each sphere to other. So we have edges connecting each to others. And the cost? You can figure it out.

    Click to See Code 
    #include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define Long                    long long
#define Ulong                   unsigned long long
#define FOR(I,A,B)              for(int I = (A); I < (B) ; ++ I)
#define REP(i,n)                for( int i=0 ; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define F                       first
#define S                       second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define Si(x)                   scanf("%d",&x);
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
#define IO                      ios_base::sync_with_stdio(0);cin.tie(0)
#define READ                    freopen("/Users/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE                   freopen("/Users/matrixcode/Desktop/out.txt","w",stdout)

inline long long bigmod(long long p,long long e,long long M){
   long long ret = 1;
   for(; e > 0; e >>= 1){
      if(e & 1) ret = (ret * p) % M;
      p = (p * p) % M;
   } return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/***************************** END OF TEMPLATE *******************************/

const int N = 105;
int x[N],y[N],z[N],r[N];
double dist[N];

double calc(int i,int j) // cost to go from i to j
{
   return max(0.0, sqrt((x[i]-x[j]) * (x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j]) + (z[i]-z[j]) * (z[i]-z[j])) - r[i] - r[j]);
}
double dij(int s,int d,int n)
{
   set<pair<double,int> > pq;
   pq.insert(mp(0,s));
   for(int i=0;i<N;i++) dist[i]=1e9;
   dist[s] = 0;
   while(pq.size()){
      auto u = *pq.begin(); pq.erase(u);
      if(u.S==d) {
         return u.F;
      }
      for(int i = 0;i < n; i ++) {
         if(dist[i] > dist[u.S] + calc(u.S,i)) {
            dist[i]  = dist[u.S] + calc(u.S,i);
            pq.insert(mp(dist[i],i));
         }
      }
   }
   return 0;
}
int main()
{
   int n,cs=0;
   while(scanf("%d",&n)==1) {
      if(n==-1)break;
      for(int i=0;i<n;i++){
         scanf("%d %d %d %d",&x[i],&y[i],&z[i],&r[i]);
      }
      scanf("%d %d %d",&x[n],&y[n],&z[n]);
      scanf("%d %d %d",&x[n+1],&y[n+1],&z[n+1]);
      r[n]= r[n+1]=0;
      printf("Cheese %d: Travel time = %d sec\n",++cs,(int)(dij(n,n+1,n+2)* 10 + .5) );
   }
   
}
/*
1
20 20 20 1
0 0 0
0 0 10
1
5 0 0 4
0 0 0
10 0 0
-1
*/

    Number Theory for Competitive Programming

    For contest programmers, Math problems are common. So, It is going to be a long post. and will updated now and then. I will try to cover as many idea as possible in this tutorial.

    GCD,LCM,EUCLID

    g = gcd(a,b) = Meaning the greatest Common divisor of a and b.Highest number which divides both a and b.
    l = lcm(a,b) = Meaning the least common multiple.
    Properties:

  • gcd(a/g,b/g)=1. This property is used to reduce fraction such that numerator and denominator has no common divisor.
  • gcd is assosiative, gcd(a,b,c) = gcd(a,gcd(b,c)) = gcd(b,gcd(a,c)) = .. for all possible combination.
  • gcd(a,b)*lcm(a,b) = a*b. This is used to calculate lcm.
  • If a = p_1^{a1}*p_2^{a2}*.... p_r^{ar} and b = p_1^{b1}*p_2^{b2}*.... p_r^{br} then gcd(a,b) = p_1^{min(a1,b1)}*p_2^{min(a2,b2)}*.... p_r^{min(ar,br)}

    • Euclid Algorithm for finding gcd(a,b) : O(log(min(a,b)) 

    
int gcd(int a,int b)
{
	if(b==0)return 1;
	return gcd(b,a%b);
}

int lcm(long long a,long long b) 
{
	return a/gcd(a,b)*g;
}

    Bézout's identity: If gcd(a,b)=g, then, we can certainly find two integer x,and y such that a*x+b*y=g.

    This is called extended euclid algorithm. Now to find this x and y, we need to trace back the process of finding gcd.

    int extended_euclid(int a, int b, int &x, int &y) {
	int xx = y = 0;
	int yy = x = 1;
	while (b) {
		int q = a / b;
		int t = b; b = a%b; a = t;
		t = xx; xx = x - q*xx; x = t;
		t = yy; yy = y - q*yy; y = t;
	}
	return a;
}

    Modular Inverse: Given a and n, compute x such that a*x = 1 (mod n).

    // Return -1, if no solution.
int mod_inverse(int a, int n) {
	int x, y;
	int g = extended_euclid(a, n, x, y);
	if (g > 1) return -1;
	return mod(x, n);
}

    Linear Diophantine Equation Solution: Given, a*x+b*y=c. Find valid x and y if possible.

    bool linear_diophantine (int a, int b, int c, int & x0, int & y0, int & g) {
	g = extended_euclid (abs(a), abs(b), x0, y0);
	if (c % g != 0)
		return false;
	x0 *= c / g;
	y0 *= c / g;
	if (a < 0)   x0 *= -1;
	if (b < 0)   y0 *= -1;
	return true;
}

    Now is the values of x and y are unique? No. 

    for each integer k,
x1 = x + k * b/g
y1 = y - k * a/g
is a solution to the equation where g = gcd(a,b).

    Now How many solution where x in range[x1,x2] and y in range[y1,y2] ?

    void shift_solution (int & x, int & y, int a, int b, int cnt) {
	x += cnt * b;
	y -= cnt * a;
}
int find_all_solutions(int a,int b,int c,int &minx,int &maxx,int &miny,int &maxy)
{
	int x,y,g;
	if(linear_diophantine(a,b,c,x,y,g) == 0) return 0;
	a/=g, b/=g;
	int sign_a = a>0 ? +1 : -1;
	int sign_b = b>0 ? +1 : -1;

	shift_solution (x, y, a, b, (minx - x) / b);
	if (x < minx)
		shift_solution (x, y, a, b, sign_b);
	if (x > maxx)
		return 0;
	int lx1 = x;
 
	shift_solution (x, y, a, b, (maxx - x) / b);
	if (x > maxx)
		shift_solution (x, y, a, b, -sign_b);
	int rx1 = x;
 
	shift_solution (x, y, a, b, - (miny - y) / a);
	if (y < miny)
		shift_solution (x, y, a, b, -sign_a);
	if (y > maxy)
		return 0;
	int lx2 = x;
 
	shift_solution (x, y, a, b, - (maxy - y) / a);
	if (y > maxy)
		shift_solution (x, y, a, b, sign_a);
	int rx2 = x;
 
	if (lx2 > rx2)
		swap (lx2, rx2);
	int lx = max (lx1, lx2);
	int rx = min (rx1, rx2);
 
	return (rx - lx) / abs(b) + 1;
}

    For Futhre Reading About this:
    1.http://e-maxx.ru/algo/euclid_algorithm
    2. http://e-maxx.ru/algo/extended_euclid_algorithm
    3. http://e-maxx.ru/algo/diofant_2_equation
    4. http://e-maxx.ru/algo/diofant_1_equation
    5. http://discuss.codechef.com/questions/20842/a-tutorial-on-the-extended-euclids-algorithm

    Problems to solve:

    Euler’s totient function

    In number theory, \phi(n) denotes the number of integers <=n which is relatively prime to n. Two numbers a and b are called relatively prime, if gcd(a,b) = 1. here gcd denotes greatest common divisor.
    For example: n = 9, there are the six numbers 1, 2, 4, 5, 7 and 8.They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, because gcd(9, 3) = gcd(9, 6) = 3 and gcd(9, 9) = 9. Therefore, φ(9) = 6.

    Properties:

    1. Euler’s totient function is a multiplicative function, meaning that if two numbers m and n are relatively prime, then \phi(mn) = \phi(m)\phi(n)
    2. \phi(p^k) = p^k-p^{k-1}
    Proof: since p is a prime number the only possible values of gcd(p^k, m) are 1, p, p^2, ..., p^k, and the only way for gcd(p^k, m) to not equal 1 is for m to be a multiple of p. The multiples of p that are less than or equal to p^k are p, 2p, 3p, ...,p^{k-1}p = p^k and there are p^{k-1} of them. Therefore, the other p^k - p^{k-1} numbers are all relatively prime to p^k.
    3. From Wiki.
    1

    Now Using these formula,
    36 = 2^2 * 3^2.
    \phi(36) = 36*(1-\frac{1}{2})*(1-\frac{1}{3}) = 12

    Problem Using Phi Function

    And many more will be added….

    System of difference constraints

    Problem Description


    Given Some inequality on some variable (Xi , Xj , …. ) in form
    Xj – Xi <= W
    We need to determine whether we can assign values to variables so that all the given inequality is satisfiable or not ? If satisfiable, then output A solution.

    This System is called System of difference constraints. This is a special case of linear programming and yet very much useful.

    Solution

    Believe it or not, This problem has an elegant solution using Shortest Path algorithm.
    To understand Please go through this :
    1. lec18
    2. Introduction To Algorithm (3rd Edition) : 24.4 Section

    So I am writing the results (no proof). Proofs are discussed in details in the suggested readings.

    Constraint Graph


    – For each variable we create a vertex.
    – For each in-equality, Xj – Xi <= W , We give an edge (Vi,Vj) with cost W
    haha
    – Create a source vertex (S) and give an edge (S,Vi) with cost = 0 ( Without using source vertex,we can solve)

    Example:
    Finding values for the unknowns x1,x2,x3,x4,x5, satisfying the following 8 difference constraints
    example

    Constraint Graph with Solutions:
    bel

    Unsatisfiable constraints


    Theorem. If the constraint graph contains a negative-weight cycle, then the system of differences is unsatisfiable.
    Proof is given in the pdf file.

    Now we know if there is a solution or not.

    Determining a Possible Solution :


    – If there is no negative cycle in the constraint graph, Then There is a solution for the system. One of the solution is
    for each variable (Xi):
    Xi = Shortest Path distance of Vi from the Source vertex in Constraint Graph.
    What about other solutions???
    Let x = {x1,x2,…, xn } be a solution to a system of difference con- straints, and let d be any constant. Then x + d = { x1 + d, x2 + d, . . . , xn + d } is a solution as well.

    Shortest Path can be calculated from Bellman-Ford algorithm.
    Other Results from The constraint Graph:
    # Bellman-Ford maximizes x1 + x2 + …. + xn subject to the constraints xj – xi ≤ wij and xi ≤ 0
    # Bellman-Ford also minimizes maximum{xi} – minimum {xi}

    Practise Problem:
    1. Uva 11478

    Solution:
    For each node v in the given graph, Create a variable D_v such that we have operated Halum (v,D_v ) on the vertex v.
    We then Binary Search on the answer.
    Let Ans = X. We need to determine is X can possibly be our answer.
    for each edge (u,v) , We get,
    D_u - D_v + cost of the edge >= X
    => D_v - D_u <= cost - X

    This is just difference constraint discussed above. We can check whether we can satisfy all these conditions.

    Lastly output the maximal answer.

    Click to See Code 
    
#include <bits/stdc++.h>
using namespace std;

struct Edge{
    int u,v,w;
};
vector<Edge>edge;
int n,e,u,v,w;
vector<pair<int,int > >G[505];

int d[505];
bool inq[505];
int Times[505];


bool spfa()
{
    queue<int>q;   // I have omitted Source vertex by pushing all the variables in queue with distance = 0
    for(int i = 1;i <= n; i ++ ) {
        d[i]= 0;
        q.push(i);
        inq[i] = 1;
        Times[i] = 1;
    }
    
    while(!q.empty()){
        int u = q.front(); q.pop();
        inq[u] = 0;
        for(int i = 0; i < G[u].size(); i ++ ) {
            int v = G[u][i].first, w = G[u][i].second;
            if(d[v] > d[u] + w) {
                d[v] = d[u]  + w;
                if(inq[v] == 0) {
                    inq[v] = 1;
                    q.push(v);
                    Times[v] ++;
                    
                    if(Times[v] > n+2 ) return 0;
                }
                
            }
        }
    }
    return 1;
}
bool can(int Mid)
{
    for(int i = 0; i <= n; i ++ ) {
        G[i].clear();
    }
    
    for(int i = 0; i < e; i ++ ) {
        u = edge[i].u, v = edge[i].v  , w = edge[i].w ;
        G[u].push_back(make_pair(v,w - Mid));
    }
    
    return spfa();
}
int main()
{
    while(scanf("%d %d",&n,&e)==2) {
        edge.clear();
        for(int i = 0; i < e; i ++ ) {
            scanf("%d %d %d",&u,&v,&w);
            edge.push_back({u,v,w});
        }
        if(can(10001)) {
            printf("Infinite\n");
            continue;
        }
        int low = 1, high = 10000, mid, ans = -1;
        while(low <= high ) {
            mid = (low+high) /2;
            if(can(mid)) {
                ans = mid;
                low  = mid+1;
            }
            else high= mid-1;
        }
        if(ans == -1 ) printf("No Solution\n");
        else printf("%d\n",ans);
        edge.clear();
    }
}

    2. Uva 515 – King
    3. POJ – 1201
    4. POJ – 2983
    5. POJ 1275
    6. POJ – 3159
    7. POJ – 3169

    Dynamic Programming Problems

    Problem 1 : CHEIFEFT
    Idea:
    From Codechef blog:

    Let, dp[i][j] = expected maximal discount that we can obtain if we consider only first ‘i’ items and first ‘j’ discounts.

    Consider the following two cases:

    1) i-th item is chosen

    We apply j-th discount to i-th item and get discount price[i] * discount[j] and turn to situation with (i-1) items and (j-1) discounts. So in this case, expected discount is equal to a[i] * b[j]+dp[i-1][j-1].

    The probability of this happening is p = j/i. Since we must choose j items from i, and probability that i’th item will be chosen is equal to j/i.

    2) i-th item is not chosen

    The answer is dp[i-1][j].

    The probability of this happening is 1-p.

    I used to use recursive Version (Memoization). So here is my code

    See details See https://discuss.codechef.com/questions/4100/chiefett-editorial

    Click to See Code 
    #include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,k;
int a[1005],p[1005];
int CS = 1;
int vis[N][N];
double dp[N][N];

double solve(int i,int j)
{
    if(j==0) return 0;
    if(i==0)return -1e8;
    if(vis[i][j] == CS) return dp[i][j];
    double res = j*1./i * (a[i] * p[j] * .01 + solve(i-1,j-1));
    if(i>=j) res += max((double)0,(1-j*1./i) * solve(i-1,j));
    vis[i][j] = CS;
    return dp[i][j] = res;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d %d",&n,&k);
        for(int i = 1; i <= n; i ++ ) scanf("%d",&a[i]);
        for(int i = 1; i <= k ; i ++ ) scanf("%d",&p[i]);
        sort(a+1,a+n+1);
        sort(p+1,p+k+1);
        printf("%.3lf\n",solve(n,k));
        CS ++;
    }
}

    Problem 2 : LEMOVIE
    Idea : DP + Combinatorics.
    Solution : lemovie-editorial

    Uva volume 10100-10199

    Uva 10154 – Weights and Measures

    Link: 10154 – Weights and Measures

    Solution: DP
    Discussion:

    * Sort the turtle ascending according to their strength( Not residual strength). If equal strength, that according weight

    Proof From Uva Forum:
    Assume the solution would have a turtle that is stacked upon a turtle with smaller strength. Then the turtle with smaller strength has to carry also the weight of the turtle with bigger strength. So it is also possible to exchange them, because if the turtle with smaller strength can carry at least both weights, then of course the turtle with bigger strength can.

    DP Solution from Uva :

    Go through the list of turtles that is sorted ascending by strength (because I try to stack a tower of turtles upon ith turtle, therefore the turtle with smallest strength has to go first). In each step calculate the minimum weight that a stack of k turtles has. If it is impossible to have a stack of k turtles, define this as Infinity. Lets define this as mw(i,k) (i is number of step).

    mw(i,k) = min(mw(i-1,k),mw(i-1,k-1)+weight(i)) if mw(i-1,k-1)+weight(i)<=strength(i)
    else mw(i,k) = mw(i-1,k).

    Answer is maximum k with mw(n,k)<infinity.

    This problem helped me to think dp problems with a different angle.

    Click to See Code 
    #include <bits/stdc++.h>
using namespace std;
const int N = 5610;
pair<int,int> b[N];
int n=0;
int dp[N][N];
bool cmp(pair<int,int> a,pair<int,int> b)
{
    if(a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

int main()
{
   
    n=1;
    while(scanf("%d %d",&b[n].first,&b[n].second)==2) {
        n++;
    }
    sort(b+1,b+n,cmp);
    int f = 0;
    for(int i= 0;i < n; i ++) {
        for(int j= 0; j < n ; j++ ) dp[i][j] = 1e8;
    }
    dp[0][0] = 0;
    for(int i = 1; i < n; i ++ ) {
        dp[i][0] = 0;
        for(int j = 1; j < n ; j ++ ) {
            dp[i][j] = dp[i-1][j];
            if(dp[i-1][j-1] + b[i].first <= b[i].second) {
                dp[i][j] = min(dp[i][j] , dp[i-1][j-1] + b[i].first);
            }
        }
    }
    for(int i = 1; i < n; i ++ ) {
        for(int j = 1; j < n ; j ++ ) {
            if(dp[i][j] < 1e8) {
                f= max(f,j);
            }
        }
    }
    printf("%d\n",f);
    
}

    Uva 10164 – Number Game

    Link: 10164 – Number Game

    Solution : Backtracking

    The backtracking solution has complexity of O(n^3) but passes quickly. As it finds answer very quickly and return from recursion.

    Three state:
    calc(sum,cnt,ind) => sum = summation of numbers that are taken, cnt = # of elements taken, ind = current position. 

    Two options:
1.we can take current number then recurse
2. or not to take and recurse

    If anytime we find a solution, we directly return.

    Click to See Code 
    #include <bits/stdc++.h>
using namespace std;
const int N = 1<<10;
int dp[N]; // This stores the number taken.
int a[N*2]; 
int n;
bool flag = 0;
void calc(int sum,int cnt, int ind)
{
    if(cnt==n){
        if(sum % n ==0){
            flag = 1; // found a solution
            printf("Yes\n");
            for(int i = 0; i < n;i ++) {
                if(i)printf(" ");
                printf("%d",dp[i]);
            }
            printf("\n");
        }
        return;
    }
    if(flag) return; // If already found a solution, then return
    if(ind >= 2*n-1) return;
    dp[cnt] = a[ind];
    calc(sum + a[ind], cnt+1, ind+1); // Taking a[ind]
    calc(sum,cnt,ind+1); // Not taking ind
    
}
int main()
{
    while(scanf("%d",&n) && n) {
        for(int i = 0; i < 2*n -1;i ++ ) {
            scanf("%d",&a[i]);
        }
        memset(dp,0,sizeof dp);
        flag = 0;
        calc(0,0,0);
        if(!flag) printf("No\n");
    }
    
}