When it gets warmer
Given a series of daily mean temperatures over n days. For each day find in how many days the first day strictly warmer than it will come (0 if there is none). Print four numbers: the sum of all waits, the longest wait, the number of the day it starts from (the earliest if there are several), and how many days never got a warmer one.
The second test is Almaty over 1941–2025 (the ERA5 reanalysis), in tenths of a degree: after 1 August 1946 a warmer day had to be waited for until July 2021. The third is the last ten years.
Input
The first line holds n (1 ≤ n ≤ 2·10⁵), the second n integers of absolute value at most 10⁶.
Output
Four numbers separated by spaces: the sum of waits, the longest wait, the number of its first day (from one), the number of days without a warmer one.
Examples
Example 1
8 73 74 75 71 69 72 76 73
10 4 3 2
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Go through the days from left to right and keep the days still waiting for an answer. What can be said about the temperatures of these days if none of them has got its answer yet?
2The idea
The waiting days form a stack, and their temperatures do not increase from bottom to top: if a later waiting day were warmer than an earlier one, the earlier one would already have its answer. A new day pops from the top everyone colder than it, and for each of them it is the first warmer day, and then it goes onto the stack itself.
3Walkthrough
Each day is pushed onto the stack once and popped at most once, so the pass is linear, although there is a loop inside the loop. The days left on the stack at the end never got an answer. The comparison is strict: a day of the same temperature does not end a wait.
The sum of waits reaches 2·10¹⁰: if all days are equal and only the last is warmer (the eighth test), each waits until the very end. In Go it is kept in int64.
3+Solution
4Complexity
O(n) time and O(n) memory for the stack.
5Common mistakes
- Looking ahead from each day. Correct, but in a series that keeps getting colder (the fourth test) each day scans the whole remainder: 2·10¹⁰ comparisons.
- A non-strict comparison. “Not colder” instead of “warmer” gives different waits on days with equal temperatures: the fifth test of nothing but fives.
- The latest of equal records. The earliest day number is needed.