SRM 717, D2, 250-Pointer (NiceTable)

James S. Plank

Wed Jul 12 21:46:27 EDT 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
A commented solution.
tests.sh. MD5 Hash: 0f9fb3e1488d42767c5e0e7d02ede61a
answers.txt. MD5 Hash: 47d609f36db052621cda60c6eaa77a7b
Problem Given in Topcoder: July, 2017
Competitors who opened the problem: 351
Competitors who submitted a solution: 262
Number of correct solutions: 170
Accuracy (percentage correct vs those who opened): 48.4%
Average Correct Time: 23 minutes, 17 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given a vector of strings called t.
Each string in t is the same size, and is composed of the characters '0', '1'.
t has at most 10 rows, and each string has at most 10 characters. (Topcoder's original constraints were 5 instead of 10).
t is considered "Nice" if there exist strings x and y such that:
- x.size() equals t.size().
- y.size() equals t[0].size().
- Both x and y are composed of just the characters '1' and '0'.
- If we consider all of the characters in t, x and y to be numbers, then for all i and j, t[i][j] is equal to x[i] XOR y[j].
Return "Nice" if t is Nice and "Not nice" otherwise.

Examples

 
#     t         Answer
-   --------    --------------------------------------
0   { "01",     "Nice" -- x = y = "10" works.  So does x = y = "01"
      "10" }    

1   { "01",     "Not Nice" -- You get the following equations for t to be nice:
      "11" }               x[0] XOR y[0] = 0
                           x[0] XOR y[1] = 1
                           x[1] XOR y[0] = 1
                           x[1] XOR y[1] = 1
                 When you set x[0] = 0, you'll find it's impossible to set the rest.  Same with x[0] = 1.

2   {"0100",     "Nice".  One setting is x = "101" and y = "1011".
     "1011",
     "0100"}


3   {"11",       "Not nice"
     "10",
     "11",
     "11",
     "11"}

Testing yourself

I have the standard tests.sh and answers.txt. See the Cryptography problem if you don't know how to use them.

Hints

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'll 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 10, and t[0].size() is at most 10. That means you can do two brain-dead enumerations: There are at most 2¹⁰ different values for x, and 2¹⁰ different values for y. If you enumerate them all, that's 2²⁰ -- well fast enough for Topcoder.

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 power 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";
}