Member Count: 598,862 - December 10, 2013  [Get Time]
 SRM 525
Added by [[rng_58]] , last edited by kauesilv on Dec 07, 2011  (view change)
Labels:
(None)

Single Round Match 525
Tuesday, November 29th, 2011

## Match summary

Almost 2000 programmers from all over the world participated in SRM 525. The stakes were high: The top three rated coders coincided in this match. On top of it, the problem set this time would reward imagination and analysis as opposed to prior knowledge in common algorithms. At the end, the outcome was a victory for Petr, the fast submission for the 525-points with over 20 points of advantage over the second fastest submission was the determining factor that allowed him to win over Eryx - Barely 8 points behind. In an unsurprising turn of events, the usual suspects ACRush, lyrically and bwps acquired the third, fourth and fifth places, respectively.

In division 2, it was harder than usual to solve all three problems. Those coders with the consistence to score the triple were rewarded with the first two places. It was newcomer night in China that day as two of their new assets dominated the division summary: isundaylee and wormsty.

# The Problems

Used as: Division Two - Level One:
 Value 250 Submission Rate 1038 / 1144 (90.73%) Success Rate 951 / 1038 (91.62%) High Score Ana_m for 249.73 points (0 mins 56 secs) Average Score 199.17 (for 951 correct submissions)

The key observation in this problem is that, since there are only two rows, we can always move from one column to another as long as any of the tiles of the other column is dry (Diagonal moves are allowed by the statement). If both tiles of a column have water, it is impossible to pass through it from the left column. Thus every column must contain at least one dry spot. If that is true, return YES. Else NO.

```string isReachable(vector <string> road)
{
// If any column in the input contains two tiles covered by
// water, it is impossible to cross. Else it is possible.
for (int i=0; i<road[0].size(); i++) {
return "NO";
}
}

return "YES";
}```

DropCoins
Used as: Division Two - Level Two:
 Value 600 Submission Rate 331 / 1144 (28.93%) Success Rate 189 / 331 (57.10%) High Score ashish.net for 599.50 points (0 mins 49 secs) Average Score 327.92 (for 189 correct submissions)
Used as: Division One - Level One:
 Value 300 Submission Rate 705 / 794 (88.79%) Success Rate 582 / 705 (82.55%) High Score bapcoi for 298.34 points (2 mins 7 secs) Average Score 212.60 (for 582 correct submissions)

Let us begin taking a look at what the operations represent. At each step, we move all the coins up, down, right, or left. If they go outside the border of the board, the coins are removed. This removal is similar to the removal of a row or column in one of the extremes, the only difference is that, in practice an empty row or column will be added to the other side of the board. The following image depicts the idea when we move all the coins up - It is equivalent to removing the first row and adding a new empty row to the bottom.

As the row or column that gets added in each step is empty, we can temporarily consider each step as removing a whole row or a whole column in one of the extremes of the board. From here we can conclude that the coins after the last step will have to come from one of the sub-rectangles of the original board.

In the last picture, the coins in the last setup all come from inside the same sub-rectangle. It always holds that at any point, all the coins in the board will be from an original subrectangle, it is also true that any subrectangle in the input can become the container of the coins that remain in the last step. Remember that the condition is to have exactly K coins in the final setup. This is possible if and only if there is at least one rectangle that contains exactly K coins.

We can try and test each of the sub-rectangles of the input board and verify if it has K coins. Note that we also need to minimize (and find) the number of steps to reach a sub-rectangle with K coins. So, of each of these rectangles, we need to calculate the minimum number of steps to end with only the coins inside the rectangle. The minimum number of steps across all the rectangles is the answer.

There is the technical aspect of picking all the rectangles and counting the number of coins inside them. There are O(w*w*h*h) sub-rectangles in a board of width w and height h. For each of them, we will need a O(w*h) loop to count the number of coins. Although we can avoid this extra w*h factor of execution time by precalculating the sum S[i][j] that contains the total sum of coins for the rectangle formed by the intersection of bottom j rows and the i left columns (We can then use this precalculated matrix to count the number of coins in any subrectangle in O(1) time). This optimization is not actually necessary due to the constraints of 30x30 - a O(w*w*w*h*h*h) algorithm with little overhead can run well in topcoder's servers, (plus many of the factors become smaller than w or h depending on the previous factors).

Once we have a given sub-rectangle and we know that it contains K coins, we need to calculate the minimum number of steps needed to end with the coins inside the rectangle. In this regard, consider that we have to remove: a columns from the left, b columns from the right, c rows from the top and d rows from the bottom. Each operation deals either only with columns or with rows, thus we can consider the vertical and horizontal problems separately.

Let us consider the vertical problem: We want to remove c top rows and d bottom rows from the original rectangle. What is the minimum number of up and down operations necessary?.

In the example, we need to remove 1 row from the top and 2 rows from the bottom. However, note what happens when we do a move up or a move down. A new row is added. Note, however, that this new row will also need to be removed later before we get to remove the rows on the other side that we were to remove in the first place. Each [up] move we use will increase the number of [down] moves we will need by 1. This is of course, as long as we do need to perform a move down. Once we only need to remove top or bottom rows, then we can just use a number of [up] or [down] operations equal to the number of rows to be removed. This implies that we have to choose the order of the operations: Shall we first perform the [down] operations to remove the bottom rows or the [up] operations to remove the top rows?. Note that if we first do the down operations, we will need (d * 2 + c) operations, because each down operation we use to remove the bottom rows will increase the number of up operations we will need later by down. If we instead do the [up] operations first, the number of operations will be: (c * 2 + d). Thus the minimum number of operations will be: min(d*2 + c, c*2 + d), which can be simplified to: (d + c + min(d, c) ).

We can then consider that horizontally, columns will behave in the same way. If we have to remove a columns from the left and b columns from the right, then the result will be: (a + b + min(a, b) ). Once we know the cost formula, we can add it to the solution that tried all the rectangles and find the answer.

#### Code

The following Java code needs less than 0.6 seconds to run in TopCoder's servers in its worst case.

```public int getMinimum(String[] board, int K)
{
int w = board.length;
int h = board[0].length();
final int INF = 1000000000; //A large number
int res = INF;

// For each subrectangle of the board:
for (int x0 = 0; x0 < w; x0 ++) {
for (int x1 = x0+1; x1 <= w; x1++) {
for (int y0 = 0; y0 < h; y0 ++) {
for (int y1 = y0+1; y1 <= h; y1++) {
// Count the coins inside the subrectangle:
int coins = 0;
for (int i=x0; i<x1; i++) {
for (int j=y0; j<y1; j++) {
if (board[i].charAt(j)=='o') {
coins ++;
}
}
}
// If there are K coins, find the minimum number of moves to
// end with that subrectangle. Remember the minimum overall.
if (coins == K) {
int a = x0;     //number of left columns  to remove.
int b = w - x1; //number of right columns to remove
int c = y0;     //number of top rows to remove
int d = h - y1; //number of bottom rows to remove.
res = Math.min(res,  a+b+c+d + Math.min(a,b) + Math.min(c,d) );
}
}
}
}
}
return ( (res==INF) ? -1 : res);
}```

MagicalSquare
Used as: Division Two - Level Three:
 Value 950 Submission Rate 37 / 1144 (3.23%) Success Rate 4 / 37 (10.81%) High Score wormsty for 497.47 points (34 mins 37 secs) Average Score 456.58 (for 4 correct submissions)

There were many approaches for this problem. Many coders prefered dynamic programming. It was however, also possible with brute force. What follows is first some arguments to show that the maximum number of ways is not very high and then a polynomial-time algorithm that is built on top of that argument. It is not the fastest solution and it has implementation complications, but it is simple in concept and we can easily verify that it will run in time.

Let us consider that the given rows and columns can be split to find the strings in the grid. If we split the rowString[0] in three parts, we will get the three strings in the first row. If we split rowString[1] in three parts, we will get the contents of the second row. Let us first enumerate the number of ways to split rowString : What is important to consider is the lengths of the fragments, once the lengths are known, the fragments can be found using the contents of rowString[0]. Let us call a, b and c the lengths of the three words in the top row. Please note that we only need a O(T*T) loop to enumerate all the possible ways to split this first row (Where T is the maximum length of the strings in the input[0]) - We can pick (a and b) and find c through a subtraction between the length of rowString[0] and (a+b). The same will happen with rowString[1] if we divide it in two first part of length x and y, the length z of the third part can be found by a substraction. If we were to do a brute force on each of these values, we would need a O(T4) iteration on a,b,x,y and we would find c and z. At this point, we could also brute force to split rowString[2], and then verify that each of the cells we split make the respective columnString value when concatenated, but that would yield a O(T7) complexity in total.

What we need is to confirm that once the lengths of the strings in the first two rows are decided, the rest of the strings have already been decided. For this, let us consider the magical square:

 S[0][0] S[0][1] S[0][2] S[1][0] S[1][1] S[1][2] S[2][0] S[2][1] S[2][2]

Note that we have decided that S[0][0] equals the first a characters of rowStrings[0]. S[0][1] the next b characters, S[0][2] the last c characters. S[1][0],S[1][1] and S[1][2] are also the first x characters, the next y characters and the last z characters of rowStrings[1], respectively. There are also other rules, for example, S[0][0]+S[1][0]+S[2][0] are supposed to equal columnStrings[0]. We already know the first two strings that are part of this concatenation, so we must verify that S[0][0]+S[1][0] forms a prefix of columnStrings[0]. More importantly, once we do verify that they are a prefix, we can find the contents of S[2][0] - Simply the remaining characters of columnStrings[0]. We can do the same with S[0][1], S[1][1], S[2][1] and columnStrings[1]. And the same with columnStrings[2]. After this, you will find all the strings in the square. There is a step left, to verify that S[2][0]+S[2][1]+S[2][2] equals rowStrings[2].

The previous paragraph shows that we only need the lengths S[0][0], S[0][1], S[1][0] and S[1][1], and we will already know if the matrix is invalid or find the remaining strings. From here we can conclude that there are at most O(T4) different ways to make the matrix (one for each tuple of four lengths). Since T = 50, this means that the limit is 6250000. The limit is in fact, smaller, because, for example a+b cannot surpass the length of rowStrigns[0]. And there are the last few constraints we check which will make some combinations of lengths impossible. You can try and verify that for a input that contains only strings of 50 a characters, the result is 879801.

From the conclusion that the number of ways to make the square is not very large, there are two roads we can take: We can try to use a brute-force search using backtracking and making sure to crop choices of lengths that will not be possible. The alternative is to notice that the proof that the number of solutions is small, also works as an algorithm that we can use: In its current state, we need O(T4) iterations for the lengths of the four strings and then we need concatenations and comparisons between strings that each take O(T) complexity. The total is O(T5). Raw complexity order does not really work well to estimate the time it will take, however. Because concatenations and comparisons will represent quite the overhead.

It is possible, to optimize the O(T5) solution so that it does not use concatenation. For example, when we want to verify that S[0][0]+S[1][0] is a prefix of columnStrings[0], we do not need to create the strings S[0][0] and S[1][0]. We already know that S[0][0] is the first a characters of rowStrings[0] and S[0][1] the first x characters of rowStrings[1]. We could compare the characters directly without extraction. This needs some extra thought, however. For example, in total the comparison to verify that they are strings will look like this: compare(a, rowStrings[0],0, columnStrings[0],0) && compare(x, rowStrings[1],0, columnStrings[0],a) - first compare the a characters that begin at the 0-th character of rowStrings[0] with the ones that begin at the 0-th character of columnStrings[0] and then do the same with the x characters at the beginning of rowStrings[1] and then x characters at position a of columnStrings[1] ).

It will surely get more complicated when we want to, for example, compare S[2][0]+S[2][1]+S[2][2] with rowStrings[2]. We first need to find that S[2][0] is equal to the last characters from columnStrings[0] after we take the first (a+x) characters. And do the same for the remaining strings. Then compare each section of columnStrings against a respective section of rowStrings.

Once we have separated each comparison, we have a O(T5) solution with less overhead that can actually be enough to pass in time. However, note that from this point, there is an optimization that will make it O(T4). It is to notice that in all the comparisons we make, we will compare portions of a columnStrings with portions of rowStrings. We can precalculate a matrix of all possible 3*3*T3 comparisons between parts of a row string and a column string. We will need O(T4) steps to precalculate this matrix. Then in the main solution, each comparison will need O(1) time. The total complexity is O(T4).

#### Solution

The implementation requires us to keep track at which substring of which column we have to compare with which substring of which row. It requires some attention to that detail. Once we do finish deciding the substrings to compare, the rest of the solution is simple.

```long long getCount(vector <string> rowStrings, vector <string> columnStrings)
{

// Precalculate the comparison:
// precalc[z] [a][x] [b][y] is true if
// row_a.substr(x,z) == col_b.substr(y,z)

bool precalc[51][3][51][3][51];
memset(precalc,0,sizeof(precalc));
for (int a=0; a<3; a++) {
for (int b=0; b<3; b++) {
for (int z=0; z<=50; z++) {
for (int x=0; x+z<=rowStrings[a].size(); x++) {
for (int y=0; y+z<=columnStrings[b].size(); y++) {
precalc[z][a][x][b][y] =
(rowStrings[a].substr(x,z) == columnStrings[b].substr(y,z));
}
}
}
}
}

int res = 0;
for (int a=0; a<=rowStrings[0].size(); a++) {
for (int b=0; b+a<=rowStrings[0].size(); b++) {
for (int x=0; x<=rowStrings[1].size() && a+x<=columnStrings[0].size(); x++) {
for (int y=0; x+y<=rowStrings[1].size() && b+y<=columnStrings[1].size(); y++) {
int c = rowStrings[0].length() - a - b;
int z = rowStrings[1].length() - x - y;

// String row0[0..a]+row1[0..x] must be a prefix of
//        column0.
if ( !( precalc[a] [0][0] [0][0]  && precalc[x] [1][0] [0][a] ) ) {
continue;
}

// String row0[a..b]+row1[x..y] must be a prefix of
//        column1.
if ( !( precalc[b] [0][a] [1][0]  && precalc[y] [1][x] [1][b] ) ) {
continue;
}

// String row0[a+b..c]+row1[x+y..z] must be a prefix of
//        column2.
if ( !( precalc[c] [0][a+b] [2][0]  && precalc[z] [1][x+y] [2][c] ) ) {
continue;
}

// String col0[a+x..] + col1[b+y..] + col2[c+z..]
// must be equal to row2
int l0 = columnStrings[0].size() - a - x;
int l1 = columnStrings[1].size() - b - y;
int l2 = columnStrings[2].size() - c - z;

if ( l0 + l1 + l2 !=  rowStrings[2].size() ) {
continue;
}

if ( ! precalc[l0] [2][0] [0][a+x]  ) {
continue;
}
if ( ! precalc[l1] [2][l0] [1][b+y]  ) {
continue;
}
if ( ! precalc[l2] [2][l0+l1] [2][c+z]  ) {
continue;
}
res++;
}
}
}
}
return res;
}```

Rumor
Used as: Division One - Level Two:
 Value 525 Submission Rate 314 / 794 (39.55%) Success Rate 162 / 314 (51.59%) High Score Petr for 474.16 points (9 mins 30 secs) Average Score 287.10 (for 162 correct submissions)

The constraints are such a vital component of a problem. In this case, there are at most 16 rabbits. This low constraint is usually a sign that the author plans us to use an exponential time algorithm. Let us keep that in mind.

We are solving an optimization problem. In optimization problems, we should consider what decisions are available for us. At the beginning of day one, some rabbits will know both rumors. This is one of the moment there are decisions to make: Each rabbit chooses one of the rumors to share. The rule extends to other days. Note that the second day, each rabbit that knew both rumors in day 1, has already shared one of the rumors. The objective is to minimize the number of days it takes for all rabbits to learn the rumors. It will not be useful to share the same rumor more than once. If a rabbit ever shares a rumor twice, all the rabbits that trust it already know the rumor the second time.

There is therefore only one decision to make, what is the first rumor each rabbit will share in case he has two unshared rumors. Note that the statement reminds us that it is possible for a rabbit to learn two rumors the same day, so it is possible that we will need to make the decision in days that are not day 1. Also note that we have to make the decision at most once for each rabbit (because the rabbit should not share the same rumor twice, it means that once we decide what rumor he will share first, there is nothing more to decide). This is where the constraints come into play. With at most 16 rabbits and two choices for each rabbit (Choose between sharing rumor 0 or 1). Then we have at most 216 total choices of assignments of first rumor to share for all rabbits.

Thus we are almost there. We can just try each of the 216 combinations of choices for the first rumor of each rabbit. Once all decisions are made, we need to simulate the process of sharing the rumors. For each day, we need a O(N) loop to assign a rumor to share for each rabbit (according to the already-made decisions). A small detail here is what to do if the rabbit learns the other rumor first - We can decide between sharing the other rumor or just breaking the loop and going to the next combination of choices (Because we will eventually visit a case that is exactly the same but has the other rumor assigned to the rabbit). The latter will yield a faster (in fact, much faster) solution. Then we need a O(N*N) loop to update the knowledge of each rabbit depending if a rabbit he trusts is sharing a rumor (For each rabbit, find if he trusts any rabbit that is sharing a rumor). This loop can be reduced to O(N) by only reviewing rabbits that we know were updated, but this is not necessary. We will repeat this O(N*N) until the simulation ends.

The simulation has to end. It will end whenever a) All rabbits know both rumors. Or b) No change has happened. b) Is only needed in the case there is a group of rabbits that does not trust (directly or indirectly) the group that knows the rumors. Then we will reach a moment in which no new rabbit can learn a new rumor. In that case, we can break the loop and not count the case. Else, when all rabbits know both rumors, we know the number of days that were needed and we can keep track of the minimum we find. We need to estimate the number of days that our simulation will take at most. Assuming all rabbits are connected to each other, the maximum distance between a rabbit that knows both rumors and a rabbit that does not is N-1. It will take the other rabbit at most (N-1) days to learn the first rumor shared by the first rabbit, and since the first rabbit will share the second rumor the second day, it the second rumor will be shared between the rabbits in paralel and need N-1 days after the second one. In total, the maximum number of days in a correct setting is N. With this knowledge, we can claim that the overall time complexity of our approach is O(2N * N*N * N). For N=16, this is not a very large complexity, also note that if we do ignore cases in which a rabbit learns his least favorite rumor first, the real number of operations will drop significantly and that we can optimize it to O(2N * N*N) If needed.

#### Code

A subproblem is to enumerate all the 216 choices for the first rumor of each rabbit. You will find that most experienced coders do this using bit operations. You can represent the choices as a single integer, and if its i-th bit is 1, the i-th rabbit wants to share rumor 1 first, and rumor 0 in another case. You can read this recipe by bmerry for more information.

```int getMinimum(string knowledge, vector <string> graph)
{
int n = knowledge.size();
const int INF = 1000000000;
int res = INF;
for (int doFirst = 0; doFirst < (1<<n); doFirst++) {
bool   known[n][2];
//known[i][x] <--> rabbit i knows rumor #x

bool   shared[n][2];
//shared[i][x] <--> rabbit i has shared rumor #x

bool   ready = true;        //true if everyone knows every rumor
for (int i=0; i<n; i++) {
for (int k=0; k<2; k++) {
known[i][k] = ( knowledge[i] == 'Y');
shared[i][k] = false;
}
}
bool changed = true; //Has anything changed this day?
int days = 0;
bool skip = false;
while ( !skip && !ready && changed ) {
days++;

// first, let each rabbit pick a rumor to share
// (depends on doFirst )
for (int i=0; i<n; i++) {
// The favorite rumor, as decided by doFirst
int fav = ( ( doFirst >> i)&1 );
// Pick the next rumor the rabbit will share.
if ( shared[i][fav] ) {
if (known[i][!fav]) {
shared[i][!fav] = true;
}
} else if (known[i][fav]) {
shared[i][fav] = true;
} else if (known[i][!fav]) {
//found unfavorite rumor before the other, skip
// (really improves execution time).
skip = true;
}
}

// update
changed = false;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if(graph[i][j]=='Y') {
//j trusts i
for (int k=0; k<2; k++) {
if (shared[i][k] && ! known[j][k] ) {
//new!
changed = true;
known[j][k] = true;
}
}
}
}
}
//verify end condition
for (int i=0; i<n; i++) {
for (int k=0; k<2; k++) {
}
}
}
res = std::min(res, days);
}
}
return ( (res==INF)? -1: res );
}```

MonochromePuzzle
Used as: Division One - Level Three:
 Value 950 Submission Rate 18 / 794 (2.27%) Success Rate 8 / 18 (44.44%) High Score Eryx for 599.29 points (25 mins 3 secs) Average Score 478.53 (for 8 correct submissions)

There are two aspects of this problem that are very specific and might be exploitable: The allowed operation and the destination pattern.

Let us begin with analyzing the allowed operation: Pick two indices, swap the two rows and then the two columns. A very interesting way to interpret this operation is as if the board was an adjacency matrix of a graph. That way, there is a road between vertex i and vertex j if and only if the cell at row i, column j is black. Wit this interpretation, you can verify that the operation is equivalent to swapping the indexes two given vertices. Thus if we pick numbers i and j for the operation, it will be the same as relabelling index i to j and vice versa.

If we are going to consider the board as an adjacency matrix, then we can see the problem of modifying the board into another board that has the specific pattern as a problem of modifying a graph into a special graph. The only allowed operation is swapping the indexes of two vertices. Let us name a solution p such that p[i] is the index of a vertex in the original graph that is equivalent to vertex i in the wanted graph. Equivalency here means that there will be a vertex between (p[i] and p[j]) in the original graph if and only if there is an edge between (i and j) in the the destination graph, for each pair of integers i and j. Imagine we knew how to find this permutation of indexes. What is the minimum number of swaps we need to turn the original graph into a graph such that the i-th index in the new graph is the original p[i]? This is actually a classical problem that comes up frequently: Swap elements of a vector that is initially 0,1,...N-1 so that it becomes a given destination - For each permutation cycle, we need (cycle_size - 1) swaps. We can also subtract the number of cycles from N.

Finding the permutation of indexes that converts the original graph into the wanted one will require us to analyze the target pattern

#### The target pattern is a prism

We have changed our vision of the problem to that of converting a graph to another by relabelling its indices. We should spend sometime into seeing how the destination pattern looks if interpreted as the adjacency matrix of a graph.

Let us begin with the first kind of black cells, those that connect row i with column j if and only if (abs(i-j) = 1). We will draw for N=8, as it is an example in the statement. If we consider each of these cells as a connection between vertices i and j, we can tell that the connection is bidirectional ( abs(i-j) equals abs(j-1) ). It will look like the following image:

Every two consecutive vertices will be connected by a bidirectional edge. Let us know consider the second kind of connection, those such that (i + j = N-1). We are now connecting a vertex with its complement: 0 with N-1, 1 with N-2, 2 with N-3, and it is also bidirectional. It effectively divides the graph into two halves. Note that there are connections of both kinds between 3 and 4:

Finally, the other kinds of vertices, note that if we continue with the idea that the previous connections divided the graph in two halves, the remaining connections in the form {0, N/2-1} and {N-1, N/2} will connect both ends of each of the halves. In this case, 0 and 3, and 7 and 4 will get new connections. After that, let us use some imagination.

That is correct, our graph looks like a prism of polygons of 4 sides. We can extend these ideas to conclude that for a given N, the graph will be a prism of polygons of N/2 sides.

#### To find the permutations

Remember that our only allowed operation is to relabel an index into another. Thus the original graph must actually also be a prism, only that its vertices will not necessarily be in the same positions as the destination. As a starting point, note that all the vertices in the destination graph have degree 3 - Each vertex has exactly three other vertices connected to it. This is true for all polygon sizes. Thus we can first verify that the degree of all vertices is 3 before doing anything else. If one vertex does not have degree 3, we can skip to return -1. Else we have to find each of the correct permutations - and of them pick the one that will need the minimum number of swaps.

We need to assign the integers p[i] of the permutation. Remember that p[i] is the index of the vertex in the original graph that is equivalent to vertex i in the destination graph. In this case, consider brute force, but to assign the equivalents of only a fixed number of vertices instead of all of them. What happens if that the structure of the graph contains so many rules that once we fix a number of vertices, the remaining vertices will be decided as a consequence of the first vertices picked. We need to figure out the minimum number of vertices required for this to happen: After inspection you may find that the number is three. If we use the following logic:

We need to assign three of the original vertices to three fixed positions of the final graph. In this case, we will pick position 0,1, and N-1 of the destination graph. The idea is that both 1 and N-1 are connected to 0, and that wit these three vertices we cover both halves (polygonal faces of the prism). What will help us also is that 0 and 1 are both the first two indices and N-1 is the last. Once we decide what vertices will be 0, 1 and N-1, we can use the following logic:

• Figure a): We decided 0, 1, and N-1=5. Let us decide what vertex will be 2 in the final graph. According to the structure, vertex 2 has to be adjacent to vertex 1, but is not adjacent to vertex 5 (N-1). The vertex that is adjacent to both 1 and 5 will be vertex #4 (N-2). There is only one vertex left, and it is #3, we can verify that this vertex will be adjacent to the assigned vertices #5 (N-1) and the two vertices we found in the last step (#2 and #4).

• Figure b): In the case N=8, we decided vertices #0, #1 and N-1 = 7. To decide #2, find a vertex that is connected with #1 and is not connected with #7. The vertex that is connected to both #1 and #7 is #6 (N-2).

• c) Note that now the vertices #3 and #{N-3} =5 can be found using #2 and #6 (the vertices we found in the previous step) In the same manner: #3 is adjacent to #2 but not #6 and #5 is adjacent to both #2 and #6. Finally, one vertex will be left without a pair, but like in a), we will compare that #3 and #5 are adjacent to it (#3 and #5 are the vertices found in the previous step).

Generalizing, once we assigned vertices 0,1 and N-1, we can pick vertices 2 and N-2, 3 and N-3, ...Eventually, vertex N/2 will be the last left.

If for each 3 vertices #0,#1 and #(N-1), we implement that logic to find a correct permutation. And then grade the permutation for cost in the number of swaps, we can pick the minimum among all permutations to find the final result. We need a O(N3) loop for the 3 fixed members of the permutation. We will also need a O(N) or O(N2) (Depending on the level of care used, for example using an adjacency list instead of a matrix) process to find the remaining positions of the permutation. In total, we will have O(N5) or O(N4) algorithm. Both alternatives are actually good for the time limit.

```// What is the cost to modify
// 0,1,...n-1 into p[0],p[1],p[2],...
// by simply swappying indexes?
int permutationCost(int* p, int n)
{
bool visited[n];
fill(visited, visited+n, false);

//This is a classic problem that depends on
// the sizes of each connected component
// x,p[x],p[p[x]],...x
int sum = 0;
for (int i=0; i<n; i++) {
int cs = 0;
int x = i;
while ( ! visited[x] ) {
visited[x] = true;
cs++;
x = p[x];
}
if (cs > 0) {
sum += (cs - 1);
}
}
return sum;
}

int getMinimum(vector <string> board)
{
int n = board.size();
// verify that each vertex has degree 3
for (int i=0; i<n; i++) {
int cnt = 0;
for (int j=0; j<n; j++) {
if (board[i][j] == '#') {
cnt ++;
}
}
if (cnt != 3) {
return -1;
}

}
const int INF = 1000000000;
int res = INF;

int p[n];
for (p[0] = 0; p[0] < n; p[0]++) {
for (p[1] = 0; p[1] < n; p[1]++) {
for (p[n-1] = 0; p[n-1] < n; p[n-1]++) {
if(  p[0] != p[1] && p[1] != p[n-1] && p[n-1] != p[0]
&&  (board[p[0]][p[1]]=='#' ) &&  (board[p[0]][p[n-1]]=='#' )
) {
// Once vertices 0, 1, and n-1 are fixed, the rest
// are also fixed.
bool taken[n];
fill(taken, taken+n, false);
taken[ p[0] ] = true;
taken[ p[1] ] = true;
taken[ p[n-1] ] = true;

//the remaining members of the permutation.
int x = 1;
int a = 2;
int b = n-2;
int y = n-1;
bool invalid = false;
while (a < b) {
// vertex a is adjacent to p[x], but is not adjacent to p[y]
int fa = -1, fb = -1;
// you can avoid this extra O(n) factor by using an adjacency
// list instead of a matrix.
for (int i=0; i<n; i++) {
if ( !taken[i] && (board[ p[x] ][i]=='#') ) {
if (board[ p[y] ][i]!='#') {
fa = i;
} else {
fb = i;
}
}
}
if ( fa==-1 || fb==-1 ) {
invalid = true;
break;
} else {
p[a] = fa;
p[b] = fb;
taken[p[a]] = true;
taken[p[b]] = true;
// Procceed to the next pair of vertices
x = a;
y = b;
a++;
b--;
}
}
if (invalid) {
continue;
}
invalid = true;
// the last vertex, now (a), is adjacent to x,y and n-1

for (int i=0; i<n; i++) {
if ( ! taken[i]
&& board[p[x]][i]=='#' && board[p[y]][i]=='#'
&& board[p[n-1]][i]=='#') {
invalid = false;
p[a] = i;
}
}
if (invalid) {
continue;
}
// p[0],p[1],...p[n] is a valid permutation, find the cost
res = std::min(res, permutationCost(p,n));
}
}
}
}
return ( (res == INF) ? -1 : res);
}```