ALTLG - Editorial (Unofficial)

editorial
,
1

I have not seen an official editorial on ‘Alternating LG Queries’ (ALTLG), so I will describe here my method of solution.

The problem statement is at CodeChef: Practical coding for everyone

Let me start with a key observation: Suppose we have a sequence of alternating gcd and lcm ending at index ‘i’. The values of the last two members of the sequence are L = lcm(A[i-1],A[i]) and G = gcd(A[i-2],L). If we then move the right limit to some position ‘j’ an even number of places to the right, and reevaluate the sequence back from there, by the time we get to position ‘i’ the value will be some factor of A[i], let’s call it D where A[i] / D = E.

When we continue to modify the sequence back from position ‘i’, we can see that lcm(A[i-1],D) will either be the same as L or be reduced by a number which is also a factor of E, let’s call it K. Similarly gcd(A[i-2],L / K) will be the same as G or be reduced by a factor of both G and K. As we work back along the sequence, the amount by which the value in the sequence is reduced will decrease from one position to the next, until it no longer changes.

Inspired by this observation I devised and implemented the following algorithm.

  1. Split the queries into two groups. In one group the gcd are applied at even indexes in the original array, and in the other at odd indexes. Note that this division is not the same as the ‘type’ of query.
  2. Evaluate the results in the most convenient order, to be stored in an array and printed at the end.

For each group:

  1. Sort the queries into ascending order of right limit. Note the minimum left limit of any query in this group.
  2. Build the sequence of results, working back from the smallest right limit to the smallest left limit.
  3. Work through the queries in ascending order of right limit. For each new limit, work back from right to left, comparing the new value in the sequence against the previous value, and stop when the value at the current index is unchanged.
    In each query the result is found at the left index in the sequence.

The time complexity is Q(log Q) to sort the queries plus something like N(log M) to build and modify the sequences, when M is the maximum value of items in the array, and logM the maximum number of factors in each item.

You can find my solution at CodeChef: Practical coding for everyone

4 Likes