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

About the Question in Edu Round Codeforces
Автор FreeHit, история, 20 месяцев назад, По-английски

At first seeing question i just got into using bfs on matrix to get minimum distance if possible but cant get to solution with it. can it be done with bfs?? here is link for question- https://codeforces.com/contest/1721/problem/B

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

»
20 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

It doesn't say: "The sum of n*m over all test cases does not exceed 10^3". So O(t*n*m) exceed time limit.

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

    even though over all worst time will be O(1e7) this will run. can you explain if will go through graph.

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

      For BFS the worst case would be searching the entire graph, which can happen if the laser has a distance of 0 and there exists a path every time. n and m have max values of 1000, so the size of the grid can be up to 10^6. With 10^4 possible test cases this could mean around 10^10 tiles searched in worst case, which will exceed time limit.

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

        if some how constraints permits bfs what will be the code:

        i coded it but gives wrong outputs even matched all conditions: ll n,m,sx,sy,d; ll dist[1010][1010]={0}; bool check(ll x,ll y){ if(x<0||x>=n||y<0||y>=m||dist[x][y]!=0||abs(sx-1-x)+abs(sy-y-1)<=d)return false; return true; }

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

          Note: spoiler parts contains hints to the solution

          The constraints make BFS impossible to use because it's not possible to check up to 10^10 tiles in 2 seconds.

          Hint for problem
          → Ответить