Блог пользователя i_am_not_special

count increasing subsequence in O(n) -> OA Problem

Автор i_am_not_special, история, 4 месяца назад, По-английски

So the question is count the number of increasing subsequence such that the gcd of subsequence will be equal to 1.

1 <= size of array <= 1e5 1 <= a[i] <= 1e6

can anyone help me solve this problem.

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

0(n) = 0 * n = 0, wtf??

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by i_am_not_special (previous revision, new revision, compare).

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by i_am_not_special (previous revision, new revision, compare).

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Create a another array called primes which will have all the prime numbers in the given array in the same seqvence of the array and now create an another array called ream where ream[i] is how many numbers which are greater than primes[i] and right side of primes[i]. Now answer is sum of 2**k for each k in ream (pardon me if it's wrong).
For finding primes we can use Sieve of Eratosthenes.
For building ream array we can use merge sort (or) fenwick tree.

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by i_am_not_special (previous revision, new revision, compare).

→ Ответить
»
4 месяца назад, # |
← Rev. 5   Проголосовать: нравится +21 Проголосовать: не нравится

Let $$$\operatorname{count}_x$$$ be the number of integers which are divisible by $$$x$$$ in the array. Now let $$$\operatorname{dp}_x$$$ be the number of subsequences whose gcd is $$$x$$$. We can calculate $$$\operatorname{dp}_x$$$ from highest to lowest $$$x$$$-value. Initially we set $$$\operatorname{dp}_x = 2^{\operatorname{count}_x} - 1$$$. Then, we subtract all $$$\operatorname{dp}_y$$$ values where $$$y$$$ is a multiple of $$$x$$$.

Now you have the number of subsequences with a gcd of any $$$x$$$ in the $$$\operatorname{dp}$$$ array. You can use this same strategy to count the number of pairs with a gcd of $$$x$$$.

Edit: Sorry, this doesn't count increasing subsequences, I misread the problem. My fault.

Edit 2: Somebody replied to me, showing how you can extend this solution to work with increasing subsequences :)

→ Ответить
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Thanks for helping. Do you have the link of this problem.

    → Ответить
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    But these doesn't mantain the increasing property

    → Ответить
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Would the different order of operations will also give the same result? I think yes, that is, dp array will store the count of elements divisible only by x, and by none of it's multiples. then use this count to calculate the number of sequences using simple combinatorics as you demonstrated. And if this works, which I think it does, it saves you some tiny cost on not having to compute pow(2, countx) for bigger countx values, as would be the case if order of operations are as you suggested. Just being picky here

    → Ответить
  • »
    »
    3 месяца назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

    I think you can extend this to increasing subsequences.

    For each $$$x$$$, we consider a compressed array, containing only the elements in the array which are a multiple of $$$x$$$. Then $$$dp_x$$$ is just the number of increasing subsequences in that array.

    Every element will be considered only once for every divisor, lets assume the max amount of divisors for any number is $$$K$$$, the time complexity is $$$O(N * K * \log(N))$$$

    → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      Yeah that's correct, great!

      → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      can you please explain this for [7, 2, 5]

      → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Can you elaborate?

      → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +21 Проголосовать: не нравится

      We want to calculate the number of increasing subsequences that have gcd exactly $$$1$$$.

      Lets fix the gcd $$$x$$$, and calculate the number of increasing subsequences that have gcd exactly $$$x$$$ (lets call it $$$dp_x$$$). To do that we calculate the number of increasing subsequences such that all its elements are a multiple of $$$x$$$ (lets call it $$$f(x)$$$), and then subtract the $$$dp$$$ of all multiples of $$$x$$$. finally $$$dp_x = f(x) - dp_{2x} - dp_{3x} - dp_{4x}...$$$

      As I mentioned earlier, you can calculate $$$f(x)$$$ by considering only the elements that are a multiple of $$$x$$$ and counting the number of increasing subsequences with a segment tree.

      consider this example: [2, 3, 5, 6]

      Unable to parse markup [type=CF_MATHJAX]

      $$$dp_5 = f(5) - dp_{2 * 5} - dp_{3 * 5}.. = f([5]) = 1$$$

      $$$dp_3 = f(3) - dp_{2 * 3} - dp_{3 * 3}.. = f([3, 6]) - dp_{6} = 3 - 1 = 2$$$

      $$$dp_2 = f(2) - dp_{2 * 2} - dp_{3 * 2}.. = f([2, 6]) - dp_{6} = 3 - 1 = 2$$$

      finally our answer is, $$$dp_1 = f(1) - dp_{2 * 1} - dp_{3 * 1}.. = f([2, 3, 5, 6]) - dp_2 - dp_3 - dp_5 - dp_6 = (2 ^ 4 - 1) - 2 - 2 - 1 - 1 = 9$$$

      → Ответить
      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Thanks it got now. Is their is any similar type of question present on codeforces can you give the link.

        → Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's present in striver A to Z DSA sheet.

→ Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    really? Can you provide a link to it?

    → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      ah, sorry I thought it as "count longest increase subsequence in O(n)" my bad. This problem is present in DP on LIS section. But that problem is not present in the sheet :)

      → Ответить
»
3 месяца назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

why is this being upvoted, op literally said OA problem (and literally noone asked if it is ongoing or not)

→ Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Pretty sure, putting a problem post in CF,is one of the slowest ways to cheat in an ongoing OA isn't it?

    → Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Go for it make a another cheating or exposed blog.

    → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      oh calm down, I have once given an answer to one of these kinds of questions before, which later turned out to be from an ongoing OA. I was severely traumatized for that incident.

      anyways I believe the consensus should be "not giving an answer to a question unless the source of the task is clear and it is obvious that the questioner is not cheating".

      → Ответить