Day 55: Competitive Programming Journal

Date: November 20, 2024
Hello Everyone,

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

What I Did Today:
I tackled two problems: Solve the Josephus problem (Recursion) and Count all possible palindromic substrings in a string.

1. Solve the Josephus problem (Recursion):
Problem:
In a circle of people, every k-th person is eliminated until only one person remains. Find the position of that last person.

Explanation:

• The Josephus problem can be solved using recursion.
• If there's only one person, the survivor is at position 0.
• Otherwise, the problem reduces to the Josephus problem for n-1 people with k as the step size.

Implementation:

int josephus(int n, int k) {
    if (n == 1) {
        return 0;
    }
    return (josephus(n - 1, k) + k) % n;
}

2. Count all possible palindromic substrings in a string:
Problem:
Given a string, count the number of palindromic substrings. A substring is considered palindromic if it reads the same forward and backward.

Explanation:

• Use dynamic programming to keep track of palindromic substrings.
• Expand around each center (both odd-length and even-length centers) to check for palindromic substrings.

Implementation:

int countPalindromicSubstrings(string s) {
    int n = s.size();
    int count = 0;

    vector<vector<bool>> dp(n, vector<bool>(n, false));

    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
        count++;
    }

    for (int i = 0; i < n - 1; ++i) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            count++;
        }
    }

    for (int len = 3; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                count++;
            }
        }
    }

    return count;
}

Reflection:
Today’s problems were both interesting! The Josephus problem helped sharpen my recursion skills, while counting palindromic substrings reinforced dynamic programming and pattern matching. Both challenges are common in algorithmic contests, so solving them will be useful in future coding interviews.

Looking forward to the next!