KQUERYO

K-Query Online

Link to the question : KQUERYO

HINT :

Question can be easily solved with Segment Trees with vector.  Read more about it here :  http://codeforces.com/blog/entry/15890

RECOMMENDED QUESTION :

Try your hands on this question : QUEEN

SOLUTION :

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mod 1000000007
using namespace std;

int n,q, ar[30005];
std::vector<int> v[100005];

void build(int id ,int l ,int r )
{
if(r == l )
{
v[id].push_back(ar[l]);
return ;
}
int mid = (l+r)/2;
build(2 * id, l, mid);
build(2*id+1, mid+1, r);
merge(v[2 * id].begin(), v[2 * id].end(), v[2 * id + 1].begin(), v[2 * id + 1].end(), back_inserter(v[id]));
}

int query(int x,int y,int k,int id ,int l ,int r )
{

if(x > r || l > y)
return 0;
if(x <= l && r <= y)
{
return v[id].size() - (upper_bound(v[id].begin(), v[id].end(), k) - v[id].begin());
}
int mid = (l+r)/2;

return query(x, y, k, 2 * id, l, mid) +
  query(x, y, k, 2*id+1, mid+1, r) ;
}


int main()
{
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &ar[i]);

build(1,0,n-1);
scanf("%d", &q);

int prev = 0;
while(q--)
{
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
int i = a^prev;
int j = b^prev;
int k = c^prev;

prev = query(i-1,j-1,k,1,0,n-1);
printf("%d\n", prev);
}
return 0;
}

QUEEN

Wandering Queen

Link to the question : QUEEN

HINT :

This question requires bfs as can be clearly understood from the tag. We start doing bfs from the position of the queen. And push into the queue all the squares which can be visited by the queen from that position and update their distance by 1 and mark it visited. For eg :
S..
 ..F
when starting from S we push into the queue positions (0,1), (0,2), (1,0), (1,1), consider 0 based indexing, update their position and mark them visited.
But while pushing into the queue just checking whether that position has been visited wont do.
Because consider the case
S..
XX.
..F
here, from (0,1) you can visit (1,2) and update its distance and mark it visited, and when you check for (0,2) you will see (1,2) is visited and not check further. This is incorrect because for optimal solution you must visit (1,2) and (2,2) from here. Hence even if the square is visited you should visit it again if it can be reached from the current position in 1 move.
Look code for further details.

RECOMMENDED QUESTION :

Try your hands on this question : Headshot

SOLUTION :

#include <iostream> #include <stdio.h> #include <queue> using namespace std; struct point { int x,y; }; int X[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int Y[] = {-1, 0, 1, -1, 1, -1, 0, 1}; int n,m; char str[1005][1005]; int dist[1000][1000]; bool check(point t) { if(t.x >=0 && t.x <n && t.y >=0 && t.y <m && str[t.x][t.y] != 'X') return true; return false; } int main() { int t; scanf("%d", &t); while(t--) { scanf("%d %d", &n, &m); for(int i=0; i<n; i++) scanf("%s", str[i]); queue<point> q; point start, final; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { dist[i][j] = 0; if(str[i][j] == 'S') { start.x = i; start.y = j; dist[i][j] = 1; } else if(str[i][j] == 'F') { final.x = i; final.y = j; } } } q.push(start); while(!q.empty()) { point temp = q.front(); q.pop(); for(int i=0; i<8; i++) { point copy = temp; copy.x += X[i]; copy.y += Y[i]; while(check(copy)) { if(dist[copy.x][copy.y] == 0) { dist[copy.x][copy.y] = dist[temp.x][temp.y] + 1; q.push(copy); } else if(dist[copy.x][copy.y] != dist[temp.x][temp.y]+1) break; copy.x += X[i]; copy.y += Y[i]; } } } cout << dist[final.x][final.y]-1 << endl; } return 0; }

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;

} 

MORENA

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;

}

TWOSQRS

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;



}

BAT3

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;

}

YELBRICK

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