5
\$\begingroup\$

Problem from Hacker Earth:

Inverted GCD:

Given an array a of \$N\$ numbers , you have to find the number of pair of indices \$i\$ and \$j\$ that satisfy the following relation:

  1. \$i < j\$
  2. \$a_i > a_j\$
  3. gcd\$(a_i , a_j) = 1\$

Input:

The first line of the input contains a single integer N - denoting the size of the array.
The next line contains N space separated integers denoting the array a.

Output:
Output a single integer - the answer to the problem stated above.

Constraints:
\$1 \le N \le 10^5\$
\$1 \le a_i \le 10^5\$

For this problem I've submitted the following solution in Python:

from fractions import gcd
n = int(input())
count = 0;
a = [int(x) for x in input().split()]
for i in range(n):
    for j in range(n):
        if(a[i]>a[j] and i<j and gcd(a[i] , a[j]) == 1):
            count +=1;
print(count)

I'm not sure what is the complexity of gcd() function in Python, but it clear due to two for loop that the time complexity is minimum \$O(n^2)\$.I can't understand how to reduce it. Because here we have to check these conditions between every pair of integers. I've seen such question here but there is no condition for gcd(), so can't relate these two questions. I'm newbie to Python.

\$\endgroup\$
3
\$\begingroup\$

I agree with coderodde's change, for possible a small performance increase.
I also agree with 200_success.

An alternate way to calculate \$\text{gcd}(a, b) = 1\$ is instead to define \$\text{prime_factors}\$ to return a set of the inputs prime factors. Then using \$\text{prime_factors}(a) \cap \text{prime_factors}(b) = \{\}\$, we can optimise you code. Since we don't want to find the gcd we don't need to have a way to store multiple numbers, and so a set is perfect.

And so we can change the driver code to something like:

def inverted_gcd(n, numbers):
    factors = [prime_factors(num) for num in numbers]
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] > numbers[j] and not factors[i] & factors[j]:
                count += 1
    return count

Personally I'd use sum and so would change it to:

def inverted_gcd(n, numbers):
    factors = [prime_factors(num) for num in numbers]
    return sum(
        1
        for i in range(n) for j in range(i + 1, n)
        if numbers[i] > numbers[j] and not factors[i] & factors[j]
    )

At this point I used an algorithm to find prime factors. After reading some of the comments around it, I decided to use a different algorithm. Turns out the algorithm I used was exactly the same, just with an optimization.

Rather than generating the primes in the algorithm, I just Googled for a fast prime generator. This gave me a large amount of functions to choose from. As I don't have psyco or numpy I decided to use rwh_primes2. This gave me the following code:

# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n//3)
    sieve[0] = False
    for i in range(int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      ((k*k)//3)      ::2*k]=[False]*((n//6-(k*k)//6-1)//k+1)
            sieve[(k*k+4*k-2*k*(i&1))//3::2*k]=[False]*((n//6-(k*k+4*k-2*k*(i&1))//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]


def build_factors(max_n):
    primes_ = primes(int(math.sqrt(max_n)) + 1)
    def factors(num):
        if num != 0:
            for prime in primes_:
                while num % prime == 0:
                    yield prime
                    num //= prime
                if num == 1:
                    break
            else:
                yield num
    return factors

I then adapted your original code, that I also changed above, to:

def invert_gcd(n, numbers):
    prime_factors = build_factors(max(numbers))
    factors = [set(prime_factors(n)) for n in numbers]
    return sum(
        1
        for i in range(n) for j in range(i + 1, n)
        if numbers[i] > numbers[j] and not (factors[i] & factors[j])
    )

This made the performance a fraction of yours: (the number before the percentage is how big the list was.)

721 11.50%
 new_invert_gcd 1.461
 old_invert_gcd 12.7
914 13.28%
 new_invert_gcd 2.604
 old_invert_gcd 19.61
685 11.31%
 new_invert_gcd 1.336
 old_invert_gcd 11.81
292 17.77%
 new_invert_gcd 0.3298
 old_invert_gcd 1.856
215 16.59%
 new_invert_gcd 0.1467
 old_invert_gcd 0.8844
374 11.56%
 new_invert_gcd 0.4022
 old_invert_gcd 3.481
990 13.21%
 new_invert_gcd 2.881
 old_invert_gcd 21.82
220 20.74%
 new_invert_gcd 0.1673
 old_invert_gcd 0.8068
296 19.70%
 new_invert_gcd 0.3351
 old_invert_gcd 1.701
194 18.18%
 new_invert_gcd 0.1212
 old_invert_gcd 0.6667
730 15.83%
 new_invert_gcd 1.999
 old_invert_gcd 12.63
113 22.15%
 new_invert_gcd 0.05051
 old_invert_gcd 0.2281
28 53.15%
 new_invert_gcd 0.006326
 old_invert_gcd 0.0119
884 13.78%
 new_invert_gcd 2.166
 old_invert_gcd 15.71
292 18.45%
 new_invert_gcd 0.4417
 old_invert_gcd 2.394
136 32.23%
 new_invert_gcd 0.1859
 old_invert_gcd 0.5768
20 99.14%
 new_invert_gcd 0.006373
 old_invert_gcd 0.006428
246 17.32%
 new_invert_gcd 0.2134
 old_invert_gcd 1.232
707 12.95%
 new_invert_gcd 1.372
 old_invert_gcd 10.6
572 16.74%
 new_invert_gcd 1.008
 old_invert_gcd 6.022

Most of the time, this algorithm is ~10-20% the speed of yours. I tested with the constraints: \$1 \le N \le 10^3\$
\$1 \le a_i \le 10^5\$
This is as if you increase \$N\$ your program takes a long time.

\$\endgroup\$
3
\$\begingroup\$

tl;dr TLE beyond input size 40000 to 50000 (10 seconds for input size 100000)

Conditions (1) and (2) are transitive but independent and one-sided. This means they can only prune half of all candidates on average each, and so their combination only reduces the average candidate set to one fourth (i.e. half of a half). Such a small constant factor is not worth it to invest in (as in 'devising a special data structure'), unless overall performance is already close to a passing grade. Asymptotic performance doesn't change at all, of course. Hence it is best to take the doubling in performance that comes from index pruning (condition (2), which is essentially free) and test condition (1) as pairs are processed.

Condition (3) induces a squarish relation all on its own already, and it is not transitive. This means that there is no efficiency gain from precomputing this relation, and memoisation is likely to be completely ineffective in the face of random inputs.

The evaluation of the GCD for a pair of numbers takes time logarithmic in the smaller of the two inputs. This time can be cut by a considerable constant factor with a bit of precomputation, by computing integer-sized 'bit vectors' representing the presence of a handful of the smallest primes in the (radical) factorisation of a number.

This way a simple binary AND can prove the absence of shared small factors and thus avoid the computation of the actual GCD in about 89% of all cases (assuming factorisation by the first 32 primes, i.e. up to 131). In the remaining 11%, only the factorisation 'remainders' need to be GCDed, i.e. what remains after dividing out the small factors/radicals represented by the bit vectors. This saves some iterations of Euclid's algorithm.

This can give you an overall speed boost of an order of magnitude or more. On top of the factor 2 speed gain from index pruning mentioned by coderodde and some general efficiency tuning this might just be enough to beat the time limit...

Note: one might be tempted to extend the 'bit vectors' from 32 bits to 64 bits to utilise the bigger machine words on 64-bit machines, but this is not worth it. It doubles the up-front factorisation effort but it improves the rejection rate only from 88.7% to 90.3%, i.e. by a completely negligible 1.8%.

Here's a small table with the pass/reject rates for bit masks involving the given number of the first primes:

 8 primes: pass 17,102%, rej. 82,898%                 # up to 4 extra radicals
12 primes: pass 14,872%, rej. 85,128% // boost 2,690% # up to 3 extra radicals
16 primes: pass 13,609%, rej. 86,391% // boost 1.484%
32 primes: pass 11,300%, rej. 88,700% // boost 2,673%
64 primes: pass  9,683%, rej. 90,317% // boost 1,823% # up to 1 extra radical

The 'up to X extra radicals' bit says how many different prime factors can remain in the factorisations of numbers not exceeding 100,000 after the the given number of the first small primes has been factored out.

P.S.: the bounds on the number of numbers is the same as the bound on the size of the numbers, which means that the factorisations can be pre-computed wholesale without any divisions (by borrowing the logic behind the Sieve of Eratosthenes). The partial factoring for the bit vectors takes less than a millisecond, and factoring the input remainders takes less than 10 milliseconds for 100,000 inputs. Hence the stuff can always be computed wholesale and it isn't even worth it to have different code paths for small and big input batches.

--- UPDATE ---

For getting a better handle on the problem I needed a closer fix on some numbers, and so I coded things up in C++. It turned out that computing the gcd of the remainders (after factoring out the small primes used in the 'bit vectors') is orders of magnitude too slow, even though it occurs only for 0.35% of all candidates. This necessitated replacing the partial factorisation remainders with lists of the (up to two) remaining radicals.

'Radical' Optimisation

For numbers less than 107113 = 43 * 47 * 53, factoring out the 13 smallest primes leaves at most two distinct prime factors ('radicals'). Moreover, only factors up to half the limit need be considered since the only numbers with bigger prime factors are the primes, which are coprime to all numbers but themselves and self-pairings get excluded via criteria (1) and (2) both. This means that 2 x 16 bits = 32 bits are sufficient for storing the 'list' of remaining radicals for a number.

This size reduction is beneficial for L1 cache utilisation and it would allow to stuff both radicals into a single 32-bit integer; however, it collides with an important optimisation of the intersection operation. This optimisation is the reduction of branchings to the absolute minimum of two to three comparisons, by always treating the two-element lists as full and by replacing all but one of the remaining non-comparison branches with arithmetic (poor man's CMOV). This makes things easier for the CPU's branch prediction logic and reduces the amount of incurred branch mis-prediction penalties, but it requires the use of sentinel values for 'missing' radicals. With the only safe sentinel for a number a[i] being a[i] itself this means that the slots for the radicals must be able to hold full-sized numbers.

Elimination of one particularly nasty branch required adding a third radical slot (which always holds a sentinel value) but it resulted in a speedup of 10%. Without this explanation it might seem odd that the code uses three slots even though there can be at most two radicals. First, the data:

uint16_t sieve[1 + LIMIT];  // bit masks of partial factorisations of 1 .. LIMIT
uint16_t v[1 + LIMIT];      // v[i] = sieve[a[i]]
uint32_t f[1 + LIMIT][3];   // remaining factors (radicals) for each input (3rd is sentinel)
uint8_t skip[1 + LIMIT];    // for each a[j]: how many successors are not less

The code for generating these tables is elementary and of little interest here (especially as it takes less than 10 milliseconds even in C#). Hence I'm skipping it in the interest of brevity. Here is the meat of the code, the function that does the counting as specified by the task:

uint64_t count_matches (uint32_t const a[], uint32_t count)
{
    uint64_t result = 0;

    prepare_tables(a, count);

    for (uint32_t i = 0; i < count; ++i)
    {
        uint32_t a_i = a[i];
        unsigned v_i = v[i];

        for (uint32_t j = i + 1; j < count; ++j)
        {
            if ((v_i & v[j]) == 0)
            {
                if (a_i > a[j])
                {
                    if (uint32_t d = f[i][0] - f[j][0])
                    {
                        uint32_t di = (d >> 31) & 1;
                        uint32_t ci = di;
                        uint32_t cj = di ^ 1;

                        if ((d = f[i][ci] - f[j][cj]) != 0)
                        {
                            di = (d >> 31) & 1;
                            ci += di;
                            cj += di ^ 1;

                            if ((d = f[i][ci] - f[j][cj]) != 0)
                                ++result;
                        }
                    }
                }
                else j += skip[j];
            }
        }
    }

    return result;
}

On my laptop this clocks a bit less than 19 seconds for random inputs of size 100,000, compared to 22 seconds for a 'branchy' version of the intersection test (which has no use for the third slot):

                    int32_t d = int32_t(f[i][0] - f[j][0]);

                    if (d > 0)
                    {
                        d = int32_t(f[i][0] - f[j][1]);

                        result += d > 0 || d && f[i][1] != f[j][1];
                    }
                    else if (d != 0)
                    {
                        d = int32_t(f[i][1] - f[j][0]);

                        result += d < 0 || d && f[i][1] != f[j][1];
                    }

Of course, in Python the optimisation is bound to get killed by the interpreter overhead, because the code contains a lot of explicit little operations instead of pushing processing into the engine. But in any case it should be beneficial to utilise the fact the 'radical factor set intersection' involves only lists of at most two elements here instead of general sets.

Skip Counts

The skip count thing hasn't been mentioned yet - it's a small optimisation that costs virtually nothing and improves speed by about 10%. It utilises the fact that a[i] <= a[j] && a[j] <= a[j + k] implies a[i] <= a[j + k], and storing/precomputing this is cheap because it involves only a[j] and its context in the input sequence instead of depending on pairings of a[i] and a[j].

Half of all skip counts are 0, of course, and half of the rest is 1. The rest peters off quickly because the probability of a skip count having value k is 1 / ((k+1)*(k+2)), which means that skip counts of four bits or so already realise most of the performance gain that can be gotten this way.

Four bits would probably be optimum if one wanted to stuff several different values - like input number, small factor bit vector and skip count - into a single integer-sized variable, especially in languages where array indexings carry a heavy cost (Python, Java, C#). In my sample code I used a separate array for simplicity, and hence allocated one whole byte for each skip count.

Numbers and Summary

The reason I sat down and got coding was that I wanted to get a fix on some numbers, in order to get a better handle on the problem and a better feeling for the lay of the land. Here are those numbers.

For a random input vector of 100,000 numbers - the limit given in the task description - and enumerating only the 4,999,950,000 pairs of numbers with i < j, it took the following amounts of time to count the following things:

  • 11.0 s for 2512386875 inversions
  • 21.5 s for 3029211382 coprime pairs
  • 17.3 s for 1527936260 candidates (a[i] > a[j] and no common factors among the first 16 primes)
  • 15.7 s for 1527936260 candidates (dito, with byte-sized skip counts)
  • 85.7 s for 1522549277 matches (with gcd applied to remainders)
  • 18.6 s for 1522549277 matches (with list intersection for remainder radicals)

The most important message here is that the number of inversions (i.e. criterion (2) in the task description), the number of coprime pairs (criterion (3)) and the number of results to be counted are all the same order of magnitude as the number of pairs with i < j. The percentages are 50.2%, 60.6% and 30.5% respectively.

Also, just counting the number of inversions takes more than five times as long as the two seconds admissible as per the task description, even though my laptop is likely quite a bit faster than the hardware used by the robot judge.

Even if I found some fiendishly clever algorithm or data structure which can prune everything that doesn't fulfil the task conditions then the time would still be 30.5% * 19 s which is about 6 seconds. In other words, on a maximum input file the code would still take three times as long as the time limit.

For comparison, counting the matches for a vector of 1000 random inputs - as per coderodde's 'lightened' specification - takes less than 2 milliseconds with this code. I'd hate to think how long coderodde's solution would take on a maximum input file as per the actual task description; extrapolation from the given results puts it at more than half an hour.

In the first two paragraphs of this post I argumented why the intersection of the task criteria must leave a number of pairings that is still square in the number of inputs; now we know that the actual number is about 30% of 'j-pruned' pairs or 15% of all input pairs. Moreover, the C++ timings suggest that counting each result pair individually is simply not an option, since the optimisation potential that's still left is far less than an order of magnitude (which is why I didn't bother to create an optimised version).

Any admissible solution must count whole swathes of pairs in one go instead of processing each pair individually, but at the moment I cannot offer any specific advice as to how one might accomplish that. One seedling of an idea might lie in the fact that any prime must a priori be coprime to any input number other than itself, so that only criteria (1) and (2) need be applied for counting it. Similar considerations apply to sets of input numbers that have disjoint sets of prime factors.

I took a peek at the submission table at HackerEarth, and the only successful submissions I could see were in C++ with timings between 3.3 seconds and 12 seconds, with codes sizes ranging from 10KB to several hundred KB. This suggests that real solutions might be quite involved, compared to the simple code that has been discussed in this topic so far. I did not look at any of the code, however, because I intend to have a stab at the problem myself first...

UPDATE #2

250,000,000 factor set intersections per second

For an input vector of 10^5 values the current algorithm has to filter 0.5 * (10^5)^2 pairs of numbers - that's about 5 billion (American-style). Performance can be roughly doubled by looking only at inversions and by removing all branches but one from the set intersection code.

The standard algorithm for inversion counting by merge sorting divides the input into non-inverted and inverted runs and tallies the latter:

long count_inversions_m1 (List<int> values)
{
    long inversions = 0;
    int n = values.Count;
    var a = values.ToArray();
    var b = new int[n];

    for (int w = 1; w < n; w <<= 1)
    {
        for (int beg = 0; beg < n; beg += w + w)
        {
            int mid = Math.Min(beg + w, n);
            int end = Math.Min(mid + w, n);

            for (int i = beg, j = mid, k = beg; k < end; ++k)
            {
                if (i < mid && (j >= end || a[i] <= a[j]))
                {
                    b[k] = a[i++];
                }
                else // a[k] > a[j] for all k in [i .. mid - 1]
                {
                    inversions += mid - i;
                    b[k] = a[j++];
                }
            }
        }

        var t = a;
        a = b;
        b = t;
    }

    return inversions;
}

In the a[i] > a[j] branch, the run from a[i] to a[mid - 1] is inverted with respect to a[j]; all inversions in the input pass that branch eventually. Replacing the line

 inversions += mid - i;

with a small loop that performs factor set intersection on the values involved gives an algorithm that is a tad faster than the earlier one, because it never has to look at any non-inverted pairs. Simply dropping the intersection code from the earlier version in there would work, but it can be made faster by using branch-less comparison.

That is, instead of branching based on the result of comparing factors, a value is computed that is 0 if the two lists of non-bitmapped prime factors (at most two elements each) have some value in common, and 1 if they do not. I chose to abuse the fact that, given a pair of unequal values a and b, either a - b or b - a must be negative but no difference is negative if the values are equal. Hence the high bit of (a - b) | (b - a) is 1 if the values are different, and 0 if they are equal (as long as the difference does not exceed INT32_MAX).

A further speedup comes from ‘compressing’ factors down to 16 bits. This is possible because the factors are only ever compared for equality, and any unique mapping of values will do just as well for that. There are only 9592 primes up to 100000, and so there are many viable schemes for assigning each prime a unique 16-bit proxy value. I chose p < UINT_MAX ? p : (ushort)(p + 3) for simplicity. This ‘compression’ from 32 bits to 16 bits leads to better cache utilisation and reduces register pressure for 32-bit architectures (since a whole pair fits into a single machine word).

Here's the final set intersection code, ready for replacing the inversion branch in the above procedure (C++ version shown, but the C# is similar):

uint32_t a_j = b[k] = a[j++];                // x 815,024
unsigned f_j = factor_bits[a_j];
unsigned bj0 = big_factors[a_j][0];
unsigned bj1 = big_factors[a_j][1];

for (uint32_t l = i; l < mid; ++l)
{
    uint32_t a_i = a[l];                     // x 2,512,386,875

    if ((f_j & factor_bits[a_i]) == 0)   
    {
        unsigned bi0 = big_factors[a_i][0];  // x 1,527,936,260
        unsigned di0 = ((bi0 - bj0) | (bj0 - bi0)) & ((bi0 - bj1) | (bj1 - bi0));
        unsigned bi1 = big_factors[a_i][1];
        unsigned di1 = ((bi1 - bj0) | (bj0 - bi1)) & ((bi1 - bj1) | (bj1 - bi1));

        result += (di0 & di1) >> 31;         // 1,522,549,277 x 1 vs 5,386,983 x 0
    }
}

The 16-bit factor bitmaps are kept in a separate array to improve cache efficiency, because the bitmap AND must occur for every inversion pair whereas comparison of the up to two extra factors occurs less often. I've annotated some code lines with execution counts for an input of 100,000 random values, to put things a bit into perspective.

The resulting code comes closer to the goal, but not close enough. The C++ version still needs 10 seconds for a maximum-size (non-degenerate) input, and for the C# edition it's 12.5 seconds. I submitted the C# but, as expected, it failed all (non-degenerate) test cases where the input size exceeded 40,000 significantly. The performance target seems almost within reach, but it seems hopeless to try squeezing another five-fold performance increase out of the current approach.

I've chosen to complete the write-up despite the failure because some of the techniques may be useful for other challenges. Thanks to Kaushal28 for bringing this neat problem to our attention - I had a lot of fun trying to solve it and I learnt a lot along the way.

\$\endgroup\$
1
\$\begingroup\$

Algorithm

You could write a little bit more succintly (and efficiently):

from fractions import gcd

n = int(input())
count = 0
a = [int(x) for x in input().split()]
for i in range(n):
    for j in range(i + 1, n):
        if a[i] > a[j] and gcd(a[i], a[j]) == 1:
            count += 1

print(count)

Above, I let j begin with the value of i + 1. That way, I prune about half of all pairs. Also, since i < j always in the above version, we can remove the test and i<j.

Coding conventions

In Python, it is advised that there is a single space around any binary operator. For example:

i < j

instead of

i<j

Also, you don't need to terminate a statement with a semicolon; be consistent.

\$\endgroup\$
  • \$\begingroup\$ it doesn't really matter. This code is also giving the same number of Time limit exceed as of mine. From 31 cases, this code fails in 18 cases, same as my code. \$\endgroup\$ – Kaushal28 Jun 29 '16 at 8:31
  • \$\begingroup\$ @Kaushal28 What is the largest integer present in the test cases? \$\endgroup\$ – coderodde Jun 29 '16 at 8:35
  • 4
    \$\begingroup\$ @Kaushal28 Feel free to ignore my answer. Since there is \$\Theta(n^2)\$ possible pairs, I don't think it is possible to reduce the complexity. If so, it would seem that computing the GCD over and over again is the performance bottleneck. Since gcd(a, b) == 1 only when \$a\$ and \$b\$ are coprime (have no common prime factors), perhaps you could try to factorize all \$a_i\$ and then instead of computing the GCD, simply look whether the factorization of the two integers intersect or not. \$\endgroup\$ – coderodde Jun 29 '16 at 8:41
1
\$\begingroup\$

You've coded the solution as a very literal translation of the problem statement. gcd(a[i] , a[j]) is likely to be the performance bottleneck.

Consider what "\$\mathrm{gcd}(a_i, a_j) = 1\$" means: it means that \$a_i\$ and \$a_j\$ have no factors in common. So, instead of computing GCDs pairwise for all pairs, find the prime factorization of each number in the list, then report the ones whose set intersection is empty.

\$\endgroup\$
0
\$\begingroup\$

(tl;dr 150 ms via Möbius inclusion-exclusion of inversion counts for values sharing factors)

My previous answer showed that dealing with each inversion individually must be too slow for meeting the performance target, unless someone can find some seriously serious optimisations that I missed.

This means that we need a way to process inversions wholesale - in batches or groups.

The sets of inputs that are coprime to any given input are potentially just as numerous as the inputs themselves, but the sets of inputs that share common factors are fewer: in the worst-case scenario of 100,000 values from 1 through 100,000 there are only 30,401 square-free divisors with an average of 24.5 multiples per divisor, for a total work factor of 748,188 (compared to the 2,500,000,000 inversions that the earlier algorithm had to deal with for a random 100k input).

This suggests computing the number of coprime inversions as the difference between the total number of inversions and the number of inversions involving inputs with shared factors, provided a thorny subproblem can be solved.

The thorny subproblem is essentially this: if we subtract inversions for multiples of 2 and inversions for multiples of 3 then the inversions for multiples of 2*3 get subtracted twice. Adding the inversions for multiples of 2*3 back in effectively leads to an excess for multiples of 2*3*5 and 2*3*5*7 and so on, partially voiding the subtractions done for factor 5 etc. pp. The solution here - which I had to google - is to use inclusion/exclusion by subtracting the counts for odd numbers of unpowered prime factors (radicals) and adding the counts for even numbers of such factors. In the end this gives exactly the desired result.

Only square-free divisors need to be considered, since the counts for powers of prime factors are already included in the counts for the unpowered prime factors if applicable. Möbius (he of the strip) invented the µ function precisely for dealing with this kind of thing: it returns -1 if the factorisation contains an odd number of radicals, +1 for even radical counts, and 0 if the number is not square-free. First draft:

long count_matches (int[] a)
{
    int max_value = a.Max();
    var moebius = Util.Moebius_up_to(max_value);
    var multiples = values_per_squarefree_divisor(a, max_value, moebius);
    var temp = new int[a.Length];

    long result = MergeSort.count_inversions(a, temp);

    for (int d = 2; d <= max_value; ++d)
        if (multiples[d] != null && multiples[d].Count > 1)
            result += moebius[d] * MergeSort.count_inversions(multiples[d], temp);

    return result;
}

µ(1) is 1 because 0 is even (i.e. 1 does not have any prime factors), which means that the loop can handle the total inversion count as well if we start the algorithm with divisor 1 instead of 2, at the comparatively small cost of effectively copying all of the input into multiples[1].

This makes the code more compact and succinct, by removing a special case from the multiples-finding code and by changing the initialisation of the result to 0. The resulting overhead is minuscule and difficult to measure since it gets swamped by the much bigger natural jitter.

long count_matches (int[] a)
{
    int max_value = a.Max();
    var moebius = Util.Moebius_up_to(max_value);
    var multiples = values_per_squarefree_divisor(a, max_value, moebius);
    var temp = new int[a.Length];

    long result = 0;

    for (int d = 1; d <= max_value; ++d)
        if (multiples[d] != null && multiples[d].Count > 1)
            result += moebius[d] * MergeSort.count_inversions(multiples[d], temp);

    return result;
}

Here is the code that collects, for each square-free divisor d, all the values in the input that are multiples of d. It is the simpler version that starts with d = 1.

//---------------------------------------------------------------------------------------------
// associate input values with all of their square-free factors (moebius[] is used for testing 
// the square-freeness of divisors, since it is readily available)

static List<int>[] values_per_squarefree_divisor (int[] a, int max_value, sbyte[] moebius)
{
    var result = new List<int>[1 + max_value];

    for (int i = 1; i <= max_value; ++i)
        result[i] = new List<int>(max_value / i);

    for (int i = 0, n = a.Length; i < n; ++i)
    {
        for (int a_i = a[i], d = 1; (long)d * d <= a_i; ++d)
        {
            int q = a_i / d;

            if (q * d == a_i)  // d divides a[i] evenly
            {
                if (moebius[d] != 0)            // d is square-free
                    result[d].Add(a_i);

                if (moebius[q] != 0 && q != d)  // q is square-free and different
                    result[q].Add(a_i);
            }
        }
    }

    return result;
}

The code for counting inversions is elementary and need not be shown. I chose an algorithm based on merge sort because merge sorting works regardless of the range of the input values whereas the performance of Fenwick trees (a.k.a. 'BIT' for 'binary-indexed tree') deteriorates to the degree that inputs deviate from a normalised state. The actual code I used is essentially same as count_inversions_m1() in my other answer, except that the temp array is passed as parameter.

Computing a table of the Möbius function is also elementary, but here's some code for completeness' sake:

sbyte[] Moebius_up_to (int n)
{
    var moebius = new sbyte[1 + n];  // +1 because indexed by numbers
    var handled = new bool[1 + n];   // composite or already processed

    Fill(moebius, (sbyte)1, moebius.Length);

    for (int i = 2, d = 1, sqrt_n = (int)Math.Sqrt(n) ; i <= n; i += d, d = 2)
    {
        if (!handled[i])
        {
            for (int j = i, k = 0; j <= n; j += i)
            {
                if (++k == i)
                    k = moebius[j] = 0;
                else
                    moebius[j] = (sbyte)-moebius[j];

                handled[j] = true;  
            }
        }
    }

    return moebius;
}

This solution takes less than 150 milliseconds for processing random inputs of size 100,000, with leaves lots of spare room for the 2-second time limit. Porting the solution to Python should be fairly straightforward...

The full code can be inspected in my submission at HackerEarth.

\$\endgroup\$
-1
\$\begingroup\$

i think the second for loop is unnecessary.

from fractions import gcd
n = int(input())
count = 0;
a = [int(x) for x in input().split()]
for i in range(n - 1 ):
    j = i + 1
    if(a[i]>a[j] and gcd(a[i] , a[j]) == 1):
            count +=1;
print(count)
\$\endgroup\$
  • \$\begingroup\$ in your solution, j = i+1 , so, condition 1, i<j is always true and this will give always wrong answer \$\endgroup\$ – Kaushal28 Jun 30 '16 at 5:01
  • \$\begingroup\$ and also you are comparing only two consecutive numbers, because you provided j=i+1. Which is totally wrong. We have to check for all the possible pairs. Not only consecutive numbers. So two for loops are required. Please edit your answer, it is totally wrong solution. \$\endgroup\$ – Kaushal28 Jun 30 '16 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.