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;

}