dmkz's blog

By dmkz, history, 6 years ago, In English

Hello, codeforces! How we can solve this problem:

We are given an array a[1...n] (n ≤ 200000, 1 ≤ a[i] ≤ 1000000) of integers and given q queries (q ≤ 200000): li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 1000000). For each query we need to answer how many indexes j: li ≤ j ≤ ri and gcd(a[j], x) = 1.

Here's what I got:

1) before 1.000.000 only 78.498 primes

2) each number from input have no more than 7 prime divisors, because 2 × 3 × 5 × 7 × 11 × 13 × 17 = 510.510

3) count(li, ri, xi) = count(1, ri, xi) - count(1, li - 1, xi), li > 1

Time Limit is 1.5 s, Memory Limit is 64 MB.

Example:

6
1 2 3 4 5 6
4
1 6 1 --> 6
1 6 2 --> 3
2 4 6 --> 0
3 6 10 --> 1

UPD: solved by Aeon. Memory: 21 MB, Time: 1.2 s on worst case.

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

»
6 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

https://www.codechef.com/MARCH18A/problems/GCDCNT same problem but with assign queries

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I would use lower_bound and inclusion-exclusion principle.

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

    Can you tell me your idea in more detail?

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

      Несколько замечаний:
      1) Нас интересуют только простые делители числа (их не больше 7)
      2) Значит не больше 2^7 комбинаций простых делителей
      3) Ответ на отрезке [l, r] для x можно представить как ответ для комбинаций простых делителей
      4) Комбинации ограничены сверху 1000000
      Исходя из этого, можно построить алгоритм за O(NlogN × 128) или даже за O(N × 128)

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

        Thanks! I hope that I will succeed in this.

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

        Какую оценку по памяти мы можем достичь? Я посчитал, что если хранить в массиве d[v] для каждого числа v все позиции чисел, которые на него делятся, для бин.поиска при подсчете количества, то выходит 97 МБ в худшем случае (128*200000*4 байта), что лежит за пределами по времени.

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

          128*1000000*4 ~ 50 mb

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

            Похоже, что это 488 МБайт:

            128 * 1000000 * 4 / 1024 / 1024 ≈ 488.28125

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

              Да верно.

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

              Вообще будет (128*200000+1000000)*4 ~ 100 mb, но 7 делителей только в худшем случае, так что я бы рискнул (в среднем будет 4-5 делителя).

              Кроме того, можно разделить отрезок на левый и правый запрос и избавиться от бинарного поиска, обрабатывая запросы в оффлайне.

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

                Основная проблема сдать задачу с такими ограничениями. Не знаю зачем школьникам давать жесткие ограничения в TL/ML.

                Очень интересно действительно ли у авторов решение с двукратным запасом по времени, потому что сайт что-то слишком медленный.

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

                  В оригинале даже трёхкратный запас, олимпиада была на yandex.contest.

                  На acmp работает 3 секунды.

                  Sorry for my english

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

                  Получаю MLE 6.

                  Предполагает ли авторское решение дополнительные оптимизации памяти?

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

                  авторское ест 16-17 МБ

                  никаких спец оптимизаций нет, даже наоборот, местами неоптимально

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

                  Добавил корневую декомпозицию запросов, получаю TLE 8. МО ожидалось?

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

                  Нет :)

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

                  Забавно :)

                  • наивный upper_bound по комбинациям простых делителей получает TLE 6
                  • сортировка запросов в оффлайне получает MLE 6
                  • сортировка запросов в оффлайне + МО получает TLE 8

                  Какое решение ожидалось автором? :)

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

                  Включения-исключения, оффлайн, выше вроде про него уже написано, но нужно за O((N + M) × 27)

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

                  я также сдал, но что-то мало верится, что там не пришлось делать оптимизации по памяти.

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

                  мм, я кажется понял

                  у вас что-то вроде O(NlogN) памяти для делителей?

                  в авторском этого нет, делители числа просто генерятся рекурсией по простым

                  если для вас это оптимизация, то прошу простить :)

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

                  Для делителей хранил только простые делители.

                  Оптимизации, которые пришлось сделать.

                  1) хранить простые делители только для чисел, которые присутствуют в запросах или в массиве

                  2) все вектора пришлось убрать и переписать на массивы.

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

                  Чтобы сдать пришлось использовать 2 оптимизации, вектора присутствуют:

                  1) генерация делителей из простых

                  2) 27 вместо 27 * 7

                  code

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

                  Наконец-то зашла с 4с и 16 мб. Перебор делителей за 2^7 и оффлайн с O(N) памяти для делителей я все же считаю оптимизацией :)

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

                  Спасибо! После замены cin / cout на scanf / printf из stdio.h решение показало 3.374 с по времени и 21 МБ по памяти на медленном сервере и 2.4 с и 23 МБ на быстром сервере, что примерно означает не более 1.2 с по времени на сервере yandex.contest. На самой олимпиаде эту задачу не решила ни одна из команд.

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

                  actually, i submit run with scanf/printf and got TLE on test 10, when i replace them with fast cin/cout i got AC

                  i don't understand russian but google translate help

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

                  acmp.ru server: Core 2 Quad 2.4 MHz, Windows XP 32 bit, MinGW.

                  This code: 3.374 s and 21 MB

                  This code: 2.874 s and 23 MB

                  Original: 4.842 s and 21 MB

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

                  прости, Виталя, я не смог ее решить самостоятельно

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

                  Отправил решение. Получило ML на 5 тесте. Из больших объектов храню только различные делители всех n чисел (1 млн) и решето (1 млн чисел). Как думаете, в чем дело?

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Inclusion_Exclusion principle: we want to compute count(1, L, x) which is number of elements which are coprime with x, so let x = 6 which has 2, 3 primes

main information we need are how many numbers up to index L has 2 as factor, the same for 3, 6 lets call them C(L, 2), C(L, 3), C(L, 6)

and compute number of coprimes by In_Ex, ans = L — C(L, 2) — C(L, 3) + C(L, 6)

»
6 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

i don't know if there is better way but to compute C(L, y)

let vector d[N];

where d[j] contains indices of all elements of array Ai where j|Ai

so C(L, y) = lower_bound(d[y], L)

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

    Amazing! Sum of 106 / k from k = 1 to 1000000 ~ 14.500.000 operations to calculate vector d is to small, thanks!

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

      Yes you can compute it with sieve style bounded by O(n logn)

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

        This will exceed the memory limit, because in worst case is 2^7 * 200000 * 4 ~ 97 MB for array d

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          Rev. 8   Vote: I like it +8 Vote: I do not like it

          ok i will give you another aproach

          first read all queries then store for each index the x value for example l r x ---> store a[l].insert(x), b[r].insert(x)

          then let d[N] an array of integers, d[j] is number of elements that passed so far and has j as factor

          let function update(Ai){

          for each factor f of Ai
              d[f] += 1
          

          }

          now pass on elements i = 0 ... n-1{

          for each element x in a[i]
              ans[i] -= count(x) // count(x) computed in same way but now C(y) = d[y]
          
          update(Ai)
          
          for each element x in b[i]
              ans[i] += count(x)
          

          }

          for each query l r x
              output(ans[r] + ans[l])
          

          compute all divisors at first by sieve method so all vecotrs will store around 13 millions number

          Edit: ans[i] must be vector not array to store answers for different x's

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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