vol_kos

  • Публикации

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

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

  • Посещение

О vol_kos

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

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

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

232 просмотра профиля
  1. Да, я выше и вправду неправильно прикинул, с неориентированными 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: Хотя не понимаю как он так быстро все варианты мог перебрать. М.б. я ошибся и их всё-таки меньше?
  2. Если все комбинации находить, то не решить. Хотя с отбросом поворотов/отражений может быть и можно. Интересно если получится. Я решал относительно числа вариантов, не задумываясь над тем как они выглядят. Это намного проще, но, конечно, куда менее увлекательно )) Upd: точнее, если все комбинации ориентированных находить, то не решить (их 1017); с неориентированными не знаю, во сколько раз их меньше? максимум в 2^25? Всё равно очень много. А 3 поворота и 1 отражение, это же число вариантов в 8 раз (4 направления × 2 ориентации) только уменьшит?
  3. Я скорее так делал: разбил задачу 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 секунды. Но я не разобрался в их решениях, это что ли получается нужно знать число вариантов для каждого возможного числа циклов?
  4. -- а какая идея-то метода решения? В моём решении --- "разделяй и властвуй" + memoization (запоминать что получилось для уже решённых подзадач, чтобы не решать то же самое второй раз). Разделять можно по-разному (2-мерно и одномерно). Я сначала запарился с 2-мерным разделением (работает в результате за одну секунду). Потом сделал одномерное, оно проще, но почему-то в несколько раз медленнее. А стандартный и более быстрый способ --- динамическое программирование. Чтобы понять что это такое, можно решить несколько задачек с hackerrank'а по этой ссылке (и м.б. посмотреть видео). Хотя на простых задачках я так и не смог понять чем словосочетание "динамическое программирование" отличается от "обычный здравый смысл" и "а как же по-другому?" ))) С этой задачей про муравьёв вроде начинает проясняться, хотя очень не до конца. Лучше всего, наверное, CLR ("ослов") почитать. У меня, если что, пока не получилось понять как этим способом нужно решать, даже глядя на чужие решения )) Т.е. я пару вариантов попробовал, но в одном случае медленно работало (то ли 10 секунд, то ли 40), а в другом оказалось, что сильно ошибся и всё не так просто. Кто-то ещё с неориентированными циклами как-то сыграл (см. картинки indi) и за 25ms решил (но тут я тоже не понял как число неориентированных посчитать, да ещё и число их вариантов). А простым перебором решать долго )).
  5. -- сколько по времени у меня в пред. сообщении дана очень оптимистичная оценка снизу, в текущем варианте д.б. подольше )) Upd. 8-49: хотя возможно так и можно решить, ну, с некоторой модификацией... (upd: т.е. подзадачи)
  6. О, если так делать, то можно картинки легко рисовать )) Но проверить _каждую_ подозрительную комбинацию, даже если они будут известны и почти все правильны --- это для задачи 10×10 триста лет займёт. Их же даже не сохранить. --------- Я в их коде не разбирался, но там народ очень стандартный подход использует; не знаю, стоит ли его называть (кмк при таком подходе даже картинку с заданным номером построить не очень сложно, хотя может я ошибаюсь). --- А у меня все более "простые" варианты решения, как оказалось, хуже работают (минимум 3.5с, чуть улучшенный основной -- 1.1с). А indi с его картинками, кмк, в чём-то близок к чуваку, который за 0.025с решил ))
  7. Мда, (глядя на свои 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 сек.)
  8. Спасибо )) Да, нужно комментарии на английский перевести и поясняющую картинку нарисовать и том сайте выложить. И ещё в чужих решениях разобраться. А то когда смотришь как у какого-то датчанина (8 Sep 2012, 19:10) эта задача решена в 30 строчек, да ещё и на медленном питоне за 1.5 секунды выполняется...
  9. Решил-таки эту задачку про муравьёв, 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 строчек --- на вид очень просто, но я ещё не разбирался. Но это лучше потом, наверное, вдруг кому-то самому интереснее решить. Или лучше так не делать, там что в правилах написано?
  10. О, понял где ошибка! Я, когда ускорял, не учёл, что в хеш-таблице коллизии могут быть . Ошибка, с одной стороны, грубая и непростительная. С другой, поучительная. Так что хорошо что я её сделал Просто я сначала хотел тупо большой массив использовать, размером с диапазон изменения ключа (от 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: Блин, чего-то я ступил конкретно . Библиотечная хеш-таблица коллизии, естественно, сама нормально обрабатывает. Париться нужно только если у меня при вычислении ключа коллизии возникают (т.е. ключ не уникален), но там и массив не поможет, естественно. Но вроде не должно их возникать. Так что непонятно где ошибка
  11. Рекурсивных, но вложенность рекурсии log2(n), совсем мало. Так это то же самое и есть )), только единица кмк лишняя, y = i(i+1)/2. Просто у меня (в следующем сообщении, которое утром) квадратное уравнение решено относительно i. Я сначала формулу для арифметической прогрессии не вспомнил и просто проинтегрировал по i от нуля до i, получилось y ≈ i2/2. Что немного грубо и даёт i = √(2y). А если считать точно, то i = ⌈√(2y+1⁄4)-1⁄2⌉.
  12. Ускорил, для 8×8 меньше чем за секунду выдаёт тот же результат: 22'902'801'416. Для 10×10 за 6 секунд выдаёт 5'485'879'679'009'802. Но проблема в том, на сайте https://projecteuler.net/problem=393 этот ответ (5485879679009802) отмечается как неверный . Для 6×6 по-прежнему результат 207408. Может конечно где-то переполнение. И с нечётными нужно разобраться. Но это потом, завтра, наверное, времени не будет. Для 9×9 получилось 4'296'562'226'298.
  13. не знаю, но интереснее попытаться ускорить.
  14. 6×6: 207408 4×4: 88 3×4: 8
  15. Да, странно, чего-то не понимаю как так получилось. Надо как-то вывести ответ.