Overview

For each of the \(N\) stocks, calculate the sum of absolute differences between consecutive days’ prices (volatility), and find the stock number with the maximum volatility.

Analysis

Understanding the Problem

“Volatility” refers to the total amount by which the stock price fluctuated up and down from day to day. For example, if a stock’s prices over 4 days were \([100, 130, 110, 150]\), the volatility is calculated as follows:

\[|130 - 100| + |110 - 130| + |150 - 110| = 30 + 20 + 40 = 90\]

Approach

This problem can be solved by straightforward simulation.

• Calculate the volatility for each stock → \(O(M)\)
• Do this for all \(N\) stocks → \(O(NM)\)

Since the constraints are small with \(N \leq 100\) and \(M \leq 100\), the computational complexity is about \(O(NM) = O(10000)\), so no special optimization is needed. There is no need to worry about TLE or WA — simply computing according to the definition will yield the correct answer.

Handling Ties

If multiple stocks share the maximum volatility, output the one with the smallest number. By iterating from stock \(1\) onward and updating the maximum only when strictly greater (using >), when there is a tie, the stock found first (= the one with the smaller number) is retained.

Algorithm

1. Read \(N\) and \(M\).
2. Initialize the maximum volatility best_val to \(-1\) and the corresponding stock number best_idx to \(0\).
3. For stock \(i = 1, 2, \ldots, N\):
   • Read the price data \(A_{i,1}, A_{i,2}, \ldots, A_{i,M}\).
   • Calculate the volatility \(v = \sum_{j=1}^{M-1} |A_{i,j+1} - A_{i,j}|\).
   • If \(v > \text{best\_val}\), update best_val to \(v\) and best_idx to \(i\).
4. Output best_idx.

Complexity

• Time complexity: \(O(NM)\) (for each stock, compute \(M-1\) differences, across \(N\) stocks)
• Space complexity: \(O(M)\) (it suffices to store only one stock’s price data at a time)

Implementation Notes

• The update condition should use > (strict inequality): If you use >=, ties would cause the stock with the larger number to be selected, failing to satisfy the “smallest number” condition.

• Stock numbers are 1-indexed: Since the loop variable i in the code starts from 0, you need to output i + 1 as the stock number.

• There is no need to store all stocks’ data in an array — it suffices to read one stock at a time, compute its volatility, and compare. This keeps the space complexity low.

  Source Code

N, M = map(int, input().split())
best_idx = 0
best_val = -1
for i in range(N):
    A = list(map(int, input().split()))
    v = sum(abs(A[j+1] - A[j]) for j in range(M-1))
    if v > best_val:
        best_val = v
        best_idx = i + 1
print(best_idx)

This editorial was generated by claude4.6opus-thinking.