- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: January, 2017 -
**Competitors who opened the problem**: 259 -
**Competitors who submitted a solution**: 238 -
**Number of correct solutions**: 215 -
**Accuracy (percentage correct vs those who opened)**: 83.0% -
**Average Correct Time**: 10 minutes, 57 seconds.

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

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