onkarhanchate14's blog

Mathology Codechef (march lunchtime )
By onkarhanchate14, history, 2 years ago, In English

link for question -> https://www.codechef.com/LTIME106B/problems/MATHOLOGY/ The question was bit tricky, Can anyone help with the approach for this question ?

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

Comments Comments (9)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved this problem this way. The task boils down to finding exactly two numbers with the maximum gcd on the subsegment of array (we don't need to find a subsequence with length more than 2). To begin with, for each number from 1 to 10^5, we will find all its divisors in O(n * logn). Then let's use MO's algorithm to process queries. We will maintain for each number from 1 to 10^5 how many numbers from the current segment it divides. The transition between queries from one block can be done for the number of divisors of the current number (which is not greater than 128 — 83160 has exactly 128 divisors). Answer for query is the biggest number which divides at least 2 numbers from subsegment of array. Complexity of this approach is O(n * sqrt(n) * d), where O(n * sqrt(n)) occurs because of MO's algorithm, d is maximum number of divisors of number from array.

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

    One more detail should be clarified. We maintain for each number from 1 to 10^5 how many numbers on the current segment it divides. To answer query, we need to find the index of the rightmost number which is at least 2 in this array. To do this, you can use Fenwick or segment tree, which will worsen the asymptotics to O(n * sqrt(n) * d * logn). But there is another way to do this. Let's split this array into blocks of size sqrt(n). While processing transition between queries in MO's algorithm you just increase or decrease by 1 d positions in the array in O(d) (in approach with Fenwick tree it is done in O(d * logn)). For each block of size sqrt(n) in this array you should maintain how many numbers not less than 2 are there in this block. When the transition is completed you can find answer to the query in O(sqrt(n)): at first, in O(sqrt(n)) find rightmost block with cnt > 0 (it means block which includes at least 1 number which devides at least 2 numbers from subsegment). After that, you can find rightmost which is at least 2 in this blocks in O(sqrt(n)) because size of the block is sqrt(n). So the total complexity is O(n * sqrt(n) * d).

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      shouldn't this give TLE when n is 1e5. n*sqrt(n)*d -> (1e5*3e2*100) I did the same during contest and it was accepted partially. My Solution. can you post you solution as well.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 4   Vote: I like it +6 Vote: I do not like it

        In such cases (when there is something scary like n * sqrt(n) * d in asymptotics and you understand that the solution is correct, and it can be optimized a little to fit in TL) I try to do following:

        0). In sqrt problems you often use division and taking the remainder of the division to find the block that the element falls into. These operations are slow and sometimes you can use multiplication instead of division or precalculate i / C and i % C for each i from 1 to n (C is constant about sqrt(n)). It can help a little.

        1). Use pragmas. I don't understand very well how they work and what they optimize. But from my own experience, I can say that writing this line #pragma GCC optimize ("unroll-loops") almost never worsens the program's running time, and often improves it. Moreover, the more nested loops there are in the program, the better it will be optimized. (I can say that if there are a lot of nested loops in the program and there are not very complex instructions in these cycles, the optimization will be great). Maybe I'm wrong, it just seems that way to me.

        2). In sqrt problems you can try to change C. I mean, in sqrt problems you often have some size of array n and constant C which is near to sqrt(n). And your algorithm has asymptotics like O(C * n + n * n / C) which is O(n * sqrt(n)) if C is sqrt(n). But you can try to increase or decrease C several times and then TL can become OK.

        Specifically in this task, "harmful advices" 1) and 2) can help to get AC. My solution gets TL and 40 points, but just writing pragmas unroll loops and -O3 gets AC. Changing C from 320 to 700 (without pragmas) gets AC too.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can I use this line — #pragma GCC optimize("unroll-loops") in every code I write. Will it improve the running time? I have never used pragmas before but now when I am seeing that without it we can get WA and with it we get AC, so should I use it in every code I write or is it not needed for now?

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            I think this way: you should not write pragmas in all your solutions. You can try to use them if you are sure that your solution is asymptotically optimal (or close to it) and it needs to be slightly non-asymptotically optimized so that it goes into TL. Also I didn't really understand about WA, I said that without unroll-loops my solution gets TL but with pragma it gets AC.

            → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Also, you can use gilbert's order to sort the queries. With that, my in-contest submission without any of the above optimizations gets AC.

          Oh yea btw, my submission does Mo's in O(d * n + sqrt(n) * n) via a trick I found here.

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

        Your code TLEs because of an additional log factor due to set.

        → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      With this trick it's possible to write a Mo's with O(n * sqrt(n) + n * d) which should fit comfortably below the time limit

      → Reply