john9's blog

TLE????
By john9, 12 years ago, In English

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

  • Vote: I like it
  • -15
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

      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

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

    I successfully solved this problem using BFS 2726786

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

then how can this pass 2801412

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

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

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.

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

    Also TLE is The Leading Edge Ltd. Thank you very much for your useful information.

    → Reply