SRM 685, D1, 250-Pointer (MultiplicationTable2)

James S. Plank

Sat Oct 19 01:25:57 EDT 2019

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: 2016
Competitors who opened the problem: 420
Competitors who submitted a solution: 397
Number of correct solutions: 294
Accuracy (percentage correct vs those who opened): 70.0%
Average Correct Time: 18 minutes, 45 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

We have made up our own multiplication operator. It works on the set of numbers from 0 to n-1.
The operator is defined by an n x n multiplication table, which is passed to you as a vector of ints. The result of i*j is in the table at index i*n+j.
A set of elements S is closed with respect to * if for all i and j ∈ S, i*j ∈ S (this includes i*i).
Return the size of the smallest, non-empty closed subset of { 0, 1, ..., n-1 }, with respect to *.
n is less than or equal to 50 (in my tests, is is less than or equal to 100).

The examples

Example	table	Answer
0	{1,1,2,3, 1,0,3,2, 2,0,1,3, 1,2,3,0}	2 (the set is {0,1})
1	{0,1,2,3, 1,2,3,0, 2,3,0,1, 3,0,1,2}	1 (the set is {0})
2	{1,1,1,1, 2,2,2,2, 3,3,3,3, 0,0,0,0}	4 (the set is {0,1,2,3})
3	{0}	1 (the set is {0})

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. Mine runs in roughly three seconds.

Hints

A first approach based on the minimum closed set containing x:

Let's first wrap our heads around the problem. Let's define CS(x) to be the smallest closed subset that contains x. We can build CS(x) incrementally, in the following way:

Start by setting CS(x) to { x } .
Enumerate all pairs of elements (i,j) in CS(x). It is possible for i to equal j.
Generate the set P where k ∈ P if and only if there is a pair of elements (i,j) such that i and j are both elements of CS(x), and i*j = k.
Set CS(x) equal to ( CS(x) ∪ P ).
If CS(x) got bigger, start again at step 2.

Let's generate CS(0) in example 0:

To start, CS(0) equals { 0 }.
It should be clear that P is { 1 }. That is because the only (i,j) pair is (0,0) and 0*0 = 1.
So set CS(0) to ( { 0 } ∪ { 1 } ), which is { 0, 1 }, and repeat step 2 above, because CS(0) got bigger.
We have:
- 0*0 = 1
- 0*1 = 1
- 1*0 = 1
- 1*1 = 0
So, P = { 0, 1 }.
This means that CS(0) equals ( { 0, 1 } ∪ { 0, 1 } ), which is { 0, 1 }.
Since CS(0) hasn't gotten any bigger, we're done, and can conclude that CS(0) = { 0, 1 }.

You can program this approach directly, and it may or may not pass topcoder's tests, because it is really slow. Think about it -- in each iteration of the steps above, you are generating |CS(x)|² pairs of values to test. Let's assume a pathelogical case, that every time, you add one element to CS(x), and that |CS(x)| will eventually equal n. Then you have:

- for every value of x                           # There are n of these
  - Calculate CS(x)                              # This will take n passes, because we add one element each time.
    - By enumerating all pairs in CS(x)          # There are n^2 pairs
      - For each pair, you insert into a set.    # This is log(n)
    -
  -
-

That's O(n⁴log(n)) which is pretty slow. I didn't test it against Topcoder, because I couldn't bring myself to write such a slow program. However, it is a sound approach -- we just need to make it faster.

A second approach: calculate only the potential new elements at each pass.

A big problem with the approach above is that it doesn't remember which pairs that it has already processed. For example, if you've already calculated 0*0 once, you don't need to calculate it again.

Here's an approach to reduce the running time. Once again, we are going to calculate CS(x) incrementally. We are going to maintain three data structures:

CS(x) -- We'll use a set.
To_Add -- This is a vector of new elements to add to CS(x).
Next_To_Add -- This is a set which contains the elements that will go into To_Add on the next pass.

We start with CS and Next_To_Add being empty, and To_Add containing x. Then we repeat the following:

Add every element of To_Add to CS(x).
For every element i in To_Add and every element j in CS(x), calculate i*j, and if it is not in CS(x) insert it into Next_To_Add. Do the same for j*i.
If Next_To_Add is empty, you're done -- you have successfully calculated CS(x).
Otherwise, clear To_Add and then add every element of Next_To_Add to To_Add.
Clear Next_To_Add
Go back to the beginning.

Determining the running time here is a little more subtle -- instead of counting loops, you can count the total number of times that certain operations are done:

- for every value of x
  - Each potential element of CS(x) is only ever inserted into CS(x) once.
  - Each product i*j is only calculated once.
  - Each product is only ever inserted into Next_To_Add once.
-

This yields a running time of O(n³log(n)). Think of it as:

Multiply by n for each value of x.
Multiply by n² for each product i*j.
Multiply by log(n) because each product does an insert().