Algorithm Trio: Pattern Search, Tree Leaf Count, and Bounded Stock Trading

Problem 1: Canvas Pattern Matching

Given an M×N canvas where '-' denotes a blank cell and '*' denotes a colored cell, and a smaller A×B pattern using the same symbols, determine how many times the pattern appears in the canvas (overlapping matches are allowed).

Input format

First line: two integers M, N (canvas height and width).

Next M lines: N characters each, either '-' or '*', describing the canvas.

Next line: two integers A, B (pattern height and width).

Next A lines: B characters each, either '-' or '*', describing the pattern.

Constraints: 1 ≤ A ≤ M ≤ 100, 1 ≤ B ≤ N ≤ 100, 1 ≤ A·B ≤ 16.

Output

A single integer – the maximum number of occurrences of the pattern in the canvas.

Sample

<code>4 5
--*--
-***-
*-***
-*--*
2 2
**
-*</code>

Output:

2

Complexity

Brute‑force O(M·N·A·B); optimal solution O(M·N).

Key point

Convert rows of '-' and '*' to binary numbers and use bitwise operations.

Problem 2: Binary Tree Leaf Count

A racing game consists of timing points forming a directed acyclic graph where each point can have 0‑2 forward branches. The structure is guaranteed to be a binary tree without cycles. Determine the number of terminal points (leaf nodes).

Input

A single line containing an integer array. The first number is the ID of the start point. Each subsequent pair of numbers gives the IDs of the two forward branches from the current point;

-1

indicates a missing branch. The total number of integers is 2ⁿ − 1 (0 ≤ n ≤ 16).

Output

An integer representing the number of leaf nodes.

Sample

<code>1 2 3 -1 4 5 6 -1 -1 7 8 9 -1 -1 10</code>

Output:

4

(leaf nodes are 7, 8, 9, 10).

Key point

The problem reduces to counting leaf nodes in a binary tree represented as an array. A simple traversal of the array suffices; time complexity O(2ⁿ).

Problem 3: Constrained Stock Trading

A trader observes N integer profit values (positive or negative) over N seconds. He may choose at most one buy‑sell pair (both at integer seconds, immediate execution) to maximize total profit, subject to two constraints: the number of negative‑profit seconds in the chosen interval cannot exceed M, and the total profit cannot exceed K. The trader may also choose to do nothing.

Input

First line: three integers N, M, K (2 ≤ N ≤ 10⁶, 0 ≤ M ≤ N, 0 ≤ K ≤ 10¹⁵).

Second line: N integers Xᵢ (‑10⁹ ≤ Xᵢ ≤ 10⁹) representing profit at each second.

Output

An integer – the maximum achievable profit under the constraints (0 ≤ result ≤ K).

Sample

<code>5 2 15
3 -7 8 -5 9</code>

Output:

12

Key point

Use a sliding window with prefix sums and a multiset to maintain candidate start positions; binary search on prefix sums yields O(N log N) time.

Reference C++ implementation

<code>#include <iostream>
#include <set>
using namespace std;

typedef long long ll;
int main() {
    int N, M; ll K;
    cin >> N >> M >> K;
    int* d = new int[N+1];
    ll* sum = new ll[N+1];
    for(int i = 1; i <= N; i++) {
        cin >> d[i];
        sum[i] = d[i] + sum[i-1];
    }
    int start = 0;
    int negative = 0;
    ll result = 0;
    multiset<ll> st;
    for (int j = 1; j <= N; j++) {
        negative += (d[j] < 0 ? 1 : 0);
        st.insert(sum[j-1]);
        while (start <= j && negative > M) {
            negative -= (d[start] < 0 ? 1 : 0);
            auto it = st.find(sum[start]);
            st.erase(it);
            start++;
        }
        if (start <= j) {
            auto it = st.lower_bound(sum[j] - K);
            if (it != st.end()) result = max(result, sum[j] - *it);
        }
    }
    cout << result << endl;
    return 0;
}
</code>

Complexity

Time O(N log N), space O(N).

Key techniques

Sliding window, prefix sums, binary search (multiset lower_bound).