Codeforces #137 (div2) C. Reducing Fractions - update

I intended to return to participating in Codeforces. Today there was a division 2 match which would be good to restart engines. It didn't go so well at first, with site issues at the announced start time. Then they delayed the start of the match by 15 minutes. I had to wait more time.

Eventually I started by solving problem C. Things were going great until I tried to submit. But I could not. At first I thought it was a bug that I had in the past in division 2 matches - That "unofficial" coders were not able to submit due to a bug. But it turns out that I was just not registered. Which is strange, as I remember that around 1 hour before the contest I clicked register and had to login. And then I remember the register button not appearing anymore, so I thought I registered... Oh well.

C. Reducing Fractions

Link to problem statement

Ok, so, let us reduce a fraction. Unfortunately the numerator is expressed as a product of up to 10⁵ numbers each from 1 to 10⁷ and the denominator as well. The result must be printed using the same format.

Of course we cannot just multiply and then reduce. But either way, each number in the product is either going to be a prime number smaller than 10⁷ or a composite composed of prime numbers less than 10⁷. We could actually just keep two arrays. Each counting the number of times a prime factor appears in total in the numerator and the denominator. After getting these arrays, we can do the reduction easily: For example, let us say we have 20*6 as numerator and 2*7 as denominator. Then we have that 2 appears 3 times in total in the numerator (20 has 2, 6 has 1) and once in the denominator. Simply subtract the minimum count for each prime factor - Thus we have that in the reduced fraction, 2 will appear once in the numerator and 0 times in the denominator.

Some analysis. Each number from 1 to 10⁷ has at most log(X) prime factors. So in total the subtraction part will take O(n * log(X)) for X <= 10⁷. The real complication comes when extracting the prime factors of each number.

I am not sure if the usual O(sqrt(X)) algorithm to extract prime factors would be fast enough, 10⁵*sqrt(10⁷) might be too much for 2 seconds. But in fact, we can make an algorithm that is quite fast at extracting all prime factors of a lot of numbers with a fixed bound. The trick is to use a modified version of the Sieve of Eratosthenes, that instead of only marking if a number is prime or not, marks the number's first prime factor (for a prime number, the result is itself). By precalculating each number's first prime factor you can then use an iterative algorithm to extract all the prime factors of a number in O(log(X)) time (exactly the number of prime factors).

The second issue is, once you have the reduced counts of each prime factor, how to rebuild the two lists of integers in the original format. My intuition tells me that just multiplying each available factor from smallest to largest until the limit of 10^/ is reached for an element (and then skip to the next) should be fast enough. Assuming that the original input was also in this format.

old wrong code was here

It seemed like a good problem. Approachable but not without tricks you had to do and suspense (still not sure it is guaranteed to always follow the required conditions for the output.

After figuring out I was not registered, I stopped caring for the match. Perhaps will try to make a virtual context for it, simulating the time I spent in this problem (I finished coding and testing it at 12:11).

Update: I tried it in practice and I failed test 42. Most likely because of an assert related to the limit on the number of integers in the output. Such a high test number tells me this was not even in the sample tests, yet it changes the problem as it means it is not trivial to correctly build the results.

But instantly after, it occurred to me that there is a simple idea for an algorithm that would be guaranteed to follow the conditions. Simply, iterate through each element of a, and for each of its prime factors, subtract it from the number of times that factor should appear, if the current count is 0, remove the factor from the element. Do the same with b.

int n, m; 
int a[100000]; 
int b[100000]; 
 
const int MAX = 10000000; 
int firstFactor[MAX+1]; 
 
int countA[MAX+1]; 
int countB[MAX+1]; 
 
 
void addCounts(int x, int * counts) 
{ 
    // How to extract prime factors from a number x. 
    // counts[] stores the number of times each prime factor appears. 
    while(x != 1) { 
        int p = firstFactor[x]; 
        // just divide 
        while (x % p == 0) { 
            x /= p; 
            counts[p]++; 
        } 
        //the new value of x is not a multiple of p, and thus will have a  
        // different value for firstFactor[x] - the next prime factor... 
    } 
} 
 
// Rebuild the set of integers for the output. 
// counts[] stores the number of times each prime factor should appear. 
void buildIt(int* counts, int* res, int & t) 
{ 
    for (int i=0; i<t; i++) { 
        int x = res[i]; 
        while (x > 1) { 
            int p = firstFactor[x]; 
            x /= p; 
            if ( counts[p] > 0) { 
                counts[p]--; 
            } else {          //remove it 
                res[i] /= p; 
            } 
        } 
    } 
} 
void solve() 
{ 
    memset(countA, 0, sizeof(countA)); 
    memset(countB, 0, sizeof(countB)); 
    for (int i=0; i<n; i++) { 
        addCounts(a[i], countA); 
    } 
    for (int j=0; j<m; j++) { 
        addCounts(b[j], countB); 
    } 
    for (int i=2; i<=MAX; i++) { 
        int s = std::min(countA[i], countB[i]); 
        countA[i] -= s; 
        countB[i] -= s; 
    } 
    buildIt(countA, a, n); 
    buildIt(countB, b, m); 
 
} 
 
inline void init() 
{ 
    //Modified sieve of Erathostenes: 
    //firstFactor[x] will tell us the first prime factor of x. 
    memset(firstFactor, 0, sizeof(firstFactor)); 
    for (int i=2; i<=MAX; i++) { 
        if (firstFactor[i] == 0) { 
            // prime 
            firstFactor[i] = i; 
            for (int j=i+i; j <= MAX; j += i) { 
                if (firstFactor[j] == 0) { 
                    firstFactor[j] = i; 
                } 
            } 
        } 
    } 
}