SRM 705, D2, 250-Pointer (SuperUserDo)

James S. Plank

Sat Feb 11 01:12:15 EST 2017
Try this on your own. If you get stuck, return here and read what I've written below.



























































This problem is a matter of choosing the right data structure for the solution, and not over-complicating it. There are 1000 libraries, numbered from 1 to 1000. And there are at most 100 programs. So, suppose you maintain a vector of integers called libraries. This vector will have 1001 elements -- from 0 to 1000. If library i is used by a program, you'll set libraries[i] to be one. Otherwise, it will be zero.

You start by setting each element of libraries to zero. Then, for each program, you set the libraries used by the program to one. At the end, you count up the number of libraries whose entries are one. That is your return value.

Thinking about running times -- There will be at most 1,000 libraries for each program, and there are at most 100 programs. That means that you will set at most 1000*100 = 100,000 library entries to one. That is well within Topcoder's time limits (you get roughly 5,000,000 operations), so it is fast enough. And you'll note, it is not a complicated solution.

I include it below:

#include <string>
#include <vector>
#include <list>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class SuperUserDo {
  public:
    int install(vector <int> A, vector <int> B);
};

int SuperUserDo::install(vector <int> A, vector <int> B)
{
  int i, j;
  vector <int> Libraries;  /* This will contain 0 if a library is not 
                              in use, and one if a library is in use. */
  int total;

  /* Initialize variables.  Set the total to zero, and 
     set every element of the Libraries vector to zero. */

  total = 0;
  Libraries.resize(1001, 0);   

  /* For each program, set the libraries that the program uses to one. */

  for (i = 0; i < A.size(); i++) {
    for (j = A[i]; j <= B[i]; j++) Libraries[j] = 1;
  }

  /* Total up the libraries that are used, and return that value. */

  for (i = 0; i < Libraries.size(); i++) total += Libraries[i];
  return total;
}