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
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.
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?)
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.
UPD: I got what are you doing. Ignore this comment.
And there are no more than two vertices in each column and each row of the same distance from the sourceThis is not true, take for example this:
There are three points with distance 7 from the point with number 2 in the first row. And this construction can be extended.
Ah, get it, thanks! Nice thingy, actually. I wonder if any other task may come out of 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.
Can you please elaborate on why 1.5e6 is not enough? I think it is way more than what is actually required.
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)
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
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.
Actually it's the first test from the hacks) Kudos to participants for helping us with tests!
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.net/contest/884/submission/47313123
same code without the random bfs fails on test 42: https://codeforces.net/contest/884/submission/47313132
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.
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...
One of the many features for which I love CF!!
BFS requires O(nm) memory for n × m grid, see e.g. here: