raid_shadow_legends's blog

IOI problem, please help
By raid_shadow_legends, history, 6 years ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 years ago, hide # |
← Rev. 2  
Vote: I like it +6 Vote: I do not like it

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 ?

→ Reply
»
6 years ago, hide # |
← Rev. 4  
Vote: I like it +19 Vote: I do not like it

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.
→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +1 Vote: I do not like it

    Thanks for your reply ! I've fully understand it now. And sorry if the name offends you, it's basically a name of a game that sponsors many youtuber's video and I just find it hilarious :)

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      I also believe that everyone can solve problems with IOI. Just then it turns out that those who have a small rating can not solve interesting problems?

      → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      It doesn't offend me, I'm just very tired of hearing about this game in every single YouTube video... :D

      Glad the explanation helped!

      → Reply