hatehate's blog

My slow solution passes the system tests
By hatehate, history, 5 weeks ago, In English

My slow solution 291665439 to 2031D - Пенчик и пустынный кролик passes the system tests.

Explanation
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

my O(n^2) brute force solution 291699055 also got accepted for 2031B - Пенчик и палочки для сатэ

→ Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    This is actually a valid $$$\mathcal{O}(n)$$$ solution. With the if condition any element will not move more than one place from the initial order so the loop never runs more than twice through the entire array.

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right, I missed that part. Thank you for the explanation! ^_^

      → Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Sir, teach us your skill of optimizing code!

→ Reply