Monday 26 October 2015

D-query :spoj (MO) (for only queries in range )

                                              http://www.spoj.com/problems/DQUERY/en/
                                         

DQUERY - D-query



In this question , the concept of rearranging queries is used , the method known as "MO". 
In the question, it is asked to find total different numbers present in the range [l,r] . "add" and "del" functions are written accordingly.





#include<bits/stdc++.h>

using namespace std;

int readInt () {
bool minus = false;
int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}


struct node
{
 int lf,rt,qno;
};

int bck_sz,ans=0;

bool cmp(struct node a,struct node b)
{
    int  i,j;
    i=a.rt/bck_sz;
    j=b.rt/bck_sz;
    if(i==j)
    {
        if(a.lf<b.lf)
            return 1;
        else
            return 0;
    }
    else{
        if(i<j)
            return 1;
        else
            return 0;
    }
}



int has[1000005];
 
void add(int num)
{
if(has[num]==0)
{
ans++;
has[num]=1;
}
else
 has[num]++;
}


void del(int num)
{
if(has[num]==1)
{
ans--;
has[num]=0;
}
else if(has[num]>1)
   has[num]--;
}



int main()
{
int n,i,j,k,l,r,q,x,y;
n=readInt();
int arr[n+1];
for(i=1;i<=n;i++)
arr[i]=readInt();
   
     bck_sz=sqrt(n);
 
q=readInt();
int result[q];
node a[q];
for(i=0;i<q;i++)
{
l=readInt();
r=readInt();
a[i].lf=l;
a[i].rt=r;
a[i].qno=i;
}

   sort(a,a+q,cmp);

  // for(i=0;i<q;i++)
    //cout<<a[i].lf<<" "<<a[i].rt<<endl;

l=1,r=0;
for(i=0;i<q;i++)
{
    x=a[i].lf;
    y=a[i].rt;
    while(r<y)
    {
 
        r++;
        add(arr[r]);
    }
    while(l>x)
    {
        l--;
        add(arr[l]);
    }
    while(l<x)
    {
        del(arr[l]);
        l++;
    }
    while(r>y)
    {
        del(arr[r]);
        r--;
    }
    result[a[i].qno]=ans; 
}


 for(i=0;i<q;i++)
  printf("%d\n",result[i]);

return 0;
}

Question which include only Queries. (MO) concept


                                   http://codeforces.com/problemset/problem/221/D

                                         D. Little Elephant and Array

In this question ,we used the concept of MO , i.e. idea of rearranging the queries according to our beneficial.

Firstily , we sort the queries using this cmp function .
In all the questions in which ,the concept of MO is used "cmp" is same and  four "while loops"
 will be same. :)

we just have to change the "add" and "del"  functions for each question. :P



#include<bits/stdc++.h>

using namespace std;

long long int readInt () {
bool minus = false;
long long int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}


struct node
{
long long int lf,rt,qno;
};

long long int bck_sz,ans=0;

bool cmp(struct node a,struct node b)
{
    int  i,j;
    i=a.rt/bck_sz;
    j=b.rt/bck_sz;
    if(i==j)
    {
        if(a.lf<b.lf)
            return 1;
        else
            return 0;
    }
    else{
        if(i<j)
            return 1;
        else
            return 0;
    }
}



long long int has[1000005];

void add(long long int num)
{
if(num>1000004)
return ;
if(has[num]>num)
{
has[num]++;
}
else if(has[num]==num)
{
ans--;
has[num]++;
}
else
{
      has[num]++;
   if(has[num]==num)
   ans++;
}

}


void del(long long int num)
{

if(num>1000004)
return ;

if(has[num]>num)
{
if(has[num]>0)
has[num]--;

if(has[num]==num)
   ans++;

}
else if(has[num]==num)
{
ans--;
if(has[num]>0)
has[num]--;
}
else
{
if(has[num]>0)
      has[num]--;
}
}



int main()
{
long long int n,i,j,k,l,r,q,x,y;
n=readInt();
q=readInt();

long long int arr[n+1];
for(i=1;i<=n;i++)
arr[i]=readInt();
 
     bck_sz=sqrt(n);
 


long long int result[q];
node a[q];
for(i=0;i<q;i++)
{
l=readInt();
r=readInt();
a[i].lf=l;
a[i].rt=r;
a[i].qno=i;
}

   sort(a,a+q,cmp);

  // for(i=0;i<q;i++)
    //cout<<a[i].lf<<" "<<a[i].rt<<endl;

l=1,r=0;
for(i=0;i<q;i++)
{
    x=a[i].lf;
    y=a[i].rt;
    while(r<y)
    {

        r++;
        add(arr[r]);
    }
    while(l>x)
    {
        l--;
        add(arr[l]);
    }
    while(l<x)
    {
        del(arr[l]);
        l++;
    }
    while(r>y)
    {
        del(arr[r]);
        r--;
    }
    result[a[i].qno]=ans;
}


 for(i=0;i<q;i++)
  printf("%d\n",result[i]);

return 0;
}

All possible sub-matrices sums.


               

                              Save the nature

https://www.codechef.com/problems/SVNTR (Lunch Time oct 2015)

 In this problem , you have to count number of sub-matrices whose sum is less than or equal to k (given).
Approach for this problem : firstly calculate the all possible column sum , i.e for c number of columns ,there will be c*(c+1)/2 columns created.

 for example : 1 2 3                                 1  3  6   2   5   3
                       4 5 6                 --->>>     4  9  15  5  11  6

  after creating "b" matrix from the given "a"  matrix.  Calculate all possible sums in each columns

In this all possible sum for 1st column is : 1,4,5.

In this all possible sum for 2nd column is : 3,9,12.

now, that count all the sums which is smaller than or equal to "k".



  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long int b[151][12255],a[151][151];
  6.  
  7.  
  8. int main()
  9. {
  10. ios_base::sync_with_stdio(0);
  11. cin.tie(0);
  12. int t;
  13. cin>>t;
  14. while(t--)
  15. {
  16. long long int r,c,make,i,j,k,l,p,s,cnt=0;
  17. cin>>r>>c>>make;
  18. for(i=0;i<r;i++)
  19. for(j=0;j<c;j++)
  20. cin>>a[i][j];
  21. for(p=0;p<r;p++)
  22. {
  23. k=0;
  24. for(i=0;i<c;i++)
  25. {
  26. s=0;
  27. for(j=i;j<c;j++)
  28. {
  29. s+=a[p][j];
  30. b[p][k++]=s;
  31. }
  32. }
  33. }
  34. long long int sz=((c*(c+1)));
  35. sz=sz/2;
  36. for(i=0;i<sz;i++)
  37. {
  38. for(j=0;j<r;j++)
  39. {
  40. s=0;
  41. for(k=j;k<r;k++)
  42. {
  43. s+=b[k][i];
  44. if(s<=make)
  45. cnt++;
  46. }
  47. }
  48. }
  49. cout<<cnt<<endl;
  50. }
  51. return 0;
  52. }

Sunday 18 October 2015

use of sscanf , takes interger from messy string R23C55.. or R2323434C44554


                                          http://codeforces.com/contest/1/problem/B

                                                     B. Spreadsheets


55 = BC
27 = AA
28 = AB

sscanf takes out number from a messy string input :

for example : if the input is R5564C757 , it takes (sscanf(s,"  %*c   %d    %*c     %d  ",&x,&y);
 x=5564
 y=757



#include<cstdio>
#include<bits/stdc++.h>

using namespace std;

void g(int t)
{
 if(t)
 {
 g((t-1)/26);
 putchar(65+(t-1)%26);
 }
}



int main()
{
  int n,x,y;
  char s[64],*p;
  for(scanf("%d ",&n);n--;)
  {
    gets(s);
    if(sscanf(s,"  %*c   %d    %*c     %d  ",&x,&y)==2)
{
      g(y);
      printf("%d\n",x);
        }
else
{
      for(x=0,p=s;*p>64;++p)
       {
        x=x*26+*p-64;
        cout<<x<<" ";
       }
      printf("R%sC%d\n", p, x);
      }
  }
  return 0;
}

Saturday 10 October 2015

No. of subsets whose gcd is 1


                                         

                           Subtraction Game 2 

                                     https://www.codechef.com/problems/AMSGAME2


                       It is only a branch and bound type of recursion.

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long int n,i;
  4. long long int a[1000];
  5. long long int dp[70][50010];
  6. long long int go(long long int cur_indx,long long int cur_gcd)
  7. {
  8. if(cur_indx>=n && cur_gcd==1)
  9. return 1;
  10. else if(cur_indx>=n && cur_gcd!=1)
  11. return 0;
  12. if(dp[cur_indx][cur_gcd]!=-1)
  13. return dp[cur_indx][cur_gcd];
  14. else
  15. {
  16. long long int result=0;
  17. result=go(cur_indx+1,cur_gcd); /// without taking a[i];
  18. result+=go(cur_indx+1,__gcd(cur_gcd,a[cur_indx])); /// with taking a[i];

  19. dp[cur_indx][cur_gcd]=result;
  20. return result;
  21. }
  22. }
  23. int main()
  24. {
  25. int t;
  26. cin>>t;
  27. while(t--)
  28. {
  29. // memset(dp,-1,sizeof(dp));
  30. for(int i=0;i<70;i++) for(int j=0;j<10005;j++) dp[i][j]=-1;
  31. cin>>n;

  32. for(i=0;i<n;i++)
  33. cin>>a[i];

  34. cout<<go(0,0)<<endl;
  35. }
  36. return 0;
  37. }

Monday 5 October 2015

wilson's theorm + fermat's theorem :---BORING Factorials

       
                           SPOJ :- BORING - Boring Factorials

 According to wilson's theorem 
 for prime numbers  ((n-1)!) mod n = n-1

In the question Boring factorials
we hv to find :---   N! mod P

(1*2*..*(n-1)*(n)*..*(p-1) )mod P= P-1  (wilson's)

(1*2*..*(n-1)*(n) )mod P  (this is the question)

=(P-1) / ((n+1)*(n+2)*..*(P-2)*(P-1)) mod P






#include<bits/stdc++.h>

using namespace std;

#define ll long long int


long long int read_int(){
char r;
bool start=false,neg=false;
long long int ret=0;
while(true){
r=getchar();
if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
continue;
}
if((r-'0'<0 || r-'0'>9) && r!='-' && start){
break;
}
if(start)ret*=10;
start=true;
if(r=='-')neg=true;
else ret+=r-'0';
}
if(!neg)
return ret;
else
return -ret;
}


ll power(ll a,ll b,ll mod)
{
ll ans=1;
while(b)
{
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod;
b/=2;
}
return ans;
}



int main()
{
 int t;
 //cin>>t;
 scanf("%lld",&t);

 while(t--)
 {

   long long int n,p,i,j,k,l,a=1;
   //cin>>n>>p;
   scanf("%lld%lld",&n,&p);

   if(n>=p)
   {
      // cout<<0<<endl;
       long long int y=0;
       printf("%lld\n",y);
       continue;
   }

   a=(p-1);
   for(i=n+1;i<p;i++)
   {
    a=((a%p)*(power(i,p-2,p)%p))%p;
    a=a%p;
   }

 // cout<<a<<endl;
  printf("%lld\n",a);


 }
return 0;
}

ETF - Euler Totient Function

                                     

ETF - Euler Totient Function

SPOJ: - http://www.spoj.com/problems/ETF/

CodeChef :- Rational Numbers (it is sum of phi upto n)


In number theory, Euler's totient function (or Euler's phi function), denoted as φ(n) or ϕ(n), is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n. (These integers are sometimes referred to as totatives of n.)


This is very common in number theory the formula for finding the number of numbers less than and co-prime with n is
N(1-1/p1)(1-1/p2).... where p1,p2.... refers to the distinct prime divisors of the number.
A example always makes it clear ,lets take n=20 hence the prime divisors are 2,5 hence by formula the number of numbers less than and prime to 20 should be 20*(1-1/2)(1-1/2)=20(1/2)(4/5)=8
Now we can count also
1,3,7,9,11,14,17,19



#include<bits/stdc++.h>
using namespace std;
int phi[1000005];
int main()
{
int i,j,k;
for(i=1;i<=1000000;i++)
    phi[i]=i;

for(i=2;i<=1000000;i++)
 if(phi[i]==i)
   for(j=i;j<=1000000;j+=i)
     phi[j]=(phi[j]/i)*(i-1);
int t;
cin>>t;
while(t--)
{
  int n;
  cin>>n;
  cout<<phi[n]<<endl;
}
return 0;
}


Saturday 3 October 2015

maximum contiguous sum in the range [l,r] .


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

GSS1 - Can you answer these queries I


In this question we have to find the maximum contiguous sum in the range[l,r]. 
To find this 
1) total sum is required 

2) suffix max is required 
3) prefix max is required = max(left child prefix max ,  left child sum + ri8 child prefix max ).

4) maximum contiguous = max ( ri8 child maximum contiguous , left child maximum contiguous,
                                                          left child suffix max + ri8 child prefix max )           
                                           







#include<bits/stdc++.h>

using namespace std;


struct node
{
  long  presum;
  long  sufsum;
  long  tmax;
  long  tsum;
};

typedef struct node grp;

grp tre[50005*4];

long a[50005];

int n;


long maxi(long x, long y) {
    return x > y ? x : y;
}


void build(int node,int st,int en)
{
  if(st==en)
  {
     tre[node].presum=a[st];
     tre[node].sufsum=a[st];
     tre[node].tmax=a[st];
     tre[node].tsum=a[st];
  }
  else
  {
     build(2*node,st,(st+en)/2);
     build(1+2*node,1+(st+en)/2,en);

     tre[node].tsum=tre[2*node].tsum+tre[2*node+1].tsum;

     long ok=maxi(tre[2*node].tmax,tre[2*node+1].tmax );
     ok=maxi(ok, tre[2*node].sufsum+tre[2*node+1].presum);
     tre[node].tmax=ok;


     tre[node].presum=maxi(tre[2*node].presum   ,  tre[2*node].tsum  + tre[2*node+1].presum);

     tre[node].sufsum=maxi(tre[2*node+1].sufsum ,  tre[2*node+1].tsum + tre[2*node].sufsum);
  }
}



grp query(int node, int st, int en, int fs, int fe)
{
   if(st>=fs && en<=fe)
   {
       return tre[node];
   }

   int md=(st+en)/2;
   if(fe<=md)
     return query(2*node,st,(st+en)/2,fs,fe);

   if(fs>md)
     return query(1+2*node,1+(st+en)/2,en,fs,fe);


     grp temp1=query(2*node,st,(st+en)/2,fs,fe);
     grp temp2=query(1+2*node,1+(st+en)/2,en,fs,fe);

      grp sent;

      sent.tsum=temp1.tsum+temp2.tsum;

      long ok=maxi(temp1.tmax, temp2.tmax);
      ok=maxi(ok,temp1.sufsum+temp2.presum);
      sent.tmax=ok;

      sent.presum=maxi(temp1.presum   ,  temp1.tsum  + temp2.presum);

      sent.sufsum=maxi(temp2.sufsum ,    temp2.tsum +  temp1.sufsum);

     return sent;
}




int main()
{
   int i,q,l,r;
   scanf("%d",&n);


  for(i=0;i<n;i++)
  scanf("%ld",&a[i]);

  build(1,0,n-1);

 scanf("%d",&q);
 for(i=0;i<q;i++)
 {
     scanf("%d%d",&l,&r);

     grp ans=query(1,0,n-1,l-1,r-1);

     printf("%ld\n",ans.tmax);
 }
return 0;
}

Uploading and Running Lambda function in AWS

Main.go package main import ( "fmt" "encoding/json" "log" "github.com/aws/aws-lambda-g...