CF 102697068 - Relative Strength Index

Rating: -
Tags: -
Solve time: 59s
Verified: yes

Solution

Problem Understanding

We are given a sequence of (N) historical prices, in chronological order. For every pair of consecutive measurements, the price either rises, falls, or stays unchanged. The RSI calculation only cares about the rises and falls.

For every increase, we collect the size of that increase. For every decrease, we collect the absolute size of that decrease. We then compute the arithmetic mean of all increases, called aveUP, and the arithmetic mean of all decreases, called aveDOWN. The required value is

[ RS = \frac{aveUP}{aveDOWN} ]

followed by

[ RSI = 100-\frac{100}{RS+1}. ]

The official statement specifies a 1 second time limit and 256 MB of memory, but it does not publish a numerical upper bound for (N). That makes the linear approach the natural target: every price only needs to participate in one comparison with its predecessor. A quadratic algorithm would perform roughly (N^2) work and becomes impractical as the input grows, while an (O(N)) scan remains easily manageable for very large sequences.

There are several details that can silently change the answer.

The first is that a decrease must contribute a positive amount. For example,

3
10 7 9

has one decrease of size (3) and one increase of size (2). Thus aveUP = 2, aveDOWN = 3, and the answer is

40.0

A careless implementation that adds the raw difference 7 - 10 = -3 to the downward sum would produce a negative average and an invalid RSI.

The second is that unchanged prices contribute nothing to either average. For example,

4
10 10 12 9

has one increase of (2) and one decrease of (3), so the answer is again

40.0

Treating an unchanged pair as either an increase or a decrease would distort one of the averages.

The third issue is that the averages are over the changes of their respective types, not over all (N-1) adjacent pairs. In the sample,

4
6500.0 6510.0 6300.0 6200.0

there is one increase of (10) and two decreases of (210) and (100). Hence aveUP = 10, aveDOWN = 155, giving the required output 6.060606060606062. Dividing both sums by (N-1=3) happens to cancel if done consistently, but separately counting the upward and downward changes makes the intended formula explicit and avoids mistakes when implementing it.

The statement also guarantees that the history contains at least one increase and at least one decrease, so both averages are defined and aveDOWN cannot be zero.

Approaches

A direct brute-force interpretation could recompute the complete set of changes every time it needs an average. For each of the (N-1) adjacent positions, such an implementation could scan all (N-1) adjacent pairs again, classify every difference, and rebuild the upward and downward sums. It is correct because every scan reconstructs exactly the information required by the formula, but it performs ((N-1)^2) pair inspections in the worst case. For (N) prices, that is (N^2-2N+1) inspections, which is unnecessary work.

The brute-force approach fails because adjacent differences are independent. Once we have examined the pair (prices[i-1], prices[i]), its contribution to the final averages never changes. There is no reason to examine that pair again.

The key observation is that the RSI formula depends only on the sum and count of positive changes and the sum and count of negative changes. We can maintain exactly those four quantities while scanning the prices once. For a positive difference, add it to the upward sum and increment the upward count. For a negative difference, add its absolute value to the downward sum and increment the downward count. A zero difference is ignored.

After the scan, the averages are simply the corresponding sums divided by their counts. The rest of the computation is constant time.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	(O(N^2))	(O(1))	Too slow for large (N)
Optimal	(O(N))	(O(1)) extra	Accepted

Algorithm Walkthrough

Read the number of prices and the price sequence. The prices are already ordered chronologically, so only consecutive values need to be compared.
Initialize up_sum, up_count, down_sum, and down_count to zero. These variables contain exactly the information needed to construct the two averages later.
For every pair of consecutive prices, compute change = current - previous. If the change is positive, add it to up_sum and increment up_count. If the change is negative, add -change to down_sum and increment down_count. If the change is zero, do nothing.

Using -change for a negative change is equivalent to taking its absolute value, while avoiding any ambiguity about the sign of the downward contribution. 4. Compute

[ aveUP = \frac{up_sum}{up_count} ]

and

[ aveDOWN = \frac{down_sum}{down_count}. ]

The problem guarantees that both counts are nonzero, so these divisions are valid. 5. Compute the relative strength with

[ RS=\frac{aveUP}{aveDOWN}. ]

Then substitute it into the RSI formula:

[ RSI=100-\frac{100}{RS+1}. ] 6. Print the resulting floating-point value. Python's standard floating-point representation is sufficient for this calculation.

The invariant throughout the scan is that after processing the first (i) prices, up_sum and up_count describe exactly all positive changes among those prices, while down_sum and down_count describe exactly all negative changes by their positive magnitudes. Every adjacent pair is processed once and placed into exactly the appropriate category, so after the final pair the four accumulated values represent precisely the quantities used by the RSI definition.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    prices = list(map(float, input().split()))

    up_sum = 0.0
    up_count = 0
    down_sum = 0.0
    down_count = 0

    for i in range(1, n):
        change = prices[i] - prices[i - 1]

        if change > 0:
            up_sum += change
            up_count += 1
        elif change < 0:
            down_sum += -change
            down_count += 1

    ave_up = up_sum / up_count
    ave_down = down_sum / down_count

    rs = ave_up / ave_down
    rsi = 100.0 - 100.0 / (rs + 1.0)

    print(rsi)

if __name__ == "__main__":
    solve()

The input is read as floating-point numbers because the prices themselves can contain fractional values. The first price has no predecessor, so the loop deliberately starts at index 1. This avoids the common off-by-one error of inventing a comparison before the first measurement.

For each subsequent price, change represents exactly one movement in the price history. Positive values update the upward statistics, negative values update the downward statistics using their positive magnitude, and zero values update neither statistic.

The averages are calculated only after the complete scan. There is no need to store the individual increases or decreases, so the algorithm uses constant extra space apart from the input array. Python integers can grow without overflow, and the sums here are floating-point values because the input prices are floating point.

The order of the final operations follows the definition directly. First the two averages are formed, then their ratio is computed, and only then is that ratio substituted into the RSI expression. The problem guarantees both an increase and a decrease, so neither average requires a special zero-count case.

Worked Examples

Sample 1

For the official sample, the price changes are (+10), (-210), and (-100).

Current price	Previous price	Change	`up_sum`	`up_count`	`down_sum`	`down_count`
6510.0	6500.0	+10.0	10.0	1	0.0	0
6300.0	6510.0	-210.0	10.0	1	210.0	1
6200.0	6300.0	-100.0	10.0	1	310.0	2

At the end, aveUP = 10 / 1 = 10 and aveDOWN = 310 / 2 = 155. Thus RS = 10 / 155, and the final RSI is 6.060606060606062, matching the official sample.

Sample 2

Consider the history

5
100 110 105 115 110

The changes are (+10), (-5), (+10), and (-5).

Current price	Previous price	Change	`up_sum`	`up_count`	`down_sum`	`down_count`
110.0	100.0	+10.0	10.0	1	0.0	0
105.0	110.0	-5.0	10.0	1	5.0	1
115.0	105.0	+10.0	20.0	2	5.0	1
110.0	115.0	-5.0	20.0	2	10.0	2

The averages are both (10) for the upward movements and (5) for the downward movements. Hence RS = 2 and the RSI is

[ 100-\frac{100}{3}=66.66666666666667. ]

The trace demonstrates that the counts belong to the direction of movement, rather than to all adjacent pairs.

Complexity Analysis

Measure	Complexity	Explanation
Time	(O(N))	Each of the (N-1) adjacent price pairs is processed once.
Space	(O(N))	The input price array is stored; the algorithm itself uses (O(1)) additional space.

The published statement gives a 1 second limit and 256 MB of memory, while omitting a numerical upper bound for (N). A single linear scan is the appropriate complexity regardless of the missing bound. The implementation performs only constant work per price and uses a fixed number of accumulators beyond the input array.

Test Cases

import sys
import io

def solve():
    n = int(input())
    prices = list(map(float, input().split()))

    up_sum = 0.0
    up_count = 0
    down_sum = 0.0
    down_count = 0

    for i in range(1, n):
        change = prices[i] - prices[i - 1]

        if change > 0:
            up_sum += change
            up_count += 1
        elif change < 0:
            down_sum += -change
            down_count += 1

    ave_up = up_sum / up_count
    ave_down = down_sum / down_count

    rs = ave_up / ave_down
    rsi = 100.0 - 100.0 / (rs + 1.0)

    return str(rsi)

def run(inp: str) -> str:
    global input
    old_stdin = sys.stdin
    old_input = input

    sys.stdin = io.StringIO(inp)
    input = sys.stdin.readline

    try:
        return solve()
    finally:
        sys.stdin = old_stdin
        input = old_input

# Provided sample
assert run(
    "4\n"
    "6500.0 6510.0 6300.0 6200.0\n"
) == "6.060606060606062", "sample 1"

# Minimum meaningful size: one increase and one decrease
assert run(
    "3\n"
    "10 11 10\n"
) == "50.0", "minimum-size input"

# All equal values are not allowed by the original problem guarantee,
# so use a repeated value inside an otherwise valid history.
assert run(
    "5\n"
    "10 10 12 12 9\n"
) == "40.0", "unchanged prices"

# Equal upward and downward average magnitudes
assert run(
    "5\n"
    "100 110 105 115 110\n"
) == "66.66666666666667", "alternating changes"

# Fractional prices and a boundary change of exactly zero
assert run(
    "4\n"
    "1.5 2.5 2.5 1.0\n"
) == "40.0", "fractional values and zero change"

# Large input to exercise linear behavior.
prices = [0.0]
for i in range(1, 100001):
    prices.append(prices[-1] + (1.0 if i % 2 else -1.0))

large_input = str(len(prices)) + "\n" + " ".join(map(str, prices)) + "\n"
large_output = run(large_input)
assert abs(float(large_output) - 50.0) < 1e-12, "large input"

Test input	Expected output	What it validates
`3 / 10 11 10`	`50.0`	Smallest valid history with one increase and one decrease
`5 / 10 10 12 12 9`	`40.0`	Zero changes must be ignored
`5 / 100 110 105 115 110`	`66.66666666666667`	Multiple increases and decreases with equal magnitudes
`4 / 1.5 2.5 2.5 1.0`	`40.0`	Fractional prices and an unchanged boundary pair
100001 alternating prices	`50.0`	Linear performance on a large input

The original statement guarantees at least one increase and one decrease, so a truly all-equal input is outside the valid input domain. The tests instead place equal consecutive values inside an otherwise valid history, which exercises the same implementation branch without violating the problem's guarantee.

Edge Cases

For a negative movement, the algorithm explicitly adds -change rather than change. On

3
10 7 9

the first difference is -3, so down_sum becomes 3, not -3. The second difference is +2, so up_sum becomes 2. The averages are 2 and 3, giving RS = 2/3 and RSI = 40.0. This directly handles the sign requirement in the statement.

For unchanged prices, consider

4
10 10 12 9

The first difference is zero and is ignored. The next difference is +2, and the final difference is -3. The accumulated values are up_sum = 2, up_count = 1, down_sum = 3, and down_count = 1, producing 40.0. A zero movement never belongs to either average.

For the first price, consider

3
10 11 10

The loop starts at the second price, so the comparisons are 11 - 10 and 10 - 11. There is no attempt to compare the first price with a nonexistent predecessor. The upward and downward averages are 1 and 1, giving RS = 1 and RSI = 50.0.

For fractional prices, consider

4
1.5 2.5 2.5 1.0

The changes are +1.0, 0.0, and -1.5. The zero is ignored, giving aveUP = 1.0 and aveDOWN = 1.5. The resulting RSI is 40.0. Reading the prices as float values is necessary because the input is explicitly allowed to contain floating-point measurements.

Finally, the algorithm relies on the problem's guarantee that at least one price increases and at least one price decreases. That means up_count > 0 and down_count > 0 after the scan, so both averages can safely be computed without artificial handling for division by zero.