SRM 610, D2, 250-Pointer (DivideByZero)

James S. Plank

Sat Jan 18 09:54:26 EST 2014
Modified: Mon Oct 18 21:15:06 EDT 2021

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: 2014
Competitors who opened the problem: 769
Competitors who submitted a solution: 643
Number of correct solutions: 441
Accuracy (percentage correct vs those who opened): 57.3%
Average Correct Time: 20 minutes, 32 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given a vector of integers, named N.
v's size is ≤ 1000 and the elements of N are between 1 and 1,000. (I've increased the topcoder constraints -- they were originally 100 and 100).
The elements of N are distinct.
Let i and j be any two distinct elements of N, and suppose that i > m. Calculate i/j, using integer division. If it is not in N add it to N.
Continue doing this until you can't add any more elements of N
Return the size of N.
BTW, it doesn't matter what order you add elements to N. The answer will always be the same.

The examples

 #  |    N                        |  Answer
--- | --------------------------- | -------
 0  | { 9, 2 }                    | 3: You'll add 9/2 = 4, but then you're done.
 1  | { 8, 2 }                    | 3: Ditto.
 2  | { 50 }                      | 1: There are no pairs of elements.
 3  | { 1, 5, 8, 30, 15, 4 }      | 11: You'll add 2, 3, 6, 7 and 10.
 4  | { 1, 2, 4, 8, 16, 32, 64 }  | 7: You're already done.
 5  | { 6, 2, 18 }                | 7: You'll add 1, 3, 4 and 9.

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt.

Hints

This one tripped up many of the Topcoder contestants -- See if you can do better!

The constraints of this problem state that N only holds numbers between 1 and 1,000, and N.size() is ≤ 1,000. Since (a div b) is always going to be less than a, the numbers in N will always be between 1 and 1,000. That puts some constraints on input that we can leverage. In particular, if our solution is O(N.size()²), it will be fast enough.

Here's a solution that comes to mind -- keep two collections of numbers: those that you have processed (call it P -- it will be a vector), and the vector N. You can also maintain a vector, which we'll call T, that tells us in O(1) time whether a number is in v. It will contain 1,001 booleans, and T[i] is true if i is in N. It is false otherwise.

Now do the following:

Set T[n] to true for each element n in N
Set P to be empty.
Now, for each element n in N, do the following:
- For each element p in P, find k = (n div p), or k = (p div n), whichever is non-zero.
- Check T to see if T[k] is true. If it is, ignore k.
- Otherwise, set T[j] to true, and add k to N.
- When you're done with each element in P, add n to P.
Finally, return the size of N or P. They will both be the same size.

Let's illustrate this with Example 0, where numbers is { 9, 2 }. Below is the initial state of the three vectors (we only show the first 12 elements of T, because all of the higher ones will always be false. Also, in the pictures, 1 is true and 0 is false):

Now, run through N with an integer i. When i = 0, n = 9. We want to run through P, but P is empty, so we're done with n -- we add it to P:

Next, i = 1 and n = 2. We run through P and there is one element: p = 9. Since p is bigger than n, we set k = (p div n) = 4. We check to see if T[4] = 0, which it does, so we set T[4] = 1 and add 4 to N:

At this point, we're done with P, so we add n to P:

Finally, we continue with i = 2 and n = 4. We run through P: When p = 9, k = 2, and since T[2] equals 1, we ignore k. Similarly, when p = 2, k also equals 2, and since T[2] equals 1, we ignore k again. At this point, we're done with P, so we add n to P:

Now, we're done with N, so we return the size of P, which is three. As you can see, when we're done, P and N will be identical, so we could simply return the size of N.

Let's think about the running time of this algorithm. Suppose there end up being n elements of N. Then our checking loop runs O(n²) times. Inside the loop we do an "if", a division, a check of T[j], potentially a push_back() to N and setting T[j] to true, and a push_back() to P. All of those are O(1). So our program is O(n²). With n capped at 1,000, this is fast enough for topcoder.

Now think about the choice of data structure for T. Because the values of v are limited to ≤ 1000, we can make T a vector of size 1,001, and checking to see whether a value is in N is O(1).

Suppose T were instead a set. Then checking would be O(log n), and our program would run in O(n²log n).

And finally, suppose that we didn't use T at all, but instead used N. Then checking would be O(n), and our program would be O(n³). As always, our choice of data structure is very important!