Subsequence Weighting

This is my first post on this blog. To get things started, I will share an interesting problem I found a while back on HackerRank.

The solution is pretty obvious for people who are familiar with segment tree or BIT. The easiest implementation to solve this would be BIT, which takes O(n log n) in this case. The solution is suffice since n\leq150000.

The solution which I will explain is not about former solution but using map function from C++ only. The first time I read about the problem, I still hasn’t grasped knowledge about those advanced data structure. I was thinking how I could project the problem to increasing value of stack.

There are few pruning that can be used if the stack consist of value and weight (increasing in value). If the value keeps increasing, the weight in element must be at least larger than the element below (smaller value) to achieve optimum result. If the property is maintain every insertion of element, it will guarantee that the weight in the top of stack will be the maximum. The problem is sometimes the element may be inserted in the middle of the stack.

The only data structure that provides that feature is map. The lookup for previous element (lower value) takes O(log n). If above element has (larger value) less weight than current element, the above element needs to be removed to maintain the property. The deletion takes O(log n). The total complexity result in O(n log n)

#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <utility>
#include <string>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
using namespace std;
// template

// abbreviations
#define vi vector <int>
#define ii pair <int, int>
#define a first
#define b second
#define vii vector <ii>
#define mii map <int, int>
#define mll map <long long, long long>
#define que queue
#define pque priority_queue
#define stk stack
#define lsone(value) (value)&(-value)

typedef unsigned long long ull;
typedef long long ll;

int main() {
    // freopen("subsequence-weighting.in", "r", stdin);
    int nt;
    scanf("%d", &nt);
    while (nt--) {
        int n;
        scanf("%d", &n);
        vector<pair<ull, ull> > seqs(n);
        for (int it = 0; it < n; ++it)
            scanf("%llu", &seqs[it].first);
        for (int it = 0; it < n; ++it)
            scanf("%llu", &seqs[it].second);


        map<ull, ull> maxWeight;

        vector<pair<ull, ull> >::iterator curr = seqs.end();
        for (advance(curr, -1); curr >= seqs.begin(); --curr) {
            ull key = curr->first;
            ull val = curr->second;
            
            map<ull, ull>::iterator higher = maxWeight.upper_bound(key);
            if (higher != maxWeight.end()) // there is no higher key
                val += higher->second;

            if ((maxWeight.count(key)) and (maxWeight[key] >= val))
                continue;

            maxWeight[key] = val;

            map<ull, ull>::iterator lower;
            while ((lower = maxWeight.lower_bound(key)) != maxWeight.begin()) {
                advance(lower, -1);
                if (lower->second < val)
                    maxWeight.erase(lower);
                else
                    break;
            }
        }
        printf("%llu\n", maxWeight.begin()->second);
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s