Coprimes on segments

6 years ago, # ^ |

Link on problem from post in russian

→ Reply

6 years ago, # |

I would use lower_bound and inclusion-exclusion principle.

→ Reply

6 years ago, # ^ |

Can you tell me your idea in more detail?

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

Thanks! I hope that I will succeed in this.

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

128*1000000*4 ~ 50 mb

→ Reply

6 years ago, # ^ |

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

128 * 1000000 * 4 / 1024 / 1024 ≈ 488.28125

→ Reply

6 years ago, # ^ |

Да верно.

→ Reply

6 years ago, # ^ |

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

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

→ Reply

the_art_of_war

6 years ago, # ^ |

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

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

→ Reply

6 years ago, # ^ |

+13

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

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

Sorry for my english

→ Reply

6 years ago, # ^ |

Получаю MLE 6.

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

→ Reply

6 years ago, # ^ |

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

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

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

Нет :)

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Забавно :)

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

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

→ Reply

6 years ago, # ^ |

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

→ Reply

the_art_of_war

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

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

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

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

→ Reply

the_art_of_war

6 years ago, # ^ |

← Rev. 2 →

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

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

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

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

→ Reply

Aeon

6 years ago, # ^ |

← Rev. 2 →

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

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

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

code

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

sodafago

6 years ago, # ^ |

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

→ Reply

Dword

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # |

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)

→ Reply

6 years ago, # |

← Rev. 3 →

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)

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

← Rev. 8 →

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

→ Reply

6 years ago, # ^ |

Thanks!

→ Reply