skpro19's blog

One doubt in Codechef January Long Problem 'MONSTER'
By skpro19, 7 years ago, In English

I have understood the sqrt decomposition + SOS DP approach to the problem. This is an accepted solution to the problem. However, on changing the size of the array Q_MAX to 'N_MAX + 100', I am getting WA. Why is that?

What am I missing?

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Changing the constant Q_MAX (that represents the quantity of queries = 2**18) to N_MAX (that represents the total of monsters = 2**17), you are decreasing the array size in (2**18)-(2**17), that is, obviously, greater than 100.

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

Can you provide the Time Complexity of your solution?

→ Reply