SRM 717, D2, 250-Pointer (NiceTable)

James S. Plank

Wed Jul 12 21:46:27 EDT 2017
When I read this problem, I figured that it would be a low-scoring one. The reason is that the temptation is to try to reason-out what x and y could be. You want to write a program that says, "If x[0] is '0', then y[0] has to be '1', and y[1] has to be '0', and so on. That can work, but there's a simpler way (at least to me):

The first thing I did was look at the constraints -- t.size() is at most 5, and t[0].size() is at most 5. That means you can do two brain-dead enumerations: There are at most 25 different values for x, and 25 different values for y. If you enumerate them all, that's 210 -- a blink of an eye.

So, here's the strategy -- do power set enumerations for x and y. For each x and y, calculate what t should be, and if t is indeed what it should be, return "Nice." If, after you've enumerated all of the x's and y's, you never got t, return "Not nice."

If anyone is reading this who hasn't taken CS302, you can read about power set enumerations here.


Examples 0 and 1

For each of these examples, you can enumerate x and y with a for loop that goes from 0 to 3. I'll do that in the following table:

X as a number X as a number X as a vector Y as a vector What T should be
0 0 {0,0} {0,0} 00
00
0 1 {0,0} {1,0} 10
10
0 2 {0,0} {0,1} 01
01
0 3 {0,0} {1,1} 11
11
1 0 {1,0} {0,0} 11
00
1 1 {1,0} {1,0} 01
10
1 2 {1,0} {0,1} 10
01
1 3 {1,0} {1,1} 00
11
2 0 {0,1} {0,0} 00
11
2 1 {0,1} {1,0} 10
01
2 2 {0,1} {0,1} 01
10
2 3 {0,1} {1,1} 11
00
3 0 {1,1} {0,0} 11
11
3 1 {1,1} {1,0} 01
01
3 2 {1,1} {0,1} 10
10
3 3 {1,1} {1,1} 00
00

As you can see, example zero works when x = 1 and y = 1, or when x = 2 and y = 2. Example one doesn't work.

Now, you can do this much faster. In fact, if you set x[0] to 0, you can determine what the other values should be, and then test to see if t is consistent. But given these constraints, the pwer set enumerations are a lot easier.


My solution

/* Topcoder SRM 717, D2 250-Pointer.
   NiceTable
   James S. Plank
   Wed Jul 12 22:29:59 EDT 2017
 */

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

class NiceTable {
  public:
    string isNice(vector <string> t);
};

string NiceTable::isNice(vector <string> t)
{
  int x, y, r, c, ok, a, b;

  /* Enumerate all possible values for x with a power set enumeration. */

  for (x = 0; x < (1 << t.size()); x++) { 

    /* Enumerate all possible values for y with a power set enumeration. */

    for (y = 0; y < (1 << t[0].size()); y++) {

      /* Now, for each row and column element, calculate what t[r][c] should be.
         If t[r][c] doesn't match any of these, set ok to false.
         If, after you test all row and column elements, ok is true, then t matched,
         and you return "Nice."  Otherwise, continue the enumerations. */

      ok = 1;
      for (r = 0; r < t.size(); r++) {
        a = (x & (1 << r)) ? 1 : 0;
        for (c = 0; c < t[0].size(); c++) {
          b = (y & (1 << c)) ? 1 : 0;
          if (t[r][c] != '0' + (a ^ b)) ok = 0;
        }
      }
      if (ok) return "Nice";
    }
  }

  /* If you are done and still haven't found a match for t, return "Not nice". */

  return "Not nice";
}