Set Multiples

Notation: We will use $S$ to denote the given set, and $T$ to denote the "goal" or optimal set that satisfies the constraints. We say we "choose" (or "select") an integer $x$ in an algorithm if it results in $x \in T$ when the algorithm is completed.

<code class="py">
Let T = {}
for x = D downto 1:
  if (A <= x<=B or C<=x<=D):
    if (no multiples of x exist in T):
      add x to T
	</code>

<code class="py">
SetMultiples1(A,B,C,D):
    if C <= D/2:
        # (Implicitly) Set T = {D,D-1,D-2,...,floor(D/2) + 1}
        return ceil(D/2)  # We only want the size of T
    else:
        Let marked = {}    be an empty set
 
        # The original ranges that define S
        Let upperRange = (C,D)
        Let lowerRange = (max(floor(B/2) + 1,A), B)
 
        for all k = 2..INFINITY:
            currentRange = (ceil(C/k), floor(D/k))
            prevRange    = (ceil(C/(k-1)), floor(D/(k-1)))
 
            if intersection(currentRange, prevRange) isnt EMPTY:        # They overlap
                marked.insert(x) : for all x from floor(D/k) downto 1
                break
            else:
                marked.insert( intersection(currentRange, lowerRange) )
 
        return upperRange.size() + lowerRange.size() - marked.size()
	</code>

Review

Summary

All-in-all, this problem required some interesting greedy observations to solve it efficiently.

We first observe that, for a given integer $x$, we "choose" $x$ to be in our final set if and only if $x$ has no larger multiples in $S$ (for simplicity, we will call all of these numbers "maximal" numbers). This always yields an optimal solution (proven above). Hence, we simply want to find all "maximal" numbers $x$ in the ranges $A \leq x \leq B$ or $C \leq x \leq D$.

To find an efficient algorithm, we can exploit the fact that $S$ consists of two disjoint intervals. This actually makes the problem much simpler and more "regular". For example, we can make the following observation: Between $C$ and $D$ (inclusive), we always need to select the numbers above $\frac{D}{2}$ (since none of these are "maximal"), if $C \leq \frac{D}{2}$. In fact, with a bit more work, we can show that, if $C \lt \frac{D}{2}$ then these are the only numbers we need to select (we can prove that any smaller number has a multiple in this set). So we can assume that $C > \frac{D}{2}$. Similarly, we can assume that $A > \frac{B}{2}$, since an analogous truth holds for $A$ and $B$.

At this point, we can assume $C$ is somewhat "close" to $D$ (in particular, $C > \frac{D}{2}$). To solve this, I tried one fairly intuitive algorithm: Look at the end-points of the interval $(C,D)$ and divide them by 2. Then every integer $x$ in this new interval $(\frac{C}{2} .. \frac{D}{2})$ has a corresponding multiple $2x$ in the original interval $(C,D)$. So all such numbers are clearly not maximal. A similar fact holds for $(\frac{C}{3}..\frac{D}{3})$, $(\frac{C}{4}..\frac{D}{4})$, ..., and so on. So, the algorithm is to try all these intervals, and "mark" the numbers $x$ that we find. One convenient fact about this is that most of these intervals are disjoint, so we don't need to explicitly mark the $x$, but we just count how many $x$ are in the range and also in the range $\frac{B}{2} .. B$. When this algorithm terminates, the size of our final set will be $(D-C+1) + (B - \max(A-1,\frac{B}{2})) - |\{\text{marked numbers}\}|$ (the numbers in our given ranges, minus the number of "marked" factors).

By inspection, the intervals $(\frac{C}{k}..\frac{D}{k})$ will eventually intersect with each other. Actually, you can prove that, after a certain $k$, the intervals will cover all numbers from $\frac{D}{k}$ down to 1. So we can actually "exit" early. This happens whenever $k > \frac{D}{D-C}$ (we proved this in Idea 2), so it happens more quickly whenever $D-C$ is large (or when $D$ is small, but we can't assume this).

By noting that this algorithm works when $D-C$ is large, we can ask the next intuitive question: "What about when $D-C$ is small?". To answer this, we realize that we can just simply explicitly find all the factors of the numbers between $C$ and $D$. We mark these factors that overlap with the chosen part of the $A..B$ interval. This runs in $O((D-C)\sqrt{D})$ time, since there are about $D-C$ numbers in the range $C..D$ and each number requires $O(\sqrt{D})$ time to find its factors. So, this algorithm is clearly better when $D-C$ is smaller.

We now have two "complimentary" algorithms, the first having $O(\frac{D}{D-C})$ time-complexity, and the second having $O((D-C)\sqrt{D})$ time-complexity. We can combine these algorithms by always choosing the "minimum" one; that is, we choose whichever algorithm runs faster for our given input. We then have an algorithm that has time-complexity: $O( \min\{\frac{D}{D-C}, (D-C)\sqrt{D}\} )$. Using some intuitive arguments (or by calculus) this function has its worst-case complexity of $D^{\frac{3}{4}}$ when $(D-C) \approx D^{\frac{1}{4}}$. Since $D \leq 10^{10}$ this just (barely) runs correctly under the time-limit for TopCoder.

Accepted.

1. We select an integer $x$ to be in our set if and only if it has no other multiples in the set $S$. This was pretty intuitive to come up with, but it was helpful when trying to find a fast algorithm.

2. Given a single interval $S = (C..D)$ we MUST select the numbers greater than $\frac{D}{2}$ in an optimal solution $T$.

3. If we take an interval of integers from $C$ to $D$, and we divide both end-points by an integer $k$, then every integer in this new interval ($\frac{C}{k} \text{ to } \frac{D}{k}$) will have a multiple $kx$ in the original range. This formed the basis of our first algorithm

4. Take an interval of integers from $C$ to $D$. Consider the intervals $(\frac{C}{2} .. \frac{D}{2})$, $(\frac{C}{3} .. \frac{D}{3})$, $(\frac{C}{4} .. \frac{D}{4})$, ..., $(\frac{C}{k-1} .. \frac{D}{k-1})$, $(\frac{C}{k} .. \frac{D}{k})$. Then $(\frac{C}{k-1} .. \frac{D}{k-1})$ will overlap with $(\frac{C}{k} .. \frac{D}{k})$ if and only if $k \geq \frac{D}{D-C}$. This showed that we could quit this algorithm early whenever $k$ gets large enough. In particular, we can end earlier if $D-C$ is larger.

5. It takes $O(\sqrt{D})$ time to find all the factors of a number. Hence, all factors of all numbers between $C$ and $D$ can be checked in $O((D-C)\sqrt{D})$ time. This gave us the basis of our second algorithm. This works whenever $D-C$ is small.

6. Consider the time-complexity function $F(x) = \min(\frac{D}{x}, x\sqrt{D})$. This function achieves its maximum (worst-case) value of $F(x) = D^{\frac{3}{4}}$ when $x \approx D^{\frac{1}{4}}$. Since $\frac{D}{x}$ is decreasing and $x\sqrt{D}$ is decreasing, we can show that the worst-case point occurs when these two functions are equal. So we set $\frac{D}{x} = x\sqrt{D}$ and solve for $x$. This gives us the formula.

7. This is largely a greedy / ad-hoc problem. These kinds of problems usually require finding good observations about the structure of the problem. It often helps to look at examples to help find these patterns. Also, once we started to find more and more observations, it was good to go back and try them on examples to get a good understanding of how they work.

8. Once we found a greedy algorithm, we realize that we can make it efficient by exploiting the structure of the problem. In particular, the input set $S$ will always consist of two disjoint intervals. (This might have been much harder if we were given an arbitrary set $S$.) Another way to exploit the conditions is to notice that $D \leq 10^{10}$. This implies that a $\Theta(\sqrt{D})$ algorithm should be possible, since $\sqrt{D} \approx 10^5$ is right around a "reasonable" input-range.

9. If you've never seen "the Square Root Trick" for factorization, then this problem becomes much harder. In addition (see the Learning Points), I've learned from experience that this "Square Root Trick" applies (in principle) to other kinds of problems. This helped us to analyse the running time achieved when combining the two algorithms. You also need some experience and intuition in basic Number Theory in general to be able to solve this problem.

10. A nice example was the case when $C=D$. This was an extreme case (i.e.: when $D-C$ was 0). By finding an algorithm that works here, we could easily generalize it to work for other small $D-C$.

11. Most of the algorithms we came up with were pretty "intuitive". The way we solved this problem was by writing out these algorithms ("testing" them), and by finding out exactly where they fail. In particular, we learned that these algorithms largely depended on the parameter $D-C$, so then we could solve the problem by focusing on this variable.

12. Instead of finding all multiples of a given number $x$, we focused on finding the factors of numbers $y$.

• The "Square-Root" Trick with Minimax Functions. In general, whenever you have two symmetric, competing "resources", you usually can achieve optimality (either maximizing or minimizing some function of these resources) by setting them equal. When factorizing a number $N$ into factors $x$ and $y$ such that $xy = N$, this principle applies because $\min(x,y)$ is maximized whenever $x = y = \sqrt{N}$. This is also the worst-case amount of numbers you would need to check to find all the factors. Or for example, if you have a function $F(x) = x + \frac{1}{x}$, this is minimized when $x = \frac{1}{x} = 1$ (I think). This also forms the basis for "Square Root Decomposition" algorithms which arise in data structures (see the Related Problems section below).

• Number Theory / Divisibility / Factorization / Square Root Trick

• Greedy / Observations / Exploit Structure and Conditions

• Brute Force / Brute Force with Greedy Optimizations

• Math / Formulas and Proofs

• SQRT-Decomposition

Given $(n+1)$ unique numbers between $1$ and $2n$ (for some positive integer $n$), prove that there exists a pair of elements $x$ and $y$ such that $y$ is a multiple of $x$. This is a nice math problem that I remembered when reasoning about divisibility.

UVa 11466 - Largest Prime Divisor. A problem on finding large prime factors. Take note of the constraints and recall out "Learning Point".

UVa 11960 - Divisor Game. This problem shows that most numbers have a small number of factors. It's also a nice illustration of working backwards.

Codeforces Round #257 (Div. 1) C - Jzzhu and Apples. Another problem dealing with number theory and divisibility. It is also an "optimization" problem where we are trying to maximize something with respect to the numbers.

NCPC 2008 Problem J: Just a Few More Triangles! Here is a harder number theory problem that I don't know how to solve. It's more practice. (I found this problem on Codeforces Gym)

Coding Contest Byte: The Square Root Trick. A nice article describing Square Root decomposition and related problems.