stark_arya's blog

Queue Overflow in BFS
By stark_arya, history, 5 years ago, In English

I am trying to solve this question 884E. Here we are given a simple 0-1 grid of max size (2^12 * 2^14). We need to determine the number of connected components consisting of 1's. The memory limit is 16 MB.

To solve this, I am using bfs with a circular queue of fixed size around 1.5e6. The whole thing (queue + grid) fits into the memory limit.

For every non-visited 1, I am starting a bfs to cover all 1's in its component. The maximum number of cells in the queue at a time should be O(n+m). The problem is my queue is overflowing in one of the cases for no reason I see.

Is there something wrong with the logic or with the implementation? My code

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

»
5 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

As far as I know 1.5e6 is not enough for this problem and if you increased it more you will fall into MLE. I don't think it's possible with bfs or dfs.

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

    I mean, is it really?) I know the intended solution but should this one fail? Seems that the queue has about O(n + m) vertices at the time for real. Like it can only store vertices of some distance d and d + 1 from the source. The second type are O(first type). And there are no more than two vertices in each column and each row of the same distance from the source, isn't it? Or am I missing something here too?)

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

      That's what my logic is based on. The maximum number of elements in the queue at a time is O(n+m). My queue's size is much greater than that.

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

        UPD: I got what are you doing. Ignore this comment.

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

      And there are no more than two vertices in each column and each row of the same distance from the source

      This is not true, take for example this:

      1 0 1 1 1 0 1
1 0 1 0 0 0 1
1 0 1 1 0 0 1
1 0 0 1 0 0 1
1 1 1 2 1 1 1

      There are three points with distance 7 from the point with number 2 in the first row. And this construction can be extended.

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

        Ah, get it, thanks! Nice thingy, actually. I wonder if any other task may come out of it)

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

        Oh, I see!!. In case of obstacles in a grid, the O(n+m) thing does not hold true. Thanks a lot for the nice explanation.

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

    Can you please elaborate on why 1.5e6 is not enough? I think it is way more than what is actually required.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 6   Vote: I like it +16 Vote: I do not like it

      i think something like this works, its a fractal based design so it can be created for bigger fields:

      (i dont know if the construction leads to the actual worstcase)

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 4   Vote: I like it +11 Vote: I do not like it

        on a 35x35 field this yields to a queue size of something around 180

        this should already be enought to fill your queue if done on a 2^12 field

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

          Wow! Thanks for the nice visualization. Kudos to you and to the problem setters to be able to think of such test cases. Thanks for your help.

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

            Actually it's the first test from the hacks) Kudos to participants for helping us with tests!

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

              well i still believe that it should be easy to pass with this solution... in my testcase its essential to start the bfs at the green position to get the worstcase. So what happens if we start the bfs at some random positions before we fill everything systematically (or just go through the positions in a random order)? that should work just fine or? (sure the green place can be extended but i dont think that that would help much as it would decrease the space for the actual pattern...)

              an accepted version with queue and some random bfs: https://codeforces.com/contest/884/submission/47313123

              same code without the random bfs fails on test 42: https://codeforces.com/contest/884/submission/47313132

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

                if you have no idea what to do or you don't want to do some complicated construction, then just do something random!

                Nice trick btw!! Greatly reduces the chances of encountering the worst case scenario.

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

                  actually i wonder right now why this worked... as in my testcase this would only half the required queue space... (if you start to the right of the green point the other sub tree still requires a big queue and vice versa) and it should be easy to get a better fraction than a half (so you will only safe a quater of queue space by this or even less...)

                  so it should be possible to create a testcase against this...

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

              One of the many features for which I love CF!!

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

      BFS requires O(nm) memory for n × m grid, see e.g. here:

      → Reply