SRM 663 D2 250-Pointer (ChessFloor)

James S. Plank

Sat Nov 12 01:08:15 EST 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: 2015
Competitors who opened the problem: 664
Competitors who submitted a solution: 479
Number of correct solutions: 345
Accuracy (percentage correct vs those who opened): 52.00%
Average Correct Time: 20 minutes, 8 seconds.

The key to this problem, in my opinion, is to not try to be too smart about it. Treat it as an enumeration problem -- enumerate all combinations of square colors, and for each combination, calculate how many changes it takes to make the checkerboard with that combination. There are 26*25 = 650 combinations of lower case letters that don't equal each other. For each of these, calculate the number of changes, and keep track of the minimum.

Solution.cpp

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

class ChessFloor {
  public:
    int minimumChanges(vector <string> floor);
};

int ChessFloor::minimumChanges(vector <string> floor)
{
  int i, j, b, w;
  int best, nc;

  /* Sentinelize best so that it is bigger than any legal answer. */

  best = floor.size() * floor.size() + 1;

  /* Enumerate all combinations of "black" and "white" */

  for (b = 'a'; b <= 'z'; b++) {
    for (w = 'a'; w <= 'z'; w++) {
      if (b != w) {

        /* For each of these, calculate the number of squares
           that you have to change to make it work. */

        nc = 0;
        for (i = 0; i < floor.size(); i++) {
          for (j = 0; j < floor.size(); j++) {
            if ((i+j)%2 == 0 && floor[i][j] != b) nc++;
            if ((i+j)%2 == 1 && floor[i][j] != w) nc++;
          }
        }

        /* Keep track of the minimum */

        if (nc < best) best = nc;
      }
    }
  }

  /* Return the minimum */

  return best;
}