A million temperatures
A weather station records the mean temperature of each day in tenths of a degree. A day is a heat record if it is warmer than all the previous days, and a cold record if it is colder than all the previous days; the first day counts as both.
How many heat records were there, how many cold records, and which day was the last heat record?
The problem itself is solved in one pass. But there may be a million days, and the time limit can be met only by reading the input fast.
Input
The first line holds n (1 ≤ n ≤ 10⁶). Then come n lines, each with one integer from −600 to 600: the day’s temperature in tenths of a degree.
Output
Three numbers: the number of heat records, the number of cold records and the number of the last heat-record day (days are numbered from one).
Examples
Example 1
8 -52 -31 -80 12 12 40 -95 38
4 3 6
Limits
- Time · Python
- 1000 ms
- Time · Go
- 500 ms
- Memory
- 256 MB
- Judging
- 6 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
The algorithm here is one pass with the current maximum and minimum. Count how many times the program calls for input and what each call costs.
2The idea
Read the whole input in one call and split it on whitespace: in Python sys.stdin.buffer.read().split(), in Go a buffered bufio.Reader and parsing the numbers by hand. Then an ordinary loop.
3Walkthrough
A solution with int(input()) for every line is correct but does not make it in time on a million days. Each call to input() asks standard input for its file number, checks whether it is a terminal and flushes the output and error buffers, and only then reads a line. Reading it all at once makes one call to the system per megabyte and one split. Why this is so and what it costs in Python and in Go is taken apart in the article “Fast input and output”.
In Go the trap is different: fmt.Scan straight from os.Stdin makes a system call for every byte of input, and that is several million calls. It is enough to wrap the input in bufio.NewReader, and faster still to read numbers from the buffer byte by byte, as in the reference solution.
The fifth test is the real 85 years of Almaty weather from a reanalysis: 31 heat records, the last on 9 August 1944, the very day that in the article on the monotonic stack never lived to see a warmer one.
3+Solution
4Complexity
O(n) time. Reading it all at once holds the whole input in memory, a few megabytes, which is acceptable; with gigabytes one would read in pieces.
5Common mistakes
input()for every line. Correct, but slow on the sixth test.fmt.Scanwithout a buffer in Go. A system call for every byte.- A non-strict comparison. A day equal to the record does not count as a record: the third test is made of equal days.