M.Ibrahim_'s blog

By M.Ibrahim_, history, 3 weeks 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

»
3 weeks 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

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

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

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

      yes.. i checked it by removing memset and using for loop to fill arr with 0.. his solution got accepted...

»
3 weeks 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)

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

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      No. Memset is O(n).

      • »
        »
        »
        »
        3 weeks 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)

        • »
          »
          »
          »
          »
          3 weeks 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.

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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.