SRM 729, D2, 250-Pointer (BrokenChessboard)

James S. Plank

Fri Sep 7 13:55:09 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
A solution.
Problem Given in Topcoder: February, 2018
Competitors who opened the problem: 371
Competitors who submitted a solution: 267
Number of correct solutions: 182
Accuracy (percentage correct vs those who opened): 49.1%
Average Correct Time: 16:00

There are two possible checkerboards -- those that start with 'B' in (0,0), and those that start with 'W' in (0,0). Let's say your board starts with a 'B' in (0,0). Then, given r and c, can you come up with a way to determine whether the square in (r,c) is a 'B' or a 'W'? Try looking at (r+c)%2.

Now, to solve this problem, you should run through boards, and maintain two sums:

SB is the number of squares you need to change if the checkerboard has 'B' in (0,0).
SW is the number of squares you need to change if the checkerboard has 'W' in (0,0).

When you look at a square, you'll be incrementing exactly one of SB or SW. At the end of your loop, return the smaller of the two sums.

Here's my solution (in Solution.cpp):

/* Solution to Topcoder SRM 729, D2, 250-pointer.
   BrokenChessboard
   James S. Plank
   Fri Sep  7 14:00:20 EDT 2018
 */

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

class BrokenChessboard {
  public:
    int minimumFixes(vector <string> board);
};

int BrokenChessboard::minimumFixes(vector <string> board)
{
  int r, c;
  int SW, SB;

  SW = 0; 
  SB = 0;

  /* Loop through every square of the checkerboard. */

  for (r = 0; r < board.size(); r++) {
    for (c = 0; c < board[r].size(); c++) {

      /* These squares will match the (0,0) square.  
         So, if they are 'B', you need to add one to SW.
         Otherwise, you add one to SB. */

      if ((r + c) %2 == 0) {
        if (board[r][c] == 'B') SW++; else SB++;

      /* These squares will match the (0,1) square.  
         So, if they are 'B', you need to add one to SB.
         Otherwise, you add one to SW. */

      } else {
        if (board[r][c] == 'W') SW++; else SB++;
      }
    }
  }

  /* Return the smaller of the two sums. */

  return (SW < SB) ? SW : SB;
}