Friday, 4 March 2016

PROFF

Standard

Professor Farouk Question


Link to the question : PROFF

HINT :

Just simple brute force.  Add one digit at a time from right to left and check if there is a carry. Keep in mind some corner cases. 

RECOMMENDED QUESTION :

Try your hands on this question : Headshot

SOLUTION :

/*  PROFF */
/* Sushant Gupta */
#include<stdio.h>
#include<string.h>
int main()
{
  
    long long int x1=1,x2=1,n1,n2;
    while(1)
    {
        scanf("%lld%lld",&x1,&x2);
        if(x1==0 && x2==0)
            return 0;
        else
        {
            n1 = x1;
            n2 = x2;
            int s=0,c=0;
            while(n1 || n2)
            {
                s = ((n1 %10) + (n2 %10) + s >=10);
                c = c+s;
                n1 = n1/10;
                n2 = n2/10;
                /*if(s>9)
                {
                    c++;
                    f=1;
                }
                else if(s==9)
                {
                    if(f==1)
                        c++;
                    else
                        f= 0;
                }
                else
                    f= 0; */
            }
            if(c==0)
                printf("No carry operation.\n");
            else if(c==1)
                printf("1 carry operation.\n");
            else
                printf("%d carry operations.\n",c);
        }
    }
}

Wednesday, 2 March 2016

ABA12C

Standard

Buying Apples!

Link to the question : ABA12C

HINT :

This is a problem of unbounded knapsack. 
We will maintain an array ans[ k+1 ] where the j th index stores the minimum money required to buy  j kg of apples. 
To find the optimal ans[ j ] , we need to decide whether to  select or reject an instance of weight 'i'.
If we reject all the weights then ans[ j ] = price[ j ], and if we select 'i'  then 
ans[ j ] = minimum[ ans[j - i] + price[ i ] ]  for i= 0,1....j-1.

You can look into the source code for a better understanding.

RECOMMENDED QUESTION :

Try your hands on this dp question :  Morena
  

SOLUTION :

   /* ABA12C - Buying Apples */
/* Sushant Gupta */

#include<bits/stdc++.h>
using namespace std;
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int n,k,b;
  scanf("%d%d",&n,&k);
  b =k;
  int p[k +1];
  int i,j;
  for( i=1; i<=k; i++ )
   scanf("%d",&p[i]);
  int ans[k+1];
  for(i=1; i<=k; i++)
  {
   //if(p[i] == -1)
   // ans[i] = INT_MAX;
   //else
    ans[i] = p[i];
  }
  for(i=2; i<=k; i++)
  {
   for(j=1; j<i; j++)
   {
    if(p[i-j] == -1  || ans[j] == -1)
     continue;
    if(ans[i] == -1)
     ans[i] = ans[j] + p[i-j];
    else
    ans[i] = min(ans[i], ans[j] + p[i-j]);

   }

  }
  if(k==0)
   printf("0\n");
  else
  printf("%d\n",ans[k]);

 }
 return 0;
}

Tuesday, 1 March 2016

KQUERY

Standard

K-query

Link to the question : KQUERY

HINT :

PREREQUISITE : BINARY INDEXED TREE

This is an offline approach. 
Store the array elements and the queries in the same array(for this you may define your own class or structure) . You can see my structure in the code below. 
Now, we sort this array in decreasing order (according to the value of the array elements and the k values of the queries) .
Now, just traverse this sorted array :
   a. If the element is array element , update the binary indexed tree to have this element  
       at the given index .
   b. If the element is a query <left,right,k> , make a query to find the number of elements in the segment tree between [left, right]. Store this information in our answer array at the location corresponding to the query number we are dealing with .
Finally, output this array .

RECOMMENDED QUESTION :

Try this question : hlprams

SOLUTION :

#include<bits/stdc++.h>
using namespace std;
int btree[30009];
struct pos
{
    int l,r,p;
    long long int v;
};
pos a[230009];
bool cmp(pos a, pos b)
{
    if(a.v == b.v)
    {
        return a.l > b.l;
    }
    return a.v > b.v;
}
void update_it(int idx, int n)
{
    while(idx <=n)
    {
        btree[idx] += 1;
        idx += idx & (-idx);
    }
}
int read_it(int idx)
{
    int s=0;
    while(idx >0)
    {
        s += btree[idx];
        idx -= idx &(-idx);
    }
    return s;
}
int main()
{
    fill(btree,btree + 30009, 0);
    int n;
    scanf("%d",&n);
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%lld",&a[i].v);
        a[i].l = 0;
        a[i].p =0;
        a[i].r = i+1;
    }
    int q;
    scanf("%d",&q);
    int ans[q+1];
    for(i=n ;i< n+q; i++)
    {
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].v);
        a[i].p = i-n+1;
    }
    sort(a,a+n+q,cmp);
    //printf("Hello\n");   //check
   /* for(i=0; i<n+q;i++)
    {
        printf("%d %d %d\n",a[i].l,a[i].r,a[i].v);
    }*/
    for(i=0;i< n+q;i++)
    {
        if(a[i].l == 0)
        {
            update_it(a[i].r,n + 9);
        }
        else
        {
           // printf("\n");
       //     for(int j=1;j<=n;j++)
         //      printf("b[%d] = %d\n",j,btree[j]);  // check
           ans[a[i].p] = read_it(a[i].r) - read_it(a[i].l -1);
        }
    }
    //for(i=1;i<=n;i++)
      //  printf("b = %d\n",btree[i]);  //check
    for(i=1;i<=q;i++)
        printf("%d\n",ans[i]);
    return 0;
}

Tuesday, 26 January 2016

PPATH

Standard

Prime Path

Link to the question : PPATH

RECOMMENDED QUESTION:


Try your hands on this permutation question : QUESTION

HINT :

A good problem on bfs for beginners. The question asks us to find the shortest route between the two prime numbers. What we can do is change each digit of the number and check whether the new number is prime. If its prime then we again apply the above process and continue this process untill we reach the destination. 
The forming of new number and traversing to new one can be easily done  using Breadth First Search. If you don't know about it, I would recommend you to have a look at it here .

SOLUTION :

#include<bits/stdc++.h>

using namespace std;


bool prime[100005];

bool visit[100005];

int dist[100005];


void sieve(int n = 100005)

{

    // Create a boolean array "prime[0..n]" and initialize

    // all entries it as true. A value in prime[i] will

    // finally be false if i is Not a prime, else true.

    

    memset(prime, true, sizeof(prime));

    prime[0] = false;

    prime[1] = false;

    for (int p=2; p*p<=n; p++)

    {

        // If prime[p] is not changed, then it is a prime

        if (prime[p] == true)

        {

            // Update all multiples of p

            for (int i=p*p; i<=n; i += p)

                prime[i] = false;

        }

    }

 

    

}

int conv_to_num(int a[])

{

int n;

n = (a[3] *1000)  + (a[2] *100)   + (a[1] * 10) + (a[0]);

return n;

}


void conv_to_arr(int digit[],int n)

{

digit[0] = n%10;

n /= 10;

    digit[1] = n%10;

n /= 10;

digit[2] = n%10;

n /= 10;

digit[3] = n%10;

}

int main()

{

int t;

sieve();

scanf("%d",&t);

while(t--)

{

    queue<int> q;

int num1, num2,  i, digit[4];

scanf("%d%d",&num1,&num2);

memset(dist,-1,sizeof(dist));

memset(visit,false,sizeof(visit));

if(num1 == num2)

{

printf("0\n");

continue;

}

q.push(num1);

   dist[num1] = 0;

   visit[num1] = true;

   //printf("hello\n");    //chedk

while(!q.empty())

{

        //printf("hello\n");    //chedk

    int val = q.front();

   // cout<<"val = "<<val<<endl;    //check

    if(val == num2)

    break;

   // q.pop();

   // conv_to_arr(val);

    //cout<<digit[3]<<digit[2]<<digit[1]<<digit[0]<<endl;

    for(i= 0; i<4; i++)

    {

       //int x = digit[i];

       conv_to_arr(digit,val);

            for(int j= 0; j<10; j++)

{

   

        digit[i] = j;

int temp = conv_to_num(digit);

if(!visit[temp] && prime[temp] && temp >= 1000) 

{

   //printf("hello\n");    //chedk

   //cout<<"temp = "<<temp<<endl;   //check

    visit[temp] = true;

    q.push(temp);

    dist[temp] =  dist[val] + 1;

     }

}

// digit[i] = x;

//cout<<digit[3]<<digit[2]<<digit[1]<<digit[0]<<endl;

}

q.pop();

}

if(dist[num2]==-1)

printf("-1\n");

else

printf("%d\n",dist[num2]);

//cout<<prime[3739]<<endl;

}

return 0;

} 

Saturday, 10 October 2015

MORENA

Standard


Morenas Candy Shop ( Easy )

Link to the question : MORENA

HINT :

Think of dp solution. We check if a[i] is > or < or = a[i-1] and store its relative sign in another array, b[i]. Now just count the number of times the sign alternates.

RECOMMENDED QUESTION :

Try solving this dp question .

SOURCE CODE :

#include<stdio.h>
long long int a[1000010];
int b[1000010];
int main()
{
    int n,i;
    scanf("%d",&n);
    b[0] = 0;
    for(i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
        if(i>0)
        {
            if(a[i]>a[i-1])
                b[i] = 1;
            else if(a[i] < a[i-1])
                b[i] = -1;
            else
                b[i] = 0;
        }
    }
    int c=1,sign=0;
    for(i=1;i<n;i++)
    {
        if((sign == 0) && (b[i] != 0))
        {
               c++;
               sign = b[i];
        }
        else if((sign ==1) && (b[i]== -1))
        {
            c++;
            sign = b[i];
        }
        else if((sign == -1) && (b[i] == 1))
        {
            c++;
            sign = b[i];
        }
    }
    printf("%d\n",c);
    return 0;
}

Monday, 5 October 2015

TWOSQRS

Standard

Two squares or not two squares

Link to the question : TWOSQRS

HINT :

Logic seems very clear. Just we need check if the number can be represented as a sum of two squares or not. A little bit optimisation may be preferrable.

RECOMMENDED QUESTION :

Try solving this  question .

SOURCE CODE :

#include<stdio.h>

#include<math.h>

void twosq(long long int x)

{

    long long int i,j=0;

    i= sqrt(x);

    while(i>0) {

    if(j*j>x)

      {



        printf("No\n");

         break;

      }

    else if(i*i + j*j == x)

        {



         printf("Yes\n");

         break;

        }

    else if(i*i + j*j <x)

         j++;

    else

        i--;

    }





}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        long long int n;

        scanf("%lld",&n);

        twosq(n);

    }

    return 0;



}

Wednesday, 23 September 2015

BAT3

Standard

BATMAN3

Link to the question : BAT3 

HINT :

I would suggest you to try the longest increasing sub sequence problem first. You can also check the algorithm for LIS in geeksforgeeks.org. 
If you have idea of LIS, then the question must be easy for you. In this we need to find the longest decreasing subsequence but with a change that we can jump one big number if we are on the Robin's number (as given in the question). Hence, we just need to add  batman can go to next cliff its smaller than the present or batman is standing on the Robin's peak (then he can go to any peak). 

RECOMMENDED QUESTION :  

Try another dp question .

SOURCE CODE :

/* Batman3 */

/* Sushant Gupta */



#include<stdio.h>



int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        int i,arr[n];

        for(i=0;i<n;i++)

            scanf("%d",&arr[i]);

        int lis[n],j;

         for ( i = 0; i < n; i++ )

      lis[i] = 1;

         /* Compute optimized LIS values in bottom up manner */

   for ( i = 1; i < n; i++ )

      for ( j = 0; j < i; j++ )

         if ( (arr[i] < arr[j] || j==m )&& lis[i] < lis[j] + 1)

            lis[i] = lis[j] + 1;

    int max =0;

   /* Pick maximum of all LIS values */

   for ( i = 0; i < n; i++ )

      {if ( max < lis[i] )

         max = lis[i];

       // printf("li = %d\n",lis[i]); //check

         }



      printf("%d\n",max);

    }

    return 0;

}

Friday, 11 September 2015

YELBRICK

Standard


The Yellow Brick Road

Link to the question : YELBRICK 

HINTS :

Very simple ad-hoc question. Just find the gcd of the length, breadth and height of the stones, and then find the number of stones that can be produced.

RECOMMENDED  QUESTION :

Try solving this question as even this requires some application of gcd.

SOURCE CODE :

#include <iostream>
using namespace std;
int gcd(int x,int y)
{
    while(x!=y){
          if(x>y)
              return gcd(x-y,y);
          else
             return gcd(x,y-x);
     }
     return x;
}
int main() 
{
    int n,i;
    while(1)
    {
        cin>>n;
        if(n==0)
        break;
        int a[n][3];
        long long vol=0;
        for(i=0;i<n;i++)
        {
            cin>>a[i][0]>>a[i][1]>>a[i][2];
        }
        int hcf =a[0][0];
        for(i=0;i<n;i++)
        {
            hcf = gcd(hcf,a[i][0]);
            hcf = gcd(hcf,a[i][1]);
            hcf = gcd(hcf,a[i][2]);
        }
        for(i=0;i<n;i++)
        {
            vol+=(long long)((a[i][0]/hcf)*(a[i][1]/hcf)*(a[i][2]/hcf));
        }
        cout<<vol<<"\n";
    }
    return 0;
}

Thursday, 10 September 2015

ZSUM

Standard

Just Add It

Link to the question : ZSUM 

HINTS :

When trying to find  (Zn+Zn-1-2Zn-2) you will notice that most of the terms of Sn and P cancel out and the terms left can be easily calculated by modular exponention.   

  You can find the code for modular exponention in my previous post YAPP .

SOURCE CODE :

/* Just Add */
/* Sushant Gupta */

#include<stdio.h>
#define mod 10000007

long long int mult(long long int x,long long int y)
{
    long long int ans =1;
    while(y>0)
    {
        if(y%2)
            ans = (ans * x) % mod;
        x = (x * x) % mod;
        y=y>>1;

    }
    return ans;
}

int main()
{
    long long int n,k;
    while(1)
    {
        scanf("%lld%lld",&n,&k);
        if(n==0 && k==0 )
            return 0;
        else
        {
            long long int s1, s2,s3,s4;
            s1 = (2 * mult(n-1,n-1) ) % mod;
            s2 = (2 * mult(n-1,k) ) % mod;
            s3 = mult(n,k);
            s4 = mult(n,n);
            long long int res = (s1 + s2 +s3 + s4) % mod;
            printf("%lld\n",res);
        }
    }

}

Tuesday, 8 September 2015

MOHIB

Standard


Mohib and series

 Link to the question : MOHIB

HINT :

Given x and the avg as input, the number of elements in the sequence, n, and the sum of the sequence can be very easily calculated by using the formula - sum of seq. / n = avg. 
Now, to find the largest possible number, lets say M, (sum of sequence - M) should be minimum. Hence in order for that to be minimum, the sequence excluding M should be 1,2,3,...n-1 such that its sum is minimum.

RECOMMENDED QUESTION :

After getting AC in this one, try getting AC in this question .

SOURCE CODE :

#include<stdio.h>

int main()
{
    int t;
    scanf("%d",&t);  
    while(t--)
    {
         int x,avg,n;
         scanf("%d%d",&x,&avg);
         n = avg - x;
         int sum = n * (avg + 1);
         sum = sum - (n*(n-1)/2) ;

         printf("%d\n",sum);
    }
    return 0;
}