M.Ibrahim_'s blog

Help Please

By M.Ibrahim_, history, 5 years ago, In English

can any one help me and tell me why this code get TLE 56138526

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

Comments Comments (10)
| Write comment?
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

one solution same like u may refer.

change memset to for i = 0 to n ... arr[i] =0

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

    You can use fill(arr,arr+n,0) instead

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

I think it's because you do memset(arr,0,sizeof arr) every testcase (it takes 200005 iterations)

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

    don't bul... memset Takes O(1)

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

      No. Memset is O(n).

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

        Oh sorry yes i typo but memset have a very good performance(much Better than simple loop)

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

          It greatly depends on the memset implementation. Many versions of memset can use a "bit blit" operation in hardware to set large groups of memory to the same value essentially instantly — or at least far faster than you could possibly do with a code-level loop — especially if you're setting the value to zero or 0xFF.

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

            But honestly, it doesn't really make a difference. The only reason I use memset is to save time.

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

              No, it makes a huge difference in runtime. It's more like O(N / insanely good constant). Actually in one problem the "second intended solution" used memset and passed and when I was still using java I couldn't get it to pass with Arrays.fill or copy or for loop or whatever other stuff java has and I had to actually find a better algorithm, lol.

              → Reply