Решение первой задачи очень проста. Она основывается на запоминания всех отрезков и прибавление один раз за все отрезки. Объявим массив длиной N у которого все значении изначально будут нулями. При каждом получение L,R увеличиваем a[L] на единицу и уменьшаем a[R] на единицу. После объявим переменную cnt который будет равняться нулю Бежим по объявленному массиву и при каждом итерации i прибавляем в cnt=cnt + a[i] и в исходный массив прибавляем cnt то-есть nums[i] = nums[i] + cnt
@letburnit5017
4 ай бұрын
КРУТО!
@kdpdev
3 ай бұрын
один q=(L=0, R=0), т.е. в результате первому элементу должно добавить еденицу. a[ 0 ] += 1 a[ 0 ] -= 1 т.е. объявленный массив а с нулями, т.е. cnt=cnt + a[i] - не меняет cnt, т.е. cnt==0 всегда, т.е. nums[i] = nums[i] + cnt - добавляется 0, т.е ничего не происходит. Правильнее выглядит a[ L ] += 1 a[ R+1 ] -= 1 ну и массив а должен быть на еденицу больше или не уменьшать ничего, если индекс за границей массива
@user-yd6px3hj4v
Ай бұрын
@@kdpdevспасибо! теперь понятно!)
@forever_anton9916
Ай бұрын
@@kdpdev я, может быть, ошибаюсь, но у меня этот вариант не работает я бы сделал что-то такое a = [0, 0, 0, 0, 0, 0, 0, 0] # исходный список q = 3 # количество запросов temp_q = [(1,4), (0,2), (2,7)] # запросы для примера temp_res = [[0,0] for _ in range(len(a))] # сохраняем сюда списки [0,0] - количество l и r в зависимости от #индексов for i in range(q): # примерно исходное решение l = temp_q[i][0] r = temp_q[i][1] temp_res[l][0] += 1 temp_res[r][1] += 1 temp = 0 for i in range(len(temp_res)): # ну и вот так проходимся temp += temp_res[i][0] a[i] += temp temp -= temp_res[i][1] print(a)
@sb9185
10 ай бұрын
В каком месте они решают задачу? Как называется платформа ?
@koral7441
Ай бұрын
Кто-нибудь скажите какие названия у этих задач на литкоде.
@soulspirit8687
9 ай бұрын
на кой чёрт ему префиксная сумма
@umni_kot
Ай бұрын
описание задачи первой: "дайются" - пиздец
@mixedeep
8 ай бұрын
Снобизм Яндекса во всей красе)
@user-py1ih2mv5t
10 ай бұрын
объясните, пожалуйста, суть решения первой задачи через префиксные суммы, не совсем поняла логику решения.
@alexandroppolus
10 ай бұрын
Чел решил непонятно как. На самом деле надо просто создать массив разностей соседних элементов, и вот на нем уже выполнять запросы.
@vladpotapov8857
9 ай бұрын
@@alexandroppolus и тогда получим условные O(q + n) вместо O(q * n)?
@RED-zs4cq
9 ай бұрын
суть префиксных сумм в том, что n-ый элемент показывает сумму всех n-1 элементов до него; парень, увеличивая l-ый элемент в исходном массиве на 1, увеличивает префиксную сумму каждого последующего элемент после этого на 1, те если мы вычтем массив префиксных сумм для исходного массива из массива префиксных сумм для измененного (в котором на 1 увеличили), то получим массив, в котором до позиции l будут стоять 0, а после 1, тк разница последующих преф. сумм = 1 (пример разности: [0,0,1,1,1,1,1]) ; если этот массив (который получили разностью преф. сумм) сложить с исходным, то получим, что к каждому элементу после l прибавиться 1 ; но нам нужно чтобы 1 прибавлялась к каждому элементу от l до r; поэтому аналогично парень вычитает 1 из r+1-го элемента исходного массива, чтобы "скомпенсировать" изменение префиксной суммы после того как к l-му элементу исходного массива прибавили 1 ; следовательно опять же найдя разность получим массив с 0 до l-го элемента, с 1 от l-го до r-го, и опять нулями после r - го, т.е. как раз отрезок, который увеличили на 1 (получим примерно такую разность: [0,0,1,1,1,0,0]); допустим у нас был еще один запрос, часть отрезка увеличения на 1 которого совпадает с предыдущим, получим массив разностей по типу такого: [0,1,2,2,1,0,0]; после кучи запросов разность между исходной префиксной суммой и префиксной суммой изменяемого массива как раз покажет насколько надо увеличить соответствующий элемент исходного массива
@user-tj9ke9nr5j
10 ай бұрын
Может я туплю, но в чем смысл решения через префиксные суммы для первой задачи, если оно так же работает за n, как и наивное. Просто доп. память под массив префиксов тратим без оптимизации.
@bulatabzalov
10 ай бұрын
Наивное работает от n ** 2
@tiimuur
Ай бұрын
Наивное решение O(nq), его решение O(n+q)
@ai8952
10 ай бұрын
Держу в курсе, первая задача решена неверно: во-первых внизу должно быть не =, а +=, во-вторых прибавлять надо не изменение, а суммировать все изменения и прибавлять текущую сумму
@raphaelosipov867
4 ай бұрын
Кандидат явно знал первую задачу, но зашел с наивного, что и заметил интервьюер. Надо было заставить его доказать корректность этого решения, думаю он бы поплыл. Во второй задаче, кандидат долго думал об обратном проходе, хотя это намного проще первой задачи, странно. Кандидат часто делает помарки и грубые ошибки логические, и ошибки синтаксиса, как будто не пишет код, а списывает. Ну или спецом это делает:) Интервьюер не помучал его, как он пришел к этому решению и почему оно корректное, странно. Просто обрадовался, что чел знает задачу =/ Во второй задаче, с вопросом про цикл вообще подсказал, а было бы весеоо, если бы промолчал:) Если что, я несколько раз проходил собес, один раз даже онсайт в Я, все завалил так или иначе, но это еще не конец:) В целом, полезное классное видео, спасибо всем и спасибо за инсайты, особенный респект ведущему и немного интервьюеру:)
@user-sc9hv7vy4z
8 ай бұрын
Префиксными суммами всë усложнил. Достаточно одного массива с изменением слагаемого для текущего и последующих элементов. И доп. памяти в 2 раза меньше нужно, хотя и формально те же o(n).
@0xreset
7 ай бұрын
++, то что ты описал это первое что мне в голову пришло. Но все любят усложнять, плюс капелька (море) стресса)
@vsratosfera1235
10 ай бұрын
Не понятно на кого собес, это интерн или Джун?
@ift1hpalkoner666
10 ай бұрын
в яндексе алгоритмический собес одинаковый, что на стажера, что на синьера
@vsratosfera1235
10 ай бұрын
@@ift1hpalkoner666 алгосы на стажку идут час - полтора
@user-ps4or2xf5x
3 ай бұрын
какой смысл решать задачу через префиксную сумму, это не дает заметного выигрыша в оптимизации только усложняет логику
@forever_anton9916
Ай бұрын
дает, его решение выполняется за O(n+q) шагов, а первое - O(nq)
@boolitdd3416
8 ай бұрын
они всех насилуют алгоритмами, не первое видео где эта недоконтора сношает ими всех подряд без причины.
@user-kp7qh4yb6m
Ай бұрын
Это не Яндекс)
@umni_kot
Ай бұрын
@@user-kp7qh4yb6m в смысле? а что?
@user-kp7qh4yb6m
Ай бұрын
@@umni_kot поступашки Это тренировочный собес
@user-kp7qh4yb6m
Ай бұрын
@@umni_kot поступашки Это просто тренировочное
@umni_kot
Ай бұрын
@@user-kp7qh4yb6m так задачи такие в Яндексе. все одно и то же
@comparison9436
7 ай бұрын
Вторая задача намного проще первой. Вот доказательство того, что зубрить алгоритмы бесполезно. Первую решил, потому что раньше решал, вторую не решил, потому что не решал раньше и не умеет думать.
@comparison9436
7 ай бұрын
Никогда не учите так алгоритмы. Парень, не понимая почему увеличивает на 1 и уменьшает на 1, ответил просто да этот алгоритм будет работать на q запросов. Он просто зазубрил алгоритмы решения задач, не понимая сути решения. Я таких сразу валю на собеседовании, мне не нужны бездумные зубрильщики в команде, мне нужны олимпиадники с нестандартным мышлением.
@Greguar199
7 ай бұрын
Зачем вам олимпиадник в команде?
@comparison9436
7 ай бұрын
@@Greguar199 он любую задачи решит сам написав 2000 строк кода, если не сможет загуглить и найти решение. Еще и быстро это сделает
@KirillAubekerov
6 ай бұрын
@@Greguar199хочет лапшичный удон в проекте
@Viacha-wo3lb
6 ай бұрын
@@Greguar199потому что олимпиадники жёсткие типочки, а литкодеры казуалы
@niksard1
5 ай бұрын
Выступать на олимпиадах. Что за вопрос? 😂
@VaxoRulitAlamantera
10 ай бұрын
Яндекс такси, где адекватные цены? Набираете лучших прогеров России, но не можете сделать адекватные алгоритмы ценообразования поездки в небольших городах
@sovaz1997
8 ай бұрын
Так цены скорее всего максимально адекватные, если мы говорим про прибыль Яндекса))
@splcell
7 ай бұрын
Это лишний раз доказывают, что алгоритмы не нужны и там сидят не лучшие прогеры, а те, кто просто как обезьянка, надрессировался решать оторваные от реальности задачки
@sovaz1997
7 ай бұрын
@@splcell Что именно доказывает? Цена не должна быть хорошей для пассажиров. Она должна быть такой, чтобы Яндекс получил максимальную прибыль. И тут зависит далеко не только от одних разработчиков
@andreianuchin157
5 ай бұрын
у них адекватные алгоритмы) Я в Чите был ровно год назад, от гостиницы до места работы 1,8 км, на улице -41, ценник 580р. В Чите, если что, такси Максим популярнее, но у меня не было приложухи. Что делаю, прогуливаюсь до магазина на след. перекрестке, примерно 300м, забегаю в магаз, греюсь, покупаю водички, проверяю отсюда ценник, стал 128р. Да, уточню, использовал Яндекс карты, нажав маршрут и выбрав транспорт такси, тем самым алгоритм спарсил такси конкурента и за мной приехал таксист из Максим. Если что, сам учусь на бесплатных курсах по питону и машинному обучению для себя, алгоритмы и математика там, как основа. Повторяю, что для себя, работа в Яндексе мне нах не нужна, но я учу все алгоритмы, матрицы, теорию поля, топологию, статистику, теорию вероятности, теорему Байеса, квантовую механику из математики и физики, для того, чтобы научить машину "думать" теми же алгоритмами, а ей пох, сколько на улице мороза, человек ленив и предсказуем по сути, для него и ценник такой) А лучшие прогеры давно за бугор уехали)
@splcell
5 ай бұрын
@@andreianuchin157 у вас уже эти алгоритмы прямо как секта стали. Обычные люди говорят повезло или Бог послал, а у вас алгоритм спарсил. Ты наверное садишься обедать и благодаришь Великий Алгоритм, за то что спарсил тебе эту еду
@igorseledtsov7345
7 ай бұрын
Как я понял туда нанимают дегенератов? Ну смех и грех... Я бы понял если бы предложили реализрвать трансцедентное разложение или хотябы алгоритм вперёд-назад ну или что нибудь не сильно сложное. Но то что предлагают, это же для школьников, причём не сильно то усердных.
@postupashki_old
7 ай бұрын
обычно все смеются над уровнем задач, пока сами не попадут на собес)
@igorseledtsov7345
7 ай бұрын
@@postupashki_old если люди ходят на собес, то уже понятен их уровень.. Это нормально. Непонятно зачем им вообше деньги платить?
Пікірлер: 57