DELARR77 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You have two arrays A and C, both of length N.
A_i can be deleted from A with a cost of A_i\cdot C_i.
After the deletion, the elements of A are re-indexed to start from 1.
Find the minimum cost to delete all the elements from A.

EXPLANATION:

Let’s look at elements of A one at a time, from left to right.

First, A_1.
Observe that we have no choice but to delete A_1 with a cost of A_1\cdot C_1, i.e. by pairing it with C_1.
This is because deleting elements after index 1 isn’t going to move A_1 from the first position.

Next, look at A_2.
Of course, we can delete it with a cost of A_2\cdot C_2.
However, observe that we can also delete it with a cost of A_2\cdot C_1 if we first delete A_1 before deleting A_2.
So, the minimum cost to delete A_2 is A_2\cdot \min(C_1, C_2).

Next we look at A_3.
Similar reasoning shows that A_3 can be paired with one of C_1, C_2, C_3 by choosing to wait a little after deleting it.

In general, the element A_i can be paired with one of C_1, C_2, \ldots, C_i by choosing to delete some elements before it first; and so the absolute minimum cost needed to delete it is A_i \cdot \min(C_1, C_2, \ldots, C_i).

Thus, a lower bound on the answer is to just sum this up across all i, to obtain

\sum_{i=1}^N A_i \cdot \min(C_1, C_2, \ldots, C_i).

This lower bound is indeed attainable, and so this is the answer.

Proof

For each index i, let m_i denote the index such that C_{m_i} = \min(C_1, C_2, \ldots, C_i).
Ideally, we want to delete A_i by pairing it with C_{m_i}.

Define d_i = i - m_i to be the number of elements that have to be deleted before index i, such that element A_i ends up at index d_i.

Now we can do the following:

  • Choose the largest index i such that d_i = 0, and delete this element.
    Note that such an index will definitely exist, because d_1 = 0.
  • After this, for each j \gt i, reduce d_j by 1 (because all larger indices now require one fewer deletion).

Simply repeat this algorithm over and over again till all the elements are deleted.
Because we always delete some element with d_i = 0, each deleted element will be paired with its optimal cost; and because we delete the rightmost one, we never delete “too many” elements and cause something to move too far to the left.

Computing this value naively can be done in \mathcal{O}(N^2) and is fast enough for this problem, though it’s also easy enough to optimize this to linear time by simply finding the prefix minimums of C.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    c = list(map(int, input().split()))
    
    ans, mn = 0, 101
    for i in range(n):
        mn = min(mn, c[i])
        ans += mn*a[i]
    print(ans)