Войти
ФлеймФорумПрограммирование

Не смог решить тестовое задание

Страницы: 1 2 341 42 Следующая »
#0
(Правка: 21:10) 21:09, 3 янв. 2020

Задание ниже в спойлере. Я в переписке с HR'ом ответил, что не могу представить себе алгоритм, который может за один вызов 'dispatch()' решить поставленную задачу меньше чем за O(n^2). Попросил у них решение. В ответ получил 'Если вы не смогли ее решить, то действительно не прошли проверку. '. Подскажите решение, пожалуйста.

+ Показать

#1
(Правка: 21:46) 21:36, 3 янв. 2020

Алмаз
игл дайнамикс? У них hr не  читает что ты ему пишешь даже когда он сам тебе первый пишет.

Плюс задача в той форме что они всем кидают априори не решаемая, чисто с точки зрения некорректной постановки задачи, партиклы с радиусом = шары? Самозатенение без рассеивания вообще зачем? Если партикл - тело, то его затенение не может быть описано числом (если вы не в друке), типа, что делать в случае частичных перекрытий? Там даже не сказано можно ли юзать дополнительную память.  Задание писал идиот, который не понимает о чем вообще речь, не удивительно что у них вакансии на одни и теже должности уже второй год висят.



#2
21:49, 3 янв. 2020

vindast
Да, они самые. Частицы с радиусом тоже смутили. И по дополнительной памяти никакой инфы, да.

#3
(Правка: 21:57) 21:53, 3 янв. 2020

Задачу без каких либо дополнительных данных, кроме как поэлементным топорным обходом массива, не решить. А это совсем не оптимально. Но исходя из логики многопоточности это будет O(n^2/k). Точнее для отдельного потока просто O(n).

Видимо это просто задача на вшивость.

#4
21:57, 3 янв. 2020

Алмаз, самозатенение обычно считают рейкастом по 3д текстуре. Чекни вот этот пайпер https://developer.nvidia.com/sites/default/files/akamai/gamedev/d… cientPost.pdf

#5
21:59, 3 янв. 2020

vindast
Это простая задача на поиск пересечения проекций кругов на плоскости, а не реальный расчет освещения.

#6
22:15, 3 янв. 2020

foxes
> Это простая задача на поиск пересечения проекций кругов на плоскости, а не
> реальный расчет освещения.
Очевидно.

#7
22:23, 3 янв. 2020

vindast
Я в курсе, что такое самозатенение и пейпер я этот читал, спасибо.

foxes
По задаче требование "оптимальный по быстродействию". O(n^2) на один поток - это не оптимальное решение.

#8
22:27, 3 янв. 2020

У меня дежавю, или эту задачу уже обсуждали на геймдев.ру?

#9
(Правка: 22:31) 22:30, 3 янв. 2020

MrShoor
Ссылку)

Алмаз
> foxes
> По задаче требование "оптимальный по быстродействию". O(n^2) на один поток -
> это не оптимальное решение.


+1

#10
22:31, 3 янв. 2020

vindast
Может им и не очень люди нужны. Темболее графику писать. Обычно графических программистов 1% от команды. Работал на проекте, где было всего 2 программиста графики. Остальных было ~200. Да и джунов пасти неохота. Даже мидлов пасти неохота.

#11
22:31, 3 янв. 2020

MrShoor
Не помнишь решения или название темы?

#12
22:37, 3 янв. 2020

vindast
> Ссылку)

Алмаз
> Не помнишь решения или название темы?

Сорян, это задание было в телеграммовском чатике, а не на этом ресурсе. :)

#13
(Правка: 22:39) 22:37, 3 янв. 2020

Алмаз
vindast
> O(n^2) на один поток - это не оптимальное решение.
Задача O(n^2) раскладывается на один поток как O(n), я уже об этом упомянул выше.

#14
(Правка: 22:41) 22:41, 3 янв. 2020

foxes
> Задача O(n^2) раскладывается на один поток как O(n), я уже об этом упомянул
> выше.
Камон, время все еще квадратное. Вспоминай как считать нотацию О большое )

Страницы: 1 2 341 42 Следующая »
ФлеймФорумПрограммирование