Стартапи і бізнес · 18 квітня 2014, 14:05 1746

Mossberg, Solution Architect

P=NP-Complete тестируем!

Вот и настал тот день!)))
Мне удалось решить NP-полную задачу, за полиномиальное время(O(N^4) или быстрее), задача Точное покрытие (Excat Cover). Сделал сайтик, на котором можно протестировать. Генератор с его исходником прилагается. На выходе получаем текстовый файл, который в конце содержит решение, для того что бы проверить правильность работы, кто будет постить тесты, удаляйте пожалуйста все что после строки с маркером «m», включая саму строку. Приветствуется критика, и замечания по самому сайту. Если у меня нет алгоритма и программы то даже на самое не большое количество строк скажем 60, уйдет очень очень большое время [math]2^60[/math] операций выбора и сравнения, даже если каждая операция будет занимать 1 такт процессора, даже при 100 мрлд операций в секунду, на нахождение решения потратится 11 млн сек.

npcomplete-001-site1.myasp.net

Теми: Exact cover, NP-Complete, solver NP

👍ПодобаєтьсяСподобалось0

До обраногоВ обраному0

Facebook

Twitter

LinkedIn

Ctrl + Enter

Ctrl + Enter

anonymous 20.04.2014 11:43

-

Відповісти

Підтримати

Mossberg Solution Architect 20.04.2014 13:21

Дело в том что данные генерируются случайным образом, как видно из кода. Так как нельзя гарантировать, что в случайных данных будет возможно найти строки которые покрывают множество, то отдельно создаются множества которые его покрывают и случайным образом эти множества расставляются в списке. После чего в конец файла для того кто будет тестировать был ответ, вернее легче было проверить. Как рекомендуется его надо удалять перед отсылкой. Можно и не добавлять в результирующий файл за что отвечает соответствующая опция генератора. По такому принципу строятся пожалуй все генераторы подобных бэнчмарков/тестов. Отдельно замечу так как HiddenSolution распределяется по вписку случайно и не какой информации о том где они находятся нет, то найти его можно только имея алгоритм.

Что касается второго замечания, то речь идет о решение NP-полной задачи, класс NP шире и включает NP-трудные задачи. А NP-полные сводятся друг к другу за полиномиальное время.

И третье, я не ставил цель сделать красивый код, а сделать минимально работающие решение, что бы можно было показывать. Ранее был еще один цикл и на внешний просто continue было перейти нельзя, надо было делать флаг и его проверку, потом код изменился goto осталось.

Відповісти

Підтримати

anonymous 20.04.2014 17:31

-

Відповісти

Підтримати

Mossberg Solution Architect 21.04.2014 12:38

Это очень сильные предположения о входных данных.

ни каких предположений не делается, по крайне мере отношение к генератору моему, мне ведь присылают самые разные файлы, вот к примеру некто exc (не с этого форума) прислал совершенно уникальные бэнчмарки, правильные))))

Я думаю Вам должно быть известно, что задача Факторизации целых чисел (Integer factorization) не является NP-полной (по крайней мере это сейчас не доказано) и относится к классу NP-intermediate

но задача факторизации сводится к SAT, а это NP-полная задача.

Извините, но я не представляю КАК можно было написать такой код независимо от целей. И если код решения написан в таком же стиле, то оценить корректность и сложность алгоритма будет сложновато, даже имея исходники.

может где то я не прав, но программа это всегда черный ящик для заказчика, вот ты ведь не знаешь как MS Word внутри сделал, и ничего пользуешься, условно, Open Office терпеть ненавидишь, хотя у него открытый исходник и код типа «правильный». У меня два условия главных выполняются, время расчета и память. Ниже в этой теме reality_hacker сделал очень красивый код, вот только не задача, он память жрет и работает медленнее чем у меня, имею ввиду на больших задачах. Нет ведь разницы 1 сек или 5 сек, но зато есть разница 5 часов или 10 часов. И память у меня 22,8МB, у него 1,2GB и я так и не дождался окончания работы. Код не важен важен результат!

Відповісти

Підтримати

Роман Цюпа Lead Dev в EPAM 19.04.2014 13:21

O(1) по памяти для такой задачи конечно круто, но боюсь тут не оценят. Ты бы на www.reddit.com/r/algorithms запостил, там больше полезного фидбека будет. А сюда можешь писать веселые истории про ХРов и апдейты курса доллара.

На самом деле ДОУ больше по части инфраструктуры и жизни программистов чем о программировании самом.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 13:34

Я написал на многие форумы, но как не странно подавляющие большинство тестов пришло именно от сюда. Тенденция такая что люди не понимаю с чем имеют дело. Спасибо за ссылку, попробую.

Відповісти

Підтримати

Роман Цюпа

Apasnuy 19.04.2014 12:37

Какой максимальный набор входных множеств вы тестили? Что означает точность O(N^4)? Я так понимаю под N понимается количество входных множеств, как будет расти время выполнения в зависимости от размера входного множества(тоесть задачи где десяток множеств, но в них по миллиарду елементов)? Как ваши результаты соотносятся с результатами из статьи www.csc.kth.se/...over-solver.pdf , есть ли возможности масштабирования алгоритма?

Если кому-то влом читать статью, то там решались проблемы с размерностью
<quote> Time requirements to ﬁnd all 7:77874 * 10^9
total output sets for the given input set, time required for the sequential
program is 19;211 seconds
<quoute>
Если я все правильно понял, то решать такое алгоритмом O(N^4) будет слишком больно.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 12:43

Что означает точность O(N^4)?

не точность, а сложность.

Я так понимаю под N понимается количество входных множеств

да правильно понимаете.

как будет расти время выполнения в зависимости от размера входного множества?

как N^4, где N-кол-во строк

есть ли возможности масштабирования алгоритма?

если речь идет о распараллеливании, на потоки, ядра, компьютеры, то да можно нет проблем.

Как ваши результаты соотносятся с результатами из статьи

Цитата: We have used Donald Knuth’s «Algorithm X» and DLX
technique [6] to solve the exact cover problem. Ни как не соотносится у них алгоритм эвристиечкий, вот тута написано что это ru.wikipedia.org/...ческий_алгоритм
у меня алгоритм точный.

Відповісти

Підтримати

Apasnuy 19.04.2014 14:16

как N^4, где N-кол-во строк

Вы хотите сказать, что алгоритм работает одинаковое количество времени для четырех множеств, каждое из которых содержит 10^9 элементов и для четырех множеств, каждое из которых содержит 10^13 элементов?

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 14:24

Как подсказывает математика 5 класс, (10^9)^4=10^36, меньше чем (10^13)^4 =10^52. Так что не одинаковое.

Відповісти

Підтримати

Apasnuy 19.04.2014 15:33

Лол. Я вначале задал вопрос какая сложность алгоритма( ошибся только словом с бодуна, но был поправлен). Получил ответ O(N^4) ОТ КОЛИЧЕСТВА МНОЖЕСТВ. По Вашей логике, сложность в обоих случаях 4^4 — она не зависит от количества элементов в множестве.

ак будет расти время выполнения в зависимости от размера входного множества(тоесть задачи где десяток множеств, но в них по миллиарду елементов)?

как N^4, где N-кол-во строк

Первая цитата вопрос мой, вторая ответ Ваш. Теперь же Вы сами себе противоречете.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 15:39

Смотрите, сложность решения находится в пределах O(N^4) где N — количество строк. Как показывают многочисленные опыты, реально время тратится на порядок меньше. Эта оценка O(N^4) она скорее ориентир на что надо расчитывать.

Відповісти

Підтримати

Apasnuy 19.04.2014 15:45

Это какой-то цирк. 4^4=16. Вы реально считаете, что если на входе будут 4 множества, в каждом из которых по 10^9 элементов то эта оценка верна? Советую чуть подумать перед тем как отвечать дабы не позориться.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 15:53

Во первых 4^4=256. Во вторых если будет 4 строки по 10^9 элементов, это не страшно, совсем не страшно, очень быстро найдет)))). В-третьих что вы понимаете под операцией? Вот к примеру возьмем полный перебор, как понимаю я один из способов его осуществить это выбирать последовательно наборы строк, щас объясню, если у нас 4 строки, то 2^4 = 16 Есть 16 вариантов выбора строк −1, когда не выбрано ни одной строки, т.е. 0001,0010,0011,0100 и т.д.Вот если такого выбора операцию считать как операцию, без учета времени на проверку покрывают ли строки множество, которое да зависит от кол-ва элементов. Но дело в том что когда у нас будет 1000 срок, и 2^1000~=10^300, тогда линейная операция проверки покрытия перестает иметь значение, а имеет значение лишь кол-во вариантов которые надо перебрать.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 16:01

не говоря уже о том что проверку покрытия можно легко реализовать на аппаратном уровне и она будет выполняться за такт(имею ввиду конечно на данном этапе развития электроники для не большого количества множеств в 10^9 элементов), но количество вариантов полного перебора увы не аппаратно не программно уменьшить не получится.

Відповісти

Підтримати

Apasnuy 19.04.2014 20:07

В-третьих что вы понимаете под операцией?

Когда вы пишете O(f(x)) то вы даете верхнюю оценку количеству элементарных операций для выполнения алгоритма. Под элементарными во всех местах где я бывал понимают операции +, -, /, *, побитовые операции, операции сравнения и т.д. Вот эти рассуждения о проделывании чего-то на аппаратном уровне можете оставить на то время, когда это будет сделано. А на данный момент вы пытаетесь выдать желаемое за действительное( может сам того не понимая)

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 20:38

Реальность такова, проверено многократно:
N=500, сложность должна быть 62*10^9, реально в 2000 раз быстрее. Это для сложных задач. Для простых задач ну пусть в 2млн раз быстрее чем оценка. Дайте пример, который выйдет за приделы оценки.

Відповісти

Підтримати

Apasnuy 19.04.2014 21:21

Сколько времени у вас решается задача, в которой 10 множеств, а в каждом из множеств по 10^12 элементов?

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 21:35

10^12*8байта = 8ТБ боюсь что в память не поместиться..... Не могу проверить.

Відповісти

Підтримати

Apasnuy 19.04.2014 21:42

Ну давайте для 10^9.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 21:47

Ну давайте файлик.

Відповісти

Підтримати

Andrey Tkachenko Senior Backend Developer в Spryker Systems GmbH 19.04.2014 18:52

вы неверно оперируете О() сложностью.
Она исключительно говорит о количестве повторений цикла алгоритма, пусть на это уходит и 1 час

Відповісти

Підтримати

Apasnuy 19.04.2014 20:02

Какие циклы, о чем вообще речь? Что делать если алгоритм без циклов? Большое О дает верхнюю оценку для количества элементарных операций нужных для выполнения алгоритма в зависимости от размера входных данных. Товарищ не понимает, что размер входных данных в его случае это не только количество множеств а и их размер.

Відповісти

Підтримати

Andrey Tkachenko

Mossberg Solution Architect 19.04.2014 20:33

Товарищ понимает и не такое ;) Но размер множеств для моего солвера не критичен.

Відповісти

Підтримати

Apasnuy 19.04.2014 14:23

m. Ни как не соотносится у них алгоритм эвристиечкий, вот тута написано что это

Там алгоритм недетерминнированный, а не эвристический. Тут можете почитать что это
en.wikipedia.org/...istic_algorithm
en.wikipedia.org/...mputer_science

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 14:27

Солвер в студию и сравним. Один я нашел — те примеры которые были в комплекте с солвером моя программа решает очень быстро, я бы даже сказал что время не растет полиномиально, мои примеры та программа не решает вообще зависает что ли эксепший там что ли (под Мак на С писано), свои примеры она решает медленно и время растет экспоненциально, как мне показалось.

Відповісти

Підтримати

Yuri Bilopolov QA Automation Engineer в Wargaming 19.04.2014 15:22

Все это выглядит в высшей степени странно.
Во-первых, вы занимаетесь проблемой более десяти лет, и при этом у вас нет собственной реализации классического алгоритма, с которым можно было бы сравнивать свои результаты, я правильно понял?
Во-вторых, с чего вы взяли, что кто-то должен верить вам на слово?

Собственно сам алгоритм такой, что должен работать правильно, там нет возможности не правильно решения если оно есть, поверь я с лета 2000 года занимаюсь данной проблемой и понимаю о чем говорю.

По вашему пониманию когда, именно после этих слов, у людей не должно остаться никаких сомнений в верности вашего подхода и правдивости опубликованных вами замеров? Или, быть может, более формальные обоснования тоже имеются?

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 15:29

Во-первых, вы занимаетесь проблемой более десяти лет, и при этом у вас нет собственной реализации классического алгоритма

За чем мне реализация не работающего алгоритма? Во вторых я ведь не точным покрытие занимаюсь а этой тематикой. Точное покрытие я реализовал за последний месяц +/-.

Или, быть может, более формальные обоснования тоже имеются?

Скажем так — можно написать, но пока что в планы не входит раскрытие.

Відповісти

Підтримати

Yuri Bilopolov QA Automation Engineer в Wargaming 19.04.2014 15:33

не работающего алгоритма

спасибо, больше вопросов не имею

Відповісти

Підтримати

Apasnuy 19.04.2014 15:36

Так это моя задача показать, что ваш алгоритм лучше хотя бы парочки уже существующих солверов или ваша?

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 15:45

Ну хорошо, я же говорю, что нашел солвер один здесь: code.google.com/.../downloads/list , больше не нашел, протестил, пришел к выводу что он и рядом не валялся. Если кто то знает солвер лучше чем нашел я, или чем сделал я, пожалуйста покажите. Кстати не плохой солвер предложил reality_hacker, исходник ниже. Правда пока что он проигрывает по памяти очень серьезно.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 14:22

Запостите пример и посмотрим.

Відповісти

Підтримати

Yuri Bilopolov QA Automation Engineer в Wargaming 19.04.2014 09:23

DOU — торт, один эпичный тред за другим :)

Приветствуется критика, и замечания по самому сайту

Английский на сайте очень плохой, думаю, стоит его подтянуть. Это пригодится и в будущем, при общении с коллегами из института Клэя, например.

Відповісти

Підтримати

reality_hacker 19.04.2014 05:36

Я кстати тут набодяжик экспоненциальный солвер на 20 строк, который рвет твой «полиномиальный» в 5 раз на твоем же тесте:

import java.nio.charset.Charset;
import java.nio.file.FileSystems;
import java.nio.file.Files;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
public class ExactCoverSolver {
  static Set<Integer> usedS = new HashSet<>();
  static Set<Long> usedAlphabet = new HashSet<>();
  static List<Set<Long>> S = new ArrayList<>();
  static Set<Long> alphabet = new HashSet<>();
 
  public static void main(String[] args) throws Exception {
    List<String> problemLines = Files.readAllLines(
        FileSystems.getDefault().getPath("sample_big.xct"),
        Charset.defaultCharset());
    for(int i = 1; i < problemLines.size(); i ++) {
      if(problemLines.get(i).startsWith("m")) {
        break;
      }
      Set<Long> subset = new HashSet<>();
      String entries[] = problemLines.get(i).split(" ");
      for(int j = 1; j < entries.length; j ++) {
        subset.add(Long.parseLong(entries[j]));
      }
      S.add(subset);
      alphabet.addAll(subset);
    }
   
    solve(0);
  }
 
  static void solve(int start) {
    if(usedAlphabet.size() == alphabet.size()) {
      System.out.println(usedS);
      return;
    }
    for(int i = start; i < S.size(); i ++) {
      if(!usedS.contains(i) && !usedInAlphabet(i)) {
        usedS.add(i);
        usedAlphabet.addAll(S.get(i));
        solve(i + 1);
        usedS.remove(i);
        usedAlphabet.removeAll(S.get(i));
      }
    }
  }
 
  static boolean usedInAlphabet(int i) {
    for(Long s: S.get(i)) {
      if(usedAlphabet.contains(s)) {
        return true;
      }
    }
    return false;
  }
}

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 09:52

я джаве не спец ине притендую, может быть что делаю не так, но:
C:\Program Files (x86)\Java\jre6\bin>java.exe ExactCoverSolver.java
Exception in thread “main” java.lang.NoClassDefFoundError: ExactCoverSolver/java
Caused by: java.lang.ClassNotFoundException: ExactCoverSolver.java
at java.net.URLClassLoader$1.run(Unknown Source)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(Unknown Source)
at java.lang.ClassLoader.loadClass(Unknown Source)
at sun.misc.Launcher$AppClassLoader.loadClass(Unknown Source)
at java.lang.ClassLoader.loadClass(Unknown Source)
at java.lang.ClassLoader.loadClassInternal(Unknown Source)
Could not find the main class: ExactCoverSolver.java. Program will exit.

Відповісти

Підтримати

reality_hacker 19.04.2014 09:53

Да, ты точно в джаве не спец.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 10:11

дай экзешник

Відповісти

Підтримати

reality_hacker 19.04.2014 10:14

Лучше попробуй набрать:
javac ExactCoverSolver.java
java ExactCoverSolver yourinputfile

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 10:56

Уже разобрался. Хорошая заявка на победу. НО рекурсия не выход, память сжирает, и через несколько часов памяти не хватит даже у меня (32GB). У меня же память не увеличивается! Лови тест.

Відповісти

Підтримати

reality_hacker 19.04.2014 10:58

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

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 11:08

Все равно придется сохранять предыдущие состояние, память тоже будет расти. У меня тоже была такая идея, по-этому знаю о чем говорю. Мало сделать быстрый поиск, надо еще сделать, что бы компьютер смог это переварить. Тот файлик, который я прислал еще не самый тяжелый пример. Как концепт хорошо, но не более, пока что.

Відповісти

Підтримати

reality_hacker 19.04.2014 11:23

Памяти даже при рекурсии нужно O(n), где n — это множество подмножеств, т.е. в терминах О оверхеда по памяти в моем концепте нету.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 11:33

Через 45 минут, у меня 22Мб, у тебя 370Мб, пока писал у тебя уже 430Мб, у меня без изменений.

Відповісти

Підтримати

reality_hacker 19.04.2014 11:34

Джава памяти ест по максимуму сколько ей дай, а когда уже не хватает запускает уборщик мусора.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 12:01

Неа. GC запускается регулярно, скажем так чаще чем раз в минуту, и это я думаю для 1-го поколения, для нулевого там раз в секунду или чаще. Даже если ты прав то по умолчанию, если я правильно понял, памяти 512Мб может не очищать, но уже 570Мб используется. Более того плагин VisualGC показывает что память чистится на «ничего не делающей» VM. К сожалению пока не понял как подключиться к процессу который выполняется как class, не хочется останавливать и перезапускать.

Відповісти

Підтримати

Anatoli Koutsevol 19.04.2014 05:35

Залил пример в 30 строк с того же сайта, но в ответ ни гу-гу. Бегло взглянул на код генератора тестов, но к ночи этого делать не стоило.

Відповісти

Підтримати

reality_hacker 19.04.2014 05:38

Я так понял солвер не выставлен онлайн, там товарищ на своем компутере его руками запускает и потом руками же отсылает результат, боится что хакеры украдут его гениальный гавнокод.

Відповісти

Підтримати

Anatoli Koutsevol

Anatoli Koutsevol 21.04.2014 04:56

Ага. Киборг-убийца смысла.

Відповісти

Підтримати

Mossberg Solution Architect 21.04.2014 12:34

Дело в том что хостинг сам по себе слабый, в смысле проц медленный и памяти маловато, боюсь что он-лай в принципе не возможно. Что то считать будет, что то нет.

Відповісти

Підтримати

Anatoli Koutsevol

Gabriel Angelos 21.04.2014 12:35

Плохому танцору всегда что-то мешает.

Відповісти

Підтримати

Mossberg Solution Architect 21.04.2014 12:42

Сделай лучше!

Відповісти

Підтримати

Gabriel Angelos

Gabriel Angelos 19.04.2014 01:56

Неясна цель — это самопиар или что?
Вам дадут премию Тьюринга?

Приветствуется критика, и замечания по самому сайту.

сайт — дерьмо, неудобный и сверстан совершенно странно, наполнение куцее.

что бы проверить правильность работы, кто будет постить тесты, удаляйте пожалуйста все что после строки с маркером «m», включая саму строку.

бугага, нет валидации входных данных — подход на ура. Самому лень обрезать маркер?

исходный код выковыривать файлики из zip — очень профессионально, видимо .NET девелоперы не эволюционируют до github/bitbucket-а.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 02:25

сайт — дерьмо, неудобный и сверстан совершенно странно, наполнение куцее.

не конструктивно

бугага, нет валидации входных данных

где именно?

исходный код выковыривать файлики из zip

в zip — только то что можно скачать с сайта, что не так?
могу разместить те исходники на github не вопрос.

Відповісти

Підтримати

Gabriel Angelos

Gabriel Angelos 19.04.2014 02:30

сайт — дерьмо, неудобный и сверстан совершенно странно, наполнение куцее.
не конструктивно

где хотя бы блок-схема алгоритма?
Я уже не говорю о подробностях реализации, которую тоже было бы неплохо разместить на сайте.

где именно?

тут:

что бы проверить правильность работы, кто будет постить тесты, удаляйте пожалуйста все что после строки с маркером «m», включая саму строку.

и тут:

0 — быть не должно в данных строк, минимум цифра 1, генератор теста ведь этого не позволяет сделать.

и наверняка где-то еще.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 02:37

где хотя бы блок-схема алгоритма?
Я уже не говорю о подробностях реализации, которую тоже было бы неплохо разместить на сайте.

не уверен что буду публиковать

тут:
что бы проверить правильность работы, кто будет постить тесты, удаляйте пожалуйста все что после строки с маркером «m», включая саму строку.

собственно для этого и дал исходник, правь как хочешь, может в отдельный файл сохранить решение. у меня файл читается без проблем. Но как то не хорошо будет если я получу решение. Хотя оно у меня у ни как не используется. Сделал что бы проверить просто было результат работы.

и тут:
0 — быть не должно в данных строк, минимум цифра 1, генератор теста ведь этого не позволяет сделать.

да согласен надо сделать валидацию. работы еще не початый край, главное что алгоритм работает.

Відповісти

Підтримати

Gabriel Angelos

reality_hacker 19.04.2014 01:30

Засунул небольшой файлик на 8 килобайт (по сравнению с 300МБ файлами в твоих тестах), уже 15 минут жду (вместо обещаных секунд), ответа все нету. ЧЯДНТ?

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 02:18

0 — быть не должно в данных строк, минимум цифра 1, генератор теста ведь этого не позволяет сделать.

Відповісти

Підтримати

reality_hacker 19.04.2014 02:20

О, а вот и валидация данных, через форум с часовой задержкой. Сейчас перезальем

Відповісти

Підтримати

reality_hacker 19.04.2014 02:22

Перезалил, жду с нетерпением

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 02:33

готово

Відповісти

Підтримати

reality_hacker 19.04.2014 02:36

Ты как и ожидалось какую то хню прислал.
1. По формулировке задачи ты должен прислать мне подмножество моих строк, ты прислал какие то свои сгенерированные.
2. По условию задачи твой результат должен покрывать все множество X, твой результат содержит только числа до 200, мой датасет содержит числа до 1000 включительно.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 02:39

Ошибки нет. Это номера строк. Которые содержат числа, от 1 до 1000. Если взять все эти строки то получится покрытие множества от 1 до 1000.

Відповісти

Підтримати

reality_hacker 19.04.2014 02:42

Ок, продолжаем дальше, в твоем результате строки 2 и 11 содержат одно и тоже число 666 — по условию задачи такого быть не должно.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 10:10

Строки считаются с нуля.

Відповісти

Підтримати

reality_hacker 19.04.2014 10:11

Да, я уже сам дошел до этого

Відповісти

Підтримати

Andrey Tkachenko Senior Backend Developer в Spryker Systems GmbH 19.04.2014 18:59

Откуда столько ненависти?

Відповісти

Підтримати

reality_hacker 19.04.2014 20:38

Что ты куриш?

Відповісти

Підтримати

Andrey Tkachenko

reality_hacker 19.04.2014 00:32

А как можно узнать что твой алгоритм всегда выдает правильный ответ?

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 00:40

Два аргумента: 1) я сделал очень много тестов, их результаты будут выложены на сайте на странице «Practical Results», просто руки не доходят это сделать. Все тесты завершились положительно. 2) Собственно сам алгоритм такой, что должен работать правильно, там нет возможности не правильно решения если оно есть, поверь я с лета 2000 года занимаюсь данной проблемой и понимаю о чем говорю. Кроме того просто сделай тест и пришли мне, ответ будешь знать только ты, если я дам тот же самый значит алгоритм правильный. Пока почему то ни кто не прислал, не понимаю почему.

Відповісти

Підтримати

reality_hacker 19.04.2014 00:42

вот была великая теорема ферма, и вроде и все тесты проходили, а математики все равно не могли успокоится, и 350 лет пытались строго ее доказать. К чему бы это?

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 00:49

Ферма не имеет сама по себе практического смысла.

Відповісти

Підтримати

reality_hacker 19.04.2014 00:55

Может быть, но речь идет о том что говорить что алгоритм правильный только на базе тестов без какого то формального доказательства в математическом обществе выглядит немного по дыбильному

Відповісти

Підтримати

Paul Loyanich CTO в CoreDev 19.04.2014 15:15

Ферма не имеет сама по себе практического смысла.

Как-как? Нет, серьезно, вы можете это вот так написать — «теорема ферма не имеет сама по себе практического смысла»? Чтобы не было двусмысленных толкований предыдущей фразы.

Відповісти

Підтримати

reality_hacker 19.04.2014 20:39

Замечу что имелась в виду большая теорема Ферма, я например тоже не в курсе какой от нее практический смысл.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 20:44

К сожалению мотивация для работы на Ферма может быть разве что у математика теоретика, для какой нибудь докторской работы ну или там ради славы потому что больше делать нечего. А на практике уравнение вычисляется на калькуляторе с точностью достаточной для любых реальных вычислений.

Відповісти

Підтримати

Apasnuy 19.04.2014 21:16

Теорема Ферма косвенно повлияло на изучение эллиптических кривых. Если бы не было такого интереса к теореме Ферма кто знает на какой бы стадии сейчас было доказательство гипотезы Таниями-Шимуры.

Відповісти

Підтримати

Mossberg Solution Architect 19.04.2014 15:17

Да разработанный при ее решении математический аппарат может быть весьма полезен.

Відповісти

Підтримати

Paul Loyanich CTO в CoreDev 19.04.2014 15:56

Дмитрий, я немного побуду буквоедом
Во-первых — не «решении», а «доказательства».
Во-вторых — не «при», а «для».
И еще — под каждым сообщением есть ссылка «Ответить». Если на нее нажать, то ответ будет опубликован сразу под сообщением — «лесенкой», это удобнее для восприятия.

А вообще — удачи вам побыстрее все провернуть и опубликовать код. Если ваше решение верно, значит есть ненулевая вероятность того, что кто-то где-то втихую уже пользует похожее и это немного пугает.

Відповісти

Підтримати

Roman Labish CTO & Co-Founder в CodeGeeks Solutions 18.04.2014 23:09

Досить цікаво) але думаю, якщо ти хочеш щоб тобі її спробували «зачаленджити» — краще запость на codeforces.ru або topcoder.com/tc

Відповісти

Підтримати

Mossberg Solution Architect 18.04.2014 14:07

Коментар порушує правила спільноти і видалений модераторами.

Підписатись на коментарі

Ваша пошта

Не підписуватись