ChallaAjay's blog

By ChallaAjay, history, 117 minutes ago, In English

Only the counterexample matters. Consider this function:

long long f(vector<int>& a) {
    int n = a.size();
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int mn = a[i];

            for (int k = i; k <= j; k++)
                mn = min(mn, a[k]);

            ans += mn;
        }
    }

    return ans;
}

The function is supposed to calculate

[ \sum_{0 \le l \le r < n}\min(a_l,a_{l+1},\ldots,a_r). ]

Assume all array elements are positive integers.

Challenge: The logic is correct, but the implementation may still fail under the right constraints.

  1. Find a valid input that breaks it.
  2. Explain precisely why it fails.
  3. Give the smallest fix that makes the implementation correct for all valid inputs under your chosen constraints.

Bonus: Can you derive an (O(n)) solution without enumerating every subarray?

No hand-waving. Give an actual counterexample and justify it.

  • Vote: I like it
  • 0
  • Vote: I do not like it