SRM 594, D2, 1000-Pointer (FoxAndGo2)

James S. Plank

Thu Oct 10 14:16:38 EDT 2019

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: 2013
Competitors who opened the problem: 567
Competitors who submitted a solution: 10
Number of correct solutions: 2
Accuracy (percentage correct vs those who opened): 0.3527
Average Correct Time: 47 minutes, 21 seconds.

This is a challenging problem to wrap your head around. As it turns out, it is most fruitful to think about the connected components than the individual cells. There are two types of connected components:

White: These are components of white tokens.
Empty: These are components of empty tokens, where you can put black tokens.

For example, look at the following board, on the left below:

ooo.
oooo
....
oooo
ooo.

There are two white components and three empty components. Let's number them, as on the right above. We know a few things:

Two components are adjacent if they each contains a cell that is adjacent to the other. So:
Component 0 is adjacent to components 1 and 2.
Component 1 is adjacent to component 0 only.
Component 2 is adjacent to components 0 and 3.
Component 3 is adjacent to components 2 and 4.
Component 4 is adjacent to component 3 only.
White components are only adjacent to empty components, and vice versa.

Now, let's define a concept of safety: An empty component E is safe with respect to a white component W if:

E and W are adjacent to each other.
Not all of E's nodes are adjacent to W.

You'll note that none of components 0, 2 or 4 are safe with respect to any of their adjacent components. However, I can tweak the board to give examples of components that are safe:

ooo..
oooo.
....o
oooo.
ooo..

Now, components 1 and 4 are both safe with respect to the other components. Component 2 is interesting -- it is unsafe with respect to components 0 and 3; however it is safe with respect to component 5.

What does safety have to do with this problem? Well, this:

If component W is safe with respect to component E, then component W may be used to kill component E without any worries about suicide moves. That's because you don't have to place black tokens into all of W to kill E. Think about the example above -- you can easily kill component 5 with three black tokens, because none of those tokens fills up an empty component.
If component E is adjacent to at most one unsafe component, then component E may be killed by surrounding it with black tokens in all of the safe components. Then when you surround it in the unsafe component, you kill it, which means that you remove it from the board and the unsafe component is now safe.
Let's think about that with respect to component 0 above. It is adjacent to components 1 (safe) and 2 (unsafe). You surround it with two tokens from component 0, which is fine because it doesn't "fill up" the component. Then you surround it with the four tokens from component 2. Although it fills up component two, it kills component 0 first, which renders component 2 safe.
After an empty component, safe or unsafe, is used to kill a white component, that component becomes safe with respect to all white components. Let's look at the following board:
.ooo. oooo. ....o oooo.

01112 11112 33334 55556
Now, all empty components are unsafe with respect to white components 1 and 5, so you can't kill them. Component 6 is unsafe with respect to component 4. However, since component 4 is only adjacent to one unsafe component, you can kill it by placing three black tokens on the board, putting the token into component 6 last. Doing this removes the white token from the board, and now those three components (2, 3 and 6) are safe with respect to all of the other tokens. That's nice because we can now kill components 5 and 1.
Once a component becomes safe with respect to another component, it will never become unsafe again. That's nice, because it means that you don't have to worry about the order in which you kill white components.

I hope that gives you a clue about how to solve this problem:

Process the graph, identifying components, and for all white components, determine the unsafe components that they are adjacent to.
If a white component is adjacent to at most one unsafe empty component, then add it to a list of killable components.
While the list of killable components is not empty, kill a component, and then for all adjacent components, make them safe with respect to all of their adjacent components.
If, by doing so, you have made any white components killable, add them to the list.

Here were my data structures:

class Cell {
  public:
    vector <Cell *> adj;          // Adjacency list (easier than using row/column)
    class Component *comp;        // My component
    int row;
    int col;
    int state;                    // '.', 'o'
    int number;                   // Each cell has a unique number - useful for computing component adjacency
};

class Component {
  public:
    int type;                     // '.' or 'o' 
    int number;                   // Unique across components
    vector <Cell *> cells;        // All of the cells in the component
    map <int, Component *> adj;   // Components to which I'm adjacenct.  Keyed by component number.
    map <int, int> adjcount;      // Keyed by component number - # of cells that we have adjacent.
    set <int> unsafe_neighbors;   // Only for white components.  Again, keyed on component number.
};

class FoxAndGo2 {
  public:
    int maxKill(vector <string> board);
    void DFS(Cell *c, Cell *start);           // For determining components
    vector <string> Board;                    // The board
    vector < vector <Cell *> > Cells;         // The cells in a grid
    vector <Cell *> AllCells;                 // All of the cells in a vector
    vector < Component * > White_Components;  // Just the white components.
    vector < Component * > Empty_Components;  // Just the empty components.
    vector < Component * > Components;        // All components
    deque < Component * > Killable;           // The killable components list.
    int Rows;
    int Cols;
};

Plus, I have annotated the output of my program; you can find outputs for each of the examples in the following links (abbreviations: WC = "White Component", UN = "Unsafe neighbor").