Beautiful People | Dynamic programming Set 5

There is a club with N members.This is a very prestigious club, its members are very rich and therefore extraordinary people, so they often extremely hate each other. Strictly speaking, i-th member of the club Mr X hates j-th member of the club Mr Y if Si ≤ Sj and Bi ≥ Bj or if Si ≥ Sj and Bi ≤ Bj (if both properties of Mr X are greater then corresponding properties of Mr Y, he doesn’t even notice him, on the other hand, if both of his properties are less, he respects Mr Y very much).Your task it to invite as many people as possible.

print the maximum number of the people that can be invited to the party and also print numbers of members to be invited in arbitrary order. If several solutions exist, output any one.

Example:
Strength[] = {1, 1, 2, 2}
Beauty[] = {1, 2, 1, 2}

In above case we can invite maximum 2 people with index 1 and 4 i.e {1,1} , {2,2}
So Output is
2
1 4

Solution:
Above problem can be solved using dynamic programming paradigm and specifically using Longest Increasing Subsequence technique.

1) Optimal Sub Structure
Let array member[] contains a members Strength and Beauty factor. D[i] contain the maximum number of people club can invite till index i such that member[i] is part of invitation and memeber[i] is the last element of invitation, then D[i] can be written as

D(i) = { 1 + Max ( D(j) ) } where j < i and D[i] = max{ D[j] +1 }for j < i and Strength[j] < Strength[i] and Beauty[j] < Beauty[i] , if there is no such j then D(i) = 1

To get Maximum number of people we need to return max(D[i]) , where 0 < i < n
and while updating D[i] , take an array P[i] which will store position or index of member which can be invited in party.

Time Complexity : O(n2)

c++ program:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

//Structure to store person informartion
typedef struct person{
    long int s;
    long int b;
    int ind;
    
    person(long int s,long int b,int ind);
} person;

//! where s = strength, b = beauty factor. ind  = index of memeber
person::person(long int s, long int b, int ind):
s(s),b(b),ind(ind)
{}

int compare(const person &a, const person &b) {
    return a.s < b.s;
}

int main( )
{

    vector<person> member;
    member.push_back(person(1,1,0));
    member.push_back(person(1,2,1));
    member.push_back(person(2,1,2));
    member.push_back(person(2,2,3));

    int n = (int)member.size();
    //! Take a array d[] which store maximum number of people can be invited in a party
    vector<long int> d(n,1);
    //! Take array p[] to store position of member invited in a party
    vector<long int> p(n,-1);
    long int max = -1;
    long int bestEnd = -1;
    sort (member.begin(), member.end(), compare);
    for(int i  = 1 ; i < n ;i++) { for(int j = i-1 ; j>=0 ; j--)
        {
            if(((d[j] + 1) > d[i]) and (member[j].b < member[i].b) and (member[j].s < member[i].s))
            {
                d[i] = d[j]+1;
                p[i] = j;
            }
        }
        if(max < d[i])
        {
            max = d[i];
            bestEnd = i;
        }
    }
    cout<<max<<endl;
    if(bestEnd != -1)

    //! print position of members
        while(bestEnd not_eq -1)
        {
            cout<<member[bestEnd].ind+1<<" ";
            bestEnd = p[bestEnd];
        }
        return 0;
}

References:
http://acm.sgu.ru/problem.php?contest=0&problem=199

Site Footer