Hello everybody

It was a very nice contest last Saturday. Congratulations to all of you. In this post I would like to explain a little bit the two problems that have not been solved, D (Multiplicity) and I (Freeways ISI) if I remember well.

The problem Freeways ISI is really easy since it's only Minimum Spanning Tree. The solution of the problem consists in building a graph with the data given in the input then perform a Minimum Spanning Tree algorithm such as Kruskal’s Algorithm that runs in O (E log V) where E is the number of the edges in the grah and V is the bnumber of vertices.

Concerning the problem Multiplicity, it's a bit complicated. The brute force solution is a very time-consuming solution and you should not even consider implementing it. It is therefore necessary to know what are the optimizations to bring in order to reduce the time cost of the algorithm.

First of all, we must know that even numbers are always included in the result since they are multiples of 2. They must be ignored during the initial processing and included in the result only in the last step. It saves time but not as much. If the treatment of odd numbers is expensive, then it does not change anything.

If we think a little bit, we realize that what is important for us are the multiples of prime numbers and the product of prime numbers. For instance, if a number is multiple of 10, 30, or 50, we would have already reported it as a multiple of 2. Therefore, we should ignore any compound number less than 130 when we consider the list of values for which we want to examine their multiples, except prime numbers, and there are 31 primes less than 130.

A simple but naive method is to add all values ​​in the range divisible by 2, 3, 5, and so on. However, doing so over-counts values divisible by 6, for example, since we count them once when we count multiples of 2 but also a second time by counting multiples of 3. The generalized solution to solve this over-counting problem is a principle known as the inclusion-exclusion principle. The principle consists in adding out items in the sets divisible by 2, 3, 5, etc., and then subtracting out all the items divisible by a product of two distinct primes, then add in all the items divisible by a product of three distinct primes, then subtract out all the items divisible by a product of four distinct primes, and so forth. The complexity of the standard implementation of this algorithm is O (2^n), where n is the number of distinct primes. In this problem, we have up to n = 31 prime numbers and an execution time of 2^31, so the solution is not good as it is.

The value of b in the problem is less or equal to 10^15. Many products of distinct prime numbers easily exceed 10^15. The product of the first 14 smaller prime numbers already exceeds 10^15 knowing that we have 31 < 130. Thus, many of the 2^31 subsets that we should theoretically take into account do not change our response at all, because no value in the given input range would be divisible by these products. It would therefore be necessary to pre-calculate only the products of distinct prime numbers < 130 which are also less than 10^15 in an efficient manner.

Moreover, for different sub-problems, we can have different limits for a, so it would be nice to be able to sort our primes products so that we do not accidentally use a smaller prime product than our b. but contains a prime factor bigger than our a, for a particular query.

The solution is to consider 30 lists, one for each odd number from 3 to 129 inclusive. The list for prime p will just store all the product of odd primes for which p is the largest odd prime. The list for 3 just stores 3, since no other odd primes are less than 3. The list for 5 contains 5 and 15, all possible products for odd prime numbers 5 or less containing a 5 ( therefore 5 and 3 * 5). The list for 7 will stock 7, 21 (7 * 3), 35 (7 * 5) and 105 (3 * 5 * 7). Initially, the size of these lists doubles because we take all the old lists and multiply each value of all the old lists by the new prime number and also include the new prime number. But ultimately, what will happen is that we will start producing products in excess of 10^15. When that happens, we will simply not add them to our list and the size of the list will stop doubling.

We will use a main list M containing all the values ​​of the previous lists in a sorted order, it will be used to store the values ​​already calculated and will generate the following list. Thus, after having processed 3, 5 and 7, we will store 4 lists in memory: the lists of 3, 5 and 7, as well as the main list (M). Here are these lists, drawn visually:

3: 3

5: 5 - 15

7: 7 - 21 - 35 - 105

M: 3 - 5 - 7 - 15 - 21 - 35 - 105

Now, in our pre-calculation, we want to build our list for 11, which we will simply do starting with 11 and adding each element of the master list multiplied by 11:

11: 11 - 33 - 55 - 77 - 165 - 231 - 385 - 1155

Now we have to update the main list. To do this, run the merge algorithm on our list for 11 and the old main list to get:

M: 3 - 5 - 7 - 11 - 15 - 21 - 33 - 35 - 55 - 77 - 105 -165 - 231 - 385 - 1155

The total number of products calculated (without exceeding 10^15) is 23 641 442 which remains very reasonable since it represents approximately 1/4 * 10^8 number of operations tolerated in a competition like the ICPC. The sorting operation of the list does not need a sorting, it is done while merging he lists and runs in O (n).

Once we do this pre-computation, then for each a and b, we can just loop through all the prime lists corresponding to primes less than or equal to a. Then, for each product of primes, if it has an odd number of primes, we add (b/product + 1)/2, using integer division to our total, and if we have an even number of primes, we subtract the same value from our total. We divide by 2 to account for the fact that the range of values we are considering are odd numbers since we are dealing with all evens separately. The +1 is to work in the corner case. Say our product is 15 and b is 15, 1/2 is 0, but we want 2/2 in this case. Similarly, say b = 45 and our product is 15, we want to count both 15 and 45. (30 was counted with the evens.) In this case 45/15 = 3 and 3/2 is 1, but we want 4/2 to indicate that there are two odd values in 1..45 that are divisible by 15.

Hope this helps.