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

TLE????
Автор john9, 12 лет назад, По-английски

My Solution to 253C - Text Editor is producing TLE? here is the link to solution 2797003

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

»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

because there is n ( <= 100 ) lines of text with length <= 100 000 (10^5) total your bfs produces 10^9 states (~ vertices of graph).

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

    10^2 * 10^5 aren't 10^9. BFS is not the best solution, but it should pass the time limit if it is implemented correctly.

    Don't push the new nodes to the queue if you have already visited them. Then it should pass...

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

      Oh, yes. you are right. I thought there was 10^7 limitations, but copy & paste method shows i was wrong. Anyway 10^7 is pretty much, it can pass Time Limit, but my solution works for my limitations too. As you can see, it is don't matter how big limitations are, for the length of particular string. You can run BFS only for states where second coordinate(Y) is equal to length of one of the n strings. So there will be totally O(n^2) states. then for each of states you should to calculate the number of moves you need? if you can't go to another line. this task can be solved in O(1) time. Answer for this question is just | r1 — r2 |.
      **Upd** Ok you can't see until my solutions published. you should use only points with coordinates (i, len[j]) where 0 <= i < n && 0 <= j && j <= n — 1

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

    I successfully solved this problem using BFS 2726786

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

then how can this pass 2801412

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

    Look this: if(Dp[NX][NY] == -1) Dp[NX][NY] = Dp[X][Y] + 1, Q.push(Pii(NX, NY))

    Each node will be pushed to the queue at most one time.

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

A two-line element set (TLE) is a data format used to convey sets of orbital elements that describe the orbits of Earth-orbiting satellites.

→ Ответить