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:

As far as I see this is an algorithm question and not a programming question. You shouldn't start to write the code before you finished the algorithm. Please provide a harder test case — Thomas Sablik
@ChristiePPP as side note, I guess you're misunderstanding the use of the ternary operator. — Moia
@Moia isn't the ternary operator refers to (statement)?(true expression):(false expression); — ChristiePPP
@ThomasSablik my method originally thought is to switch once for column and once for row in order to get the result because the original test case I get is the simple one which I can implement this silly method — ChristiePPP
I think what @Moia is referring to you using the ternary operator as an if-statement, while ignoring that it is an expression that actually returns a value (which you can do; your code works). For example: (test) ? A = 1: A = 2; can also be written as A = (test) ? 1 : 2; which would be more in line with the operators intended use. — Frodyne

Peter Cheng Peter Cheng · Accepted Answer · 2019-11-26T14:06:53

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.

Coin Flipping Counting Game C++ Data Structure！

4 Answers