SPOJ PROBLEM 95: STREET PARADE (STPAR)

Problem Link 

Done using stack 

Logic is to take an test array and make operations to make an series of 1,2,3,4...........
if possible!!!!

Code::

#include <iostream>
#include<stack>
#define MAX 1001
using namespace std;

int main() {
    int n;
    stack<int> s;      
    cin>>n;
    while(n!=0)
    {
    int arr[MAX]={0},test[MAX]={0};
    while(!s.empty())   s.pop();   // clear the stack
    for(int i=1;i<=n;i++)    cin>>arr[i];
    int j=0;
    int num=1;
    
     for(j=1;j<=n;j++)
    {
           if(arr[j]==num)      // checked in array if number is present
              {
                  test[num++]=arr[j];
                  continue;
              }
            while(!s.empty() && s.top()==num)  //checked at the top of stack if num is present
            {
                test[num++]=s.top();
                s.pop();
            }
            s.push(arr[j]);
    }
    while(s.size()!=0)         // making the stack empty at the last
    {
        test[num++]=s.top();
        s.pop();
    }
    int flag=0;
    for(int k=1;k<=n;k++)      // checking whether array can be modified in the way given 
    {
        //cout<<test[k];
        if(test[k]!=k)   {  flag=1;  break;  }
    }
    if(flag==0)  cout<<"yes"<<endl;
    else   cout<<"no"<<endl;
    cin>>n;
    }
    // your code goes here
    return 0;
}

SPOJ PROBLEM 4343: EMPTY BOXES (EBOXES)

http://www.spoj.com/problems/EBOXES/
 
BRUTE FORCE
MAKE EQUATIONS AND SOLVE IT...

Let intial no. of boxes be N and let X1,X2,...............,X(T) be the no. of selected boxes in T trials

Let K be no. of smaller boxes kept in each larger boxes.

No. of empty boxes would be=:

N -X1 + (K*X1-X2) +   (K*X2-X3)....................+(K*X(T-1)-X(T))+K*X(T)=F

N + K*(X1+X2...........+X(T)) - (X1+X2...........+X(T))=F

(X1+X2............+X(T))=(F-N)/(K-1)

Total no. of boxes would be=:

N+K*(X1+X2...........+X(T))    =>   N+K*((F-N)/(K-1))

SPOJ PROBLEM 9788: Friends of Friends (FACEFRND)

STL simply makes life easier!!!!
used set stl...................
Counted all non duplicates and then subtracted up by no. of friends of Bob

Code#

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

int main() {
    int n;
    cin>>n;
    set<int> myset;
    set<int>::iterator it;
    pair<set<int>::iterator,bool> w;
    w=myset.insert(0);
    if(w.second==true)
          it=w.first;
    for(int i=0;i<n;i++)
    {
          int x;
           cin>>x;
           myset.insert(it,x);
           int num;
           cin>>num;
           for(int j=0;j<num;j++)
           {
                int y;
                cin>>y;
                myset.insert(it,y);
           }
    }
    int count=0;
    for(it=myset.begin();it!=myset.end();it++)
        count++;
    cout<<count-(n+1)<<endl;
    // your code goes here
    return 0;
}

SPOJ PROBLEM 14930: PRINCESS FARIDA (FARIDA)

Easy DP problem!!!

The problem states that it will either accept coins from ith mobnster or leave it...........
It will accept if previous sum was less than the sum of adding coins to previous to previous
sum of coins..........

 Consider dp[n] array for storing no. of coins till ith position(0-based)

So,     dp[0]=arr[0]   //no other option but just to consider it
         dp[1]=max(dp[0],arr[1])
         dp[2]=max(dp[1],arr[2]+dp[0])
         dp[3]=max(dp[2],arr[3]+dp[1])
         .
         .
         .
         dp[i]=max(dp[i-1],arr[i]+dp[i-2])

Testcase#1:
1 3 6 4 5                     
dp[0]=1
dp[1]=3
dp[2]=7
dp[3]=7
dp[4]=12

Answer is: 12

Testcase#2:
1 2 3 4 5
dp[0]=1
dp[1]=2
dp[2]=4
dp[3]=6
dp[4]=9

Answer is: 9