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 2^{5} different values for x, and 2^{5} different values for y. If you enumerate them all, that's 2^{10} -- 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.
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.
/* 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"; } |