SRM 702, D1, 300-Pointer (GridSortMax)

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:

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 <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;
}