Блог пользователя ChallaAjay

Автор ChallaAjay, история, 3 часа назад, По-английски

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.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
90 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is the fast solution

Spoiler