COMPILER: Compilers and parsers

COMPILER: Compilers and parsers

Link for the problem: COMPILER

SOLUTION:

Let S be a valid substring of the given string. Then,
1.) '<'+S+'>' will be a valid substring.
2.) Similarly, if S1 is also a valid substring and S and S1 are connected then S+S1 will be a valid substring.
In order to solve the problem, first, we find all valid substring.
To find valid substring we use a stack.

i) If the s[i] is '<', then push its index in the string.
ii) If s[i] is '>' and stack is not empty, then substring from the top stack index to the current ith index will be a valid substring.
Implementing above with an array of length of the input string, where the initial value of each element will be '-1', and if there is a valid substring from index i to index j, then arr[i] =j.
As problem ask us to find longest prefix substring, we have to start from index i=0, as if arr[i]!=-1 then there is a valid substring from i to arr[i], Now we check for index i=a[i]+1 in similar manner.


CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        string s;
        cin>>s;
        stack <int> st;
        int i,j,k,l;
        l=s.size();
        int a[l]={-1};
        memset(a,-1,sizeof(a));
        for(i=0;i<l;i++)
        {
            if(s[i]=='<')
            {
                st.push(i);
            }
            else
            {
                if(st.size())
                {
                    a[st.top()]=i;
                    st.pop();
                }
            }
        }
        int sm=0;
        for(i=0;i<l;)
        {
            if(a[i]!=-1)
            {
                sm+=a[i]-i+1;
                i=a[i]+1;
            }
            else
            break;
        }
        printf("%d\n",sm);
    }
    return 0;

}

ONP : Transform the Expression

ONP: Transform the Expression


Link for the Problem: ONP


SOLUTION:

In this problem, we have to convert given infix expression to postfix expression. To know more about postfix expression follow the link: Postfix wiki.

IMPLEMENTATION:

In the input string, we will encounter four types of characters-
1.) Opening bracket '('
2.) Closing bracket ')'
3.) Operands
4.) Operators {+,-,*,/}
To solve this problem, we will traverse from left in the string.
i) If the character is '(', Push it in the stack.
ii) If it is an operand character, then print it.
iii) If it is an operator, the push it in the stack.
iv) if it is ')' i.e. closing bracket, then print the top of the stack and pop the stack until we get '(' as top.
     pop '(' also from the stack.


CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        string s;
        cin>>s;
        int l;
        l=s.size();
        stack <char> st;
        int i,j,k;
        for(i=0;i<l;i++)
        {
            if(s[i]=='(')
            {
                st.push(s[i]);
            }
            else if(s[i]>='a'&&s[i]<='z')
            {
                cout<<s[i];
            }
            else if(s[i]==')')
            {
                while(st.top()!='(')
                {
                    cout<<st.top();
                    st.pop();
                }
                st.pop();
            }
            else
            st.push(s[i]);
        }
        cout<<endl;
    }
    return 0;

}

STPAR : Street Parade

STPAR : Street Parade

Link for the Problem : STPAR

SOLUTION:

In the above problem, you have to find whether is it possible to arrange the given sequence of number in increasing sorted order or not by using the side lane. As from side lane, the vehicle entering first will leave in the last, so it follows LIFO order which makes it stack.

IMPLEMENTATION:

1.) Initialize a variable j=1;
2.) Now traverse in the array, for the ith element, first push it in the stack.
3.) While top of the stack equals j, Now pop the stack and increase j by 1.
4.) After processing above for every element of the sequence, if there is any element present in the stack, then the answer will be 'no'.
else if stack is empty then the answer will be 'yes'.

CODE:
#include <bits/stdc++.h>
using namespace std;
int main()
{
    while(1)
    {
        int n;
        scanf("%d",&n);
        if(n==0)
        break;
        int a[n],i,k;
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        stack <int> st;
        int f=0,j=1;
        for(i=0;i<n;i++)
        {
            st.push(a[i]);
            while(st.size())
            {
                if(st.top()==j)
                {
                    j++;
                    st.pop();
                }
                else
                break;
            }
        }
        if(st.size()>0)
        printf("no\n");
        else
        printf("yes\n");
    }
    return 0;

}

JNEXT : Just Next !!!

JNEXT : Just Next !!!

Link for the problem: JNEXT

Problem:
The problem asks you to print the just next permutation of the given sequence of digits. If next permutation is not possible then you have to print '-1'.

Solution:

> There will be always a possible next permutation, if for any digit at index i there is another greater digit than ith digit and lies to the right of i.
> If the above is not true for any index i, then the answer will be -1, i.e. there is no possible next permutation.
> To find next permutation, we have to find first index i from right.
> After finding above index, swap it with the element which lies to the right and is just greater than that element.
(see code for more clarification)
> After swapping, sort rest right part of the sequence (excluding that element).
>print the sequence.

Code:
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int a[n],i,j,k;
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        int f=0;
        for(i=n-1;i>=1;i--)
        {
            if(a[i]>a[i-1])
            {
                f=1;
                break;
            }
        }
        if(f){
        int m=i;
        for(j=i+1;j<n;j++)
        {
            if(a[j]<a[m]&&a[j]>a[i-1])
            m=j;
        }
        k=a[i-1];
        a[i-1]=a[m];
        a[m]=k;
        sort(a+i,a+n);
        for(i=0;i<n;i++)
        printf("%d",a[i]);}
        else
        printf("-1");
        printf("\n");
    }
    return 0;

}


STL Method:

This problem can be solved by using STL in C++. The function used is next_permutation(). If Next permutation is not possible then it returns 'False' else 'True' and you have to just print the sequence.
(see Code)

CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
    int n;
    scanf("%d",&n);
    int a[n],i,j,k;
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    bool v=next_permutation(a,a+n);
    if(v==false)
    printf("-1");
    else
    {
        for(i=0;i<n;i++)
        printf("%d",a[i]);
    }
    printf("\n");
}
return 0;

}

CSUB : Count Substrings

CSUB : Count Substrings

Link for the problem: CSUB

Solution:

To solve this problem, you have to focus on two points.
1.) A substring of a single character '1' is a valid string.
2.) For every character '1' in the string, every other '1' occurring before will make a valid substring with it.
So from these two points, the total number of valid substring would be 1+2+3+...+k. Where k is the total number of 1s in the string. So it is k*(k+1)/2.

Code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
      int n;
      scanf("%d",&n);
      char s[100001];
     scanf(" %s ",s);
     long long int i,j,k,c=0;
     for(i=0;i<n;i++)
     {
         if(s[i]=='1')
         c++;
     }
     printf("%lld\n",(c*(c+1))/2);
    }
    return 0;

}

COPS : Cops and the Thief Devu

COPS : Cops and the Thief Devu
Link for the problem: COPS

Solution:

We will find the extremum for every cop i.e. leftmost and the rightmost house in which a cop can search for thief Devu.
We can use a colouring method to solve this problem. Let an array of size 101 so that it has index 1 and 100 in it.
Initialize it with zeros i.e. it is uncoloured. We have to colour the array for every cop. To do this in O(n) complexity, colour the leftmost element by -1 and element after rightmost element by 1.
 So that when we do the cumulative sum in the array, the elements in the range of cop will be negative and other will be zero.
So summing for every cop, if the given element is negative then the cop can reach that house and if it is 0 or positive, then no cop can reach that house.

Code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
      int m,x,y;
      scanf("%d %d %d",&m,&x,&y);
      int a[m],i,j,k,d=x*y;
      for(i=0;i<m;i++)
      scanf("%d",&a[i]);
      int b[102]={0};
      for(i=0;i<m;i++)
      {
          int m1,m2;
          m1=max(a[i]-d,1);
          m2=min(a[i]+d+1,101);
          b[m1]+=-1;
          b[m2]+=1;
      }
      int c=0;
      for(i=1;i<=100;i++)
      {
          b[i]=b[i-1]+b[i];
          if(b[i]>=0)
          c++;
      }
      printf("%d\n",c);
    }
    return 0;

}

FRGTNLNG : Forgotten Language

FRGTNLNG : Forgotten Language
Link for Problem: FRGTNLNG

Solution:
In the problem you just have to apply a simple brute force approach.

Code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
       int n,k,i,j;
       scanf("%d %d",&n,&k);
       string a[n];
       int b[n]={0};
       for(i=0;i<n;i++)
       cin>>a[i];
       vector <string> v;
       for(i=0;i<k;i++)
       {
           int l;
           scanf("%d",&l);
           for(j=1;j<=l;j++)
           {
               string s;
               cin>>s;
               v.push_back(s);
           }
       }
      int l=v.size();
       for(i=0;i<n;i++)
       {
           for(j=0;j<l;j++)
           {
               if(a[i]==v[j])
               {
                   b[i]=1;
                   break;
               }
           }
       }
       for(i=0;i<n;i++)
       {
           if(b[i]==1)
           printf("YES ");
           else
           printf("NO ");
       }
       printf("\n");
    }
    return 0;

}

RAINBOWA: Chef and Rainbow Array

RAINBOWA: Chef and Rainbow Array
Link for the Problem: RAINBOWA

Problem:
In the problem, you have to find if the given array is a Rainbow Array or not.

Solution:
Consider the consecutive similar elements as bundles. Each bundle will consist of 2 characteristics. First the number of similar elements in that bundle and the second, value of similar elements in that bundle.
We will handle these bundles by vector pair. It can be done with other methods too. If the size of the vector is not equal to 13 then acc to problem array will be not a Rainbow array. And the vector should be a palindrome.

Code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int a[n],i,j,k;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        vector<pair<int,int>> v;
        int c=1,vl=a[0];
        for(i=1;i<n;i++)
        {
            if(a[i]!=a[i-1])
            {
                v.push_back(make_pair(c,vl));
                c=1;
                vl=a[i];
            }
            else
            {
                c++;
            }
        }
        v.push_back(make_pair(c,vl));
        int f=0;
        if(v.size()==13&&v[6].second==7)
        {
            for(i=0;i<6;i++)
            {
                if(v[i].first!=v[12-i].first||v[i].second!=i+1||v[12-i].second!=i+1)
                {
                    f=1;
                    break;
                }
            }
        }
        else
        {
            f=1;
        }
        if(f==0)
        printf("yes\n");
        else
        printf("no\n");
    }
    return 0;
}

SALARY: The Minimum Number Of Moves

SALARY: The Minimum Number Of Moves
Link for the problem: SALARY

Problem:
In the problem, there is an array where ith element denotes salary of the ith worker. Your task is to equalize all salary in minimum no of operations. In one operation we can select ith salary, and increasing every salary by 1 except the selected one. We can select different worker's salary in different operations.

Solution:

The problem can be solved by applying the greedy approach.
1) First sort the array in ascending order.
2) Now select the lowest element i.e. a[0] and make it equal to a[1]
   i.e. we are selecting a[1] in every operation until a[0] becomes equal to a[1]. Update other elements accordingly.
3) now select a[2] apply the operation until a[1] becomes equal to a[2]
  -> This will make a[0],a[1], and a[2] equal
4) Similarly doing this up to a[n-1]
5) counting the number of operation every time.

This is O(n2) approach. This problem can also be solved in O(n).

Code:
Below is the code with O(n) complexity:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int  t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int a[n],i,j,k;
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        sort(a,a+n);
        int p1=a[0],p2,c=0,s=0;
        for(i=1;i<n;i++)
        {
            s=s+(a[i]+c-a[i-1]);
            c=c+a[i]-a[i-1];
        }
        printf("%d\n",s);
    }
    return 0;
}

CNOTE: Chef and Notebooks

CNOTE: Chef and Notebooks
Link for the problem: CNOTE

Solution:
Chef wants to write X pages long poetry and there are Y pages left in the current notebook. So he needs to buy a notebook at least X-Y pages long notebook. He has only K rubles left.
=> We will try to find a notebook having at least X-Y pages and price not greater than K.
i) if we get the notebook print "LuckyChef"
ii) else print "UnluckyChef"

Code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int x,y,k,n,l,i,f=0;
        scanf("%d %d %d %d",&x,&y,&k,&n);
        l=x-y;
        for(i=0;i<n;i++)
        {
           int p,c;
           scanf("%d %d",&c,&p);
           if(p<=k&&c>=l&&f==0)
           {
               f=1;
               printf("LuckyChef\n");
           }
        }
        if(f==0)
        printf("UnluckyChef\n");
    }
    return 0;

}

LECANDY: Little Elephant and Candies

Link for the Problem: LECANDY

This is the first problem of CCDSAP prepare.

Problem:

In the problem, you will be given the number of elephants and total no of candies in the zoo and an array of number where ith element denotes the number of candies by which ith elephant will be happy. You have to tell whether all the elephant can be happy or not.

Solution:

1. Take the summation of candies required by each elephant. Let it be S.

2. i) If it is less than or equal to total no of candies then print 'Yes'.

    ii) Else print 'No'.

Code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,c;
        cin>>n>>c;
        int a[n],i,j,s=0;
        for(i=0;i<n;i++)
        {
            cin>>j;
            s+=j;
        }
        if(s>=c)
        printf("Yes\n");
        else
        printf("No\n");
    }
    return 0;
}