- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: November, 2016 -
**Competitors who opened the problem**: 205 -
**Competitors who submitted a solution**: 159 -
**Number of correct solutions**: 129 -
**Accuracy (percentage correct vs those who opened)**: 62.9% -
**Average Correct Time**: 32 minutes, 51 seconds.

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.

/* Topcoder SRM 702 D1 300-pointer. GridSortMax James S. Plank Sun Nov 20 11:40:05 EST 2016 */ #include <string> #include <vector> #include <iostream> #include <cstdio> #include <cstdlib> using namespace std; class GridSortMax { public: string findMax(int n, int m, vector <int> grid); }; string GridSortMax::findMax(int n, int m, vector <int> 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 <int> VR, VC; /* These are vectors that hold vr and vc for each v. */ vector <int> VR_Swapped; /* Where has each row been swapped to? (-1 if unswapped yet) */ vector <int> VC_Swapped; /* Where has each column been swapped to? */ vector <int> TR_Swapped; /* Which row was swapped here? (-1 if unsapped yet) */ vector <int> 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; } |