Голодные гусеницы
От: sergey2b ЮАР  
Дата: 04.10.15 18:24
Оценка:
Здравствуйте, 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.


05.10.15 05:19: Ветка выделена из темы Hackerrun test
Автор: sjukov
Дата: 26.09.15
— kaa.python
Re: Голодные гусеницы
От: Sni4ok  
Дата: 05.10.15 00:30
Оценка:
Здравствуйте, 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;
}
Re[2]: Голодные гусеницы
От: sergey2b ЮАР  
Дата: 05.10.15 01:08
Оценка:
Здравствуйте, Sni4ok, Вы писали:

10^9 это 10 в 9 степени те 1 000 000 000 и масcив шагов может быть 1 000 000 000 и гусинец 15
Отредактировано 05.10.2015 1:25 sergey2b . Предыдущая версия . Еще …
Отредактировано 05.10.2015 1:20 sergey2b . Предыдущая версия .
Re[3]: Голодные гусеницы
От: Sni4ok  
Дата: 05.10.15 01:25
Оценка: -1
Здравствуйте, sergey2b, Вы писали:

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


и что? минутки за 3 просчитает невижу тут причин для оптимизации преждевременной)
Re[4]: Голодные гусеницы
От: sergey2b ЮАР  
Дата: 05.10.15 01:34
Оценка: :)
Здравствуйте, Sni4ok, Вы писали:


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


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


вас здесь некто за язык не тянул — а реальная разработка это когда гуи формочки и простенькие sql запросики?
Re[5]: Голодные гусеницы
От: Sni4ok  
Дата: 05.10.15 01:46
Оценка:
Здравствуйте, sergey2b, Вы писали:

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


вы приписываете какие-то воображаемые требования к задаче(например по использованию cpu), которых небыло изначально?
Re[6]: Голодные гусеницы
От: sergey2b ЮАР  
Дата: 05.10.15 01:50
Оценка:
Здравствуйте, Sni4ok, Вы писали:


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


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


решение в лоб я сделал от безысходности это незачет
до кое какой оптимизации я додумался но сказали это недостаточно
Re[2]: Голодные гусеницы
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 05.10.15 02:17
Оценка:
Здравствуйте, Sni4ok, Вы писали:

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

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

Потому как с точки зрения hackerrun – ты задачу не решил. Задачи там алгоритмические и O(n) за верный ответ там обычно не считается.
Re: Вопрос.
От: Serg27  
Дата: 05.10.15 05:01
Оценка:
Здравствуйте, sergey2b, Вы писали:

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

Не люблю, когда ради оживляжа берут математическую проблему и начинают накручивать вокруг нее какую-то "историю". Тем кому интересна математика это не надо, кому математика не интересна все равно читать не будут. А иногда получается вот такая же чушь...
Отредактировано 05.10.2015 5:09 Serg27 . Предыдущая версия .
Re[4]: Голодные гусеницы
От: Don Reba Канада https://stackoverflow.com/users/49329/don-reba
Дата: 05.10.15 05:08
Оценка:
Здравствуйте, Sni4ok, Вы писали:

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


Гусеницы всё равно медленнее прыгают, как бы голодны они ни были.
Ce n'est que pour vous dire ce que je vous dis.
Re[2]: Вопрос.
От: sergey2b ЮАР  
Дата: 05.10.15 05:17
Оценка:
Здравствуйте, Serg27, Вы писали:

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


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


я задал аналогичный вопрос (к сожаллению не сохранил пояснений)
если она попала на уже съеденный лист тут же переходит к следующему
Re[3]: Вопрос.
От: Serg27  
Дата: 05.10.15 05:32
Оценка:
Здравствуйте, sergey2b, Вы писали:

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

S>если она попала на уже съеденный лист тут же переходит к следующему

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

Ну и так до бесконечности...
Re[4]: Вопрос.
От: sergey2b ЮАР  
Дата: 05.10.15 06:11
Оценка:
Здравствуйте, Serg27, Вы писали:

нет все гусеницы идут до посленего листа в списке и потом на другое дерево
Re[2]: Голодные гусеницы
От: T4r4sB Россия  
Дата: 05.10.15 08:00
Оценка:
Здравствуйте, Sni4ok, Вы писали:

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

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

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


А мне по условию показалось, что листья с нуля нумеруются.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re: Голодные гусеницы
От: _DAle_ Беларусь  
Дата: 05.10.15 08:25
Оценка: +2
Здравствуйте, 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
Re[3]: Голодные гусеницы
От: _DAle_ Беларусь  
Дата: 05.10.15 08:40
Оценка:
Здравствуйте, kaa.python, Вы писали:

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


Hackerrank? Или есть еще какой-то hackerrun?
Re[4]: Голодные гусеницы
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 05.10.15 08:53
Оценка:
Здравствуйте, _DAle_, Вы писали:

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


Нету, конечно, речь о Hackerrank.
Re: Голодные гусеницы
От: VTT http://vtt.to
Дата: 05.10.15 11:51
Оценка:
Тут вроде сводится к нахождению взаимно съеденных листьев, т.е. таких, которые могла бы съесть данная гусеница, но которые были съедены до нее другой.
Например: если сначала была гусеница с шагом 4, а затем с шагом 6, то на ее пути будут съедены листья с индексами, кратными 12.
Это количество можно найти как (всего листьев / НОК (шаг пред, шаг)).
НОК можно посчитать зная НОД.
НОД, в свою очередь, можно посчитать по алгоритму Евклида, который описан у Кнута в 4.5.2.
Для каждой следующей гусеницы надо учитывать съеденное всеми предыдущими.
Говорить дальше не было нужды. Как и все космонавты, капитан Нортон не испытывал особого доверия к явлениям, внешне слишком заманчивым.
Re[2]: Голодные гусеницы
От: sergey2b ЮАР  
Дата: 05.10.15 13:44
Оценка:
Здравствуйте, _DAle_, Вы писали:


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


накодировать собеседование в Блумбрег
Re[3]: Голодные гусеницы
От: _DAle_ Беларусь  
Дата: 05.10.15 14:22
Оценка: +1
Здравствуйте, sergey2b, Вы писали:
_DA>>Это за 15 минут надо было накодировать что ли? Или придумать решение?

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


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

А как решать задачу понятно стало?
Re[4]: Вопрос.
От: sergey2b ЮАР  
Дата: 05.10.15 16:45
Оценка:
Здравствуйте, Serg27, Вы писали:

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


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

S>>если она попала на уже съеденный лист тут же переходит к следующему

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


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


нет гучиница не может умереть по дороге она дойдет до конца всех листьев и перейдет на другое дерево (я вообще не знаю зачем они стали про гусинец говорить а не дали формальную задачу)
Re: Голодные гусеницы
От: Кодт Россия  
Дата: 05.10.15 17:47
Оценка:
Здравствуйте, 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 — выгоднее брутфорсом.
Перекуём баги на фичи!
Re[3]: Голодные гусеницы
От: Sni4ok  
Дата: 06.10.15 11:04
Оценка:
Здравствуйте, 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;
}
Re[2]: Голодные гусеницы
От: Буравчик Россия  
Дата: 06.10.15 18:54
Оценка: 9 (2)
Здравствуйте, _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 * (2K) * (log N), а вернее даже
K * (2K) * (log (max Ai))

P.S. variants написан с помощью монад — элегантно, но непонятно.
Более понятно, но длиннее будет как-то так:
variants [] = [[]]
variants (x:xs) = 
  let vs = variants xs 
  in map (x:) vs ++ vs
Best regards, Буравчик
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.