Find the maximum possible mex (minimal excluded) number from a square matrix

Question

I have a question about the following challenge:

Given a n by n square matrix of positive integers, select n cells that do not share rows or columns. The goal is to select cells that maximize the lowest positive integer that is not selected.

Example

For the matrix

[ 21  13  21* 4
  19   4  16  2*
  17   1* 11  1
   0*  0   0  0
]

Select the marked cells. The smallest positive integer not selected is 3.

I was thinking of some dynamic programming approach, but could not do it.

What is the an efficient approach to solve this problem?

Answer 1

Well, I asked for a reopen, so I had better have a go. This is basically testing all feasible routes via backtracking.

It first stores all the (row,column) positions of the 0's, then the 1's, then 2's, etc. up to N-1.

It then tests the placements of the 0's, 1's, 2's etc in turn.

At the end it outputs the first excluded non-negative integer (same length as the fittable sequence) and the (row,column) positions of what it has managed to fit. You can take what you like from the remaining rows and columns; they won't change the Max-Mex.

#include <iostream>
#include <vector>
using namespace std;

using sequence = vector<pair<int,int>>;

//----------------------------------------------------------------------

void optimise( int level, const vector<sequence> &locations, sequence &best, sequence &current, vector<bool> &rowUsed, vector<bool> &colUsed )
{
   if ( level == locations.size() ) return;

   for ( auto pr : locations[level] )                                          // all possibilities at this level
   {
      int i = pr.first, j = pr.second;
      if ( !( rowUsed[i] || colUsed[j] ) )
      {
         rowUsed[i] = colUsed[j] = true;
         current.push_back( { i, j } );                                        // next route to try

         if ( current.size() > best.size() ) best = current;

         optimise( level + 1, locations, best, current, rowUsed, colUsed );    // go to next level

         current.pop_back();                                                   // clean up for next route
         rowUsed[i] = colUsed[j] = false;
      }
   }
}

//----------------------------------------------------------------------

sequence maxMex( const vector<vector<int>> &A )
{
   int N = A.size();        // The best possible would be N
   // Locate all the x=0, 1, ... (N-1) and store them in locations[x]
   vector<sequence> locations( N );
   for ( int i = 0; i < N; i++ )
   {
      for ( int j = 0; j < N; j++ ) if ( A[i][j] < N ) locations[A[i][j]].push_back( { i, j } );
   }

   sequence best, current;
   vector<bool> rowUsed( N, false ), colUsed( N, false );
   optimise( 0, locations, best, current, rowUsed, colUsed );
   return best;
}

//----------------------------------------------------------------------

int main()
{
   vector<vector<int>> A = { { 21, 13, 21, 4 },
                             { 19,  4, 16, 2 },
                             { 17,  1, 11, 1 },
                             {  0,  0,  0, 0 } };

   sequence best = maxMex( A );
   cout << "Max Mex = " << best.size() << "\n\n";
   cout << "Value" << '\t' << "Row" << '\t' << "Column" << '\n';
   for ( int n = 0; n < best.size(); n++ ) cout << n << '\t' << best[n].first << '\t' << best[n].second << '\n';
}

Output:

Max Mex = 3

Value   Row     Column
0       3       0
1       2       1
2       1       3