MedoN11's blog

Getting weird TLE?
By MedoN11, 9 years ago, In English

link to problem : http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1301

Link to my solution : https://ideone.com/4rRdS9

I'm basically precomputing the input, and for each cell that lies in x-d<=i && y-d<=j, I'll add it's cost to killed[i][j].

It's a classical problem, if there is anything that's not clear within my code. I'm willing to provide a more detailed explanation.

I estimated the complexity to be N*d^2. Isn't that ok enough for 3 seconds?

Thanks.

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

»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I am sorry. It's fast enough.

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

    It's fast, but you are right that it can be solved with O(Size^2) that would be better because it would be independent from maximum of "d"-value.

    All you need to calculate sum[i][j] — prefix sum of all rats on area [1..i, 1..j] (it can be calculated in O(Size^2)). After that sum of some area [x1..x2][y1..y2] can be easily calculated in O(1).

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

    Still, thanks for putting your time to help me. ;)

    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I'm not sure, but it seems that you have bug in this line:

	for(int k=y-d;j<=k+d;k++){

I think that it should be like

	for(int k=y-d;k<=y+d;k++){
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot. It was a stupid typo from my part. Got AC :).

    → Reply