Shudi's blog

The lost 300 ms. Memory?
By Shudi, history, 7 years ago, In English

Hello! I have been solving Div2 D problem from the latest contest ( It's just simply BFS ) and faced with one strange fact. When I use two arrays in my solution I got AC with 1700 ms or more — 31662651 and it's near the TL = 2000 ms. So, I decided to improve it and figured out that when I use only one array instead of two I got AC with 1388 ms — 31662579. So, you can see that it's almost there is no difference between them in memory, then where is my 300 ms? Thanks.

P.S. Feel free to post your answers on Russian too.

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

»
7 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Those 300ms goes into allocating memory to the extra array.

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

    No, my guess is that caching works better when using one array.

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

      Okay, I guess it's final answer. Thanks a lot !

      → Reply