LIS Memo (Intuitive memo(index, msf))

Fastrail08

May 28th, 2025

804

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 3.69 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
//Used for creating hashing key for pair
// struct pair_hash {
// template <class T1, class T2>
// size_t operator()(const pair<T1, T2>& p) const {
// return hash<T1>()(p.first) ^ (hash<T2>()(p.second) << 1);
// }
// };
// Better Hashing algo than XOR pair hash above
// Used in CP/online judges to avoid TLE
// Better spread out hash keys, so less chaining
struct pair_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(pair<int, int> p) const {
uint64_t hash1 = splitmix64(p.first);
uint64_t hash2 = splitmix64(p.second);
return hash1 ^ (hash2 << 1);
}
};
// Recursive Code for LIS
int getLIS2(int level, int msf, string psf, vector<int> &v){
if(level >= v.size()){
// as we only created the valid subsequences by checking before a call, we can directly take the maximum length of subsequence generated.
cout << psf << '\n';
return 0;
}
//only include when v[level] > msf (A condition needed to always have increasing subsequence, we can only include those v[level] which are greater than those which are already in the current subsequence, or greater than maximum so far of the current subsequence)
int sizeOfSubInc = 0, sizeOfSubExc = 0;
if(v[level] > msf){
sizeOfSubInc = 1 + getLIS2(level + 1, v[level], psf + to_string(v[level]) + " ", v);
}
//exclude (exclusion does not affect our validity of subsequence; it should always increase, as no new item was included)
sizeOfSubExc = getLIS2(level + 1, msf, psf, v);
return max(sizeOfSubExc, sizeOfSubInc);
}
// MEMO CODE using HASH Table
int getLIS2Memo(int level, int msf, vector<int> &v, unordered_map<pair<int, int>, int, pair_hash> &memo){
if(level >= v.size()){
// as we only created the valid subsequences by checking before a call, we can directly take the maximum length of subsequence generated.
return 0;
}
//memo check
if(memo.count(make_pair(level, msf)) > 0){
return memo[make_pair(level, msf)];
}
//only include when v[level] > msf (A condition needed to always have increasing subsequence, we can only include those v[level] which are greater than those which are already in the current subsequence, or greater than maximum so far of the current subsequence)
int sizeOfSubInc = 0, sizeOfSubExc = 0;
if(v[level] > msf){
sizeOfSubInc = 1 + getLIS2Memo(level + 1, v[level], v, memo);
}
//exclude (exclusion does not affect our validity of subsequence; it should always increase, as no new item was included)
sizeOfSubExc = getLIS2Memo(level + 1, msf, v, memo);
return memo[make_pair(level, msf)] = max(sizeOfSubExc, sizeOfSubInc);
}
int main() {
// your code goes here
int n;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++){
cin >> v[i];
}
// cout << getLIS2(0, INT_MIN, "", v) << '\n';
//Memo call
//As our subproblem is uniquely identified with memo(level, msf), we need to create a hash with
//key = {level, msf} and int to store the LIS for that subproblem
unordered_map<pair<int, int>, int, pair_hash> memo;
// reserve space before execution so that less rehashing is required.
// 1 << 19 = 524288, reserve a bucket of this size (~ 5 lakh unique entries possible, to avoid rehashing with small bucket)
memo.reserve(1 << 19);
cout << getLIS2Memo(0, INT_MIN, v, memo) << '\n';
}

Add Comment

Please, Sign In to add comment