Программирование[11]

Grohuf написал 3 часа назад:

Если хочешь пример задачки, которую НИКТО не решил из тех, кого я собеседовал, то вот:

Имеем массив натуральных чисел от 1 до N. Числа идут в произвольном порядке. Из этого массива убрали 2 числа. Нужно найти эти два числа, не изменяя массив. Удачи решить 

эта по-проще задача

Ну, это рил математическая задача на Элазора.

У меня правда теперь вопрос, олимпиадники перестали в яндекс идти, чи шо?

ArzanisAncient написал 41 минуту назад:

Grohuf написал 1 час назад:

Ну я, когда даю эту задачу, обычно разрешаю модифицировать массив. Боюсь, в оригинальной трактовке ее никто не решил кроме челика ее предложившего (сейчас CTO одного из бизнесов яндекса)

 

Ну, крч.

Есть формула суммы квадратов чисел натурального ряда.
Есть формула сумма чисел натурального ряда.
Считаем первую и вторую какие доллжны быть и каие есть в массиве.

Дальше система:
x + y = N, где N - разница между ожидаемой и реальной суммой
x^2 + y^2 = M, где М - разница между ожидаемой и реальной суммой квадратов

Система сводится к квадратному уравнению, решить его за O(N) можно.

Бери в яндекс

Хмм, я уже не помню, почему возведение в квадрат было не самым лучшим решением. Это было очень давно.

Grohuf написал Только что:

ArzanisAncient написал 35 минут назад:

Grohuf написал 55 минут назад:

Ну я, когда даю эту задачу, обычно разрешаю модифицировать массив. Боюсь, в оригинальной трактовке ее никто не решил кроме челика ее предложившего (сейчас CTO одного из бизнесов яндекса)

 

Ну, крч.

Есть формула суммы квадратов чисел натурального ряда.
Есть формула сумма чисел натурального ряда.
Считаем первую и вторую какие доллжны быть и каие есть в массиве.

Дальше система:
x + y = N, где N - разница между ожидаемой и реальной суммой
x^2 + y^2 = M, где М - разница между ожидаемой и реальной суммой квадратов

Система сводится к квадратному уравнению, решить его за O(N) можно.

Бери в яндекс

Хмм, я уже не помню, почему возведение в квадрат было не самым лучшим решением.

Ну там изи пробиваешь лонг, но это "оптимизируется" вычислением кэфа квадратного уровнения на лету.
Другое дело что это все надо на листочке написать, чтобы увидеть сокращение кэфов и как разницы превращаются в кэф.

А хотя сама сумма квадратом пробьет тоже. Ну значит еще больше сокращений в формулах.

Ожидаемым решением было использование факта, что имея сумму двух чисел, можно найти среднее. И одно число будет больше среднего, а второе - меньше. Собственно, я эту задачу привел как раз как пример того, что писал Olololnet: "собственно, ознакомившись с ответом, я как-то нихуя не уверен, что до этого можно догадаться и реализовать за разумные сроки ни разу с подобным не столкнувшись." Догадаться, что, используя среднее от суммы двух чисел, можно разбить изначальный массив на два подмассива и свести задачу к поиску одного пропавшего числа (которая чрезвычайно проста), это очень не просто, не сталкиваясь раньше с подобными задачами.

Интересно а многие такую решат: дано N натуральных чисел, все числа имеют ровно 1 дубль кроме K чисел, которые в единственном экземпляре. Найти эти K чисел.

E1azor написал 10 минут назад:

Grohuf написал 3 часа назад:

Если хочешь пример задачки, которую НИКТО не решил из тех, кого я собеседовал, то вот:

Имеем массив натуральных чисел от 1 до N. Числа идут в произвольном порядке. Из этого массива убрали 2 числа. Нужно найти эти два числа, не изменяя массив. Удачи решить 

эта по-проще задача

Задача Olololnet просто на перебор действий, которые можно сделать с массивом. Хорошая задача на то, что человек сразу не сдается, когда первая идея оказалась не правильной, и думает до победного. Еще хорошая задача из той же серии - задача на закольцованный поезд с лампочками. Но она в интернете уже много где.

А кста, оба решения не O(1) по памяти, потому что сумма от 1 до N - не O(1). 

ArzanisAncient написал 5 минут назад:

А кста, оба решения не O(1) по памяти, потому что сумма от 1 до N - не O(1). 

 

Необязательно же сумму вычислять до конца, а только потом вычитать, можно вычитать из неё параллельно 

Вот крутая задача ещё: Найти сумму N чисел double

хотя вроде уже сюда её вбрасывал

ArzanisAncient написал 9 часов назад:

Взять произведение всех элементов, а при сборке делить на текущий?
O(2n)?

не бывает O(2n) тк это == O(n)

Пришел душитель

besteady написал 2 минуты назад:

ArzanisAncient написал 9 минут назад:

А кста, оба решения не O(1) по памяти, потому что сумма от 1 до N - не O(1). 

 

Необязательно же сумму вычислять до конца, а только потом вычитать, можно вычитать из неё параллельно 

В решении со средним не получится, там среднее от суммы потом сравнивается с каждым элементом.

В моем в теории можно, но чет не уверен, что получится. Кажется, даже от ЯП зависит.
Но мои полномочия тут всё. Пусть более шарящие скажут за это

Grohuf написал 4 часа назад:

Olololnet написал 4 часа назад:

Grohuf написал 4 часа назад:

Olololnet написал 9 часов назад:

собственно, ознакомившись с ответом, я как-то нихуя не уверен, что до этого можно догадаться и реализовать за разумные сроки ни разу с подобным не столкнувшись.

Ну отвлекшись на 5 минут от работы я без труда придумал решение.

так оно в посте написано, немного другая версия

Я его не заметил, поэтому 7891 пост написал.

Задача довольно простая, так как никаких особых алгоритмов не использует и не требует никаких знаний. Когда решаешь задачу, то обычно просто перебираешь имеющиеся у тебя инструменты и смотришь, можно ли этим инструментом решить задачу. Так как она ничего кроме умножения не требует, то решается довольно просто.

 

Если хочешь пример задачки, которую НИКТО не решил из тех, кого я собеседовал, то вот:

Имеем массив натуральных чисел от 1 до N. Числа идут в произвольном порядке. Из этого массива убрали 2 числа. Нужно найти эти два числа, не изменяя массив. Удачи решить 

 

так. а в чем проблема. то?

вариант номер раз

создаешь массив N

идешь по исходному, валуе элемента используешь как индекс второго - записываешь туда труе

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

вариант номер два - сортируешь и идешь пока не найдешь скачек (потенциально двойной, + учесть краевые когда число на границе)

так и хули тут решать?

Just.Doit написал 7 минут назад:

ArzanisAncient написал 9 часов назад:

Взять произведение всех элементов, а при сборке делить на текущий?
O(2n)?

не бывает O(2n) тк это == O(n)

 

X не существует потому что X=Y

ебать ты перегрелся

Grohuf написал 1 час назад:

Ну ограничения O(N) по времени и O(1) по памяти, думаю, очевидны

ебанько чтоли

очевидно что ограничений в исходной задаче нет

Дуит ща последовательно на каждый пост ответит не читая тему до конца. 

Чисто синхронный.

Just.Doit написал Только что:

Grohuf написал 4 часа назад:

Olololnet написал 4 часа назад:

Grohuf написал 4 часа назад:

Olololnet написал 9 часов назад:

собственно, ознакомившись с ответом, я как-то нихуя не уверен, что до этого можно догадаться и реализовать за разумные сроки ни разу с подобным не столкнувшись.

Ну отвлекшись на 5 минут от работы я без труда придумал решение.

так оно в посте написано, немного другая версия

Я его не заметил, поэтому 7891 пост написал.

Задача довольно простая, так как никаких особых алгоритмов не использует и не требует никаких знаний. Когда решаешь задачу, то обычно просто перебираешь имеющиеся у тебя инструменты и смотришь, можно ли этим инструментом решить задачу. Так как она ничего кроме умножения не требует, то решается довольно просто.

 

Если хочешь пример задачки, которую НИКТО не решил из тех, кого я собеседовал, то вот:

Имеем массив натуральных чисел от 1 до N. Числа идут в произвольном порядке. Из этого массива убрали 2 числа. Нужно найти эти два числа, не изменяя массив. Удачи решить 

 

так. а в чем проблема. то?

вариант номер раз

создаешь массив N

идешь по исходному, валуе элемента используешь как индекс второго - записываешь туда труе

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

 

вариант номер два - сортируешь и идешь пока не найдешь скачек (потенциально двойной, + учесть краевые когда число на границе)

 

так и хули тут решать?

ещё пузырёк предложил бы докучи, стыдоба ты луковая

@E1azor если у нас промежуточные вычислении пробивают типы, а конечные нет, в одной большой формуле, мы получим ошибку переполгения? От чего-то зависит мб?

Ток не ебашь в лицо, я сквель макака, мне можно.

ArzanisAncient написал 6 минут назад:

@E1azor если у нас промежуточные вычислении пробивают типы, а конечные нет, в одной большой формуле, мы получим ошибку переполгения? От чего-то зависит мб?

Ток не ебашь в лицо, я сквель макака, мне можно.

Если double то вроде пиздец будет, но можно уменьшить шанс пиздеца, если правильно суммировать

При сложении целых вроде проблем не должно быть (для unsigned int точно)

При умножении целых знаки теряются, так что переполнение портит результат.

ну можно найти разницу сумм и отношение произведений
тоесть найти сумму этих двух чисел и их произведение

а ну и дальше система двух уровнений x1 + x2 = A, x1*x2 = B
выражаем одно через другое и считаем

ArzanisAncient написал 1 час назад:

Есть формула суммы квадратов чисел натурального ряда.
Есть формула сумма чисел натурального ряда.

ты можешь без формулы за O(n) посчитать перебором

ArzanisAncient написал 1 час назад:

Система сводится к квадратному уравнению, решить его за O(N) можно.

за О(н) систему уравнений?

ты математику в школе проебал?

Grohuf написал 52 минуты назад:

И одно число будет больше среднего, а второе - меньше.

а дальше что?