Здравствуйте, sjukov, Вы писали:

так как у нас образовался клуб любителей hackerrun которые не быдлокодят формочки
вопрос с моего собеседования на hackerrun на решение дели 15 минут
если надо могу пояснить условие задачи




K caterpillars are eating their way through N leaves. Each caterpillar falls from leaf to leaf in a unique sequence. All caterpillars start at a twig in position 0 and fall onto the leaves at positions between 1 and N. Each caterpillar i has an associated 'jump-number' Ai. A caterpillar with jump number j eats leaves at positions that are multiples of j. It will proceed in the order j, 2j, 3j, ... till it reaches the end of the leaves, then it stops and builds it cocoon.



Given a set A of K elements, we need to determine the number of uneaten leaves.



Input Format:

N = number of leaves
K = number of caterpillars

A = Array of integer jump numbers (one per line).



Constraints:

1 < N < 10^9

1 < K < 15

1 < A[i] < 10^9

Output Format:

Print an integer denoting the number of uneaten leaves.

Sample Input:

10
3
2
4
5

Sample Output:

4

Explanation: [2,4,5] is the 3-member set of jump numbers. All leaves which are multiples of 2, 4, and 5 are eaten. Only 4 leaves which are numbered 1,3,7,9 are left.

Здравствуйте, sergey2b, Вы писали:
S>вопрос с моего собеседования на hackerrun на решение дели 15 минут

ушло меньше 15 минут:

#include <iostream>
#include <vector>

int main()
{
    int l, c;
    std::cin >> l >> c;
    std::vector<int> eat(c);
    for(int i = 0; i != c; ++i)
        std::cin >> eat[i];

    int cl = 0;
    for(int i = 1; i <= l; ++i)
    {
        bool e = false;
        for(auto& v: eat){
            if(!(i % v)){
                e = true;
                break;
            }
        }
        if(!e)
            ++cl;
    }
    std::cout << cl << std::endl;
}

Здравствуйте, Sni4ok, Вы писали:

10^9 это 10 в 9 степени те 1 000 000 000 и масcив шагов может быть 1 000 000 000 и гусинец 15

Здравствуйте, sergey2b, Вы писали:

S>10^9 это 10 в 9 степени те 1 000 000 000 и масcив шагов может быть 1 000 000 000 и гусенец 15

и что? минутки за 3 просчитает невижу тут причин для оптимизации преждевременной)

Здравствуйте, Sni4ok, Вы писали:


S>>10^9 это 10 в 9 степени те 1 000 000 000 и масcив шагов может быть 1 000 000 000 и гусенец 15

S>и что? минутки за 3 просчитает невижу тут причин для оптимизации преждевременной)

вас здесь некто за язык не тянул — а реальная разработка это когда гуи формочки и простенькие sql запросики?

Здравствуйте, sergey2b, Вы писали:

S>вас здесь некто за язык не тянул — а реальная разработка это когда гуи формочки и простенькие sql запросики?

вы приписываете какие-то воображаемые требования к задаче(например по использованию cpu), которых небыло изначально?

Здравствуйте, Sni4ok, Вы писали:


S>>вас здесь некто за язык не тянул — а реальная разработка это когда гуи формочки и простенькие sql запросики?

S>вы приписываете какие-то воображаемые требования к задаче(например по использованию cpu), которых небыло изначально?

решение в лоб я сделал от безысходности это незачет
до кое какой оптимизации я додумался но сказали это недостаточно

Здравствуйте, Sni4ok, Вы писали:

S>>вопрос с моего собеседования на hackerrun на решение дели 15 минут
S>ушло меньше 15 минут:

Потому как с точки зрения hackerrun – ты задачу не решил. Задачи там алгоритмические и O(n) за верный ответ там обычно не считается.

Здравствуйте, sergey2b, Вы писали:

Какое то не полное условие. А что будет с гусеницей, когда она прыгнет и попадет на уже съеденный лист? Сдохнет? Будет прыгать дальше? Или я что-то пропустил в условии? Что будет если на один лист попадут две гусеницы? Съедят его в 2 раза быстрее? Тогда надо вводить "шаги" это процесса и уметь их дробить. Одна съест другую? по какому критерию? После этого она останется на этом листе в следующем шаге или окуклится?

Не люблю, когда ради оживляжа берут математическую проблему и начинают накручивать вокруг нее какую-то "историю". Тем кому интересна математика это не надо, кому математика не интересна все равно читать не будут. А иногда получается вот такая же чушь...

Здравствуйте, Sni4ok, Вы писали:

S>и что? минутки за 3 просчитает невижу тут причин для оптимизации преждевременной)

Гусеницы всё равно медленнее прыгают, как бы голодны они ни были.

Здравствуйте, Serg27, Вы писали:

S>Здравствуйте, sergey2b, Вы писали:

S>Какое то не полное условие. А что будет с гусеницей, когда она прыгнет и попадет на уже съеденный лист? Сдохнет? Будет прыгать дальше? Или я что-то пропустил в условии? Что будет если на один лист попадут две гусеницы? Съедят его в 2 раза быстрее? Тогда надо вводить "шаги" это процесса и уметь их дробить. Одна съест другую? по какому критерию? После этого она останется на этом листе в следующем шаге или окуклится?

я задал аналогичный вопрос (к сожаллению не сохранил пояснений)
если она попала на уже съеденный лист тут же переходит к следующему

Здравствуйте, sergey2b, Вы писали:

S>я задал аналогичный вопрос (к сожаллению не сохранил пояснений)
S>если она попала на уже съеденный лист тут же переходит к следующему

Отлично! А есть ли ограничение на число прыжков, которое может сделать голодная гусеница? Если она в конце концов остановится изголодав полностью, то следующая гусеница попавшая на нею может ее съесть и продолжить путешествие?

Ну и так до бесконечности...

Здравствуйте, Serg27, Вы писали:

нет все гусеницы идут до посленего листа в списке и потом на другое дерево

Здравствуйте, Sni4ok, Вы писали:

S>Здравствуйте, sergey2b, Вы писали:
S>>вопрос с моего собеседования на hackerrun на решение дели 15 минут

S> for(int i = 1; i <= l; ++i)

А мне по условию показалось, что листья с нуля нумеруются.

Здравствуйте, sergey2b, Вы писали:

S>Здравствуйте, sjukov, Вы писали:

S>так как у нас образовался клуб любителей hackerrun которые не быдлокодят формочки
S>вопрос с моего собеседования на hackerrun на решение дели 15 минут

Это за 15 минут надо было накодировать что ли? Или придумать решение?

S>если надо могу пояснить условие задачи

Могу направить в нужное русло. Нам нужно посчитать количество чисел от 1 до N, таких, что они не делятся нацело ни на одно из Ai. Будем искать другую величину, количество чисел, которые делятся как минимум на одно из Ai.
Возьмем некоторое Ai. Количество чисел, делящихся на Ai будет равно N / Ai. Можем сложить все эти значения, получим верхнюю оценку ответа S.
Теперь рассмотрим все возможные пары чисел (Ai, Aj), нам нужно будет найти все числа от 1 до N, которые делятся одновременно на Ai и на Aj, так как мы эти числа посчитали на предыдущем шаге дважды (как минимум), и вычесть количество таких числе из S. Затем рассмотреть все тройки чисел и т.д. Почитать про этот способ можно вот тут: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

Здравствуйте, kaa.python, Вы писали:

KP>Потому как с точки зрения hackerrun – ты задачу не решил. Задачи там алгоритмические и O(n) за верный ответ там обычно не считается.

Hackerrank? Или есть еще какой-то hackerrun?

Здравствуйте, _DAle_, Вы писали:

_DA>Hackerrank? Или есть еще какой-то hackerrun?

Нету, конечно, речь о Hackerrank.

Тут вроде сводится к нахождению взаимно съеденных листьев, т.е. таких, которые могла бы съесть данная гусеница, но которые были съедены до нее другой.
Например: если сначала была гусеница с шагом 4, а затем с шагом 6, то на ее пути будут съедены листья с индексами, кратными 12.
Это количество можно найти как (всего листьев / НОК (шаг пред, шаг)).
НОК можно посчитать зная НОД.
НОД, в свою очередь, можно посчитать по алгоритму Евклида, который описан у Кнута в 4.5.2.
Для каждой следующей гусеницы надо учитывать съеденное всеми предыдущими.

Здравствуйте, _DAle_, Вы писали:


_DA>Это за 15 минут надо было накодировать что ли? Или придумать решение?

накодировать собеседование в Блумбрег

Здравствуйте, sergey2b, Вы писали:
_DA>>Это за 15 минут надо было накодировать что ли? Или придумать решение?

S>накодировать собеседование в Блумбрег

Жесткие они.. интересно вот, им реально нужны именно олимпиадники? ) Слабо верится, что человек, никогда не участвовавший в алгоритмических соревнованиях, за 15 минут напишет работающее решение.

А как решать задачу понятно стало?

Здравствуйте, Serg27, Вы писали:

S>Здравствуйте, sergey2b, Вы писали:

S>>я задал аналогичный вопрос (к сожаллению не сохранил пояснений)
S>>если она попала на уже съеденный лист тут же переходит к следующему

S>Отлично! А есть ли ограничение на число прыжков, которое может сделать голодная гусеница? Если она в конце концов остановится изголодав полностью, то следующая гусеница попавшая на нею может ее съесть и продолжить путешествие?

S>Ну и так до бесконечности...

нет гучиница не может умереть по дороге она дойдет до конца всех листьев и перейдет на другое дерево (я вообще не знаю зачем они стали про гусинец говорить а не дали формальную задачу)

Здравствуйте, sergey2b, Вы писали:

В общем, нужно посчитать количество чисел из [1..N] кратных {Ai}. Ну, или дополнение до N, если угодно.

Обозначим множество чисел из R=[1..N] кратных произвольным числам a,b,...,z как M(a,b,...z) — Multiples
Мощность |M(abc..z)| = m(abc...z)

Для одиночного множителя
m(f) = floor(N/f)

Для пары множителей
M(a,b) = M(a) U M(b)
m(a,b) = m(a)+m(b)-m(a#b) — где a#b — наименьшее общее кратное — поскольку кратные НОК'у множителей мы сосчитали дважды, то одно вхождение выкинем

Для тройки
m(a,b,c) = m(a)+m(b)+m(c)-m(a#b)-m(a#c)-m(b#c)+m(a#b#c)

Ну и так далее.
Надо подумать (сейчас немножко влом), как посчитать для K-кортежа. То ли рекурсивно, то ли рекуррентно, то ли в цикле, забегом по K-битным числам.

Разумеется, следует подумать о том, как быстро считать НОКи сочетаний чисел. Возможно, что для больших K есть смысл сперва факторизовать числа, чтобы не считать НОК каждого с каждым "с нуля".

И разумеется, следует выполнять оценку трудоёмкости: что больше, O(2^K) или O(K*N).
Для N = 10^9, K ~ 15 выгоднее на НОКах. Для N ~ 1000, K = 15 — выгоднее брутфорсом.

Здравствуйте, kaa.python, Вы писали:

KP>Потому как с точки зрения hackerrun – ты задачу не решил. Задачи там алгоритмические и O(n) за верный ответ там обычно не считается.

с точки зрения HackerRank, ты делаешь сначала задачу как угодно, а потом в случае завала каких-то тестов(например по перфомансу)- оптимизируешь код, для данной задачи вот оптимизация на перфоманс, но это не означает что нулевое решение бы не прошло все тесты

#include <iostream>
#include <vector>
#include <algorithm>

struct caterpillars
{
    int l, eat;
    std::vector<int> ctps;
    caterpillars(std::vector<int>&& ctps, int l) : ctps(ctps), l(l), eat(){
    }
    int next_eaten()
    {
        int next = l + 1;
        for(int v: ctps){
            int c = eat - eat % v;
            while(c <= eat)
                c += v;
            next = std::min(next, c);
        }
        eat = next;
        return eat;
    }
};

int main()
{
    int l, c;
    std::cin >> l >> c;
    std::vector<int> eat(c);
    for(int i = 0; i != c; ++i)
        std::cin >> eat[i];

    caterpillars cp(std::move(eat), l);
    int ce = 0;
    for(int next = 0; next <= l;){
        next = cp.next_eaten();
        if(next <= l)
            ++ce;
    }

    std::cout << (l - ce) << std::endl;
}

Здравствуйте, _DAle_, Вы писали:

_DA>Могу направить в нужное русло. Нам нужно посчитать количество чисел от 1 до N, таких, что они не делятся нацело ни на одно из Ai. Будем искать другую величину, количество чисел, которые делятся как минимум на одно из Ai.
_DA>Возьмем некоторое Ai. Количество чисел, делящихся на Ai будет равно N / Ai. Можем сложить все эти значения, получим верхнюю оценку ответа S.
_DA>Теперь рассмотрим все возможные пары чисел (Ai, Aj), нам нужно будет найти все числа от 1 до N, которые делятся одновременно на Ai и на Aj, так как мы эти числа посчитали на предыдущем шаге дважды (как минимум), и вычесть количество таких числе из S. Затем рассмотреть все тройки чисел и т.д. Почитать про этот способ можно вот тут: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

Решение на Haskell, может кому будет интересно

import Control.Monad

-- Реализация функции включений-исключений
countIncExc :: Num a => ([t] -> a) -> [t] -> a
countIncExc f xs = sum [sign var * f var | var <- variants xs]
  where variants xs = filterM (const [True,False]) xs          -- все возможные варианты слагаемых
        sign var = if even (length var) then (-1) else 1       -- знак слагаемого
        
-- Решение задачи        
solve :: Integral a => a -> [a] -> a
solve totalLeaves caterpillarsJumps = totalLeaves - countIncExc f caterpillarsJumps
  where f [] = 0
        f jumps = totalLeaves `div` (foldl1 lcm jumps)

Пример:

solve 10 [2,4,5]
4

solve (10^9) [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
138704065

Сложность:
Если количество листьев N, а количество гусениц K, то сложность алгоритма будет
K * (2^K) * (log N), а вернее даже
K * (2^K) * (log (max A_i))

P.S. variants написан с помощью монад — элегантно, но непонятно.
Более понятно, но длиннее будет как-то так:

variants [] = [[]]
variants (x:xs) = 
  let vs = variants xs 
  in map (x:) vs ++ vs