A rate with no setbacks
The cover of a report needs a chart on which the rate only rises. Faking the numbers is not allowed, but dropping some days is: the chart will keep the real rates of real days, just not all of them. To keep the picture more honest, you want to keep as many days as possible.
Given a series of n rates by day, in tiyn. Choose as many days as possible so that on the chosen days, in order, the rate strictly rises: two equal rates in a row look like a step on the chart, not a rise. The tests include real rates of the dollar, euro and yuan against the tenge over five years; in them the rate for Saturday, Sunday and Monday is almost always the same.
Input
The first line holds n (1 ≤ n ≤ 100,000). The second holds n integers a1, …, an (1 ≤ ai ≤ 109): the rate on each day.
Output
The first line holds the greatest number of days k. The second, the numbers of those days in increasing order, separated by spaces (days are numbered from one). If there are several options, print any.
Examples
Example 1
12 42375 42402 42513 42432 42432 42432 42638 42583 42551 42424 42516 42516
4 1 2 10 12
Example 2
5 50000 49900 49850 49850 49000
1 5
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 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
First an honest table: for each day i, how many days are in the longest rising chain that ends on day i. How is it computed from the table for the previous days? And what does it cost at n = 100,000?
2Hint 2
Of all chains of length k, the one that ends lower is more useful: it is easier to extend. Keep only the lowest end for each length. How is this array arranged, and what does the next day do to it?
3The idea
This is the longest increasing subsequence. The array tops: tops[k] is the lowest rate a rising chain of k + 1 days can end on. It strictly increases, so for a new rate x the place is found by binary search: the first cell where tops[k] ≥ x. If there is none, the chain has grown longer; otherwise x replaces tops[k]. To name the days themselves, each day remembers the previous day of its chain, the one that lay in tops[k − 1] when it arrived.
4Walkthrough
Go through the days. For the rate x find k = bisect_left(tops, x), remember prev[i] = top_at[k − 1] (or “none” if k = 0) and put x in place k, with the day’s number in top_at[k]. At the end the answer is the length of tops, and the days are recovered from top_at of the last cell along the prev pointers backwards and reversed.
Why the pointer is right: when day i arrives, tops[k − 1] holds the end of a chain of length k, and it is less than x, otherwise the binary search would have stopped earlier. So day i can be appended to that chain, giving a chain of length k + 1 that ends on day i.
Strictness is decided by one word. bisect_left puts an equal rate in place of the equal one, and the chain does not grow: in the first example the rate 424.32 three times in a row gives one rung, not three. bisect_right would extend the chain with an equal rate; that is how a “non-decreasing” subsequence is computed, and on real data it is almost twice as long: 269 days against 151 for the dollar.
4+Solution
5Complexity
O(n log n) time: for each day a binary search over an array no longer than the answer. O(n) memory for the pointers. The table from the first hint is O(n²), five billion comparisons at n = 100,000.
6Common mistakes
- The quadratic table. Correct, it passes the tests with real rates (1900 days there), but is too slow on a hundred thousand.
- bisect_right instead of bisect_left. You get a chain where the rate does not fall; it is longer and wrong: neighbouring equal rates are not a rise.
- Printing the contents of tops. Its length is the answer, but the numbers in it are usually not a chain: tops[0] may hold the rate of the last day and tops[1] an earlier one. The days have to be recovered by the pointers.