ADC - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: shubham_6105
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Greedy

PROBLEM:

You’re given the price of a stock at N time instants, denoted P_1, \ldots, P_N; as well as a transaction cost K.

Find the maximum number of winning trades possible, where each trade corresponds to buying/selling at one index and then selling/buying respectively at a later index.
A trade is winning if its selling price minus its buying price minus K is positive.

If a trade is done with indices i and j, no other buy/sell operations are allowed between indices i to j, inclusive.

EXPLANATION:

A trade involving indices i and j is profitable if and only if either P_i - P_j - K \gt 0 or P_j - P_i - K \gt 0 (depending on whether we sell at i and buy at j or vice versa.)
Note that at most one of those inequalities can possibly be true; and we can in fact reduce the condition to the single inequality |P_i - P_j| - K \gt 0.

Now, suppose we perform m profitable trades.
Let the i-th of these be involving indices x_i and y_i (with x_i \lt y_i).

Then, since trades cannot overlap with each other, we must have

x_1 \lt y_1 \lt x_2 \lt y_2 \lt\ldots\lt x_m \lt y_m

Now, observe that it’s optimal to choose y_1 to be as small as possible.
That is, let r_1 be the smallest index such that there exists an index l_1 \lt r_1 for which the trade (l_1, r_1) is winning.
Then, it’s optimal to choose y_1 = r_1.
This is because we certainly must have y_1 \ge r_1 by definition of r_1; and if y_1 \gt r_1 we can then replace (x_1, y_1) with (l_1, r_1) to obtain the same number of trades (every following trade remains valid.)

Let’s now try to find the index r_1; so that we know what the first trade is.

Let’s iterate i = 1, 2, 3, \ldots and check if i = r_1 is possible.
For this to work, there must be an index j \lt i such that |P_i - P_j| - K \gt 0.
Observe that if any element P_j satisfies this, then certainly either the minimum element or the maximum element before index i will too.

So, we only need to know the minimum and maximum elements before index i; and if either of them allows for a profitable trade, then we have i = r_1.
If not, update the minimum/maximum elements with P_i, and move on to checking for index i+1.

This allows us to find the index r_1 in linear time.

Observe that after finding r_1, we essentially have to solve the same problem on the remaining suffix of P, starting from index r_1 + 1 instead.
That is, the next trade must be done with the smallest index r_2 \gt r_1 such that a winning trade is possible with index r_2 and some other index in [r_1+1, r_2-1], and so on after r_2.

Just as we found r_1 in linear time, we can find r_2 in linear time, then r_3, and so on.

Note that as long as we break out of the loop immediately upon finding one r_i (or equivalently, reset the min/max so far), each index will only need to be processed once; so the overall complexity is linear.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    
    mn, mx = 10**10, 0
    for x in a:
        mn = min(mn, x)
        mx = max(mx, x)
        if mx - mn - k > 0:
            ans += 1
            mn, mx = 10**10, 0
    print(ans)
3 Likes