- Thoughts.
- There are a lot of general operations that I’d like to limit more.
- Is there an optimal solution that moves 1 first?
- Not necessarily.
- If 1 is at the beginning from the beginning
- To move a number before 1 backward
- For example, 3,1,2 is once if you move 3, but not if you bring 1 to the top.
- Is it OK to choose the first or last value from the one with the furthest distance?
- Regarding “selecting the first or last value from the one with the furthest distance
- Never move the same number twice.
- Assuming we don’t move the number of the farther distance…
- 3,2,1,6,5,4
- Doesn’t look too bad? I need more certainty.
- Consider [number of events (e.g. accidents, crimes, meetings, housing starts, hits on a web page)
- The number of falls is reduced by the number of times the number at the end jumps over the number greater than the number in front of you.
- The maximum number of overturns in a column of length N is the triangular number T(N-1)
- hmm
- I want to show that “move the one with the larger number of overturns among the leading or trailing values to the end” is the correct greedy algorithm.
- After moving it, it comes down to one smaller problem.
- Correct when N is 3.
- The number of moves is monotonically nondecreasing with respect to the number of falls, which seems to be the case, but I can’t show it.
- Look again at the constraints
- 300,000
- I don’t know how to calculate the number of falls.
- Official Explanation - The order of operation is irrelevant. - You can think of it as pulling it out and putting it back in [All at the same time - In that case, the condition that works is “monotonically increasing the remaining rows that are pulled out.” - LAM
This page is auto-translated from /nishio/abc006_4 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.