Whitemuha's blog

I need help to solve this problem
By Whitemuha, history, 4 months ago, In English

I was trying to solve this problem and this is my code I thought it will pass but it gives TLE can anybody tell is it possible to optimize my code or my solution is completely wrong

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
4 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I don't know why it didn't work but I tried all the combinations which I can, then I got accepted:

this is the fixed code of yours:

https://cses.fi/paste/fb8283dd74e36c37103d53d/

→ Reply
»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Your code stores dp like dp[x][n] where x <= 1e6 and n <= 100, and when you get dp it first goes for 1e6 then goes to 100 which is slow, so you can just make first go 100 and then 1e6 by swaping this two states. Code

→ Reply
  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    But what is the difference betweeen 1e6*100 and 100*1e6?

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

      I think you can do some search what is the difference between dp[100][1e6] and dp[1e6][100] in c++, there are high educated people that explains better than me

      → Reply
    • »
      »
      »
      4 months ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +1 Vote: I do not like it
      image

      Transitions between blocks are the most costly ones

      → Reply
      • »
        »
        »
        »
        4 months ago, hide # ^ |
         
        Vote: I like it +1 Vote: I do not like it

        Until today I thought they were the same thing. Thanks for the explanation

        → Reply
        • »
          »
          »
          »
          »
          4 months ago, hide # ^ |
           
          Vote: I like it +1 Vote: I do not like it

          in a vacuum, yes they are the same. in reality the first one has better performance because of fewer cache misses (i think, might be something else).

          in general accessing lots of memory addresses that are next to each other is faster than accessing the same number of addresses randomly distributed throughout RAM

          → Reply
  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    You can even get rid of the second dimension: here

    → Reply