codeislife99's blog

By codeislife99, history, 5 years ago, In English

My submission(Problem D). returns the correct answer on all test cases but gets TLE on higher recursion levels. I am unable to understand how memoization can be implemented in this case. Any help would be appreciated.

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

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

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

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

There can be at-most 2^29 particles after N explosions. If you consider a state of the particle in terms of Grid,Level,Direction (X,Y,T,Dir) from Pigeon Hole Principle there must exist (at some point 2^k > 321^2 * 30 * 3^2) two or more particles starting in the same Grid, moving in the same direction at the Same level. For these kinds of particles, you only need to track one instance (Memoize instances) of it. By this way you wont be keeping track of more than 321^2 * 8 particles at an instance.

This leaves you with a complexity of O(Height*Breadth*Levels*Distance*Directions) O(N^2 * 30 * 5 * 8) O(N^2)

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

    Thank you so much man!

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

    At first I wondered how you are still a newbie by your color and then I realized CF has fucked up all the color ratings