### James S. Plank

Sun Nov 20 11:11:23 EST 2016
This one is not very subtle. It just requires you to get your details and indices right.

To explain this one, let's suppose that n and m are big numbers. You're always going to be able to swap the "1" into the right place. That means that whichever row and column are currently holding 1, they will be swapped into row 0 and column 0. This means that the first digit of your return string will be "1", which is what you want.

Now, you can concentrate on the "2", because you'd like for its digit in the return string to be "1" if possible. If the "2" is in the same row as "1", then you'll be able to swap it into column 1, and you can set its digit in the return string to be "1". Otherwise, the "2" will never be in the same row as "1", and you'll have to ignore it, setting its digit in the return string to "0".

Then, you'll move onto the "3", and so on.

So, you are going to proceed with a greedy strategy. For each value v from 1 to n*m, you are going to go through the following series of actions:

• Let vr and vc be v's current row and column, and let tr and tc be the "target" row and column, where v belongs in order to make its digit in the return string "1".

• Have vr and vc been swapped yet? Have other rows swapped into tr yet, and have other columns swapped into tc yet? If the answer to all of these is "no", then you will be able to swap vr to tr, and vc to tc, and v will be in the right place. Do those moves, push '1' onto the return string, and move on.

• Now, if vr hasn't been swapped, but another row has been swapped to tr, then you'll never get v to the right row. Push '0' onto the return string and move on.

• Similarly, if vc hasn't been swapped, but another row has been swapped to tc, then you'll never get v to the right column. Push '0' onto the return string and move on.

• On the other hand, if vr has been swapped, but it's not to tr, then again, you'll never get v to the right row. Push '0' onto the return string and move on.

• Similarly vc has been swapped, but it's not to tc, then you'll never get v to the right column. Push '0' onto the return string and move on.

• If you've gotten here, then you are in one of three conditions: (1) You've already swapped v to the correct row when you were dealing with a previous value of v. And you are free to swap v to the correct column. Do so, push '1' onto the return string, and move on.

• Or, (2) You've already swapped v to the correct column when you were dealing with a previous value of v. And you are free to swap v to the correct row. Do so, push '1' onto the return string, and move on.

• Or, (3) You've already swapped v to the correct row and column when dealing with a previous value of v. You can push '1' onto the return string, and move on.
Game over -- you're done. I'll leave it up to you to think of what data structures you need to solve the problem. You can see my solution below if you want.
Solution.cpp:

 ```/* Topcoder SRM 702 D1 300-pointer. GridSortMax James S. Plank Sun Nov 20 11:40:05 EST 2016 */ #include #include #include #include #include using namespace std; class GridSortMax { public: string findMax(int n, int m, vector grid); }; string GridSortMax::findMax(int n, int m, vector G) { int i, j; /* Temporary variables. */ int v; /* The value that we're focusing on (will go 1, 2, 3, etc.) */ int vr, vc; /* V's current row and column */ int tr, tc; /* The target row and column for V */ string rv; /* The return string */ vector VR, VC; /* These are vectors that hold vr and vc for each v. */ vector VR_Swapped; /* Where has each row been swapped to? (-1 if unswapped yet) */ vector VC_Swapped; /* Where has each column been swapped to? */ vector TR_Swapped; /* Which row was swapped here? (-1 if unsapped yet) */ vector TC_Swapped; /* Which column was swapped here? */ /* Calculate VR and VC from G. We're going to look at values of v from 1 to n*m, so we need VR and VC to have n*m+1 elements, and we'll ignore element 0. */ VR.resize(G.size()+1); VC.resize(G.size()+1); for (i = 0; i < G.size(); i++) { v = G[i]; VR[v] = i/m; VC[v] = i%m; } /* Now, run through the values of v from 1 to n*m, and do the steps that I outlined in the writeup. */ VR_Swapped.resize(n, -1); VC_Swapped.resize(m, -1); TR_Swapped.resize(n, -1); TC_Swapped.resize(m, -1); for (v = 1; v <= n*m; v++) { vr = VR[v]; vc = VC[v]; tr = (v-1)/m; tc = (v-1)%m; // printf("v = %d. vr:%d vc:%d tr:%d tc:%d\n", v, vr, vc, tr, tc); /* Each of these follows the bullets in the writeup in order: First case is when you can swap vr and vc to their correct place. */ if (VR_Swapped[vr] == -1 && VC_Swapped[vc] == -1 && TR_Swapped[tr] == -1 && TC_Swapped[tc] == -1) { VR_Swapped[vr] = tr; VC_Swapped[vc] = tc; TR_Swapped[tr] = vr; TC_Swapped[tc] = vc; rv.push_back('1'); /* Here, you haven't swapped VR, but the target row is occupied. (Same with the column) */ } else if (VR_Swapped[vr] == -1 && TR_Swapped[tr] != -1) { rv.push_back('0'); } else if (VC_Swapped[vc] == -1 && TC_Swapped[tc] != -1) { rv.push_back('0'); /* You have swapped vr, but not to the target row. (Same with the column) */ } else if (VR_Swapped[vr] != -1 && TR_Swapped[tr] != vr) { rv.push_back('0'); } else if (VC_Swapped[vc] != -1 && TC_Swapped[tc] != tc) { rv.push_back('0'); /* You have swapped the row already to its proper place, and you can swap the column. */ } else if (VC_Swapped[vc] == -1 && TC_Swapped[tc] == -1) { VC_Swapped[vc] = tc; TC_Swapped[tc] = vc; rv.push_back('1'); /* You have swapped the column already to its proper place, and you can swap the row. */ } else if (VR_Swapped[vr] == -1 && TR_Swapped[tr] == -1) { VR_Swapped[vr] = tr; TR_Swapped[tr] = vr; rv.push_back('1'); /* The row and column are already swapped to their correct place. */ } else rv.push_back('1'); } return rv; } ```