Longest Monotonic Subsequence via Greedy Array

Core Concept

The "pseudo-monotonic stack" approach for finding longest monotonic subsequences uses a dynamic array that maintains potential candidates for optimal sequence construction. This method efficiently builds the solution in O(n log n) time complexity.

Algorithm Mechanics

For a sequence arr[1..n], we maintain an array tail[] where tail[len] stores the smallest possible ending value for a monotonic subsequence of length len.

For Longest Increasing Subsequence:

• If arr[i] exceeds tail[current_max], it extends the longest sequence
• Otherwise, binary search finds the first element tail[pos] >= arr[i] and replaces it

Key Insights

1. The final tail[] array doesn't necessarily represent an actual subsequence but encodes the optimal structure
2. Replacement strategy ensures future elements have better extension opportunities
3. The binary search target differs based on strictness:
   • Strictly increasing: find first >= (prevents duplicates)
   • Non-decreasing: find first > (allows duplicates)

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

int findLIS(vector<int>& sequence) {
    vector<int> tail;
    for (int x : sequence) {
        auto it = lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) tail.push_back(x);
        else *it = x;
    }
    return tail.size();
}

Probability-Based Dynamic Programming

Problem Characteristics

Models scenarios with equiprobable state transitions where outcomes depend on cumulative probability distributions across multiple steps.

Implementation Approach

Use a DP table where prob[step][value] tracks reachable state counts. When value ranges include negatives, apply offset transformation to ensure valid array indices.

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

const int MAX_STEPS = 32;
const int OFFSET = 61;
const int MAX_BALANCE = 110;

long long stateCount[MAX_STEPS][MAX_BALANCE];
int outcomes[4] = {-1, -2, 0, 1};

int main() {
    int rounds;
    cin >> rounds;
    
    memset(stateCount, -1, sizeof(stateCount));
    stateCount[0][OFFSET] = 1;
    
    for (int step = 0; step < rounds; ++step) {
        for (int balance = 0; balance < MAX_BALANCE; ++balance) {
            if (stateCount[step][balance] == -1) continue;
            
            for (int outcome : outcomes) {
                int nextBalance = balance + outcome;
                if (nextBalance < 0 || nextBalance >= MAX_BALANCE) continue;
                
                if (stateCount[step + 1][nextBalance] == -1)
                    stateCount[step + 1][nextBalance] = 0;
                    
                stateCount[step + 1][nextBalance] += stateCount[step][balance];
            }
        }
    }
    
    long long totalPaths = 0, winningPaths = 0;
    for (int balance = 0; balance < MAX_BALANCE; ++balance) {
        if (stateCount[rounds][balance] == -1) continue;
        totalPaths += stateCount[rounds][balance];
        if (balance >= OFFSET) winningPaths += stateCount[rounds][balance];
    }
    
    if (winningPaths == 0) {
        cout << "0/1";
    } else {
        long long g = gcd(winningPaths, totalPaths);
        cout << winningPaths/g << "/" << totalPaths/g;
    }
    return 0;
}

Constrained Selection Knapsack

Problem Model

A 0/1 knapsack variant where selected items must maintain minimum separation distance K between their indices.

State Definition

maxVal[i][c] represents maximum value achievable using first i items and selecting exactly c items.

Transition Logic

• Base cases: Single-item selections bypass distence constraints
• General case: For c > 1, transitions only valid from items at least K positions back

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

const int MAX_ITEMS = 10000;
const int INF = -1e9;

int values[MAX_ITEMS];
int maxVal[MAX_ITEMS][101]; // items x count

int main() {
    int itemCount, selectCount, minDistance;
    cin >> itemCount >> selectCount >> minDistance;
    
    for (int i = 1; i <= itemCount; ++i) {
        cin >> values[i];
    }
    
    // Initialize with negative infinity
    for (int i = 1; i <= itemCount; ++i) {
        for (int j = 1; j <= selectCount; ++j) {
            maxVal[i][j] = INF;
        }
    }
    
    maxVal[1][0] = 0;
    maxVal[1][1] = values[1];
    
    for (int i = 2; i <= itemCount; ++i) {
        maxVal[i][0] = 0;
        for (int j = 1; j <= selectCount; ++j) {
            // Don't take current item
            maxVal[i][j] = maxVal[i-1][j];
            
            // Take current item as first selection
            if (j == 1) {
                maxVal[i][j] = max(maxVal[i][j], values[i]);
            }
            
            // Take current item with distance constraint
            if (i - minDistance >= 1 && maxVal[i-minDistance][j-1] != INF) {
                maxVal[i][j] = max(maxVal[i][j], 
                                 maxVal[i-minDistance][j-1] + values[i]);
            }
        }
    }
    
    cout << maxVal[itemCount][selectCount];
    return 0;
}

Boolean Existance DP

Concept

Using boolean arrays to track feasibility of reaching specific states, particularly useful for subset-sum problems.

Approach

reachable[i][w] indicates whether weight w is achievable using first i items.

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

const int MAX_ITEMS = 35;
const int MAX_CAPACITY = 20000;

int weights[MAX_ITEMS];
bool reachable[MAX_ITEMS][MAX_CAPACITY];

int main() {
    int capacity, itemCount;
    cin >> capacity >> itemCount;
    
    for (int i = 1; i <= itemCount; ++i) {
        cin >> weights[i];
    }
    
    reachable[1][0] = true;
    reachable[1][weights[1]] = true;
    
    for (int i = 1; i < itemCount; ++i) {
        for (int w = 0; w <= capacity; ++w) {
            if (!reachable[i][w]) continue;
            
            reachable[i+1][w] = true; // Skip item
            if (w + weights[i+1] <= capacity) {
                reachable[i+1][w + weights[i+1]] = true; // Take item
            }
        }
    }
    
    int maxReachable = 0;
    for (int w = 0; w <= capacity; ++w) {
        if (reachable[itemCount][w]) {
            maxReachable = max(maxReachable, w);
        }
    }
    
    cout << capacity - maxReachable;
    return 0;
}

Modular Space Optimization

Technique

When DP states exhibit periodicity modulo M, reduce memory from O(n×M) to O(M) by storing only current and next states.

Counting States

Track occurrence counts rather than just existence to handle multiple paths reaching the same state.

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

const int MODULO = 3600;
const int MAX_TRACKS = 100000;

int durations[MAX_TRACKS];
int state[2][MODULO]; // rolling arrays

int main() {
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int trackCount;
        cin >> trackCount;
        
        for (int i = 1; i <= trackCount; ++i) {
            cin >> durations[i];
            durations[i] %= MODULO;
        }
        
        memset(state, 0, sizeof(state));
        state[0][0] = 1; // Initial state
        
        for (int i = 1; i <= trackCount; ++i) {
            if (state[0][0] > 1) break; // Multiple paths found
            
            // Transition to next state
            for (int t = 0; t < MODULO; ++t) {
                state[1][t] += state[0][(t - durations[i] + MODULO) % MODULO];
            }
            
            // Merge states
            for (int t = 0; t < MODULO; ++t) {
                state[0][t] += state[1][t];
                state[1][t] = 0;
            }
        }
        
        if (state[0][0] > 1) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

Time-Dependent Value Degradation

Problem Feature

Item values decay linearly over time at different rates, making selection order significant.

Ordering Strategy

Sort items by decay-rate to preparation-time ratio to maximize total value.

Mathematical Justification

For items i and j, comparing sequences shows optimal ordering occurs when decay_i/time_i <= decay_j/time_j.

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

struct Dish {
    int baseValue;
    long long decayRate;
    long long prepTime;
};

const int MAX_DISHES = 55;
const int MAX_TIME = 1000005;

Dish menu[MAX_DISHES];
long long dp[MAX_TIME];

int main() {
    int categories, dishCount;
    long long maxTime;
    cin >> categories >> dishCount >> maxTime;
    
    vector<long long> decayFactors(categories + 1);
    for (int i = 1; i <= categories; ++i) {
        cin >> decayFactors[i];
    }
    
    for (int i = 1; i <= dishCount; ++i) {
        int category;
        cin >> category >> menu[i].baseValue >> menu[i].prepTime;
        menu[i].decayRate = decayFactors[category];
    }
    
    // Sort by decayRate/prepTime ratio
    sort(menu + 1, menu + dishCount + 1, [](const Dish& a, const Dish& b) {
        return a.decayRate * b.prepTime < b.decayRate * a.prepTime;
    });
    
    memset(dp, 0x80, sizeof(dp)); // Negative infinity
    dp[0] = 0;
    
    for (int i = 1; i <= dishCount; ++i) {
        for (int t = maxTime; t >= menu[i].prepTime; --t) {
            dp[t] = max(dp[t], dp[t - menu[i].prepTime] + 
                       menu[i].baseValue - 1LL * t * menu[i].decayRate);
        }
    }
    
    long long bestValue = LLONG_MIN;
    for (int t = 1; t <= maxTime; ++t) {
        bestValue = max(bestValue, dp[t]);
    }
    
    cout << bestValue;
    return 0;
}

Space Optimization with Rolling Arrays

Technique

For DP with high dimensionality, use rolling arrays to compress the first dimension when transitions only depend on immediate previous state.

Application

3D DP problems where resource allocation across different item types can be processed sequentially.

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

const int MAX_MEMBERS = 610;
const int MAX_RESOURCE = 140;

int power[MAX_MEMBERS], cost[MAX_MEMBERS];
int teamDP[MAX_RESOURCE][6][6]; // resource, members, special

int main() {
    int warriors, mages, resourceLimit;
    cin >> warriors >> mages >> resourceLimit;
    
    int totalMembers = warriors + mages;
    for (int i = 1; i <= totalMembers; ++i) {
        cin >> power[i] >> cost[i];
    }
    
    int maxStrength = 0;
    
    // Process warrior type members
    for (int i = 1; i <= warriors; ++i) {
        for (int r = resourceLimit; r >= cost[i]; --r) {
            for (int members = 1; members <= min(5, i); ++members) {
                teamDP[r][members][0] = max(teamDP[r][members][0],
                                          teamDP[r - cost[i]][members - 1][0] + power[i]);
                maxStrength = max(maxStrength, teamDP[r][members][0]);
            }
        }
    }
    
    // Process mage type members
    for (int i = warriors + 1; i <= totalMembers; ++i) {
        for (int r = resourceLimit; r >= cost[i]; --r) {
            for (int members = 1; members <= 5; ++members) {
                for (int special = 1; special <= min(members, i - warriors); ++special) {
                    teamDP[r][members][special] = max(teamDP[r][members][special],
                                                    teamDP[r - cost[i]][members][special - 1] + power[i]);
                    maxStrength = max(maxStrength, teamDP[r][members][special]);
                }
            }
        }
    }
    
    cout << maxStrength;
    return 0;
}

Dependency-Based Knapsack

Problem Structure

Items have hierarchical dependencies where accessories require their main item to be selected first.

Solution Strategy

For each main item, enumerate all valid combinations of its accessories (0, 1, or 2 attachments) and treat each combination as a consolidated choice.

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

struct Item {
    int price;
    int value;
    int parent;
};

const int MAX_ITEMS = 65;
const int MAX_BUDGET = 32000;

Item items[MAX_ITEMS];
vector<int> attachments[MAX_ITEMS];
int dp[MAX_BUDGET];

int main() {
    int budget, itemCount;
    cin >> budget >> itemCount;
    
    for (int i = 1; i <= itemCount; ++i) {
        cin >> items[i].price >> items[i].value >> items[i].parent;
        if (items[i].parent != 0) {
            attachments[items[i].parent].push_back(i);
        }
    }
    
    for (int i = 1; i <= itemCount; ++i) {
        if (items[i].parent != 0) continue; // Skip attachments
        
        for (int b = budget; b >= items[i].price; --b) {
            // Option 1: Take only main item
            dp[b] = max(dp[b], dp[b - items[i].price] + items[i].price * items[i].value);
            
            // Option 2: Main item + one attachment
            if (!attachments[i].empty()) {
                for (int att : attachments[i]) {
                    int totalPrice = items[i].price + items[att].price;
                    if (b >= totalPrice) {
                        dp[b] = max(dp[b], dp[b - totalPrice] + 
                                  items[i].price * items[i].value + 
                                  items[att].price * items[att].value);
                    }
                }
            }
            
            // Option 3: Main item + both attachments
            if (attachments[i].size() >= 2) {
                int att1 = attachments[i][0];
                int att2 = attachments[i][1];
                int bundlePrice = items[i].price + items[att1].price + items[att2].price;
                if (b >= bundlePrice) {
                    dp[b] = max(dp[b], dp[b - bundlePrice] + 
                              items[i].price * items[i].value +
                              items[att1].price * items[att1].value +
                              items[att2].price * items[att2].value);
                }
            }
        }
    }
    
    int maxValue = 0;
    for (int b = 0; b <= budget; ++b) {
        maxValue = max(maxValue, dp[b]);
    }
    
    cout << maxValue;
    return 0;
}