_QWOiNYUIVMPFSBKLiGSMAP_'s blog

By _QWOiNYUIVMPFSBKLiGSMAP_, history, 18 months ago, In English,

the problem is http://codeforces.com/contest/513/problem/C

the solution is http://codeforces.com/contest/513/submission/9761274

i wonder how this solution not TLE it is 1009*1009*6*6*6 which is TLE

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by XMORE (previous revision, new revision, compare).

»
18 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Dude. You don't just analyze the complexity by counting for loops

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the each iteration in the for loop work as i clear the dp array so this is the complexity i am confused :s

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For clearing the dp array, I see four for loops and they go till 6,6,6,10009 so how TLE?

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        no i mean the dp is in 10009*6*6*6 okay but there is for loop iterating on dp in the main so what is the total complexity ?

        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Memoization technique has been used in the solution, which means you just calculate the value for each state only once. Therefore the whole solution proceeds 10009*6*6*6 different states which is pretty far from TLE.

          • »
            »
            »
            »
            »
            »
            18 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            i memorize on dp[i][maxi][eq][gr] for each iteration in loop maxi will be different so it is like i am doing dp again from scratch