Re[2]: Тесты для алгоритмов
От: e.thrash  
Дата: 21.05.21 12:58
Оценка:
Здравствуйте, maxkar, Вы писали:



ET>>я правильно понимаю тут нет простого решения, может тестами как-то можно найти косяк в алгоритме?


M>Вот как раз на хакерранке есть простое решение! Там же можно посмотреть на падающий тест за hackos. Потом скопировать и протестировать алгоритм на этом входе.


так если набор данных большой и падает не по таймауту сложно понять что не так в конкретно данной задаче
Re[3]: Тесты для алгоритмов
От: Буравчик Россия  
Дата: 21.05.21 22:33
Оценка:
Здравствуйте, e.thrash, Вы писали:

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


Конкретно в твоем случае можно сравнить результаты твоего алгоритма и результаты заведомо правильного.
Best regards, Буравчик
Re[4]: Тесты для алгоритмов
От: e.thrash  
Дата: 26.05.21 14:58
Оценка:
Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, e.thrash, Вы писали:


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


Б>Конкретно в твоем случае можно сравнить результаты твоего алгоритма и результаты заведомо правильного.



это да, только хочется "не подглядывать")
Re[4]: Тесты для алгоритмов
От: e.thrash  
Дата: 30.05.21 13:05
Оценка:
Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, e.thrash, Вы писали:


ET>>по результатам не проходит на большом наборе. а там задача еще не так просто найти на каком шаге ошибке

ET>>задача

Б>Данная задача аналогична задаче топологической сортировки.

Б>Решается с помощью поиска в глубину (DFS) за O(N).


я вот нашел тут описание

но мне непонятно как найти вершину с которой начинаем?
вот к примеру массив 2 4 2 6 1 7 8 9 2 1
Re[5]: Тесты для алгоритмов
От: e.thrash  
Дата: 30.05.21 14:53
Оценка:
Здравствуйте, 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>

Re[6]: Тесты для алгоритмов
От: maxkar  
Дата: 01.06.21 18:35
Оценка:
Здравствуйте, e.thrash, Вы писали:

ET>возвращается 3, а надо 2


Стоп! Откуда 2?
Два дитя. Каждое должно получить хотя бы по одной конфетке. Причем первое (рейтинг 3) должно получить больше, чем второе (рейтинг 1). Т.е. распределение [2, 1]. И сумма (минимальное количество конфет для покупки) — 3.

Или в коде что-то смущает? Array.fill вычисляет вторую группу аргументов (то, что в фигурных скобках) для каждого элемента. Дальше идет борьба с граничными условиями. Простым приписыванием слева/справа (по ним итераций нет). Дальше детей сортируем по их рейтингу. Точнее, индексы детей. Добавленные элементы ("вне" исходных данных) не берем (поэтому и индексы в idx начинаются с единицы а не с нуля). А дальше — перебираем детей по рейтингу. Ну или индексы детей (которые отсортированы по рейтингу). Смотрим на соседей. Если рейтинг у кого-то ниже, мы его уже обработали (потому что сортировка!). А все остальные случаи — даем единичку. Ну и я сумму еще в том же цикле посчитал. Можно было sum сделать, но я код писал вечером и сильно тормозил. Поставил лишние скобки в вызове sum, подумал минуту, написал inline.
Re[7]: Тесты для алгоритмов
От: e.thrash  
Дата: 12.06.21 21:34
Оценка:
Здравствуйте, maxkar, Вы писали:

M>Здравствуйте, e.thrash, Вы писали:


ET>>возвращается 3, а надо 2


M>Стоп! Откуда 2?

M>Два дитя. Каждое должно получить хотя бы по одной конфетке. Причем первое (рейтинг 3) должно получить больше, чем второе (рейтинг 1). Т.е. распределение [2, 1]. И сумма (минимальное количество конфет для покупки) — 3.

M>Или в коде что-то смущает? Array.fill вычисляет вторую группу аргументов (то, что в фигурных скобках) для каждого элемента. Дальше идет борьба с граничными условиями. Простым приписыванием слева/справа (по ним итераций нет). Дальше детей сортируем по их рейтингу. Точнее, индексы детей. Добавленные элементы ("вне" исходных данных) не берем (поэтому и индексы в idx начинаются с единицы а не с нуля). А дальше — перебираем детей по рейтингу. Ну или индексы детей (которые отсортированы по рейтингу). Смотрим на соседей. Если рейтинг у кого-то ниже, мы его уже обработали (потому что сортировка!). А все остальные случаи — даем единичку. Ну и я сумму еще в том же цикле посчитал. Можно было sum сделать, но я код писал вечером и сильно тормозил. Поставил лишние скобки в вызове sum, подумал минуту, написал inline.


Извиняйте, у вас всё верно.
Блин, настолько элегантное решение. Я неделю каждый день почти думал над задачей и кроме кучи ифов не было решений.
Как выйти на такой уровень как у вас?
Просто вот тратить 3 месяца на прочтение спец книг нету, а вот насколько я понял по задаче надо распознать какой алгоритм тут, а без книг никак
Re[8]: Тесты для алгоритмов
От: maxkar  
Дата: 14.06.21 17:24
Оценка:
Здравствуйте, e.thrash, Вы писали:

ET>Как выйти на такой уровень как у вас?

ET>Просто вот тратить 3 месяца на прочтение спец книг нету, а вот насколько я понял по задаче надо распознать какой алгоритм тут, а без книг никак

А даже если бы и было 3 месяца, этого мало. Я олипмиадами занимался профессионально. Т.е. в течение 5 лет тренировки. Минимум раз в две недели полноценный командный раунд на 5 часов. Плюс какие-нибудь разборы отдельных тем между этого. Плюс летние сборы. А до этого — еще несколько лет математические олимпиады (тоже со сборами и лагерями). Ну да, в какие-то летние каникулы (во время университета) я еще все "Алгоритмы: построение и анализ" прорешал. Но это мелочи на фоне всего остального.

Ну и я еще не хвастаюсь тем, что у меня хромает. Например, какие-нибудь максимальные парасочетания в двудольном графе я может и найду, а написать не смогу. И геометрию я недолюбливаю. Зато были другие члены команды, которые умели это решать/писать. А вот триаж был моей ответственностью в команде. Поэтому обнаружение классов алгоритмов у меня работает (это до половины всех задач в один ход решается).

В данном случае был жадный алгоритм. Он в отличие от многих классических алгоритмов (вроде графов и т.п.) не имеет четкой стандартной формы. Т.е. "графы" в задаче обычно видно. А вот критерий для минимизации в жадном алгоритме нужно заметить. Из плюсов — обычно решение выглядить как раз очень банально. Это такая задача, которая с точки зрения обычного человека (не разработчика) решается "в лоб", без излишней рефлексии о сложности алгоритма и т.п. (Правда нужно понять, что именно жадный алгоритм а не что-то другое). И из-за своих свойств в книжках ему не слишком много внимания уделяется. Так что нужно прорешать много задач, алгоритм в мое время встречался часто (больше половины соревнований имели хотя бы одну задачу).

Ну и стоит попрактиковаться в triage. Там, где не только сложность алгортима имеет значение, но еще и время на написание алгоритма. А также и время на triage тоже. Посмтрите что-нибудь вроде такого. Там полу-ACM (половина времени, штраф за неверный submission тоже половинка стандартного).

Из плюсов triage — он учит искать не просто "конкретные алгоритмы", а те, которые вы (или команда) умеете решать. И приоритизировать по времени решения. А заодно еще тренирует не гоняться за оптимальным решением а писать то, что влезает в рамки задачи (ага, ограничения — это часто подсказка на сложность алгоритма). В качестве побочных эффектов все это еще учит забивать на тесты там, где вероятность ошибки низкая. Потому что тесты — это слишком дорого. Полезно тестировать только то, что представляет большой риск.

Может есть и другие online judges, но сейчас не сезон (лето, каникулы). Больше будет к осени. А без необходимости триажа к алогритмам немного другое отношение получается.
Re[9]: Тесты для алгоритмов
От: e.thrash  
Дата: 16.06.21 17:52
Оценка:
Здравствуйте, maxkar, Вы писали:

M>Здравствуйте, e.thrash, Вы писали:



у меня несколько вопросов.

Дало ли в жизни выхлоп время потраченное на алгоритмы в таком объеме по сравнению со обычным программистом? т.е. работа в штатах например в хорошей компании, зп выше рынка?
Как форму держите?
Как лучше решать задачи? сначала изучить базовые алгоритмы поверхностно хотя бы, чтобы triage делать или брать задачу и там смотреть уже?
Re[10]: Тесты для алгоритмов
От: maxkar  
Дата: 22.06.21 15:40
Оценка: 12 (1)
Здравствуйте, e.thrash, Вы писали:

ET>у меня несколько вопросов.


ET>Дало ли в жизни выхлоп время потраченное на алгоритмы в таком объеме по сравнению со обычным программистом? т.е. работа в штатах например в хорошей компании, зп выше рынка?


Работа в Европе (не хочу в штаты), зарплата выше/топ рынка в моем месте. Задачи в олимпиадном стиле я уже не помню когда при приеме на работу давали. Одно тестовое задание на дом несколько лет назад я точно из-за алгоритмов зававлил. Написал оптимальное олимпиадное решение, а от меня очень хотели идеоматическую Scala. А кроме этого что-то измерить сложно. Развитие мозга и алгоритмы связаны, но не понятно, кто из них — причина, а кто — следствие.

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

ET>Как форму держите?


Никак. Для меня алгоритмы уже не очень актуальны (больше по архитектуре и культуре вопросы). Плюс типичные задачи на собеседованиях из "простых" олимпиадных. Т.е. те алгоритмы, которые оттренированы много много раз. Хотябы потому, что если не все олимпиадники решают более сложные задачи, то чего ждать от простого человека?

ET>Как лучше решать задачи? сначала изучить базовые алгоритмы поверхностно хотя бы, чтобы triage делать или брать задачу и там смотреть уже?


Для triage полезно знать какие есть алгоритмы и их ассимптоматику. Еще очень полезно знать "конкретику" по константам. Например, в мое время O(NlogN) проходило на размерностях порядка миллиона. Т.е. если задача сводилась к сортировке миллиона чисел — это можно было делать. А вот пять миллионов уже не сортировались (не хватало времени), обычно нужно было линейное решение.

Без знания ассортимента алгоритмов на некоторые задачи можно смотреть очень долго . Так что полезно _поверхностно_ изучить какой-нибудь учебник. Т.е. какие задачи решаются, какая ассимптоматика, описывает она худший или средний случай, сколько требуется памяти. После этого — можно смотреть на задачи и пытаться найти алгоритм. Когда нашли (т.е. свели вашу задачу к известной) — можно писать по учебнику, адаптировать известный код. Так будет более интересно, чем читать учебник подряд.

Но здесь есть одна подстава. Не все алгоритмы в учебнике — алгоритмы. Большинство — решают конкретную задачу (поиск путей в графе, выпуклой оболочки и т.п.). Но при этом есть веселые главы, описывающие классы алгоритмов. Как минимум, это жадные алгортимы и динамическое программирование. У них есть "идея" решения. И все. Нет канонической формы задачи. Нет классического кода. Только идея. Вот задачи из этих классов нужно решать. Тогда с практикой станет легче классифицировать задачи под эти алгоритмы.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.