Из всего, что здесь написано, интерес представляют идеи использования дробных и отрицательных чисел в некоторых местах. Но, думаю, математики уже давно додумались до применения такого в своих задачах.
Лупа и Пупа пошли получать зарплату. Лупа получил кучу денег, а Пупа — только одну купюру.
— Что случилось? — спросил я. — Один из тех несчастных случаев на производстве, — сказал он.
Я никогда не мог заставить его рассказать об этом подробнее.
Он просто сказал: «Один из тех».
Элементарное означает, что в нём используются только понятия и прочие инстументы, не выходящие за пределы школьной программы (без всяких лютых «высших» математик), хотя оно может быть довольно большим и его будет не так просто понять.
Это примерно как переписать программу без использования сторонних библиотек.
Это разные задачи. В теореме о четырёх красках граф планарный (точнее, плоский), то есть его можно нарисовать на плоскости так, чтобы ребра, изображенные в виде кривых, не пересекались. Здесь же граф единичный расстояний — т.е. рёбра могут пересекаться как угодно, главное чтобы при изображении на плоскости длины всех рёбер были равны единице.
Вспомнилось, как я году эдак в 2013 матрицы перемножал. Правда, там в ячейках были не float, а int64 (точнее, в A*B=C в A и B — инты, а в C должно было инт64 влезать). Размеры матричек 5000х5000. Подробнее о задаче на fastcomputing.org (вебархив, ибо проект ныне покойный). А вот табличка рекордов. В 40 секунд тогда упихал. Подробности реализации сейчас не вспомню, но вроде там Виноград-Штрассен, который где-то то ли на 200х200, то ли на 1000х1000 переключается уже на перемножение в лоб. Без Штрассена было тормознее, насколько помню. В перемножении в лоб тоже всякие SSE, помню разве что только один хак: мы умножаем не строчку A на строчку B (B транспонирована, конечно), а пару строчек A на пару строчек B, тем самым сокращая число чтений, потом все идет чисто на регистрах процессора, и на выходе получаем 4 значения для этих самых пар строчек.
Немного пооптимиздил:
10^6 22сек — 102 тройки
10^7 30мин — 212 троек
Это все в 1 поток на ноутбуке.
Есть еще несколько идей как ускорить, надеюсь 10^8 затащу. Ну и я еще подумаю код сюда сразу скинуть или статью написать — а то много довольно интересных идей всплыло.
Да, я нашел это различие, просто поймал себя на мысли, что слишком долго сижу и ищу где же оно. Сначала долго выбирал рандомные позиции — везде сходилось, затем наконец начал последовательно проверять все посимвольно, пока не нашел наконец.
Тут какой-то бред написан. Мало того, что любая задача из #P не проще аналогичной из NP, они еще и в разных «весовых категориях» — у задачи из #P на выходе число (counting problem), а у задачи из NP — «да» или «нет» (decision problem), и для «да» есть сертификат, проверяемый за полином. И вот мы для задачи из #P получили число — и как мы проверим за полином, что это число верное, раз эта задача еще и в NP лежит?
Корреляция не указывает в какую сторону идет причинно следственная связь. Т.е. тут легко спутать причину со следствием. Может там все наоборот: если по каким-то причинам теломеры короче, то тело субъективно старее, а значит тогда на бегать/секс сил никаких нет.
Это примерно как «ученые нашли корреляцию между богатыми людьми и людьми, у которых есть яхта». Согласно логике статьи получаем вывод «если купите яхту — сразу станете богаты».
Моменты, которые очень хорошо помню: выбешивали крысы в подземных переходах между улицами в городе, ибо двигались они полностью рандомно и слить на них пару жизней было очень легко. Еще помню грибок в лесу, мимо которого я ходил очень долго, думая, что это элемент фона, а оказалось, что это предмет, который можно (и нужно) было брать.
Ну норм группа, похожие штуки уже давно придуманы и даже используются на практике
https://ru.wikipedia.org/wiki/Нумерация_Гёделя
https://ru.wikipedia.org/wiki/Гладкое_число
https://ru.wikipedia.org/wiki/Алгоритм_Диксона
Из всего, что здесь написано, интерес представляют идеи использования дробных и отрицательных чисел в некоторых местах. Но, думаю, математики уже давно додумались до применения такого в своих задачах.
Но ведь можно было дать рандомное лечение только одному ребенку, в итоге получить одну смерть с вероятностью 50%, и 0 смертей тоже с вероятностью 50%.
— Что случилось? — спросил я. — Один из тех несчастных случаев на производстве, — сказал он.
Я никогда не мог заставить его рассказать об этом подробнее.
Он просто сказал: «Один из тех».
Это примерно как переписать программу без использования сторонних библиотек.
Кароси
10^6 22сек — 102 тройки
10^7 30мин — 212 троек
Это все в 1 поток на ноутбуке.
Есть еще несколько идей как ускорить, надеюсь 10^8 затащу. Ну и я еще подумаю код сюда сразу скинуть или статью написать — а то много довольно интересных идей всплыло.
Еще у Вас, кстати, на 10^7 переполнение тут:
Но путь «жизнь» -> метаклетки -> компьютер -> «жизнь», конечно, интереснее
Тут какой-то бред написан. Мало того, что любая задача из #P не проще аналогичной из NP, они еще и в разных «весовых категориях» — у задачи из #P на выходе число (counting problem), а у задачи из NP — «да» или «нет» (decision problem), и для «да» есть сертификат, проверяемый за полином. И вот мы для задачи из #P получили число — и как мы проверим за полином, что это число верное, раз эта задача еще и в NP лежит?
Вот еще крутая головоломка, о которой почти никто не знает: Recursed
привет
я в этот раз буду решать удаленно от основной команды, пока непонятно что из этого получится
Это примерно как «ученые нашли корреляцию между богатыми людьми и людьми, у которых есть яхта». Согласно логике статьи получаем вывод «если купите яхту — сразу станете богаты».