AboAbdoMC's blog

One quick question
By AboAbdoMC, history, 2 years ago, In English

why AC?

https://mirror.codeforces.com/contest/81/submission/177441374

shouldn't this be O(n^2)?

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

Comments Comments (13)
| Write comment?
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think so but it is an old problem so maybe bad test cases?

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

    I tried it on my local machine with this testcase:

    "a"*100000 + "bc"*50000

    it passed in 200ms :)

    → Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

This solution uses ovidiush11's trick. String erase is apparently O(0). I hope he can explain with more details because I am not good enough for this obscure idea yet.

Marinush

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    what is O(0)

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Takes exactly 0 time, else it can't be bounded above by a multiple of 0

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Well, technically every code is $$$\Omega (0)$$$ ;)

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it -15 Vote: I do not like it

          Hi, your comment is not funny nor helpful. Next time, please refrain from writing such comments.

          Please, live a life.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it +17 Vote: I do not like it

            Sure thing, you too :)

            Spoiler
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it -26 Vote: I do not like it

              Hi, your comment is not funny nor helpful. Next time, please refrain from writing such comments.

              Please, live a life.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it +8 Vote: I do not like it

                Hi, your comment is not funny nor helpful. Next time, please refrain from writing such comments.

                Please, live a life.

                → Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

It is $$$O(n^2)$$$, but all your operations are basically memcpy, so the constant factor is really small.

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

order is n^2 but Coefficient is small

→ Reply