Overview

From the stock price data of each stock, calculate the sum of absolute differences between consecutive days’ prices (volatility), and find the stock number with the highest volatility. If there are multiple such stocks, select the one with the smallest number.

Analysis

In this problem, time series data of stock prices is given for each stock, and we need to calculate the sum of absolute differences between consecutive days’ prices. This can be computed simply by processing the data sequentially from the beginning.

For example, if stock \(i\) has prices \([100, 120, 110]\), the volatility is \(|120 - 100| + |110 - 120| = 20 + 10 = 30\).

By calculating the volatility for each stock and maintaining the maximum value as we go, we can identify the stock with the highest volatility at the end. Also, since we need to choose the smaller number when volatilities are equal, processing in order of stock number and updating only when a new value strictly exceeds the current maximum naturally satisfies this condition.

Even a straightforward approach has no computational issues, and simply taking differences of adjacent terms for all stocks runs sufficiently fast.

Algorithm

1. For each stock, do the following:
   • Read the stock price data.
   • Calculate the volatility by summing the absolute differences between consecutive days’ prices.
2. Keep track of the maximum volatility and the corresponding stock number.
3. If a new stock’s volatility is strictly greater than the current maximum, update it.
4. Output the recorded stock number at the end.

Complexity

• Time complexity: \(O(N \times M)\)
  Since we perform \(M-1\) subtractions and absolute value calculations for each stock, the total number of operations is approximately \(N(M-1)\).
• Space complexity: \(O(M)\)
  An array of size \(M\) is needed to temporarily store the price list for each stock.

Implementation Notes

• volatility should be initialized for each stock.

• By updating the stock number only when the volatility strictly exceeds the current maximum, the condition “choose the smallest number if there are ties” is automatically satisfied.

• Reading and processing input line by line is efficient, as it avoids the need to hold all data in memory simultaneously.

  Source Code

N, M = map(int, input().split())
max_volatility = -1
result_index = -1

for i in range(N):
    prices = list(map(int, input().split()))
    volatility = 0
    for j in range(M - 1):
        volatility += abs(prices[j + 1] - prices[j])
    
    if volatility > max_volatility:
        max_volatility = volatility
        result_index = i + 1

print(result_index)

This editorial was generated by qwen3-coder-480b.