FreeHit's blog

About the Question in Edu Round Codeforces
By FreeHit, history, 2 years ago, In English

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://mirror.codeforces.com/contest/1721/problem/B

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

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

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

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

      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.

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

        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; }

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

          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
          → Reply