Players fighting in a circle

circle-fights.cpp

vector<int> get_losers_for_me(int player) {
  return vector<int>();
}

bool dp(int opponent, int st, int en) {
  int opponent_index = get_player_index(opponent, st, en);
  if (opponent_index == -1) return false;
  if (abs(st - en) == 0) return true;
  if (DP[opponent][st][en] != -1) return DP[opponent][st][en];
  
  bool possible_to_win_left = false,
        possible_to_win_right = false;
  vector<int> losers_for_me = get_losers_for_me(opponent);
  for (auto player : losers_for_me) {
    possible_to_win_left ||= dp(player, st, (opponent_index - 1 + n) % n);
    possible_to_win_right ||= dp(player, (opponent_index + 1) % n, en);
  }
  return DP[opponent][st][en] = possible_to_win_left && possible_to_win_right;
}

vector<int> get_winners(const vector<int>& circle) {
  int n = circle.size();
  
  vector<int> winners;
  for (int i = 0; i < n; ++i) {
    if (dp(circle[i], 0, n - 1))
      winners.push_back(circle[i]);
  }
  return winners;
}

// vector<int> get_losers_for_me(int player) {
//   // TODO
//   // Look at given data structure to find out:
//   // who are the opponents this player can win against
//   return vector<int>();
// }

// // Returns true if player (opponent param in dp function below) can win in [st, en] part of circle
// // This can be used to determine if a player can win the whole circle at the end
// // Recursion:
// // f(player, st, en) = f(opponent_left, st, player_index - 1) && f(opponent_right, player_index + 1, en)
// // ^ For each opponent of player we try to win on both left and right sides of player in [st, en]
// bool dp(int opponent, int st, int en) {
//   int opponent_index = get_player_index(opponent, st, en);
//   // Player not in range of [st, en]
//   if (opponent_index == -1) return false;
//   // Only one player left!
//   if (abs(st - en) == 0) return true;
//   // We already saw this player :)
//   if (DP[opponent][st][en] != -1) return DP[opponent][st][en];
  
//   // Do heavy lifting
//   bool possible_to_win_left = false,
//         possible_to_win_right = false;
//   vector<int> losers_for_me = get_losers_for_me(opponent);
//   for (auto player : losers_for_me) {
//     possible_to_win_left ||= dp(player, st, (opponent_index - 1 + n) % n);
//     possible_to_win_right ||= dp(player, (opponent_index + 1) % n, en);
//   }
//   return DP[opponent][st][en] = possible_to_win_left && possible_to_win_right;
// }

// vector<int> get_winners(const vector<int>& circle) {
//   int n = circle.size();
  
//   vector<int> winners;
//   for (int i = 0; i < n; ++i) {
//     if (dp(circle[i], 0, n - 1))
//       winners.push_back(circle[i]);
//   }
//   return winners;
// }