My Solution to 253C - Text Editor is producing TLE? here is the link to solution 2797003
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
because there is n ( <= 100 ) lines of text with length <= 100 000 (10^5) total your bfs produces 10^9 states (~ vertices of graph).
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...
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
I successfully solved this problem using BFS 2726786
then how can this pass 2801412
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.
Also TLE is The Leading Edge Ltd. Thank you very much for your useful information.