Здравствуйте! Идеи, как решить следующую задачу, зашли в тупик, поэтому нужна помощь:
У нас есть массив a[1...n] (n ≤ 200000, 1 ≤ a[i] ≤ 1000000) из целых чисел и есть q запросов к этому массиву (q ≤ 200000) вида: li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 1000000). Для каждого запроса мы должны ответить сколько есть различных индексов j таких что li ≤ j ≤ ri и gcd(a[j], x) = 1.
Вот, что удалось осознать:
1) До 1.000.000 всего 78.498 простых чисел.
2) Каждое число во вводе не может иметь более 7 различных простых делителей, так как 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
Ограничения по времени 1.5 с, памяти 32 MB.
Задача была на полуфинале ВКОШП в Красноярском крае в сезоне 2017/2018 как задача "G. Скучные запросы". Разбор и архив жюри найти не удалось, а очень хочется. Здесь ее можно сдать, ограничения по времени немного увеличены в сравнении с оригиналом, так как сервер не самый быстрый, а система 32-битная.
Пример:
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: решено Aeon. Memory: 21 MB, Time: 1.2 s на худшем случае.
https://www.codechef.com/MARCH18A/problems/GCDCNT same problem but with assign queries
Link on problem from post in russian
I would use lower_bound and inclusion-exclusion principle.
Can you tell me your idea in more detail?
Несколько замечаний:
1) Нас интересуют только простые делители числа (их не больше 7)
2) Значит не больше 2^7 комбинаций простых делителей
3) Ответ на отрезке [l, r] для x можно представить как ответ для комбинаций простых делителей
4) Комбинации ограничены сверху 1000000
Исходя из этого, можно построить алгоритм за O(NlogN × 128) или даже за O(N × 128)
Thanks! I hope that I will succeed in this.
Какую оценку по памяти мы можем достичь? Я посчитал, что если хранить в массиве d[v] для каждого числа v все позиции чисел, которые на него делятся, для бин.поиска при подсчете количества, то выходит 97 МБ в худшем случае (128*200000*4 байта), что лежит за пределами по времени.
128*1000000*4 ~ 50 mb
Похоже, что это 488 МБайт:
128 * 1000000 * 4 / 1024 / 1024 ≈ 488.28125
Да верно.
Вообще будет (128*200000+1000000)*4 ~ 100 mb, но 7 делителей только в худшем случае, так что я бы рискнул (в среднем будет 4-5 делителя).
Кроме того, можно разделить отрезок на левый и правый запрос и избавиться от бинарного поиска, обрабатывая запросы в оффлайне.
Основная проблема сдать задачу с такими ограничениями. Не знаю зачем школьникам давать жесткие ограничения в TL/ML.
Очень интересно действительно ли у авторов решение с двукратным запасом по времени, потому что сайт что-то слишком медленный.
В оригинале даже трёхкратный запас, олимпиада была на yandex.contest.
На acmp работает 3 секунды.
Sorry for my english
Получаю MLE 6.
Предполагает ли авторское решение дополнительные оптимизации памяти?
авторское ест 16-17 МБ
никаких спец оптимизаций нет, даже наоборот, местами неоптимально
Добавил корневую декомпозицию запросов, получаю TLE 8. МО ожидалось?
Нет :)
Забавно :)
Какое решение ожидалось автором? :)
Включения-исключения, оффлайн, выше вроде про него уже написано, но нужно за O((N + M) × 27)
я также сдал, но что-то мало верится, что там не пришлось делать оптимизации по памяти.
мм, я кажется понял
у вас что-то вроде O(NlogN) памяти для делителей?
в авторском этого нет, делители числа просто генерятся рекурсией по простым
если для вас это оптимизация, то прошу простить :)
Для делителей хранил только простые делители.
Оптимизации, которые пришлось сделать.
1) хранить простые делители только для чисел, которые присутствуют в запросах или в массиве
2) все вектора пришлось убрать и переписать на массивы.
Чтобы сдать пришлось использовать 2 оптимизации, вектора присутствуют:
1) генерация делителей из простых
2) 27 вместо 27 * 7
code
Наконец-то зашла с 4с и 16 мб. Перебор делителей за 2^7 и оффлайн с O(N) памяти для делителей я все же считаю оптимизацией :)
Спасибо! После замены cin / cout на scanf / printf из stdio.h решение показало 3.374 с по времени и 21 МБ по памяти на медленном сервере и 2.4 с и 23 МБ на быстром сервере, что примерно означает не более 1.2 с по времени на сервере yandex.contest. На самой олимпиаде эту задачу не решила ни одна из команд.
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
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
прости, Виталя, я не смог ее решить самостоятельно
Отправил решение. Получило ML на 5 тесте. Из больших объектов храню только различные делители всех n чисел (1 млн) и решето (1 млн чисел). Как думаете, в чем дело?
Автокомментарий: текст был переведен пользователем dmkozyrev (оригинальная версия, переведенная версия, сравнить).
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)
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)
Amazing! Sum of 106 / k from k = 1 to 1000000 ~ 14.500.000 operations to calculate vector d is to small, thanks!
Yes you can compute it with sieve style bounded by O(n logn)
This will exceed the memory limit, because in worst case is 2^7 * 200000 * 4 ~ 97 MB for array d
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){
}
now pass on elements i = 0 ... n-1{
}
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
Thanks!
Автокомментарий: текст был обновлен пользователем dmkozyrev (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by dmkozyrev (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем dmkozyrev (предыдущая версия, новая версия, сравнить).