Monthly Archives: September 2015

Spoj BUSYMAN solution

Spoj BUSYMAN solution. Spoj I AM VERY BUSY solution.

Category: Standard Algorithm, greedy

This is the direct application of  standard Greedy, Activity Selection Problem. Read the post to understand the problem and its solution.

Here, we use STL and make a Vector of Pairs, and then sort them according to the finish time. The use of timings, vector and pair has been explained using comments in the following code:

Here is the working code:

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

int main() {
     int t,n;
     int start,fin,Res=0;;
     scanf("%d",&t);
     while(t--)
     {
          scanf("%d",&n);
          /*Making vector of Pair*/
          vector <pair<int,int> > v;
          
          Res=1; // as the first activity is always printed
          for(int i=0;i<n;++i)
          {
               scanf("%d%d",&start,&fin);
               /*we make the finish time as the first element
               and start time as the second element*/
               v.push_back(make_pair(fin,start))	;
          }
          /*Using STL sort, we sort according to the first element as the key*/
          sort(v.begin(),v.end());
          
          int PresentFin=v[0].first; // stores the finish time of activity presntly selected
          
          /*Selecting the activites from the set*/
          for(int i=1;i<n;++i)
               if(v[i].second>=PresentFin)
               {
                    Res++;
                    PresentFin=v[i].first;
               }
          printf("%d\n",Res);
          
     }
     return 0;
}

Activity Selection Problem

Problem :

You are given n activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

This is the most basic example of Greedy Approach.

Greedy Choice Property: Pick/select the activity whose finish time is minimum among all the remaining activities and its start time is greater or equal to the finish time of previously selected activity.

Algorithm:

  1. Sort all the activities in increasing order of their Finish times (Pair-wise sorting of Start and Finish time is required)
  2. Select the first activity and print it.
  3. For all remaining activities,
    1. if the start time is greater than or equal to the finish time of previous activity, then print it,
    2. Else leave that activity and move on in the list.

In the code below, we assume that the activities are already sorted in the increasing order of their finish times.

Here is the working code:

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

/*The start[] and fin[] array are used to store the starts 
and finish times of the activites resp. */

/*This function Prints the Index of the activities selected*/
void ActivitySelection(int start[], int fin[], int size)
{
    int PresentActivity, j;
    cout<<"The Activities Selected are as follows:\n";
    
    // The first activity always gets selected
    PresentActivity = 0;
    cout<<PresentActivity<<" ";
 
    // Consider rest of the activities
    for (j = 1; j < size; j++)
    {
      /* If this activity has start time greater than or equal to the finish
       time of previously selected activity, then select it */
      if (start[j] >= fin[PresentActivity])
      {
          cout<<j<<" ";
          PresentActivity = j;
      }
    }
}
 
// driver program to test above function
int main()
{
    int start[] =  {4 ,5 ,7 ,8 ,0 ,4 };
    int fin[] =  {5 ,7 ,9 ,9 ,10 ,10 };
    int size = sizeof(start)/sizeof(start[0]);
    ActivitySelection(start, fin, size);
    
    return 0;
}

Time Complexity: O(N) without sorting, O(NlogN)  with sorting included.

Output:

The Activities Selected are as follows:
0 1 2

The assumptions that we took, that the arrays are already sorted, may not be already given in that case, you need to do either of the following 3 things:

  1. Modify sorting algorithm to sort Start[] and finish[] array so that corresponding updations are made in both the arrays.
  2. Make structure and use STL sort, with user define compare function.
  3. Make a Vector of Pairs, with first element as the finish time, and second element as the starting time of the activity. In this method STL sort can be used, without any user defined compare function.

An application of this algorithm is the Spoj BUSYMAN question. Here we use the the 3rd approach mentioned above to solve it. To understand how STL solution works, read the question and then refer to Spoj BUSYMAN solution.

Spoj ARRAYSUB solution

Spoj ARRAYSUB solutions. Spoj  Solution.

Category: AdHoc, Arrays, Segment Tree

This question can be solved using the optimum approach of Maximum of all Sub-arrays of size K.

We exactly follow the algorithm stated in the above post. Refer to it for detailed explanation.

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

int MaxPos=-1;

int FindMaxOfSub(int a[],int start,int end)
{
     int maxV=a[start];
     for(int i=start+1 ;i<=end ;++i)
          if(maxV<a[i])
          {
               maxV=a[i];
               MaxPos=i;
          }
     return maxV;	
}

int main() {
     int n,k;
     scanf("%d",&n);
     int a[n];
     for(int i=0;i<n;++i)
          scanf("%d",&a[i]);
     scanf("%d",&k);	
     int maxV=FindMaxOfSub(a,0,k-1);
     printf("%d ",maxV);
     for(int i=k;i<n;++i)
     {
          if( MaxPos> i-k)
          {
               if(a[i]>maxV)
               {
                    maxV=a[i];
                    MaxPos=i;
               }
          }
          else
          {
               maxV=FindMaxOfSub(a,i-k+1,i);
          }
          printf("%d ",maxV);
     }
     return 0;
}

Solution of Spoj ARRAYSUB Using Segment Tree :

This question can also be solved using Segment Tree.
The nodes of the Segment Tree that we construct are used to store the maximum of the given range.

Other query and construction are similar to that of the basic Segment Tree.

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

int tree[3*1000000];
int arr[1000000];

/*this function is used to build the 
Segment Tree. We used o-indexed array
to store the tree*/
void build(int node,int start,int end)
{
   if(start==end)
   {
      tree[node] =  arr[start];
   }
   else
   {
      int mid = (start+end)/2;
      build(2*node+1,start,mid);
      build(2*node+2,mid+1,end);
      tree[node] =  max(tree[2*node+1],tree[2*node+2]);
   }
   
}

/*This function is used to query the Segment Tree
to find the maximum of the given range*/
int query(int node,int start,int end,int l,int r)
{
   if(start>r || end<l || l>r)
      return 0;
   
   /*If completely inside*/	
   if(l<=start && end<=r)	
      return tree[node];
   
   int mid = (start+end)/2;
   /*If partially inside*/
   int p1 = query(2*node+1,start,mid,l,r);
   int p2 = query(2*node+2,mid+1,end,l,r);
   return max(p1,p2);
}

int main() {
   ios::sync_with_stdio(false);
   
   int n,k;
   cin>>n;
   for(int i=0;i<n;++i)
      cin>>arr[i];
      
   cin>>k;	
   build(0,0,n-1);
   
   for(int i=0;i<n-k+1;++i)
      cout<<query(0,0,n-1,i,i+k-1)<<" ";
   return 0;
}

Maximum of all Sub-Arrays of size K

Maximum of all Sub-Arrays of size K.

Problem:

Given an array, and a number K, we need to print the maximum value in all the sub-arrays of size K.

Example:

Input
arr[]={9, 1, 8, 2, 7, 3, 6, 4, 5, 15, 17}
K=4
Output: 9 8 8 7 7 6 15 17

 

Input
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3
Output: 3 3 4 5 5 5 6

Solution

Approach 1:  Naive

Here we run two loops, the inner loop runs K times, whereas the outer one runs (N-K+1) times. We find the maximum of each sub-array or each window using this.

Algorithm:

  1. Initialize maxV as the 1st element of the window
  2. Compare all the other elements with maxV, if anyone is greater, update maxV and carry on.
  3. Print the maxV value.
  4. Repeat the process for all such N-K+1 windows.

Here is the working code:

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

void FindMaxOfSub(int a[],int n,int k)
{
     for(int i=0;i<n-k+1;++i)
     {
          int maxV=a[i]; // initialising maxV with 1st element
          for(int j=i+1 ;j<i+k ;++j)
               if(maxV<a[j])
               {
                    maxV=a[j]; // updating if any other is greater
               }
          cout<<maxV<<" ";
     }		
}

int main() {
     int k=4;
     int a[]={9, 1, 8, 2, 7, 3, 6, 4, 5, 15, 17};
     FindMaxOfSub(a,sizeof(a)/sizeof(a[0]),k);
     return 0;
}

Time Complexity: O(NK)

NOTE:

This solution can be made better by storing the storing the position of the maxV element.

Optimised Method:

Algorithm:

  1. Find and store the position of maximum element for 1st K sized window (MaxPos) using the function.
  2. For all other windows, do the following
  3. If the MaxPos falls inside the window, then just compare it with the newly entered last element**.
  4. else call the function to find the maxV for the specific window.

** for each new window, we just remove the leftmost window and a new element on the right side.

Here is the working code:

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

int MaxPos=-1; //  to store the index/position of current maxV

/*Function that gives the max value in a given window*/
int FindMaxOfSub(int a[],int start,int end)
{
     int maxV=a[start];
     for(int i=start+1 ;i<=end ;++i)
          if(maxV<a[i])
          {
               maxV=a[i];
               MaxPos=i;
          }
     return maxV;	
}

int main() {
     int k=4;
    int a[]={9, 1, 8, 2, 7, 3, 6, 4, 5, 15, 17};
    int n=sizeof(a)/sizeof(a[0]);
    FindMaxOfSub(a,n,k);
     int maxV=FindMaxOfSub(a,0,k-1);
     printf("%d ",maxV);
     for(int i=k;i<n;++i)
     {
          /*If the position falls in the present window*/
          if( MaxPos> i-k)
          {
               if(a[i]>maxV)
               {
                    maxV=a[i];
                    MaxPos=i;
               }
          }
          /*if the position is not in the present window*/
          else
          {
               maxV=FindMaxOfSub(a,i-k+1,i);
          }
          printf("%d ",maxV);
     }
     return 0;
}

Time Complexity: O(NK)

Though the complexity is same asymptotically, there is a big difference in the average running time.

Spoj HANGOVER solution

Spoj Hangover solution.

Category: AdHoc

Straight forward question, do what is said in the question i.e. find the given sum for different values of N.

“In general you can make n cards overhang by 1/2+ 1/3 + 1/4 ++ 1/(n + 1) card lengths”

Here is the working code:

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

int main() {
     float val=0;
     scanf("%f",&val);
     while(val)
     {
          float comp=0;
          float i=1;
          
          for(i=1;comp<val;++i)
               comp+=(1/(i+1));
          
          printf("%.0f card(s)\n",i-1);
          scanf("%f",&val);
     }
     return 0;
}

Spoj JULKA solution

Spoj JULKA solution. Spoj Julka solution.

Category: AdHoc

Here the Input numbers are really large, so they wont fit in the range of normal variables, we need to use Strings to represent them.

Used below are some standard functions that are used to give remainder/divide/add two number represented by string .
The first function works on a number which is represented in reverse order. Thus, we first reverse the number (represented as a string).

Other Such Functions and Other important concepts of competitive coding can be found here. (pg. 25)

Algorithm:

  1. Input numbers, reverse them
  2. Add both, //a=a+b
  3. divide a by 2, you have the larger number, print it
  4. subtract b from a, //a=a-b, you have the second number, print it.

Example:

Lets see what each step in algo does.

  1. a=10, b=2
  2. a=a+b, a=12
  3. a/=2, a=6  // this is the first answer
  4. a-=b, 6-2= 4  ; a=4  // this is the second answer.

Here is the working code:

#include <stdio.h>
#include<string.h>

/*This method adds two Numbers represnted using strings*/
void add(char v1[], char v2[])// v1 = v1+v2;
{
     int i,d,c=0;
     int l1=strlen(v1);
     int l2=strlen(v2);
     for(i=l1;i<l2;i++) 
          v1[i]='0';
     for(i=l2;i<l1;i++) 
          v2[i]='0';
     for(i=0;i<l1||i<l2;i++)
     {
          d=(v1[i]-'0')+(v2[i]-'0')+c;
          c=d/10;
          d%=10;
          v1[i]='0'+d;
     }
     while(c)
     {
          v1[i]='0'+(c%10);
          c/=10;
          i++;
     }
     v1[i]='\0';
     v2[l2]='\0';
}

/*This function subtracts two numbers represnted using string*/
void subs(char v1[], char v2[])
// v1=v1-v2;
{
     int i,d,c=0;
     int l1=strlen(v1);
     int l2=strlen(v2);
     for(i=l2;i<l1;i++)
          v2[i]='0';
     for(i=0;i<l1;i++)
     {
          d=(v1[i]-'0'-c)-(v2[i]-'0');
          if(d<0)
          {
               d+=10; 
               c=1;
          }
          else c=0;
          v1[i]='0'+d;
     }
     v2[l2]='\0';
     i=l1-1;
     while(i>0 && v1[i]=='0') 
          i--;
     v1[i+1]='\0';
}

/*This function divides a number represented using string by a constant*/
int divi(char v[], int q)
// returns the reminder
{
     int i,l=strlen(v);
     int c=0,d;
     for(i=l-1;i>=0;i--)
     {
          d=c*10+(v[i]-'0');
          c=d%q; d/=q; v[i]='0'+d;
     }
     i=l-1;
     while(i>0 && v[i]=='0') 
          i--;
     v[i+1]='\0';
     return c;
}
/*This function reverses the number*/
void rev(char v[]) 
{
     int l=strlen(v);
     int i; char cc;
     for(i=0;i<l-1-i;i++)
     {
          cc=v[i];v[i]=v[l-1-i];v[l-i-1]=cc;
     }
}

/*All the above codes are predefined given in the pdf link above on Pg no. 25*/

int main() {
     char a[102],b[102];
     for(int i=0; i<10 ;++i)
     {
          /*Inputing numbers as strings*/
          gets(a);
          gets(b);
          
          /*We can apply the above functions
	  only if the numbers are represented 
   	  in reverse manner*/ 
          rev(a);
          rev(b);
         
          /*Adding both numbers*/ 
          add(a,b);

          /*we divide to get one answer*/
          divi(a,2);
         
          /*Reverse and output answer*/ 
          rev(a);
          puts(a);
          
          /*To calculate further, we need to 
	  again reverse the number*/ 
          rev(a);
          subs(a,b);

          /*Reverse and output second answer*/  
          rev(a);
          puts(a);
          
          
     }
     return 0;
}

Spoj FENCE1 solution

Spoj FENCE1 solution. Spoj Build a Fence solution.

Category: AdHoc

In this question, we are given the length of the fence, and we need to maximise the area enclosed by it.

The fence will enclose maximum are when it is put in the form of semi-circle.

Formula:

πR=L

that is, R=L/π.

The area is given by πR2, substituting R from above, we get,
Area= (L*L)/(2*π)   as the area will be semicircular in shape.

Here is the working code:

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

int main() {
     int num;
     scanf("%d",&num);
     while(num)
     {
          float res=0;
          res=(1/2.0)*(num*num)*(1/3.1415926);
          printf("%.2f\n",res);
          scanf("%d",&num);	
     }
     return 0;
}

Spoj LASTDIG2 Solution

Spoj LASTDIG2 Solution. Spoj The last digit re-visited solution.

Category: Number Theory

The solution is similar to the LASTDIG solution, but here A can have <=6000 digits.

What we do here is, we consider A as a character array, or string. We assign a new integer C with the last character of A, (this is equivalent to taking A%10).
Then we apply the same Modular Exponentiation on C^B%10.

Here is the working code:

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

//ModularExponentiaion
int ModEx(int x,long long n,int p=10)
{
       int ans=1,temp=x%p;
       while(n)
       {
              if(n&1) // to check if last bit is 1 or not
              {
                     ans=(ans*temp)%p;
              }
              n>>=1;
              temp=(temp*temp)%p;
       }
       return  ans;
}

int main() {
     long long b;
     int t;
     string a;
     scanf("%d",&t);
     while(t--)
     {
          cin>>a;
          scanf("%lld",&b);
          /*getting the last digit*/
          int c=a[a.length()-1]-'0';
          printf("%d\n",ModEx(c,b));
     }
     return 0;
}

 

Spoj LASTDIG solution

Spoj LASTDIG solution. Spoj THE LAST DIGIT solution.

Category: Number Theory

In this question, we need to find  the last digit of A^B.
For finding the last digit of any number we take its modulus with 10,

Applying this fact here, we need to find A^B%10 . Thus, this is a question of Modular Exponentiation.

Here is the working code:

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

//ModularExponentiaion
int ModularExponentiaion(int x,long long n,int p=10)
{
       int ans=1,temp=x%p;
       while(n)
       {
              if(n&1) // to check if last bit is 1 or not
              {
                     ans=(ans*temp)%p;
              }
              n>>=1;
              temp=(temp*temp)%p;
       }
       return  ans;
}

int main() {
     long long b;
     int t,a;
     scanf("%d",&t);
     while(t--)
     {
          scanf("%d %lld",&a,&b);
          printf("%d\n",ModularExponentiaion(a,b));
     }
     return 0;
}

Spoj ONP solution

Spoj ONP solution. Spoj Transform the Expression solution.

Category: AdHoc
Uses: stack

This question involves conversion of Infix to Postfix expression.

Algorithm:

  1. Print operands as they arrive.
  2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto the stack.
  3. If the incoming symbol is a left parenthesis, push it on the stack.
  4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until you see a left parenthesis. Discard the pair of parentheses.
  5. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
  6. If the incoming symbol has equal precedence with the top of the stack, use association. If the association is left to right, pop and print the top of the stack and then push the incoming operator. If the association is right to left, push the incoming operator.
  7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop the stack and print the top operator. Then test the incoming operator against the new top of stack.
  8. At the end of the expression, pop and print all operators on the stack. (No parentheses should remain.)

For example and detailed explanation refer here.

Here is the working code:

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

int i=0,j=-1; 
int op(char c)
{ 
     int j; 
     switch(c) 
     {
          case '^':return 5;
          case '/':return 4; 
          case '*':return 3; 
          case '+':return 2; 
          case '-':return 1; 
          default : return 0; 
     }
} 

int main()
{ 
     int k,n; 
     string a;
     scanf("%d",&n); 
     char waste;
     scanf("%c",&waste); // to take care of enter key
     
     for(k=0;k<n;++k) 
     {
          stack<char> b;
          getline(cin,a);
          i=0;
          j=-1;
          while(a[i]!='\0')
          { 
               if(((a[i]>=65) && (a[i]<=90)) || ((a[i]>=97) && (a[i]<=122)))
                    printf("%c",a[i++]); 
               else 
               {
                    if(a[i]=='\0')
                         break;
                    else if( a[i]!='(' && a[i]!=')') 
                    {
                         while(op(a[i]) <= op(b.top()) && (b.top()!='(') && j!=-1) 
                         {
                              printf("%c",b.top()); 
                              b.pop();
                         }	
                         b.push(a[i++]); 
                    } 
                    else if(a[i]=='(') 
                         b.push(a[i++]);
                    else if(a[i]==')') 
                    {
                         while(b.top()!='(') 
                         {
                              printf("%c",b.top());
                              b.pop();
                              if(j<0) 
                                   break;
                         }
                         if(b.top()=='(') 
                              b.pop();
                         i++;
                    }
               }
          }
     printf("\n"); 
     } 
     return 0; 
}