mr_knownothing's blog

How to solve DISTX on SPOJ?
By mr_knownothing, history, 7 years ago, In English

As the title is pretty clear, I want to solve this problem DISTX but I am unable to design any algorithm within time limit. The best I can think of is an n2 approach.

Can anyone please help me solve this problem?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 4   Vote: I like it +11 Vote: I do not like it

A parallel BFS from each point should run in O( MAX * (sqrt(MAX) / log(sqrt(MAX)) ) if you only transition through the primes lower than sqrt(MAX) and handle the (possibly) single prime bigger than that separately.

That said, my solution with runs locally on maximal random inputs in 0.7s keeps getting TLE, so maybe this isn't the right approach.

EDIT: Accepted, works but you reaaaally need to squeeze it.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Solution with O(N + MAX * log(MAX)) complexity exists. On Java it gets TLE, actually, but on CPP 14 it has "Time 1.20" on SPOJ (your AC solution has 2.74).

    Before all we need calculate distance from any number to 1. It can be done with Sieve of Eratosthenes and storing smallest/largest prime for each number for fast factorization.

    There are two main cases in this problem:

    1. a[i] == a[j], i != j — distance is 0;
    2. a[i] is unique in the input set.

    First case is handled very simply: we store for each value first and second index of element with that value. If element is first with that value — answer is second index, else — first index.

    Second case we can process next way: each path from x to y (x != y) can be represented as several divide operations and several multiplications. Let's call lca(x, y) number, before that we divide and after — multiply. It's obvious, that lca(x, y) is divisor of x and y. And d(x, lca, y) equals to distance(x) — distance(lca) + distance(y) — distance(lca) = distance(x) + distance(y) — 2 * distance(lca).

    We can see that if we fix lca, we can find optimal y for each x — it will be such y, that distance(y) is minimal, y is multiple of lca and y is presented in the input (tiebreaker is index of value in the input array). Actually, we need second minimum, too (when first minimum is start of path). So we can iterate over all numbers as lca in some answer paths and try to update minimal distances.

    It's known that complexity of 'for each number from 1 to N iterate over all multiples of that number)' is O(NlogN), so total complexity is O(N + MAX * log(log(MAX)) + MAX * log(MAX)) = O(N + MAX * log(MAX)).

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      That's a neat idea, I tried to make the LCA approach work with a BFS-like implementation but failed, didn't even imagine this sieve-like technique, thanks!

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Okay, that is a really helpful comment, and I tried implementing it, and I am facing TLE. That is because I am storing all the prime factors of each number in a vector in the sieve function. Obviously, we need all the prime factors of a number to get all the ancestors of that number, so that we can iterate over them.

      How have you tackled this situation?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        I am storing only one (any) prime divisor of each number (sieve is needed exactly for it). After that I can calculate distances for all numbers next way:

        distances[0] = distances[1] = 0;
for (int v = 2; v < MAX_N; ++v) 
   distances[v] = distances[v / prime_divisor[v]] + 1;
        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          If you are storing only one factor, that is the smallest one, then how do you calculate all the ancestors of any number, for e.g. if we have a number 12, then we need to go to all the ancestors of 12, right? That is, 12, 6, 4, 3, 2, 1. But if we store only one prime divisor, then the ancestors that we can get to are, 12, 6, 3, 1.

          How, by storing only one prime divisor, you are getting all the ancestors?

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +9 Vote: I do not like it

            First just get the distance from each number to 1, like Slamur's code above is doing.

            Then, if your lca is L, the distance from a multiple M to L is just distances[M] — distances[L], and this is all you need for the algorithm: fix L and iterate through all M = k*L. No need to generate every divisor, or even every prime divisor!

            → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            My point of view is not from element to it's divisors, but from divisor to all it's multiples.

            I iterates over divisors from 1 to MAX, for each divisor I update answers for elements of array that are multiples of this divisor, it can be done with simple 'for'-array:

            for (divisor = 1; divisor <= MAX; ++divisor) {
   for (multiple = divisor; multiple <= MAX; multiple += divisor) {
       // some code
   }
}

            Smallest prime for each number I store only for calculating distances from number to 1 (code in my previous commentary).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              Thanks a lot guys, Slamur and itu, I finally solved the problem in O(N+max*log(max)).

              It was definitely a challenging one for me!

              → Reply