Блог пользователя raid_shadow_legends

IOI problem, please help
Автор raid_shadow_legends, история, 6 лет назад, По-английски

I was trying to solve problem Median Strength from IOI 2000. Having only managed to come up with a stupid O(n^2) algorithm, i take a look at the editorial. The paragraph that I'm having a difficult time to understand is Linear insertion is quadratic in both worst and average cases, and linear in best cases. Binary and ternary insertion have N*log N complexity (ternary has smaller constant factor). Here are my questions: 1. I'm not sure how I can run binary search on this problem. 2. After binary/ternary search the position to insert the object, moving elements to the right of that position will take another O(n), why is the complexity still O(n log n) ?

Please help. Also remember to wash your hands regularly. Thanks.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +6 Проголосовать: не нравится

What's wrong with a newbie asking for help ? If you don't want to help me, just leave, why do you have to downvote ?

→ Ответить
»
6 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +19 Проголосовать: не нравится

I'll downvote anything containing words "raid", "shadow" and "legends" in that combination. :D But the fact that I had to find the editorial myself, probably didn't help.

On a serious note, you're correct, time complexity would still be quadratic. But in this problem, you're not interested in time complexity, you're interested in the amount of comparison calls you need to make, and in that aspect, switching to binary and ternary insertions reduce that complexity to O(N log N).

As for approaches, in all you have an array of $$$x$$$ indices sorted and you want to add $$$x+1$$$ in the right position.

  • Linear insertion just check all consecutive two indices and your new index, until it is reported as a median – that would be the right position for it.
  • Binary insertion – check two consecutive elements in the middle: if the median isn't your new index, then based on which one of the two old ones is reported as median you can eliminate half of possible positions.
  • Ternary insertion – take two elements at around 1/3 and 2/3 of interval. Based on median reported, leave only the appropriate third of the interval.
→ Ответить