PROFF

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);





        }

    }





}

ABA12C

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;
}

KQUERY

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;

}

PPATH

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;

}