Coin Flipping Counting Game C++ Data Structure！

Question

Here is the question. In the game, there is a rectangular grid of coins, with heads =1 and tails = 0. The game has one simple rule: the player cannot flip a single coin, instead, the player can choose one row (or one column) and flip all the coins in that row (or that column) simultaneously. The objective of the game is to find out a strategy to flip the coins so that the number of head coins is maximized. The first input value is row >> then column >> and the coins

Sample inputs:
5 4
1010
0101
1010
1010
1010 //Sample output of this: 20
5 4
0010
1101
0110
0110
1011 //Sample output of this: 17

I finished my code using the method of counting the '0' and '1', if zero is more, switch it. This method only pass the simple test case, but when it goes to the hard one, it failed because there are some cases require twitting more than once. I cannot think of another better way of dealing with it.

Here is my code:

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool ConeIsMore(vector <vector<char> > table, int size, int j) {
    int countzero = 0;
    int countone = 0;
    for (int i = 0; i < size; i++) {
        (table[i][j] == '0')?++countzero: ++countone;
    }
    if (countone >= countzero) {
        return true;
    }
    return false;
}

bool RoneIsMore(vector <vector<char> > table, int size, int i) {
    int countzero = 0;
    int countone = 0;
    for (int j = 0; j < size; j++) {
        (table[i][j] == '0') ? ++countzero : ++countone;
    }
    if (countone >= countzero) {
        return true;
    }
    return false;
}

int main() {
    //Initialise row and column
    int row; 
    int column;
    while (cin >> row >> column) {
        //Initiallise 2D vector
        vector <vector<char> > table(row, vector<char>(column));

        //get each digit of number and store it into number
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                cin >> table[i][j];
            }
        }

        //check for column
        for (int j = 0; j < column; j++) {
            if (!ConeIsMore(table, row, j)) {
                for (int i = 0; i < row; i++) {
                    (table[i][j] == '0') ? table[i][j] = '1' : table[i][j] = '0';
                }
            }
        }

        //check for row
        for (int j = 0; j < row; j++) {
            if (!RoneIsMore(table, column, j)) {
                for (int i = 0; i < column; i++) {
                    (table[j][i] == '0') ? table[j][i] = '1' : table[j][i] = '0';
                }
            }
        }

        //Count One in the table
        int ans = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                (table[i][j] == '1') ? (ans++) : (ans = ans);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

When I study through the test cases, I fount out there are some requires checking various time which makes me feel my method is not a good one. Can anyone suggest a better way in dealing with it? Thank you so much.

The followings are harder test cases:

5 4
0010
1101
0110
0110
1011 //17

5 4
0110
1111
0101
0110
0100  //16

5 4
0110
1001
0011
1110
1000 //16

5 4
1100
0001
1111
0101
1010 //16

5 4
0101
0110
1001
1000
0011 //16

5 4
0111
1100
0100
1000
1011 //16

5 4
1101
1110
0111
1011
0111 //15

5 4
1100
1001
0110
1001
1000 //17

Answer 1

I'm sorry, but @Peter Cheng's answer can be incorrect with some test cases. Simply try this with his algorithm:

1 0 1 0
1 1 0 1
1 0 0 1
1 1 1 1
1 1 1 0

C[-5,-1,-1,-1]

R[0,-2,0,-4,-2]

With his algorithm the answer will be 14. But, you can flip the third row, then flip the fourth column for 15 heads.

I suggest testing both cases. If you encounter a zero value, your decision to flip should be based on whether the first coin of that row or column is already a head. And, if you encounter a zero value, your decision to flip should be based on whether the first coin of that row or column is not a head, then take the higher value for the final answer.

Answer 2

The following is my code after Peter Cheng's help in providing the algorithm. It works till calculating the row and column but cannot flip the table.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int RcountDifference(vector <vector<char> > table, int col, int var) {
    int Difference = 0;
    for (int j = 0; j < col; j++) {
        if (table[var][j]=='1') {
            Difference -= 1;
        }
        else {
            Difference += 1;
        }
    }
    return Difference;
}

int CcountDifference(vector <vector<char> > table, int row, int var) {
    int Difference = 0;
    for (int i = 0; i < row; i++) {
        if (table[i][var] == '1') {
            Difference -= 1;
        }
        else {
            Difference += 1;
        }
    }
    return Difference;
}

int main() {
    //Initialise row and column
    int r;
    int c;
    while (cin >> r >> c) {
        //Initiallise 2D vector
        vector <vector<char> > table(r, vector<char>(c));

        //get each digit of number and store it into number
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                cin >> table[i][j];
            }
        }

        //Build two arrays to store the value "zero-one"
        vector <int> row;
        vector <int> column;

        //store for vector
        //For Row
        for (int i = 0; i < r; i++) {
            row.push_back(RcountDifference(table, c, i));
        }
        //For Column
        for (int j = 0; j < c; j++) {
            column.push_back(CcountDifference(table, r, j));
        }

        Flip(r, c, table, row, column);
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                //Flip for row
                if (row[i]>0) {
                    (table[i][j] == '0') ? '1' : '0';
                }
                else if (row[i] == 0 && table[i][0]=='0') {
                    (table[i][j] == '0') ? '1' : '0';
                }
                else {
                    (table[i][j] == '0') ? '0' : '1';
                }
                row.clear();
                row.push_back(RcountDifference(table, c, i));
                column.clear();
                column.push_back(CcountDifference(table, r, j));
                //Flip for column
                if (column[j] > 0) {
                    (table[i][j] == '0') ? '1' : '0';
                }
                else if (column[j] == 0 && table[0][j] == '0') {
                    (table[i][j] == '0') ? '1' : '0';
                }
                else {
                    (table[i][j] == '0') ? '0' : '1';
                }
                row.clear();
                row.push_back(RcountDifference(table, c, i));
                column.clear();
                column.push_back(CcountDifference(table, r, j));
            }
        }

        //Output Check
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                cout << table[i][j];
            }
        }

    }

    return 0;
}

After I finished my solution, I would like to put it here as well, for people like me who are new to coding, it will be good to learn different questions.

Answer 3

We need to track how many more heads your total will have if you flip each column or row. For a given row or column, calculate the number of tails minus the number of heads to yield the net increase of heads, should you decide to flip that row or column. Store these values in two arrays, one for columns and one for rows. At this point you should have two arrays, one of size row and one of size column, with either negative, zero, or positive values.

5 4
1010
0101
1010
1010
1010 //Sample output of this: 20

row: [0, 0, 0, 0, 0]
column: [-3, 3, -3, 3]

Now iterate through the row and column vector and if you encounter a positive value, you need to flip that row or column. If you encounter a negative value, do not flip. If you encounter a zero value, your decision to flip should be based on whether or not the first coin of that row or column is already a head or not. This will help solve edge cases like this:

2 2
10
01 // output should be: 4
row: [0, 0] // How can we know to flip row 1 but not row 0? Because arr[0][0] = 1 already
column: [0, 0]

The other step you must take is when you flip a row, you must update the values in your column array as well and vice versa. You should also update the 2d coins array in memory as well to reflect the new state. After the first flip the problem state looks something like this

5 4
1010
1010 // this row was flipped because arr[1][0] was 0
1010
1010
1010 

row: [0, 0, 0, 0, 0]
column: [-5, 5, -5, 5]

Continue until there are no more rows or columns that can be flipped. There is a good opportunity for recursion in the implementation.

Answer 4

You should perhaps output result of your strategy not only count of heads to see better what is going on. Two ideas of improving your implementation:

1) Your code is not doing what you describe your algorithm is when there is even number of coins in row or column. You say:

counting the '0' and '1', if zero is more, switch it.

Your code does:

if (!ConeIsMore(table, row, j)) {
    // switch it
}

It switches when there are not more heads. As result when there is even number of coins you switch also when the count of heads and tails is equal. Switching when the counts are equal is speculative, it is unclear if it improves anything and so you should perhaps treat it specially.

2) You can perhaps continue iterating until there are no columns nor rows left in what are more tails than heads.

As of data structure std::vector<bool> table(row*column) is likely going to be more efficient but also to take bit more care to handle correctly.