4

I have been struggling with an algorithmic problem for a couple of days now, I tried a lot of ways to solve it, but they weren't accurate / fast enough, so I'm counting on you - I'm looking for tips or anything what would be helpful.

So the problem is following, there is square two-dimensional array of bools 

bool array[n][n] (n <= 1000)

And as you can presume, it is full of ones and zeros, but ones are always grouped in rectangles, like that:

11100
11100
00001
11100

The algorithm can change two zeros into ones and form as big as possible shape of ones (the formed shape doesn't have to be rectangular) and return the number of ones forming this shape. Diagonal connections are not counted.

for instance:

101
010
101

Should return 7. The problem is that, this algorithm should work as fast as possible, let's say 1-2 seconds for 1000x1000 array is going to be the upper border. So what I have tried:

  1. Firstly, I grouped the squares of ones into groups and formed an array with their sizes and X, Y of corners. Then I was checking the relations between them, but it was very hard to effectively find the group with the biggest potential (especially when the given array was like a chessboard). I was just checking the groups one after another, check its adjacent groups, and then check the next ones for a second additional one to put. It was like brute force, so checking about 500 000 (for a 1000x1000 chessboard) groups was just too much.

  2. Another method I tried was to create an array with its neighbors for every zero, but it was very unoptimal to find another group of ones, again, it was brute force.

I'm sorry for my English if there are any mistakes, I'm not a native speaker. So do you have any tips for me, any links to algorithms or similar problems? Maybe somebody is going to write a (pseudo)code? Anything you can do to help, I will be grateful.

Improve this question
8
  • A few things aren't clear. What do you mean by the ones are "always grouped in rectangles"? Given any array of 1s and 0s, it's always possible to break the 1s into (possibly touching, possibly 1x1) rectangles. Commented Nov 10, 2015 at 22:54
  • I am very much an algorith man, and would love to take a crack at this. Sounds like the sort of problem I do for fun, but I cannot get a handle on what you are trying to do. Why does your "for instance" return 7?. And your first example array has an isolated 1, so the rectangles can be as small as a single boolean, a single cell in the array? Commented Nov 10, 2015 at 22:56
  • What is a "shape"? If two 1s are directly next to each other, are they part of the same "shape"? (This would be termed a connected component.) If so, are diagonal connections allowed? Commented Nov 10, 2015 at 22:56
  • 1
    I think i am getting it. diagonal connections are not counted, so in his for instance, you could change the zeros at row 1, col 2 and row 3 col 2, then you'd get an H shape that is made of 7 zeros. You could also change row 2, col 1 and row 2 col 3, and you'd also get an H shape of 7 ones. But if you changed row 1 col 2 and row 2 col 1, you'd only get a triangle shape that has 6 ones, so not optimal (not max number of ones). Commented Nov 10, 2015 at 23:03
  • Question, to start with, are all the rectangles of ones always disconnected disconnected from the others, or is is possible to have rectangles that are adjacent? Commented Nov 10, 2015 at 23:05

2 Answers 2

Reset to default
1

The first thing that occurred to me is brute force. But 500,000 x 500,000 cells-containing-zero would indeed be too slow.

So then I thought about this: for each cell-containing-zero, work out how many 1's you can join by setting it to 1. Create an object called OnTurning to represent this action. Rank them from the biggest regions down. Then for each pair of OnTurnings, in rough order of the sum of their region sizes, work out the size of their union. Stop searching when the sum of the region sizes of the OnTurnings is less than the largest union you've found so far.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thank you for your response, 500,000 x 500,000 cells isn't needful, there are going to be 1000x1000 cells at most. I'm not very into OOP, so let's say OnTurning would be an int array[x][y] if it is not going to change anything (if it is - just say). Your method sounds promising, I'm going to try it today, thanks to you again.
@Wolf that's not 500,000×500,000 cells, that's 500,000×500,000 pairs of cells in a 1,000×1,000 grid
So I writed an algorithm you described, but there is one big problem with looking for the best combination of two additional ones. Because two similar ones can link the same unions, the sum of the linkings is depending on how much unions are connected by both of the additional 1s.
1

Compute a list of connected components and their sizes. For each 1-cell, keep a pointer to its connected component.

Now when you flip a cell fron 0 to 1 and back, you can quickly update all components adjacent to it with the new cell count. Moreover, you only ever need to flip cells adjacent to connected components. Further still, when you flip a cell, you only need to try another cell if it is adjacent to the newly created block.

I think this will allow for an algorithm that is linear in total number of cells.

Improve this answer

4 Comments

Thank you for your answer. The problem is that I need to find the best combination, for i.e. 1000x1000 chessboard it wiill have to be a brute force, and It wouldn't be so effective.
"I need to find the best combination". Yes, that's what I'm talking about. "it will have to be a brute force". If by brute force you mean trying all 1000×1000×1000×1000/2 pairs of cells, then no, it doesn't have to be, and it isn't.
If we have a square area with n = w*w cells, then I think the following instance will take O(w^3) time (i.e., O(n^(3/2)) time): The input consists of alternating rows of 1-cells and 0-cells. Now there are w^2/2 0-cells that are adjacent to a connected component, so your outer loop runs O(w^2) times to consider them all; for each one, there are 2w 0-cells that are adjacent to the newly-formed block (the row of w 0-cells above the top component, and the row below the bottom component), for O(w^3) overall.
@j_random_hacker Looks like you're right. Perhaps this can be optimized further by eliminating "similar" 0-cells.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.