Question 2: Diverse Deputation

We need to choose 3 people out of (m+w) total, excluding cases that don't have at least one man and one woman .

Overview

We need exactly three members with at least one man and one woman, meaning either 1 man and 2 women, or 2 men and 1 woman. We can use basic combinatorics to calculate the number of ways to pick these specific group compositions. By adding the combinations of these two mutually exclusive valid scenarios together, we mathematically guarantee our total answer.

1. The Logic Behind the Math

 Think of a situation where you try to write a loop to generate every possible combination; it would be way too slow! Instead, just look at the two acceptable scenarios. To pick 2 people from any group of size N, the math formula is simply N *(N - 1) / 2.

2. Calculating the Two Scenarios

• Scenario A (1 Man, 2 Women): Pick 1 man (there are m ways) and multiply by the number of ways to pick 2 women from w, which is w \times (w - 1) / 2.

• Scenario B (2 Men, 1 Woman): Pick 1 woman (there are w ways) and multiply by the number of ways to pick 2 men from m, which is m \times (m - 1) / 2.

Add them together, and you have your answer in an instant!

Implementation

#include <iostream>

using namespace std;

long long nCr(int n, int r) {
    if (r > n || r < 0) return 0;
    if (r == 0 || r == n) return 1;
    if (r == 1) return n;
    if (r == 2) return (1LL * n * (n - 1)) / 2;
    if (r == 3) return (1LL * n * (n - 1) * (n - 2)) / 6;
    return 0;
}

long long solve(int m, int w) {
    long long total = nCr(m + w, 3);
    long long onlyM = nCr(m, 3);
    long long onlyW = nCr(w, 3);
    return total - onlyM - onlyW;
}

int main() {
    cout << solve(1, 3); // Output: 3
    return 0;
}

Logic:

• Total Combinations: Calculate all possible ways to pick 3 people from the total pool:

• Exclusion: Subtract groups consisting only of men or only of women.

• Constraint: This ensures every valid group has at least one of each.

Same Substring Solution

Topics Involved / Prerequisites

• Sliding Window / Two Pointers

Overview

1. We want to find the longest continuous segment where the total cost to match characters does not exceed K.
2. Instead of checking every possible segment, we can use an expanding window that stretches right to include new characters.
3. If the cost exceeds K, we simply shrink the window from the left until it is valid again, keeping track of the maximum size.

Approach

1. The Sliding Window

We use two pointers, l (left) and r (right), to represent the edges of this frame. We move r forward, calculating the absolute difference between characters and adding it to our running total cost.

2. Shrinking the Frame

If adding a new character makes our total cost greater than K, we don't need to start all over. We just pull the l side of the frame forward, subtracting the cost of the characters that fall out of the frame, until our total cost is <=K again. At each valid step, the length of our frame (r - l + 1) is a potential answer, so we just remember the biggest one we find!

Psudo Code

function sameSubstring(s, t, K):
    n = length of s
    ans = 0
    cost = 0
    l = 0
    
    for r from 0 to n - 1:
        // Add the cost of changing the current character
        diff = abs(s[r] - t[r])
        cost = cost + diff
        
        // Shrink the window from the left if we exceed K
        while cost > K AND l <= r:
            leftDiff = abs(s[l] - t[l])
            cost = cost - leftDiff
            l = l + 1
            
        // Record the maximum window size
        ans = max(ans, r - l + 1)
        
    return ans

Time Complexity

• Time: O(N)- Both the l and r pointers only move forward, meaning we visit each character at most twice.

• Space: O(1)- We only use a few integer variables to track the cost and window size.