Sahashoo's blog

expecting TLE but get an AC
By Sahashoo, 7 years ago, In English

Submission Link

Hi,

I was thinking about 442-div 2-D problem and I come up with noting except a bad solution.

as I say it was a bad solution because it run from O(n*m*k) thus it should get TLE but I got an AC!?

can anybody say just why?????

sorry for bad Eng.

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

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

Your solution isn't O(nmk) due to if(...||mrk[x][y][i])break;. Try to construct a worse case scenario for simple map with m=1 and you'l see that factor k doesn't apply.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    So you mean I didn't implement what I wanted??

    and could you say why that if(...||mrk[x][y][i])break; make Order better????

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

    Can we tell that worst case complexity is O(n*m) by bfs?

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

You can't enter in vertex more than 4 times, so your solution is O(nm).

→ Reply