Да, товарищи, в 4ой задаче проморгали ограничения по памяти. Но там можно просто отказаться от ввода матрицы, так как она по факту для решения не нужна. Алгоритм же тот же самый.
Кажется, что можно вообще без аллокаций. Понятно, что L - это транспонирование матрицы + reverse по каждой строке, R - реверс , а потом транспонирование. Транспонирование-это (n^2-n)/2 операций, реверс по каждой строчке - это n/2 × n операций. То есть сразу знаем количество операций, ну и просто выводим транспонирование и реверс. Да, будут ненужные операции, да, не самое оптимальное по количество операций, но зато О(1) памяти :)
Кажется, в решении третей задачи есть проблемы со временем. Сортировка слишком долгая из-за того, что сравнение двух векторов строк может занимать миллион операций.
подскажите, может я не понимаю насчет кода для четвертой задачи выходит так, что для матрицы [[1,2,3], [4,5,6], [7,8,9]] массив swapOperations будет иметь 6 подмассивов, и вроде бы правильно, за 6 операций мы повернем массив на 90 градусов, но почему в задаче вывод 3?
Там идеальный вариант где ты минимум операций используешь, но на самом деле главное чтобы меньше 7n^2. Более того, тебе памяти в принципе не хватит хранить матрицу при вводе ее, то есть ты можешь просто принять размер матрицы и направление поворота и просто вывести операции. Там же написано, что не обязательно минимально.
это просто не минимум, делай все как в решении, главное по памяти не пролететь, матрицу записывать не нужно, алгоритм аналогичный вне зависимости от матрицы
В тестовой задаче с ответом 3 данные [[0, 1, 0], [1, 0, 0], [4, 3, 0]], и соответственно есть частное решение с меньшим количеством свапов. Но наименьшее количество свапов не просят, так что и 6 - ок
В фейке я указал левый тг, имя и написал невероятную историю про организацию митинга против повышения цен в столовой в графе про ораганизационные навыки
@@ibcavid да уж, ну не расстраивайтесь, насколько я знаю, мест для стажи правда очень мало у них, вы молодец все равно)) посоветуйте , как готовиться к таким контестам? Может сможете подсказать ресурсы наподобие литкода, буду благодарен
@@SemyonMerchenko-rd5on спасибо ☺️. Я лично решаю на codeforces. Но я думаю решать там, чтобы подготовится может быть слишком время затратным. Наверное лучше решать с литкода. Вот первые 3 задачи с собеса это более-менее простые задачи в плане идеи решения, нужно просто суметь закодить относительно прямолинейный подход. Для этого должны подойти, easy или medium задачи с литкода. А еще в литкоде есть такая вещь как acceptance rate, если решать например easy задачи но с очень низким таким показателем, то скорее всего задачу закодить неприятно, как раз можно потренить этот скилл. 5 задача - более-менее стандартная задача на динамическое программировавание. Можете погуглить и найти стандартные задачи и их решения, потренить можно также на литкоде. 4 задача это ad-hoc задача, тоесть нет конкретной тематики, такие задачи самые неприятные, сложно подготовится. Не знаю что советовать. 6 задача- это на графы. Решайте на литкоде но нужно ознакомится с материалом соответствующим: хранение графа в виде списка смежности или таблтцы инцидентности, dfs, bfs, dijkstra’s algorithm. Это базовые необходимые знания.
![BOWKYLION - วิงวอน (ex-change) [Official MV]](http://i.ytimg.com/vi/cLdnZWDaO-w/mqdefault.jpg)
![Тестовый вопрос, на который все ответили неверно [Veritasium]](/img/n.gif)
Да, товарищи, в 4ой задаче проморгали ограничения по памяти. Но там можно просто отказаться от ввода матрицы, так как она по факту для решения не нужна. Алгоритм же тот же самый.
Кажется, что можно вообще без аллокаций.
Понятно, что L - это транспонирование матрицы + reverse по каждой строке, R - реверс , а потом транспонирование.
Транспонирование-это (n^2-n)/2 операций, реверс по каждой строчке - это n/2 × n операций. То есть сразу знаем количество операций, ну и просто выводим транспонирование и реверс. Да, будут ненужные операции, да, не самое оптимальное по количество операций, но зато О(1) памяти :)
ребят, осенняя стажа, ждем решения, браткииии
Вот это золото, а не видео!
Святой человек
А будет на осеннюю стажу разбор по проге?
в первой можно дпшкой решить, а потом взять максимум из того, что получилось
Кажется, в решении третей задачи есть проблемы со временем. Сортировка слишком долгая из-за того, что сравнение двух векторов строк может занимать миллион операций.
Спасибо за ролик!
Требуем видос про Safeboard)
Скоро будет
подскажите, может я не понимаю насчет кода для четвертой задачи
выходит так, что для матрицы [[1,2,3], [4,5,6], [7,8,9]] массив swapOperations будет иметь 6 подмассивов, и вроде бы правильно, за 6 операций мы повернем массив на 90 градусов, но почему в задаче вывод 3?
Там идеальный вариант где ты минимум операций используешь, но на самом деле главное чтобы меньше 7n^2. Более того, тебе памяти в принципе не хватит хранить матрицу при вводе ее, то есть ты можешь просто принять размер матрицы и направление поворота и просто вывести операции. Там же написано, что не обязательно минимально.
это просто не минимум, делай все как в решении, главное по памяти не пролететь, матрицу записывать не нужно, алгоритм аналогичный вне зависимости от матрицы
В тестовой задаче с ответом 3 данные [[0, 1, 0], [1, 0, 0], [4, 3, 0]], и соответственно есть частное решение с меньшим количеством свапов. Но наименьшее количество свапов не просят, так что и 6 - ок
А зачем в 3ей задаче рут переименовывать, он же и так всегда первый у всех путей
чтобы ascii код меньше был. Для сортировки нужно
@@ift1hpalkoner666 у меня без переименовывания все работает
@@ift1hpalkoner666 Так у них у всех префикс одинаковый, сортировать будет с учетом того, что идет только после него
@@Эльф-п9р так если рут пустой то должны его в первую очередь выводить, чек первый пример
@@МаксимДудко-г5г "гарантируется, что первая директория во всех путях одинаковая и имеет непустое имя"
Я с фейка набрал больше очков, чем с оригинала. Что делать?
В фейке я указал левый тг, имя и написал невероятную историю про организацию митинга против повышения цен в столовой в графе про ораганизационные навыки
Менять паспорт
Точно такие же решения, вышло 550 баллов. Интересно сколько набрал автор видео
Вы прошли?
@@SemyonMerchenko-rd5on Нет(, судя по всему анкета сильно решает, либо же 600 балльников много было ( что врядли)
@@ibcavid да уж, ну не расстраивайтесь, насколько я знаю, мест для стажи правда очень мало у них, вы молодец все равно)) посоветуйте , как готовиться к таким контестам? Может сможете подсказать ресурсы наподобие литкода, буду благодарен
@@SemyonMerchenko-rd5on спасибо ☺️.
Я лично решаю на codeforces. Но я думаю решать там, чтобы подготовится может быть слишком время затратным. Наверное лучше решать с литкода.
Вот первые 3 задачи с собеса это более-менее простые задачи в плане идеи решения, нужно просто суметь закодить относительно прямолинейный подход. Для этого должны подойти, easy или medium задачи с литкода. А еще в литкоде есть такая вещь как acceptance rate, если решать например easy задачи но с очень низким таким показателем, то скорее всего задачу закодить неприятно, как раз можно потренить этот скилл.
5 задача - более-менее стандартная задача на динамическое программировавание. Можете погуглить и найти стандартные задачи и их решения, потренить можно также на литкоде.
4 задача это ad-hoc задача, тоесть нет конкретной тематики, такие задачи самые неприятные, сложно подготовится. Не знаю что советовать.
6 задача- это на графы. Решайте на литкоде но нужно ознакомится с материалом соответствующим: хранение графа в виде списка смежности или таблтцы инцидентности, dfs, bfs, dijkstra’s algorithm. Это базовые необходимые знания.
@@SemyonMerchenko-rd5on Почему не подходит литкод?