Light OJ: 1421 – Wavio Sequence

0

Problem Link : http://lightoj.com:81/volume/problem/1421


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int ara[100006];
int lis[100005];
int lds[100005];
int temp[100005];

void LIS(int n)
{
    loop(i,n+5) temp[i]=infinity;
    temp[0]=-infinity;
    int len=0;
    for(int i=0; i<n; i++)
    {
        int lo=0,hi=len;
        while(lo<=hi)
        {
            int mid=(lo+hi)/2;
            if(temp[mid]<ara[i])
                lo=mid+1;
            else
                hi=mid-1;
        }
        temp[lo]=ara[i];
        lis[i]=lo;
        if(lo>len) len++;
    }
}

void LDS(int n)
{
    loop(i,n+5) temp[i]=infinity;
    temp[0]=-infinity;
    int len=0;
    for(int i=0; i<n; i++)
    {
        int lo=0,hi=len;
        while(lo<=hi)
        {
            int mid=(lo+hi)/2;
            if(temp[mid]<ara[i])
                lo=mid+1;
            else
                hi=mid-1;
        }
        temp[lo]=ara[i];
        lds[i]=lo;
        if(lo>len) len++;
    }
}


int main()
{

//     freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int n;
    int t;
    sf(t);
    TEST_CASE(t)
    {
        sf(n);
        loop(i,n) sf(ara[i]);
        LIS(n);
        reverse(ara,ara+n);
        LDS(n);
//        loop(i,n) cout<<lis[i]<<" ";
//        cout<<endl;
//        loop(i,n) cout<<lds[i]<<" ";
//        cout<<endl;
        reverse(lds,lds+n);
        int ans=0;
        for(int i=0; i<n; i++)
        {
            ans=max(ans,(2*min(lis[i],lds[i]))-1);
        }
        PRINT_CASE;
        printf("%d\n",ans);
    }

    return 0;
}


UVa 10131 – Is Bigger Smarter?

0

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1072

Solution Idea:

Given some pairs where in each pair fist integer is weight and second integer is IQ. Now we have to select some pairs from the given pairs where –

W[a[1]] < W[a[2]] < … < W[a[n]]

and  S[a[1]] > S[a[2]] > … > S[a[n]]

Here n is the number of pairs which we select and a[] contain the index of the pairs which is given in the input order.

After reading the problem statement we can understand that this is a LIS(Longest Increasing Sub-sequence) problem. Generally we can calculate LIS of an array of integers by comparing the values. But In this case we need one first element of the pair in strictly increasing order and second element of the pair in strictly decreasing order. So for solving this problem we can sort one element of the input pairs initially in a order which we want in the output and run LIS on all the input pairs.

In this solution I am sorting the IQ elements in Descending Order because we want it in the output in descending order. After sorting we need to run LIS for every input pair. We need to do this because we have to calculate the maximum LIS and for this we are taking every input pair as the staring element of the LIS and we are taking the maximum one as our ans.

Note that in the problem statement the inequalities are “strict”. Therefore within LIS algorithm, we need to check that the next weight in the sequence is greater than the previous weight, and the next IQ is less than the previous one.

LIS algorithm tutorial in Bengali is Here.


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

struct data
{
    int w, s, id;
};

vector<data>v;

int n=0;

int dp[1005];
int path[1005];

bool cmp(data a, data b)
{
    return a.s>b.s;

}

int LIS(int idx)
{

    int &ret=dp[idx];
    if(ret!=-1) return ret;

    int maxi=0;

    for(int i=idx+1;i<n;i++)
    {
        if(v[i].w>v[idx].w)
        {
            if(LIS(i)>maxi)
            {
                maxi=LIS(i);
                path[idx]=i;
            }
        }
    }

    return dp[idx]=1+maxi;
}

void path_print(int idx)
{
    if(idx==-1) return;
    printf("%d\n",v[idx].id);
    path_print(path[idx]);
}


int main()
{
//    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int a,b;
    while(sff(a,b)==2)
    {
        data temp;
        temp.w=a;
        temp.s=b;
        temp.id=n+1;
        v.pb(temp);
        n++;
    }


    sort(all(v),cmp);
    ms(dp,-1);
    ms(path,-1);

    int ans=-1,start;

    loop(i,n)
    {
        if(LIS(i)>ans)
        {
            ans=LIS(i);
            start=i;
        }
    }
    printf("%d\n",ans);
    path_print(start);

    return 0;
}

UVa 481 – What Goes Up

0

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=422

Solution Idea:

This is a LIS problem. But in this problem input size/number of elements in the list is not mentioned. So we have to use faster solution like NlogK algorithm because if the input list is large then O(n^2) solution can give a TLE. So in this problem we use LIS NlogK approach. We need to just run the algorithm and print the solution.


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

vector<int>v,print_ans;
int n=0;

int L[1000000];
int I[1000000];

int LIS_NlogK()
{
    loop(i,n+2) I[i]=inf;
    I[0]=-inf;

    int length=0;

    for(int i=1;i<=n;i++)
    {
        int low=0, hi=length, mid;

        while(low<=hi)
        {
            mid=(low+hi)/2;
            if(v[i]>I[mid])
                low=mid+1;
            else
                hi=mid-1;
        }

        I[low]=v[i];
        L[i]=low;
        length=max(length,low);
    }
    return length;
}


int main()
{
//    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    v.pb(-100000);

    int a;
    while(sf(a)==1)
    {
        n++;
        v.pb(a);
    }

    int ans=LIS_NlogK();

    int i;

    int temp=ans;

    for(i=n;i>0;i--)
    {
        if(L[i]==temp)
        {
            temp--;
            print_ans.pb(v[i]);
            break;
        }
    }

    for(--i;i>0 && temp ;i--)
    {
        if(v[i]<print_ans.back() && L[i]==temp)
        {
            print_ans.pb(v[i]);
            temp--;
        }
    }

    printf("%d\n-\n",ans);

    for(i=ans-1;i>=0;i--)
        printf("%d\n",print_ans[i]);

    return 0;
}


UVa 231 – Testing the CATCHER

0

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=167

Solution Idea:

This is a straight forward LIS problem. Just take input and calculate the Longest increasing sub-sequences and print the answer.

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

vector<int>v;
int dp[100005];

int LIS(int u)
{
    int &ret=dp[u];

    if(ret!=-1) return ret;

    int maxi=0;

    for(int i=u+1;i<SZ(v);i++)
    {
        if(v[i]<=v[u])
        {
            maxi=max(maxi,LIS(i));
        }
    }
    return ret=1+maxi;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int a;
    int z=0;
    while(sf(a) && a!=-1)
    {
        if(z) pf("\n");
        v.pb(a);
        while(sf(a) && a!=-1)
        {
            v.pb(a);
        }
        ms(dp,-1);
        int ans=0;

        for(int i=0;i<SZ(v);i++)
            ans=max(ans,LIS(i));
        pf("Test #%d:\n",++z);
        pf("  maximum possible interceptions: %d\n",ans);
        v.clear();
    }
    return 0;
}

Another Iterative solution of this problem is here —


#include <bits/stdc++.h>
 
#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 100100
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,a) for(int i=0;i<a;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int
 
using namespace std;
int L[1000000];
int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int n;
    vector<int>v;
    int z=0;
    while(cin>>n && n!=-1)
    {
        if(z)
            cout<<endl;
        v.pb(100000);
        v.pb(n);
        int num;
        while(cin>>num &&num!=-1)
            v.pb(num);
        int sz=SZ(v);
        for(int i=0;i<=sz;i++)
            L[i]=1;
        int ans=1;
        for(int i=1;i<sz;i++)
        {
            for(int j=i+1;j<sz;j++)
                if(v[j]<v[i] && L[i]+1 > L[j])
                    ans=max(ans,++L[j]);
        }
        pf("Test #%d:\n",++z);
        cout<<"  maximum possible interceptions: "<<ans<<endl;
        v.clear();
    }
    return 0;
}