CHEFST: Chef and the stones

CHEFST: Chef and the stones

Link for the problem: CHEFST

SOLUTION:

For a given max possible no of stones that can be removed from each pile is m+(m-1)+(m-2)+...3+2+1. Which is m*(m+1)/2.  Let it be S. So we can see that between 1 and S any no of stones can be removed.

CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long int n1,n2,m,n,s;
        cin>>n1>>n2>>m;
        s=(m*(m+1))/2;
        n=min(n1,n2);
        if(s>n)
        printf("%lld\n",max(n1,n2)-n);
        else
        {
            printf("%lld\n",n1+n2-2*s);
        }
    }
    return 0;

}

MAXDIFF: Maximum Weight Difference

MAXDIFF: Maximum Weight Difference

Link for the problem: MAXDIFF

SOLUTION:

All the weights can be divided in to two parts, one having 'k' number of weights and another with 'n-k' weights. We have to minimize one part and maximize another. So first we will  sort the sequence, then summing the minimum number of (either k or n-k) elements which will be carried by son.

CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int  n,k;
        cin>>n>>k;
        int a[n],i,s=0,s1=0,s2=0;
        for(i=0;i<n;i++)
        {
            cin>>a[i];
            s+=a[i];
        }
        sort(a,a+n);
        int m=min(k,n-k);
        for(i=0;i<m;i++)
        {
            s1+=a[i];
        }
        printf("%d\n",s-2*s1);
    }
    return 0;

}

CIELRCPT: Ciel and Receipt

CIELRCPT: Ciel and Receipt

Link for the problem: CIELRCPT

SOLUTION:

We have total price P. To buy min number of menu, we would start buying menu with maximum price if possible. So  we would always make this as our greedy choice.

CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[12],i,j,k;
    for(i=0;i<12;i++)
    {
        a[i]=pow(2,i);
    }
   int t;
   cin>>t;
   while(t--)
   {
       int n,s=0;
       cin>>n;
       for(i=11;i>=0;i--)
       {
          s+=(n/a[i]);
          n=n%a[i];
       }
       printf("%d\n",s);
   }
    return 0;

}

TACHSTCK: Chopsticks

TACHSTCK: Chopsticks

Link for the problem: TACHSTCK

SOLUTION:

Pairs can be formed by just greater or just smaller chopstick for a particular chopstick. So the problem can be solved by just sorting.

CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,d,i,j,k,s=0;
    cin>>n>>d;
    int a[n];
    for(i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);
    for(i=0;i<n-1;)
    {
        if(a[i+1]-a[i]<=d)
        {
            s+=1;
            i+=2;
        }
        else
        i++;
    }
    cout<<s<<endl;
    return 0;

}

C. Longest Regular Bracket Sequence

C. Longest Regular Bracket Sequence

Link for the problem:C. Longest Regular Bracket Sequence

Solution:
Every regular bracket sequence can be determined by using a stack.
Let S be the input string and S1 and S2 be the regular bracket substring. 
Then-
1.) '('+S1+')' will be a regular bracket sequence.
2.) S1+S2 will be regular bracket sequence;

CODE:

#include <bits/stdc++.h>

using namespace std;

int main()

{

    string s;

    cin>>s;

    int i,j,k,l;

    int a[1000001]={0};

    l=s.size();

    stack< int> st;

    vector <int> v;

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

    {

        if(s[i]=='(')

        {

            st.push(i);

        }

        else

        {

            if(st.size()){

            a[i+1]+=-1;

            a[st.top()]+=1;

            st.pop();}

        }

    }

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

    {

        a[i]=a[i-1]+a[i];

    }

    int sm=0,mx=0;

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

    {

        if(a[i]>0)

        {

            sm++;

        }

        else

        {

            //printf("Y\n");

            if(sm>mx)

            mx=sm;

            v.push_back(sm);

            sm=0;

        }

    }

    if(sm>mx)

    mx=sm;

    v.push_back(sm);

    l=v.size();

    sm=0;

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

    {

        if(v[i]==mx)

        {

            sm++;

        }

    }

    if(mx)

    printf("%d %d\n",mx,sm);

    else

    printf("0 1\n");

    return 0;

}

B. Alternating Current

B. Alternating Current

Link for the problem: B. Alternating Current


SOLUTION:

This is a direct and easy implementation of stack.
See the code for more explanation.


CODE:

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
int main()
{
    string s;
    int i,k,l;
    cin>>s;
    l=s.length();
    vector<char> v;
    v.push_back(s[0]);
    for(i=1;i<l;i++)
    {
        if(s[i]==v[v.size()-1])
        v.pop_back();
        else
        v.push_back(s[i]);
    }
    if(v.size())
    cout<<"No";
    else
    cout<<"Yes";
    return 0;

}

C. Minimal string

C. Minimal string

Link for the problem: C. Minimal string

SOLUTION:

To solve this problem, we have to do a little precomputation. Let the given string v S and its length be l. Now we make another character array C such that C[i] is the smallest element from i to l-1. The precomputation can be done in O(n) by starting from right end of string and using already computed value.
Now, for every element S[i], there is a C[i].  To solve this problem we use stack.
For every element S[i], we follow operations:-
1.)  If stack is empty, push s[i].
2.) Else, while c[i] is greater than or equal to top of stack, print the top for answer and then pop. Push the s[i].
After processing for all S[i], empty the stack by printing and popping the top.

CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    stack<char> s;
    string s1;
    cin>>s1;
    int l=s1.length(),i,j,k;
    char c[l];
    c[l-1]=s1[l-1];
    for(i=l-2;i>=0;i--)
    {
        c[i]=min(s1[i],c[i+1]);
    }
    for(i=0;i<l;i++)
    {
        while(!s.empty()&&c[i]>=s.top())
        {
                cout<<s.top();
                s.pop();
        }
        s.push(s1[i]);
    }
    while(!s.empty())
    {
        cout<<s.top();
        s.pop();
    }
    return 0;

}

ANARC09A: Seinfeld

ANARC09A: Seinfeld

Link for the problme: ANARC09A

SOLUTION:

Approach for the problem is similar to MMASS and the solution to this problem is here. Problem can be solved by using a stack. Steps involved are:-
1.) If s[i] is '{' then push it in stack.
2.) If s[i] is '}' then there are two conditions, if top of stack is '{' then pop the stack else if stack is empty or top of stack is '}' then push s[i] in stack.
3.) Count the number of '{' and '}' remaining in stack, let it be s1 and s2.
  if s1 and s2 are even, then answer would be (s1+s2)/2.
  else it would be (s1+s2)/2+1.

CODE:

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

}

D. Maximum Xor Secondary

D. Maximum Xor Secondary

Link for the problem:- D. Maximum Xor Secondary

Solution:

As we can see, there is no need to check for every interval. Just care about the first maximum and second maximum interval. While a new element came into the view, pop the top element in the stack, and check the corresponding interval until the new element is greater than the top element in the stack. We can easily see it is correct since we won’t lose the answer as long as it exists.
Time complexity of this solution is O(n).

CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n],i,j,k,mx=0;
    stack<int> st;
    for(i=0;i<n;i++)
    cin>>a[i];
    for(i=0;i<n;i++)
    {
        while(!st.empty())
        {
            mx=max(mx,st.top()^a[i]);
            if(st.top()<a[i])
            st.pop();
            else
            break;
        }
        st.push(a[i]);
    }
    cout<<mx;
    return 0;

}

HISTOGRA : Largest Rectangle in a Histogram

HISTOGRA : Largest Rectangle in a Histogram

Link for the problem: HISTOGRA

SOLUTION:
The hight of rectangles of the histogram is given in the sequence. We have to find the area of the largest possible rectangle in the Histogram. Area of a rectangle is equal to Length*Height.  The height of the largest possible rectangle will be hight of the any given rectangles. So to find the largest possible area, we will find max possible width for every given rectangle. For any given rectangle, when we consider it as forming the largest rectangle, we have to find left limit and right limit up to where the height of the rectangle is less than or equal.
This problem can be solved by using a stack. For every ith rectangle, we have to find left and right index of the rectangle, whose height is less than ith rectangle. Difference between right index and left index will give the possible width for ith rectangle.

IMPLEMENTATION:
Let arr[] be the array of integer denoting heights.
1.) For ith element, if stack is empty push it in the stack.
2.) If stack is not empty, then pop the stack until top is less than ith element. If jth element is popped by ith element then right limit for jth element will be i.
3.) Index of element lying just below ith element in stack will be left limit of ith element.

CODE:

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
int main()
{
    while(1)
    {
      long long int n;
      cin>>n;
      if(n==0)
      break;
      long long int a[n],b[n][2],i,j,k;
      for(i=0;i<n;i++)
      {
          cin>>a[i];
          b[i][1]=-1;
      }
      vector<long long int> v;
      v.push_back(0);
      b[0][0]=-1;
      for(i=1;i<n;i++)
      {
          int sz=v.size();
          
          while(sz>=1)
          {
              if(a[i]<a[v[sz-1]])
              {
                  int t;
                  t=v[sz-1];
                  v.pop_back();
                  b[t][1]=i;
                  sz--;
              }
              else
              break;
          }
          if(!v.size())
          {
              b[i][0]=-1;
          }
          else{
              b[i][0]=v[v.size()-1];
          }
          v.push_back(i);
      }
      for(i=0;i<n;i++)
      {
          if(b[i][1]==-1)
          b[i][1]=n;
      }
      long long int max=0,p;
      for(i=0;i<n;i++)
      {
            p=a[i]*(b[i][1]-b[i][0]-1);
            if(max<p)
            max=p;
      }
      printf("%lld\n",max);
      
    }
    return 0;

}

MMASS : Mass of Molecule

MMASS : Mass of Molecule
Link for the problem: MMASS

SOLUTION:

Mass of Molecule can be determined by knowing the mass of sub-molecules. A submolecule is always lie in between '(' and ')' in the formula and followed by an integer. The integer represents the number of times that submolecule exist in the molecule.
So, to find the mass of a submolecule we use a stack.
We will use following operations in for different characters of string  S : -

1.) If  S[i] is '(', Then push it in the stack. (left boundary of a submolecule)
2.) If it is 'C','O' or 'H' then push its corresponding mass in the stack.
3.) If it is an integer between 2 to 9, Then multiply this to top of stack.
4.) If S[i] is ')', i.e. right boundary of submolecule, then sum up to left boundary of molecule by popping out the stack.
5.) After getting mass of a submolecule, push it in the stack, As it can be part of another submolecule.

After doing all these operations, sum up the values of the stack to get the mass of molecule.

CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    stack <int> st;
    int i,j,k,l;
    l=s.size();
    for(i=0;i<l;i++)
    {
        if(s[i]=='(')
        {
            st.push(s[i]);
        }
        else if(s[i]=='C')
        {
            st.push(12);
        }
        else if(s[i]=='O')
        st.push(16);
        else if(s[i]=='H')
        st.push(1);
        else if(s[i]>='1'&&s[i]<='9')
        {
            k=st.top();
            st.pop();
            st.push(k*(s[i]-'0'));
        }
        else if(s[i]==')')
        {
            int sm=0;
            while(st.top()!='(')
            {
                sm+=st.top();
                st.pop();
            }
            st.pop();
            st.push(sm);
        }
    }
    int sm=0;
    while(st.size())
    {
        sm+=st.top();
        st.pop();
    }
    cout<<sm<<endl;
    return 0;

}

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;

}