Day 56: Competitive Programming Journal

Date: November 21, 2024
Hello Everyone,

Today marks Day 56 of my competitive programming journey. Here’s what I worked on today:

What I Did Today:
I tackled two problems: Solve the Subset Sum problem (Backtracking) and Find the length of the shortest common supersequence of two strings.

1. Solve the Subset Sum problem (Backtracking):
Problem:
Given a set of integers, determine if there exists a subset whose sum is equal to a given sum S.

Explanation:

Use backtracking to explore all possible subsets and check if their sum equals S.
If a subset's sum matches S, return true.

Implementation:

bool subsetSum(vector<int>& nums, int n, int target) {
    if (target == 0) return true;
    if (n == 0) return false;
    if (nums[n - 1] > target) return subsetSum(nums, n - 1, target);
    return subsetSum(nums, n - 1, target) || subsetSum(nums, n - 1, target - nums[n - 1]);
}

2. Find the length of the shortest common supersequence of two strings:
Problem:
Given two strings X and Y, find the length of their shortest common supersequence (SCS). A supersequence is a sequence that includes both strings as subsequences with the minimum possible length.

Explanation:

• Use dynamic programming to solve this by finding the longest common subsequence (LCS) and then adjusting the result based on the length of LCS.
• The formula is: SCS_length = len(X) + len(Y) - LCS_length

Implementation:

int shortestCommonSupersequence(string X, string Y) {
    int m = X.size(), n = Y.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Fill dp table for LCS
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    int lcs_length = dp[m][n];
    return m + n - lcs_length;
}

Reflection:
Today’s problems were a nice blend of backtracking and dynamic programming. The subset sum problem was a good reminder of how powerful backtracking can be, especially when dealing with subsets and combinations. The shortest common supersequence problem was an insightful way to utilize LCS to simplify the overall solution.

Looking forward to tomorrow's challenges!