Getting the minimum number of tails of a coin after repeatedly repeating the entire row or column

Question

If coins are placed in a grid, and you can flip only a whole row or column, how can we flip coins to get the minimum number of tails.

I tried using a greedy solution in which I flip a row or column where the number of tails is greater than the heads, and repeat the process until the number of numbers changes. But I found that this approach does not give me the optimal solution several times.

HHT THH THT 

For example, if the coins are placed as above, and I flip the coins below, the resulting value is 3, but in fact the answer is 2.

 1. Flip the row 3 HHT THH HTH 2. Then there exists no row or column where the number of tails are greater than that of heads. 3. But if I flip the column 3, row 3, column 1, there exists a solution whose value is 2. THH HHT HHH 

So, I think this algorithm does not work. Which approach and which algorithm should I use?

Answer 1

First, note that it makes no sense to flip the same row or column for two or more (the best solution is always to either flip the row / column zero or once), and the order that we flip across rows or columns is irrelevant, so we can describe solution as a 2N bitmap. One bit per row and one bit per column. If we flip this row / column once, turn it off if we flip it to zero time.

So, we need to look for 2 ^ (2N) possible solutions, preferring solutions with a large number of zeros.

Secondly, note that for one solution there are four possible coin states:

• Coin did not flip (0 flip)
• The coin was flipped over by its line (1 flip)
• The coin was flipped over by its column (1 flip)
• The coin was flipped both its row and column (2 flip)

Note that states 1 and 4 result in the original value of the coin

Also note that state 2 and 3 result in the opposite initial coin value

Start by expressing the initial state of the coins as a binary matrix (B). A 2N-bit field as 2 binary vectors (R, C) and the total number of tails as a function of this f (B, R, C) and the total number of bits as a function of g ( V_1 , V_2 )

So your goal is to make f> = minimum while minimizing g.

Think that if we first correct our R configuration (which rows will be thrown), how can we solve the problem only for C (which columns will we flip)? In other words, consider the simpler problem of only allowing column flipping and not allowing line reversal. How would you solve this? (hint: DP) Can you redistribute this article to the full issue again?

Answer 2

Not sure about the complete algorithm, but one thing you should definitely try using here is a lot of symmetries in your problem.

Many different coin configurations will be virtually equivalent, so you can rotate, flip the configuration without changing this problem. Most importantly, since you can undo the entire set by flipping all the lines, finding the minimum number of tails is equivalent to finding the minimum number of heads.

In your case it will be

 HHT THH THT HTT TTH TTT 

Having flipped the middle column, and you are done (then you need to flip everything if you really need it).

Answer 3

The obvious solution is to try to use all the features to translate a row or column. There are such possibilities. However, we can solve the problem in O(N^2 * 2^N) with a combination of greedy + brute force.

Create all the possibilities of turning over rows ( O(2^N) ), and for each of them turn over each column with more tails than heads. Take a decision that will give you minimal tails.

That should work. I will add more information about why a little later.

Answer 4

One approach would be to use http://en.wikipedia.org/wiki/Branch_and_bound , alternately looking at new vertical lines and new horizontal lines. There is also some symmetry that you can remove - if you flip all the horizontal lines and the entire vertical line, you will return to where you started, so with the branch and link you can also arbitrarily assume that the leftmost vertical line never flips.

 HHT THH THT 

In this example, if we assume that the leftmost vertical line is not inverted, then if we branch out on the lowest horizontal line, we know the value of the leftmost lowest coin, so we have two possible partial solutions: one in which this the only known coin is fixed on the tails, and one in the heads. If we first recurse in order to try to expand a partial solution in which one known coin is heads, and find that we can extend it to a solution that does not create tails, then we can refuse all partial solutions created by expanding another, therefore that all his descendants must have at least one tail.

I will be the next branch on the leftmost, but one vertical line, which will give us another known coin and continue branching alternately horizontally and vertically.

This would be a feasible way to find the exact solution if there is an almost perfect solution or if the table is very small. Otherwise, you will have to stop it at an early stage or skip reliable solutions to solve the problem in a reasonable amount of time, and you probably won’t get the exact answer.