vol_kos

  • Публикации

    417
  • Сообщений в день

    0,14
  • Зарегистрирован

  • Посещение

Репутация

0 Neutral

О vol_kos

Дополнительная информация

  • Имя
    Владимир
  • Адрес
    Санкт-Петербург

Посетители профиля

284 просмотра профиля
  • Haze

  • AndrSlav

  • indi

  • MaryT

  • Demeter

  1. Это с пуховыми спальниками )) С синтетикой зимой четырём в трёшке самое то ))) Хотя если там одни мужики, то м.б. и вправду лучше 2.5 кг спальник )) jao же привёл ссылку, по которой убедительно показано, что в соло-походе фотоаппаратов должно быть не DVA, а минимум TRI )) Спасибо за ссылки. Про пешего туриста тоже интересно. А насчёт лыжника -- раньше про этого легендарного человека только байки слышал в стиле "провалился где-то в Сибири в реку, рюкзак у костра оттаял и маршрут не прервал", или как на Ладоге привычно провалился и дальше пошёл. Ну и ролик 2011 года про работу Экстремума, в котором 400 км летом после травмы упомянуты. А реальность (то, что описано в интервью), как оказалось, эти байки просто напрочь затмевает. Интересно. --- Насчёт межсезонья вспомнилась история двухлетней давности, как на Северном Урале нашли отшельника из Челябинска, замёрзшего в хижине в палатке (видимо просто от усталости) в трёх ходовых днях от базы. Он пешком был, а там снег выпал:
  2. Имел в виду vсредн = c/2, т.е. ответ m⋅с²/4; Но собственно в предыдущем сообщении AndrSlav уже всё написал в относительной системе: m⋅с²/2 - 2m(c/2)²/2 = m⋅с²/4, я чёт сразу не сообразил. Upd: а сложную задачку indi из PE я даже на трезвую голову так и не решил ((
  3. mv₁²/2+mv₂²/2-(2m)((v₁-v₂)/2)²/2 = mv₁²/4+mv₂²/4+mv₁v₂/2 = m((v₁+v₂)/2)² = m⋅vсредн² mg(√(L²+H²)-H) == mv²/2, v=...
  4. Про Кандалакшу тоже удивился (хотя у меня и лавинного опыта тоже нет). Но мне в своё время запомнилась картинка из статьи сахалинских авторов про лавины c небольших склонов. Там склон чуть больше, но в принципе из серии «Орехово, соревнования по ТЛТ, этап "лавина"» )). И реально лавина с погибшим. 31 декабря. Но это Сахалин, возможно у них там снег другой системы (чаще бывает перекристаллизовавшимся, например). Картинка:
  5. Кмк, в данном случае ровно наоборот. Upd: Т.е. ваша мысль была высказана не П/Е, а Арсом. P/E, наоборот, с ней активно спорил. Можно такую аналогию провести: Пусть в городе установили норму веса рюкзака для школьников 10 кг и охранники в магазинах проверют соответствие веса рюкзака норме. Из магазина выходит школьник с рюкзаком 4 кг. Рюкзак взвешивает 1-й охранник и делает запись "вес в пределах нормы". Следом школьника ловит 2-й охранник и находит в рюкзаке украденный из магазина коньяк (1кг). Далее такой диалог упвп: P/E: первый охранник написал чушь Ars: но ведь 4 кг < 10 кг, т.е. утверждение "вес рюкзака (4кг) лежит в пределах нормы (10 кг)" истинно. P/E, как настоящий юрист: суммарный вес рюкзака складывается из веса его составных частей, включая и 1кг ворованного коньяка; воровать нехорошо, т.е. ненормально. Значит и вес, включающий в себя 1 кг стыренного коньяка, ненормален. Утверждение "вес рюкзака в пределах нормы" ложно. Ars, аппелируя к диплому математика: но 4 кг < 10 кг... P/E: но первый охранник должен был заметить, что на входе у школьника рюкзак был 3кг, а потом потяжелел Ars: но утверждение "4 кг < 10 кг" от этого ложным не становится... vsh: вот ты, Ars, всё Путина защищаешь, а между тем P/E правильно говорит: плохой охранник.
  6. Да, я выше и вправду неправильно прикинул, с неориентированными 10^17/2^25/10^9*100 ячеек ~= 300 секунд. Это оценка снизу, понятно что и вариантов циклов больше, и времени на каждый уйдёт больше чем 100*10-9. Но это хоть уже какое-то разумное время. Собственно, там есть итальянец, распараллеливший задачу на 6 потоков и решивший. Пост начинается со слов "I'm an idiot. I have tried for hours to dynamic-program it without any result... Then I decided to bruteforce it." )) А заканчивается "Oh, you may be asking for the execution time. Well... It's about 12 hours! XD". На C++ )) Upd. 00-15: посчитал число неориентированных циклов, для 10×10 получилось ~299.6·1010 ~= 2^41. В тысячу раз больше грубой оценки. Если на 1 клетку уходит 10-9 секунд, то 2996 * 100 клеток / 3600 секунд / 6 потоков ~= 14 часов. Молодец итальянец! Если конечно я правильно посчитал: для 4×4 получилось 20 вариантов, для 6×6 --- 15963, для 8×8 --- ~1.372·109. Upd. 00-39: Т.е. при таком подходе, видимо, задача 10×10 в 2000 раз сложнее, чем 8×8. Upd. 00-47: А для ориентированных циклов для сетки 10×10 вариантов в 5 _миллионов_ раз больше, чем для 8×8! Upd. 01-05: Хотя не понимаю как он так быстро все варианты мог перебрать. М.б. я ошибся и их всё-таки меньше?
  7. Если все комбинации находить, то не решить. Хотя с отбросом поворотов/отражений может быть и можно. Интересно если получится. Я решал относительно числа вариантов, не задумываясь над тем как они выглядят. Это намного проще, но, конечно, куда менее увлекательно )) Upd: точнее, если все комбинации ориентированных находить, то не решить (их 1017); с неориентированными не знаю, во сколько раз их меньше? максимум в 2^25? Всё равно очень много. А 3 поворота и 1 отражение, это же число вариантов в 8 раз (4 направления × 2 ориентации) только уменьшит?
  8. Я скорее так делал: разбил задачу 10x10 на 2 задачи 10x5. И рекурсивно решал каждую (т.е. получилось 4 задачи размером 5x5 и так далее). При этом они должны как-то стыковаться. Одинаковые задачи по несколько раз лучше не решать (хотя за ночь может и с одинаковыми посчитало бы). Потом, пытаясь улучшить, я стал задачи 1x10 рассматривать, работало в 3 раза медленнее, --- но это да, построчно и отсекая. Upd.: так-то в общем, понятно почему медленнее: если построчно, то это n рекурсивных вызовов, а в первом варианте 4log(n). Но я и напополам делить пытался (как одномерную, например в сортировке слиянием), там почему-то то ли 10 то ли 40 секунд получилось, ещё хуже. Хотя не, туплю: n=10 )) Просто если двумерно делить, то видимо больше одинаковых подзадач и memoization эффективнее оказывается. Без запоминания одномерный вариант должен лучше работать по идее. А у них DP и то же что-то про "row-wise" (upd: "column-wise"), но быстро. Про повороты/отражения не понял. А так ясно, что если есть C неориентированных циклов, то число ориентированных это 2^C (2 возможных направления в каждом цикле). Там 2 человека про это пишут, "I made this too complicated, keeping track of connected paths and multiplying the count for each possible column by 2^(# of newly closed cycles) while stepping from column to column", 0.159 с на ML. Кто-то про какие-то Гамильтоновы циклы пишет, 23 строчки на питоне и 2.5 секунды. Но я не разобрался в их решениях, это что ли получается нужно знать число вариантов для каждого возможного числа циклов?
  9. -- а какая идея-то метода решения? В моём решении --- "разделяй и властвуй" + memoization (запоминать что получилось для уже решённых подзадач, чтобы не решать то же самое второй раз). Разделять можно по-разному (2-мерно и одномерно). Я сначала запарился с 2-мерным разделением (работает в результате за одну секунду). Потом сделал одномерное, оно проще, но почему-то в несколько раз медленнее. А стандартный и более быстрый способ --- динамическое программирование. Чтобы понять что это такое, можно решить несколько задачек с hackerrank'а по этой ссылке (и м.б. посмотреть видео). Хотя на простых задачках я так и не смог понять чем словосочетание "динамическое программирование" отличается от "обычный здравый смысл" и "а как же по-другому?" ))) С этой задачей про муравьёв вроде начинает проясняться, хотя очень не до конца. Лучше всего, наверное, CLR ("ослов") почитать. У меня, если что, пока не получилось понять как этим способом нужно решать, даже глядя на чужие решения )) Т.е. я пару вариантов попробовал, но в одном случае медленно работало (то ли 10 секунд, то ли 40), а в другом оказалось, что сильно ошибся и всё не так просто. Кто-то ещё с неориентированными циклами как-то сыграл (см. картинки indi) и за 25ms решил (но тут я тоже не понял как число неориентированных посчитать, да ещё и число их вариантов). А простым перебором решать долго )).
  10. -- сколько по времени у меня в пред. сообщении дана очень оптимистичная оценка снизу, в текущем варианте д.б. подольше )) Upd. 8-49: хотя возможно так и можно решить, ну, с некоторой модификацией... (upd: т.е. подзадачи)
  11. О, если так делать, то можно картинки легко рисовать )) Но проверить _каждую_ подозрительную комбинацию, даже если они будут известны и почти все правильны --- это для задачи 10×10 триста лет займёт. Их же даже не сохранить. --------- Я в их коде не разбирался, но там народ очень стандартный подход использует; не знаю, стоит ли его называть (кмк при таком подходе даже картинку с заданным номером построить не очень сложно, хотя может я ошибаюсь). --- А у меня все более "простые" варианты решения, как оказалось, хуже работают (минимум 3.5с, чуть улучшенный основной -- 1.1с). А indi с его картинками, кмк, в чём-то близок к чуваку, который за 0.025с решил ))
  12. Мда, (глядя на свои 300 строчек и 2 секунды) кажется, что с отсылки правильного ответа работа с задачей должна только начинаться У кого-то 23 строчки на питоне, 2.5 секунды, и получен результат для 10x100 за 6 секунд; У кого-то 17 строк на Mathematica. 9 секунд. У кого-то 26 строк на Haskell'е, 0.7 секунд. У кого-то на с++ за 0.228 секунд, у кого-то -- 0.14 секунд (на основе задачи 289). А один американец, тоже на с++, -- за 25мс (0.025с) решил, правда длинно )) Голландец на с++ -- за 0.016 секунды! Кто-то на c++ без всяких рекурсий, 35 коротких строчек и 3.5 минуты. Разве что порадовал итальянец, у которого 6 потоков 12 часов работали Я пока не разбирался, но уже ясно, что нужно было немного по-другому решать. С непривычки я так конкретно перемудрил, можно намного проще делать (хотя базовые элементы совпадут). Интересно, там нет такой же, только трёхмерной? офигеть; в своём решении я даже 1 вариант ответа не смог вывести (правда в том, которое я теперь хочу сделать, это должно быть уже не так сложно). Upd 12.09, 07-02: Блин, сделал как проще, стало в 22 раза медленнее работать (Upd: т.е. стало 42 сек. вместо 1.9 сек.)
  13. Спасибо )) Да, нужно комментарии на английский перевести и поясняющую картинку нарисовать и том сайте выложить. И ещё в чужих решениях разобраться. А то когда смотришь как у какого-то датчанина (8 Sep 2012, 19:10) эта задача решена в 30 строчек, да ещё и на медленном питоне за 1.5 секунды выполняется...
  14. Решил-таки эту задачку про муравьёв, https://projecteuler.net/thread=393 (#543). Смотрю на решение какого-то китайца на форуме и идиотом себя чувствую , у меня 320 строчек, а у него штук 45, правда без комментариев. С нечётными n и вправду нули получаются. indi правильно подсказал, правда я всё равно не понимаю почему. У меня там что-то напутано было с порядком в котором данные о перемещениях муравьёв хранились при разбивке на подзадачи. Почему-то вплоть до 8x8 всё правильно получалось, за исключением нечётных n, а дальше и для чётных ошибка появлялась. Переписал тот кусок с разбивкой намного более понятным образом и заработало. В общем, ответы такие, результат, время (Core i3-530 2.93GHz, win-x64), и (примерное) потребление памяти: 2 × 2: 2 4 × 4: 88 ~= 2^6.46; t=0.0002с; 0.4МБ 6 × 6: 207408 ~= 2^17.7; t=0.0049с; 0.6МБ 8 × 8: 22902801416 ~= 2^34.4; t=0.0504с; 1.4МБ 10×10: *** = 1.123e+17 ~= 2^56.6; t=1.9017с; 23.8МБ 12×12: 2.407511687e+25 ~= 2^84.3; t=35.397с; 127МБ 13×13: 0 t=259.26с; 636МБ 14×14: 2.232966561e+35 ~= 2^117 ; t=1448.3c; 4220МБ --- Для n>10 я приближённо считал, целочисленная переменная там переполняется. Для 14x14 результат уже вероятно неправильный (64+52=116, соответственно после 2^116 даже большое целое число не прибавить, оно всё в погрешность уйдёт). Программку могу под спойлером выложить + там народ на форуме много программок выложил, более красивых и коротких ))). У кого-то на питоне 1.5 секунды и 30 строчек --- на вид очень просто, но я ещё не разбирался. Но это лучше потом, наверное, вдруг кому-то самому интереснее решить. Или лучше так не делать, там что в правилах написано?
  15. О, понял где ошибка! Я, когда ускорял, не учёл, что в хеш-таблице коллизии могут быть . Ошибка, с одной стороны, грубая и непростительная. С другой, поучительная. Так что хорошо что я её сделал Просто я сначала хотел тупо большой массив использовать, размером с диапазон изменения ключа (от 0 до 3^10) --- по сути та же хеш-таблица, но с единичной хеш-функцией и без коллизий. Прикинул, что это в память хорошо помещается. Потом по ходу дела решил, что удобнее вместо массива библиотечную хеш-таблицу взять. Но про то, что тогда нужно ей встроенную хеш-функцию на свою единичную поменять --- и думать забыл . Да и ключ у меня в конечном итоге из диапазона [0..3^40] получился, а тут уже никакой памяти не хватит (хотя это я в спешке делал, реально нужен диапазон где-то до 312 ≈ 219). Короче, нужно либо с коллизиями разобраться, либо диапазон в котором ключ лежит уменьшить. Upd: поэтому видимо и получается для 6×6 и 8×8 правильно, что там вариантов меньше и вероятность коллизии ниже. А для 10×10 возникает ... сейчас посчитаю сколько и дополню ... Upd2: короче, коллизий возникает много, даже для 4×4; но на результате до поры до времени это почему-то не сказывается... Upd3: "единичная функция" читать как идентичная "тождественная" (identity function), h(k):=k, короче. Upd4: Блин, чего-то я ступил конкретно . Библиотечная хеш-таблица коллизии, естественно, сама нормально обрабатывает. Париться нужно только если у меня при вычислении ключа коллизии возникают (т.е. ключ не уникален), но там и массив не поможет, естественно. Но вроде не должно их возникать. Так что непонятно где ошибка