---

"Little by little, a little becomes a lot; grain by grain, a heap is formed. Seconds may be short, yet they compose the great eras of eternity. — Fletcher"

---

Key Topics Covered

1. Depth-First Search (DFS)

Fibonacci Triple Sum Problem

Problem Description: Given an integer t test cases, for each query integer k, output three distinct Fibonacci numbers that sum exactly to k. If no such triplet exists, output -1.

Solution Approach: Precompute a sufficiently large Fibonacci sequence (up to values exceeding typical input constraints). For each k, repeatedly find the largest Fibonacci number ≤ remaining target sum, add it to a temporary list, and subtract it from the remaining sum. Stop when either 3 numbers are collected (output them) or no more valid Fibonacci numbers can be added (output -1).

Rewritten Code:

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

vector<long long> precompute_fibs() {
    vector<long long> fibs = {1, 2};
    for (int i = 2; i < 90; ++i) {
        fibs.push_back(fibs[i-2] + fibs[i-1]);
    }
    return fibs;
}

int find_max_fib_idx(long long target, const vector<long long>& fibs) {
    int left = 0, right = fibs.size() - 1;
    int best = 0;
    while (left <= right) {
        int mid = left + (right - left)/2;
        if (fibs[mid] <= target) {
            best = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    vector<long long> fibs = precompute_fibs();
    int test_cases;
    cin >> test_cases;
    
    while (test_cases--) {
        long long k;
        cin >> k;
        vector<long long> result;
        long long remaining = k;
        
        while (remaining > 0 && result.size() < 3) {
            int idx = find_max_fib_idx(remaining, fibs);
            long long chosen = fibs[idx];
            if (!result.empty() && chosen == result.back()) {
                // Skip duplicates
                break;
            }
            result.push_back(chosen);
            remaining -= chosen;
        }
        
        if (remaining == 0 && result.size() == 3) {
            for (long long num : result) {
                cout << num << " ";
            }
        } else {
            cout << -1;
        }
        cout << "\n";
    }
    
    return 0;
}

---

2. Linear Dynamic Programming (DP)

Longest Increasing Subsequence (LIS)

Rewritten Code (standard O(n²) solution for clarity):

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    
    vector<int> lis_len(n, 1);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (arr[i] > arr[j]) {
                lis_len[i] = max(lis_len[i], lis_len[j] + 1);
            }
        }
    }
    
    cout << *max_element(lis_len.begin(), lis_len.end()) << "\n";
    return 0;
}

Longest Bitonic Subsequence

Problem Description: Given n integers representing children's heights, find the minimum number of children to remove so that the remaining children form a sequence that first strictly increases, then strictly decreases (a "bitonic" sequence).

Solution Approach: Compute two DP arrays:

1. inc_dp[i]: Length of the longest strictly increasing subsequence ending at index i.
2. dec_dp[i]: Length of the longest strictly decreasing subsequence starting at index i.

For each index i, the length of the bitonic sequence with peak at i is inc_dp[i] + dec_dp[i] - 1 (subtract 1 because the peak is counted twice). The maximum of these values across all i gives longest bitonic subsequence. The minimum number of removals is n - max_bitonic_len.

Rewritten Code:

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> heights(n);
    for (int i = 0; i < n; ++i) {
        cin >> heights[i];
    }
    
    vector<int> inc_dp(n, 1);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (heights[i] > heights[j]) {
                inc_dp[i] = max(inc_dp[i], inc_dp[j] + 1);
            }
        }
    }
    
    vector<int> dec_dp(n, 1);
    for (int i = n-2; i >= 0; --i) {
        for (int j = n-1; j > i; --j) {
            if (heights[i] > heights[j]) {
                dec_dp[i] = max(dec_dp[i], dec_dp[j] + 1);
            }
        }
    }
    
    int max_bitonic = 0;
    for (int i = 0; i < n; ++i) {
        max_bitonic = max(max_bitonic, inc_dp[i] + dec_dp[i] - 1);
    }
    
    cout << n - max_bitonic << "\n";
    return 0;
}

---

3. Introduction to Dijkstra's Algorithm

Dijkstra's aglorithm is a greedy-based shortest path algorithm used to find the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.

Common shortest path algorithms include:

1. BFS (unweighted graphs)
2. Dijkstra's (non-negative weighted graphs)
3. Floyd-Warshall (all-pairs shortest paths, small graph size)

High-level pseudocode:

DIJKSTRA(Graph, source):
    Initialize distance array dist[] with INF for all vertices except source (dist[source] = 0)
    Initialize unvisited set containing all vertices
    Initialize previous vertex array prev[] as empty
    
    while unvisited set is not empty:
        Select vertex v with minimum dist[v] from unvisited set
        Remove v from unvisited set
        
        For each neighbor u of v:
            if u is in unvisited set:
                tentative_dist = dist[v] + weight(v, u)
                if tentative_dist < dist[u]:
                    dist[u] = tentative_dist
                    prev[u] = v

---

4. Additional Problem Walkthroughs

Modulo Product with Reverse Operation

Problem Summary: Given constraints where direct forward computation causes integer overflow, reverse the problem-solving direction to apply modulo operations incrementally and avoid overflow.

Sum Transformation with Repeated Halving

Problem Summary: Use mathematical summation formulas instead of brute force or fast exponentiation to efficiently compute the required result, even for large values of n and k.

---

Summary

This practice session covers fundamental competitive programming algorithms and problem-solving techniques. Dijkstra's algorithm and linear DP are core topics that require further practice and exploration of variants (e.g., heap-optimized Dijkstra's, O(n log n) LIS).