0ms with aggressive state space reduction

• Sharing my 0ms solution with detailed explanation:

First, let's apply standard backtracking/dfs with memoization, but keeping the game state abstract:

``````class Solution {
unordered_map<GameState, bool, GameStateHash> cache;
bool canWin(const GameState& s) {
auto it = cache.find(s);
if (it != cache.end()) return it->second;
vector<GameState> next = s.generatePossibleNextMoves();
for (const GameState & n : next)
if (!canWin(n)) return cache[s] = true;
return cache[s] = false;
}
public:
bool canWin(const string& s) { return canWin(GameState(s)); }
};
``````

The naive implementation of a GameState can be a string with +/- and generatePossibleNextMoves() from the easy version of the problem.

Now, let's see how we can define the GameState to have 0ms runtime. In a nutshell, we can compress/reduce state space, by merging similar game states with the same outcomes (e.g. beginner-wins or beginner-loses).
Example: following game states are actually the same:

``````+++-++++-+++++
+++++-++++-+++
++++-+++++-+++
---+++--++++---+++++--
``````

Thus, we can encode these states as (3,4,5): an ordered list of integers, where each integer is a length of a chains of consequtive +-es.

It's also easy to see that singe + can be ignored. ++ and +++ same, so we can encode both ++ and +++ as 3 (for consistency), and skip 1-s.

This is already pretty great state space reduction, isn't it? But we can do much better:

Consider “symmetric” states, where each number repeats even number of times (example: 3,3,4,4,9,9,9,9). It is easy to show that every symmetric state is a beginner-loses state. It is easy to show that winning strategy exists for the 2nd player, since 2nd-player can always mirror the move of the opponent at each step. Thus, those “symmetric” states, being “beginner-loses” are equivalent to the empty state (). Similarly, it is also easy to show that removing a symmetric sub-state from the game-state doesn't change the outcome. E.g. (5,5,6,6,6,7,7,7,7,8,8,8,8,8) after removing a symmetric sub-state (5,5,6,6,8,8,8,8) becomes (6,8).

Thus, each game state can be represented as a set of unique integers: set < int >

Note, that we need to implement generatePossibleNextMoves(), so we need to actively add and remove numbers to the set.

Addition a number to the set and removal of the number to the game state in our reduced state space becomes one operation: toggle(), which adds the number if it was absent and removes if it was present.

``````struct GameState {
set<int> chains;
int hash = 0;
GameState() {}
GameState(const string& s) {
int l = 0;
for (int i=0; i<=(int)s.size(); i++)
if (s[i]=='+') l++; else toggle(l), l = 0;
}

void toggle(int len) {
if (len<=1) return;
if (len==2) len = 3;
auto it = chains.find(len);
if (it == chains.end()) chains.insert(len); else chains.erase(it);
hash ^= len * len * len;
}
};
``````

Generating possible moves is trivial:

``````struct GameState { // continued
vector<GameState> generatePossibleNextMoves() const {
vector<GameState> result;
for (int len : chains) {
GameState s = *this;
s.toggle(len);
if (len <= 3) result.push_back(s);
else {
for (int j=0; j<len-2 && j<len/2; j++) {
GameState t = s;
t.toggle(j);
t.toggle(len-2-j);
result.push_back(t);
}
}
}
return result;
}
};
``````

We also need a hashcode and equality comparer for the GameState, so we can use it as a key in unordered_map. For efficiency, the hash code is stored directly as a field, and updated incrementally on each toggle() operation.

``````struct GameStateHash { size_t operator() (const GameState& s) const { return s.hash; } };

bool operator == (const GameState& a, const GameState& b)
{ return a.hash == b.hash && a.chains == b.chains; }
``````

Further optimization is possible:

• instead of set<int>, you can also use bitset<> class.

• instead of generating new set of possible moves you can incrementally change the state

• The part "removing a symmetric sub-state doesn't change the outcome" is indeed inspiring.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.