Queue and hull optimisations

Questions 1 to 5 of 8

1. 1. The transition is dp[i] = min over j < i of dp[j] + (A[i] - A[j]) * B[i]. Which rewrite turns it into line queries?

   Slope B[j], intercept dp[j], and the query point is A[i]Slope A[i], intercept dp[i], and the query point is j, so each j is a pointSlope -A[j], intercept dp[j], and the query point is B[i]; add A[i] * B[i] after the minimumNo line form exists, because the cost is not linear in j
2. 2. An AI tool wrote a hull whose pointer only moves right. It is used on queries B[i] that can be negative, and it passes the lesson's sample. A reviewer says it is unsafe. Which statement shows the problem?

   The sample a = 2 3 1 5 with b = 1 -2 4 -1 passes with the pointer, so the pointer is safe on every inputThe pointer prints a number too large for 64 bits when a = 4 3 1 1 5Every input with a negative b makes the pointer print a negative answerWith a = 4 3 1 1 5 and b = 2 1 -5 3 3, the naive loop prints 5, but the pointer version prints 21, because the best line for a smaller query can lie behind the pointer
3. 3. In the sliding window deque for the window [i - B, i - A], why does the front pop test use lo, as in dq.front() < lo, and not hi?

   lo never decreases, so an index below lo can never come back into the window, and the test removes exactly the indices that have left ithi is always smaller than lo, so the test must use hi to keep the deque from emptyingThe front holds the largest value, so the front pop must compare values, not indicesThe test is only a speed trick, and removing it changes nothing in the answer
4. 4. Which statements about the monotone deque for a sliding window minimum are true?

   Pick every answer that is true.

   The stored values increase from front to back, so the front is the window minimumBefore a new index is pushed, pop from the back while the back value is at least the new valuePop from the front when the index is at most hi, because hi is the newest index in the windowEach index is pushed and popped at most once, so the whole pass is O(n)
5. 5. For the sample input below, where the segment cost is (A[i] - A[j]) * B[i], what is the minimum total cost? ``text 4 2 1 3 -2 1 4 5 -1 ``

   Type a number.