Блог пользователя stas99

Автор stas99, 9 лет назад, По-русски

Здравствуйте! Есть такая задача: Есть объекты, их нужно распределить на 2 множества. Вводятся условия типа эти 2 объекта точно лежат/не лежат в одно множестве. Нужно такие запросы обрабатывать в онлайн и проверять на противоречивость. И еще нужно уметь по запросу выводить корректный пример разбиения. Хочу предложить такой метод решения данной задачи: Создадим СНМ из 2*n множеств. Каждой вершине соответствуют 2 множества 2*i и 2*i+1. В множестве 2*i лежат вершины которые точно находятся в одном множестве с i, а в множестве i*2+1 те, которые точно не в одном множестве с i. Таким образом утверждается что запрос "вершины a и b лежат в одном множестве" сводится к unite(a*2, b*2) и unite(a*2+1, b*2+1). А запрос "вершины a и b не лежат в одном множестве" сводится к unite(a*2, b*2+1) и unite(a*2+1, b*2). Утверждается, что при этих операциях свойство про то, что в множестве 2*i лежат вершины которые точно находятся в одном множестве с i, а в множестве i*2+1 те, которые точно не в одном множестве с i, будет соблюдаться, т.к. несложно заметить, что i*2 и i*2+1 всегда имеют одинаковые ранги. Вот исходный код решения: http://pastebin.com/6z1dvy2Q. Что вы думаете по этому поводу? Существуют ли альтернативные алгоритмы? Можно ли решить задачу быстрее(обязательно онлайн)?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

Автор stas99, 10 лет назад, По-русски

Здравствуйте! Я недавно решил попрактиковаться в Java и решить простую задачу про выпуклую оболочку. Мое решение на С++ работает за 0.006 на макс. тесте, А на Java изначально — 0.644, после оптимизаций — 0.373. Мне кажется, что это слишком большая разница (ну не может быть java в 50 раз медленнее! Они утверждают, что Питон за 0.081 заходит!). Прошу вас мне помочь в поиске способа довести решение на java до адекватного времени работы. Сама задача: http://informatics.mccme.ru/mod/statements/view3.php?id=634&chapterid=638#1 Решение на С++: http://pastebin.com/L69S2vGx Решение на Java: http://pastebin.com/HnyTqMuF Заранее благодарен всем за вашу помощь.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится