Здравствуйте, Буравчик, Вы писали: Б>Данная задача аналогична задаче топологической сортировки. Б>Решается с помощью поиска в глубину (DFS) за O(N).
Интересно! А если не секрет, сколько времени ушло на решение с такой ассимптоматикой? Просто по формулировке и ограничению эта задача решается максимум за 15 минут. Там же прямо после прочтения жадный алгоритм напрашивается. Отсортировали по рейтингу а дальше даем конфетки по минимуму (смотрим только на соседних). Это O(N*log(N)), в time limit укладывается с запасом. А на дальнейшие раздумия смысла время тратить нет. Я вижу, что ваше решение тоже пишется прекрасно за 10 минут. Поэтому и интересно, насколько сразу вы его нашли
Мое решение ниже. 12 минут, считая от момента когда я пошел открывать sbt в проекте до accepted, я еще с отладкой сильно локально тормозил (невнимательность в формулах) на олимпиаде со всем готовым минут 10 было бы.
Решение
import java.io._
object Solution {
def main(args: Array[String]): Unit = {
val s = new java.util.Scanner(System.in)
//val printWriter = System.out
val printWriter = new PrintWriter(sys.env("OUTPUT_PATH"))
val iarr = Array.fill(s.nextInt) { s.nextInt }
val arr = (Integer.MAX_VALUE +: iarr) :+ Integer.MAX_VALUE
val idx = Array.tabulate(iarr.length) {x => x + 1 }
val c = new Array[Int](arr.length)
val poses = idx.sortBy(x => arr(x))
var res = 0L
for {
pos <- poses
} {
var w = 1
if (arr(pos) > arr(pos-1))
w = Math.max(w, c(pos-1) + 1)
if (arr(pos) > arr(pos+1))
w = Math.max(w, c(pos+1) + 1)
c(pos) = w
res += w
}
//printWriter.println(res)
printWriter.close()
}
}
Здравствуйте, e.thrash, Вы писали:
ET>у меня несколько вопросов.
ET>Дало ли в жизни выхлоп время потраченное на алгоритмы в таком объеме по сравнению со обычным программистом? т.е. работа в штатах например в хорошей компании, зп выше рынка?
Работа в Европе (не хочу в штаты), зарплата выше/топ рынка в моем месте. Задачи в олимпиадном стиле я уже не помню когда при приеме на работу давали. Одно тестовое задание на дом несколько лет назад я точно из-за алгоритмов зававлил. Написал оптимальное олимпиадное решение, а от меня очень хотели идеоматическую Scala. А кроме этого что-то измерить сложно. Развитие мозга и алгоритмы связаны, но не понятно, кто из них — причина, а кто — следствие.
Еще иногда алгоритмы в работе используются. Например, написать топологическую сортировку вместо "неограниченного рекурсивного спуска" (и нормально вывести обнаруженный цикл, а то многие фреймворки выводят "не смогла я, ищите сами где цикл начинается")
ET>Как форму держите?
Никак. Для меня алгоритмы уже не очень актуальны (больше по архитектуре и культуре вопросы). Плюс типичные задачи на собеседованиях из "простых" олимпиадных. Т.е. те алгоритмы, которые оттренированы много много раз. Хотябы потому, что если не все олимпиадники решают более сложные задачи, то чего ждать от простого человека?
ET>Как лучше решать задачи? сначала изучить базовые алгоритмы поверхностно хотя бы, чтобы triage делать или брать задачу и там смотреть уже?
Для triage полезно знать какие есть алгоритмы и их ассимптоматику. Еще очень полезно знать "конкретику" по константам. Например, в мое время O(NlogN) проходило на размерностях порядка миллиона. Т.е. если задача сводилась к сортировке миллиона чисел — это можно было делать. А вот пять миллионов уже не сортировались (не хватало времени), обычно нужно было линейное решение.
Без знания ассортимента алгоритмов на некоторые задачи можно смотреть очень долго . Так что полезно _поверхностно_ изучить какой-нибудь учебник. Т.е. какие задачи решаются, какая ассимптоматика, описывает она худший или средний случай, сколько требуется памяти. После этого — можно смотреть на задачи и пытаться найти алгоритм. Когда нашли (т.е. свели вашу задачу к известной) — можно писать по учебнику, адаптировать известный код. Так будет более интересно, чем читать учебник подряд.
Но здесь есть одна подстава. Не все алгоритмы в учебнике — алгоритмы. Большинство — решают конкретную задачу (поиск путей в графе, выпуклой оболочки и т.п.). Но при этом есть веселые главы, описывающие классы алгоритмов. Как минимум, это жадные алгортимы и динамическое программирование. У них есть "идея" решения. И все. Нет канонической формы задачи. Нет классического кода. Только идея. Вот задачи из этих классов нужно решать. Тогда с практикой станет легче классифицировать задачи под эти алгоритмы.
Здравствуйте, e.thrash, Вы писали: ET>по результатам не проходит на большом наборе. а там задача еще не так просто найти на каком шаге ошибке ET>задача
Данная задача аналогична задаче топологической сортировки.
Решается с помощью поиска в глубину (DFS) за O(N).
Решение
def candies(n, arr):
count = [None] * len(arr)
# we use Depth-first search
stack = list(range(len(arr)))
while len(stack) > 0:
i = stack[-1]
# out of array or already knownif i < 0 or i >= len(arr) or count[i] is not None:
stack.pop()
# left unknown valueelif i >= 1 and arr[i] > arr[i-1] and count[i-1] is None:
stack.append(i-1)
# right unknown valueelif i < len(arr) - 1 and arr[i] > arr[i+1] and count[i+1] is None:
stack.append(i+1)
# we know left and right valueelse:
left = count[i-1] if i >= 1 and arr[i] > arr[i-1] else 0
right = count[i+1] if i < len(arr) - 1 and arr[i] > arr[i+1] else 0
count[i] = max(left, right) + 1
stack.pop()
return sum(count)
Здравствуйте, e.thrash, Вы писали:
ET>зы. а как искать нужный алгоритм для неизвестной для себя задачи?
Так это знать, т.е. понимать к какому классу задач данная задача относится. Хотя еще важнее знать
основные алгоритмы и уже исходя из этих знаний прикидывать как штурмовать задачу.
Здравствуйте, Pzz, Вы писали:
Pzz>Да, согласен. Ну значит, надо выделять локальные экстремуму (минимуми и максимуми), и двигаться от минимумов к соседним экстримумам или краям массива, двигаясь только по возрастанию.
Pzz>В принципе, можно и не двигаться никуда вовсе, а только длинну диапазона возрастания/убывания подсчитывать. Это можно сделать в один проход, заодно с поиском экстримумов, но алгоритм более путанный получится; можно погрязнуть в деталях.
я именно так и сделал за один проход, но детали и в итоге каждый кейс новый иф.
ок. спасибо за наводку про минимумы
Pzz>Два прохода — это тоже O(n). Любое константное количество проходов — это O(n). Вот если бы количество проходов зависило от n, было бы не O(n)
офигеть, прям открытие.
т.е. массив в 100К элементов если 10 раз прогнать тоже будет O(n)??
решаю задачи на хакерранке. на простых данных все проходит, на больших наборах данных не проходит.
Как найти что не так?
я правильно понимаю тут нет простого решения, может тестами как-то можно найти косяк в алгоритме?
Здравствуйте, e.thrash, Вы писали:
ET>Привет
ET>решаю задачи на хакерранке. на простых данных все проходит, на больших наборах данных не проходит. ET>Как найти что не так? ET>я правильно понимаю тут нет простого решения, может тестами как-то можно найти косяк в алгоритме?
Не проходит с неверным результатом или по лимиту времени? Во втором случае надо научится считать сложность алгоритма и находить решения с необходимо сложностью.
Здравствуйте, Dziman, Вы писали:
D>Здравствуйте, e.thrash, Вы писали:
ET>>Привет
ET>>решаю задачи на хакерранке. на простых данных все проходит, на больших наборах данных не проходит. ET>>Как найти что не так? ET>>я правильно понимаю тут нет простого решения, может тестами как-то можно найти косяк в алгоритме? D>Не проходит с неверным результатом или по лимиту времени? Во втором случае надо научится считать сложность алгоритма и находить решения с необходимо сложностью.
по результатам не проходит на большом наборе. а там задача еще не так просто найти на каком шаге ошибке задача
по таймату все прошли.
зы. а как искать нужный алгоритм для неизвестной для себя задачи?
Здравствуйте, e.thrash, Вы писали:
ET>решаю задачи на хакерранке. на простых данных все проходит, на больших наборах данных не проходит. ET>Как найти что не так? ET>я правильно понимаю тут нет простого решения, может тестами как-то можно найти косяк в алгоритме?
Я решал итеративно: сначала простенькие тесты на всякие случае до сабмита, если результат
сабмита дает ошибку в логике, то они данные предоставляют и пишете уже новый тест с этими данными,
т.е. чтобы и старые не упали (одно лечим, другое калечим).
Здравствуйте, e.thrash, Вы писали:
ET>зы. а как искать нужный алгоритм для неизвестной для себя задачи?
Да, сводить к известным задачам, для которых уже есть решение. У Стивена Скиена есть отличная книжка про алгоритмы, где подробно разбирается такой подход.
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, e.thrash, Вы писали:
ET>>зы. а как искать нужный алгоритм для неизвестной для себя задачи?
Pzz>Ну видимо, путем творческого сведения его к решению известных тебе задач.
Pzz>В данном случае мне на ум приходят такие слова, как "локальный минимум", и "диапазон монотонного возрастания".
у меня 5 кейсов проходят, остальные падают не по таймауту а по логике, но на большом объеме данных это как иголку искать в стоге
Здравствуйте, e.thrash, Вы писали:
Pzz>>В данном случае мне на ум приходят такие слова, как "локальный минимум", и "диапазон монотонного возрастания".
ET>у меня 5 кейсов проходят, остальные падают не по таймауту а по логике, но на большом объеме данных это как иголку искать в стоге
Тесты, это круто, конечно, но у тебя должно быть какое-то логическое обоснование, почему твой алкогоритм работает. Оно у тебя есть?
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, e.thrash, Вы писали:
Pzz>>>В данном случае мне на ум приходят такие слова, как "локальный минимум", и "диапазон монотонного возрастания".
ET>>у меня 5 кейсов проходят, остальные падают не по таймауту а по логике, но на большом объеме данных это как иголку искать в стоге
Pzz>Тесты, это круто, конечно, но у тебя должно быть какое-то логическое обоснование, почему твой алкогоритм работает. Оно у тебя есть?
потому что конкретно в этой задаче как мне кажется конечное число автоматов
1 рост всегда
2 падение всегда
3 рост — падение
4 падение падение (4 3 2 4 3 2)
5 рост рост (2 3 4 2 3 4)
6 все цифры одинаковы
и дальше вставляем пункт 6 в кейсы 1-5 вначале в середине и в конце
сейчас понял что наверное надо все эти кейсы подготовить и прогнать, а я где-то половину прогнал
Здравствуйте, e.thrash, Вы писали:
ET>сейчас понял что наверное надо все эти кейсы подготовить и прогнать, а я где-то половину прогнал
Мне навскидку кажется, что надо дать по одной конфетке каждому ребенку, у который находится на локальном минимуме или на плато, а дальше двигаясь от тех, кто на локальном минимуме, давать на одну конфетку больше каждому его соседу по возрастанию.
Все это должно делаться за время O(n), потому что локальные минимумы находятся за O(n), а общая длинна повторных проходов не превышает длинну масива, и требовать памяти O(1).
При этом надо быть аккуратным на краях массива, потому что там соседи есть не со всех сторон.
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, e.thrash, Вы писали:
ET>>сейчас понял что наверное надо все эти кейсы подготовить и прогнать, а я где-то половину прогнал
Pzz>Мне навскидку кажется, что надо дать по одной конфетке каждому ребенку, у который находится на локальном минимуме или на плато, а дальше двигаясь от тех, кто на локальном минимуме, давать на одну конфетку больше каждому его соседу по возрастанию.
если я правильно понял задачу то эта логика не будет работать на кейсе 4 3 2 4 3 2
первая двойка локальный минимум, а резульат должен быть 3 2 1 3 2 1
Pzz>Все это должно делаться за время O(n), потому что локальные минимумы находятся за O(n), а общая длинна повторных проходов не превышает длинну масива, и требовать памяти O(1).
а O(n) это разве не один проход массива?
насколько я понял тут за первый проход мы находим минимумы, а на втором уже конфетки раздаем
Здравствуйте, e.thrash, Вы писали:
ET>если я правильно понял задачу то эта логика не будет работать на кейсе ET>4 3 2 4 3 2
ET>первая двойка локальный минимум, а резульат должен быть 3 2 1 3 2 1
Да, согласен. Ну значит, надо выделять локальные экстремуму (минимуми и максимуми), и двигаться от минимумов к соседним экстримумам или краям массива, двигаясь только по возрастанию.
В принципе, можно и не двигаться никуда вовсе, а только длинну диапазона возрастания/убывания подсчитывать. Это можно сделать в один проход, заодно с поиском экстримумов, но алгоритм более путанный получится; можно погрязнуть в деталях.
Pzz>>Все это должно делаться за время O(n), потому что локальные минимумы находятся за O(n), а общая длинна повторных проходов не превышает длинну масива, и требовать памяти O(1).
ET>а O(n) это разве не один проход массива? ET>насколько я понял тут за первый проход мы находим минимумы, а на втором уже конфетки раздаем
Два прохода — это тоже O(n). Любое константное количество проходов — это O(n). Вот если бы количество проходов зависило от n, было бы не O(n)
Здравствуйте, e.thrash, Вы писали:
ET>у меня 5 кейсов проходят, остальные падают не по таймауту а по логике, но на большом объеме данных это как иголку искать в стоге
Они же выдают желаемое число, соотв. можно поставить условный брейкопоинт где-нибудь и посмотреть что происходит.
Здравствуйте, e.thrash, Вы писали:
ET>Как найти что не так?
Перебором и зависит от алгоритма. Вариантов не слишком много:
Граничные условия алгоритма
Граничные и особые случаи задачи (когда ввод/вывод хитрый)
"Случайный" ввод (сравнение с другим, заведомо работающим алгоритмом)
Проговорить алогритм вслух. Можно рассказать другу.
Есть еще особые классы задач (на хакерранке пока не видел) на "посчитать floating point с минимальной потерей точности". Там для алгоритмов желательно уметь оценивать потецниальные погрешности математики.
Есть и хардкорные методы "посмотреть на тесты" (не точно, дает только качественную оценку "есть или нет какое-то явление") путем side channel. У нас же есть разные результаты запуска теста — time limit, wrong answer, crash и т.п. Поэтому можно вычислять свои предикаты на входных условиях и падать (или не падать) с соответствующей ошибкой. Но это тактика на случаи, когда заняться совсем нечем.
ET>я правильно понимаю тут нет простого решения, может тестами как-то можно найти косяк в алгоритме?
Вот как раз на хакерранке есть простое решение! Там же можно посмотреть на падающий тест за hackos. Потом скопировать и протестировать алгоритм на этом входе.
Здравствуйте, maxkar, Вы писали:
M>Интересно! А если не секрет, сколько времени ушло на решение с такой ассимптоматикой? Просто по формулировке и ограничению эта задача решается максимум за 15 минут. Там же прямо после прочтения жадный алгоритм напрашивается. Отсортировали по рейтингу а дальше даем конфетки по минимуму (смотрим только на соседних). Это O(N*log(N)), в time limit укладывается с запасом. А на дальнейшие раздумия смысла время тратить нет. Я вижу, что ваше решение тоже пишется прекрасно за 10 минут. Поэтому и интересно, насколько сразу вы его нашли
Трудно оценить время, потому что я не сделал задачу за один подход. В первом подходе я попробовал сделать через сортировку, но ошибся — вместо "дальше даем конфетки по минимуму" индивидуально, я давал одинаковое количество конфет всем ученикам, имеющим одинаковый рейтинг. Отложил. Позже, в фоновом режиме, осознал, что надо давать всем индивидуально. А после этого появился алгоритм с DFS.
Я не использовал IDE (а надо было бы!). В первый раз потратил минут 30, но так и не решил, во второй потратил минут 20. Плюс время на раздумья в фоне — не сильно много, но не знаю как оценить
M>Мое решение ниже. 12 минут, считая от момента когда я пошел открывать sbt в проекте до accepted, я еще с отладкой сильно локально тормозил (невнимательность в формулах) на олимпиаде со всем готовым минут 10 было бы.
Круто, имхо это очень быстро. У меня сильно больше
ET>>я правильно понимаю тут нет простого решения, может тестами как-то можно найти косяк в алгоритме?
M>Вот как раз на хакерранке есть простое решение! Там же можно посмотреть на падающий тест за hackos. Потом скопировать и протестировать алгоритм на этом входе.
так если набор данных большой и падает не по таймауту сложно понять что не так в конкретно данной задаче
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, e.thrash, Вы писали:
ET>>так если набор данных большой и падает не по таймауту сложно понять что не так в конкретно данной задаче
Б>Конкретно в твоем случае можно сравнить результаты твоего алгоритма и результаты заведомо правильного.
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, e.thrash, Вы писали:
ET>>по результатам не проходит на большом наборе. а там задача еще не так просто найти на каком шаге ошибке ET>>задача
Б>Данная задача аналогична задаче топологической сортировки. Б>Решается с помощью поиска в глубину (DFS) за O(N).
Здравствуйте, maxkar, Вы писали: M>Здравствуйте, Буравчик, Вы писали:
то ли я скалу плохо знаю, то ли алгоритм не понял ваш.
на таком наборе 3 1 здесь
возвращается 3, а надо 2
код ваш не менял, выделил что поменял M>
Решение
M>
import java.io._
object Solution {
def main(args: Array[String]): Unit = {
val s = new java.util.Scanner(System.in)
val iarr = Array.fill(2) { s.nextInt }
val arr = (Integer.MAX_VALUE +: iarr) :+ Integer.MAX_VALUE
val idx = Array.tabulate(iarr.length) {x => x + 1 }
val c = new Array[Int](arr.length)
val poses = idx.sortBy(x => arr(x))
var res = 0L
for {
pos <- poses
} {
var w = 1
if (arr(pos) > arr(pos-1))
w = Math.max(w, c(pos-1) + 1)
if (arr(pos) > arr(pos+1))
w = Math.max(w, c(pos+1) + 1)
c(pos) = w
res += w
}
print(res)
}
}
M>
Здравствуйте, e.thrash, Вы писали:
ET>возвращается 3, а надо 2
Стоп! Откуда 2?
Два дитя. Каждое должно получить хотя бы по одной конфетке. Причем первое (рейтинг 3) должно получить больше, чем второе (рейтинг 1). Т.е. распределение [2, 1]. И сумма (минимальное количество конфет для покупки) — 3.
Или в коде что-то смущает? Array.fill вычисляет вторую группу аргументов (то, что в фигурных скобках) для каждого элемента. Дальше идет борьба с граничными условиями. Простым приписыванием слева/справа (по ним итераций нет). Дальше детей сортируем по их рейтингу. Точнее, индексы детей. Добавленные элементы ("вне" исходных данных) не берем (поэтому и индексы в idx начинаются с единицы а не с нуля). А дальше — перебираем детей по рейтингу. Ну или индексы детей (которые отсортированы по рейтингу). Смотрим на соседей. Если рейтинг у кого-то ниже, мы его уже обработали (потому что сортировка!). А все остальные случаи — даем единичку. Ну и я сумму еще в том же цикле посчитал. Можно было sum сделать, но я код писал вечером и сильно тормозил. Поставил лишние скобки в вызове sum, подумал минуту, написал inline.
Здравствуйте, maxkar, Вы писали:
M>Здравствуйте, e.thrash, Вы писали:
ET>>возвращается 3, а надо 2
M>Стоп! Откуда 2? M>Два дитя. Каждое должно получить хотя бы по одной конфетке. Причем первое (рейтинг 3) должно получить больше, чем второе (рейтинг 1). Т.е. распределение [2, 1]. И сумма (минимальное количество конфет для покупки) — 3.
M>Или в коде что-то смущает? Array.fill вычисляет вторую группу аргументов (то, что в фигурных скобках) для каждого элемента. Дальше идет борьба с граничными условиями. Простым приписыванием слева/справа (по ним итераций нет). Дальше детей сортируем по их рейтингу. Точнее, индексы детей. Добавленные элементы ("вне" исходных данных) не берем (поэтому и индексы в idx начинаются с единицы а не с нуля). А дальше — перебираем детей по рейтингу. Ну или индексы детей (которые отсортированы по рейтингу). Смотрим на соседей. Если рейтинг у кого-то ниже, мы его уже обработали (потому что сортировка!). А все остальные случаи — даем единичку. Ну и я сумму еще в том же цикле посчитал. Можно было sum сделать, но я код писал вечером и сильно тормозил. Поставил лишние скобки в вызове sum, подумал минуту, написал inline.
Извиняйте, у вас всё верно.
Блин, настолько элегантное решение. Я неделю каждый день почти думал над задачей и кроме кучи ифов не было решений.
Как выйти на такой уровень как у вас?
Просто вот тратить 3 месяца на прочтение спец книг нету, а вот насколько я понял по задаче надо распознать какой алгоритм тут, а без книг никак
Здравствуйте, e.thrash, Вы писали:
ET>Как выйти на такой уровень как у вас? ET>Просто вот тратить 3 месяца на прочтение спец книг нету, а вот насколько я понял по задаче надо распознать какой алгоритм тут, а без книг никак
А даже если бы и было 3 месяца, этого мало. Я олипмиадами занимался профессионально. Т.е. в течение 5 лет тренировки. Минимум раз в две недели полноценный командный раунд на 5 часов. Плюс какие-нибудь разборы отдельных тем между этого. Плюс летние сборы. А до этого — еще несколько лет математические олимпиады (тоже со сборами и лагерями). Ну да, в какие-то летние каникулы (во время университета) я еще все "Алгоритмы: построение и анализ" прорешал. Но это мелочи на фоне всего остального.
Ну и я еще не хвастаюсь тем, что у меня хромает. Например, какие-нибудь максимальные парасочетания в двудольном графе я может и найду, а написать не смогу. И геометрию я недолюбливаю. Зато были другие члены команды, которые умели это решать/писать. А вот триаж был моей ответственностью в команде. Поэтому обнаружение классов алгоритмов у меня работает (это до половины всех задач в один ход решается).
В данном случае был жадный алгоритм. Он в отличие от многих классических алгоритмов (вроде графов и т.п.) не имеет четкой стандартной формы. Т.е. "графы" в задаче обычно видно. А вот критерий для минимизации в жадном алгоритме нужно заметить. Из плюсов — обычно решение выглядить как раз очень банально. Это такая задача, которая с точки зрения обычного человека (не разработчика) решается "в лоб", без излишней рефлексии о сложности алгоритма и т.п. (Правда нужно понять, что именно жадный алгоритм а не что-то другое). И из-за своих свойств в книжках ему не слишком много внимания уделяется. Так что нужно прорешать много задач, алгоритм в мое время встречался часто (больше половины соревнований имели хотя бы одну задачу).
Ну и стоит попрактиковаться в triage. Там, где не только сложность алгортима имеет значение, но еще и время на написание алгоритма. А также и время на triage тоже. Посмтрите что-нибудь вроде такого. Там полу-ACM (половина времени, штраф за неверный submission тоже половинка стандартного).
Из плюсов triage — он учит искать не просто "конкретные алгоритмы", а те, которые вы (или команда) умеете решать. И приоритизировать по времени решения. А заодно еще тренирует не гоняться за оптимальным решением а писать то, что влезает в рамки задачи (ага, ограничения — это часто подсказка на сложность алгоритма). В качестве побочных эффектов все это еще учит забивать на тесты там, где вероятность ошибки низкая. Потому что тесты — это слишком дорого. Полезно тестировать только то, что представляет большой риск.
Может есть и другие online judges, но сейчас не сезон (лето, каникулы). Больше будет к осени. А без необходимости триажа к алогритмам немного другое отношение получается.
Здравствуйте, maxkar, Вы писали:
M>Здравствуйте, e.thrash, Вы писали:
у меня несколько вопросов.
Дало ли в жизни выхлоп время потраченное на алгоритмы в таком объеме по сравнению со обычным программистом? т.е. работа в штатах например в хорошей компании, зп выше рынка?
Как форму держите?
Как лучше решать задачи? сначала изучить базовые алгоритмы поверхностно хотя бы, чтобы triage делать или брать задачу и там смотреть уже?
