Блог пользователя Sahashoo

expecting TLE but get an AC
Автор Sahashoo, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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????

    → Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить