Олимпиадное хобби. Задача об утилизации отходов

    Привет. С вами олимпиадное хобби. Здесь мы выбираем себе олимпиадную задачу по программированию, разбираем ее, вырабатываем возможные пути решения и реализовываем задуманное, после чего отправляем на суд. Нам потребуется знание одного из языков программирования: c, c++, java, pascal, терпение, ловкость и базовые знания английского языка, чтобы понимать условие задачи, хотя последний пункт необязателен, ведь я вольно перескажу условие на русском языке.

    Вы не забыли размяться? Если забыли, то быстренько разминайтесь, и возвращайтесь к нам.

    Напоминаю, что я беру задачи с сайта http://uva.onlinejudge.org, и сегодня случайный выбор пал на задачку под номером 154 — задачу об утилизации отходов.

    Краткий перевод условия задачи (вольный перевод):

    В Новую Зеландию прибыла технология сбора мусора Kerbside. Пять мусорных корзин разных цветов: красный (red), оранжевый (orange), желтый (yellow), зеленый(green) и синий (blue), в которые определены 5 видов отходов: пластиковые отходы (Plastic), стеклянные (Glass), алюминиевые (Aluminium), стальные(Steel) и бумажные (Newspaper). К сожалению, никакой координации между городами не было, поэтому каждый город поставил в соответствие цветным корзинам произвольный вид отходов. Теперь, когда правительство смогло решить все маловажные задачи (вроде реорганизации здравоохранения, соц. обеспечения и образования), оно решило заняться другими проблемами. Министр охраны окружающей среды представил в парламент документ о регулировании соответствия видов отходов цветными корзинами, но для этого ему необходимо выбрать собственное распределение отходов по цветам. Будучи сторонником демократии, он исследовал все города, которые используют Kerbside. С помощью полученных данных он хочет выбрать город, чья схема соответствия видов отходов цветным корзинам (будучи распространенной по всей стране) вызовет наименьшее количество изменений. Размер города не имеет значения, согласно демократии: 1 город — 1 голос.

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

    Входные данные: серия блоков. Каждый блок будет содержать несколько строк, выражающих распределение видов отходов по цветам, по 1 строке на каждый город. Городов может быть до 100. Каждый блок оканчивается строкой, начинающийся с символа «e». Конец входных данных ознаменуется строкой из одного символа "#".

    Выходные данные: На каждый входящий блок необходимо вывести порядковый номер города, чью схему распределения стоит выбрать в качестве эталона.

    Пример входящих данных:
    r/P,o/G,y/S,g/A,b/N
    r/G,o/P,y/S,g/A,b/N
    r/P,y/S,o/G,g/N,b/A
    r/P,o/S,y/A,g/G,b/N
    e
    r/G,o/P,y/S,g/A,b/N
    r/P,y/S,o/G,g/N,b/A
    r/P,o/S,y/A,g/G,b/N
    r/P,o/G,y/S,g/A,b/N
    ecclesiastical
    #

    Результат:
    1
    4


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

    Первый вариант (неверный) решения этой задачи, который мне пришел в голову почти мгновенно, таков:
    1. Выбираем по каждому цвету вид отходов, который представлен данным цветом в максимальном количестве городов
    2. Создаем схему соответствия цветов видам отходов, которые были выбраны в 1 пункте
    3. Выбираем город, чья схема распределения видов отходов по цветам максимально похожа на схему из пункта 2

    К сожалению, оказалось, что такое решение неверно, хотя бы потому, что иногда встречаются города с одинаковой схожестью с эталонной схемой (выбранной в пункте 2). Вот вам контрпример:
    r/P,o/G,y/S,g/A,b/N
    r/P,o/S,y/A,g/N,b/G
    r/S,o/G,y/P,g/N,b/G
    r/A,o/S,y/P,g/N,b/G
    r/G,o/S,y/P,g/A,b/N

    Эталонная схема согласно пункту 2:
    r/P.o/S,y/P,g/N,b/G

    Второй и четвертый города одинаково похожи на выработанную схему, теме не менее, при выборе города №4 число изменений в остальных городах меньше, чем при выборе города №2.

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

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

    Каждый город необходимо сравнить со всеми остальными, причем сравнений будет 5, по каждому цвету, т.е. 5(n-1) сравнений на каждый город, где n — количество городов. В сумме выходит 5n(n-1) сравнений на все города. Если принять во внимание тот факт, что городов не больше 100, то число сравнений не превосходит 5*100*99=49500. Операции сравнения также будут сопровождаться операциями наращивания счетчика различия каждого города. Но даже в сумме, при наихудших условиях, число операций не превысит 49500 сравнений и 49500 операций прибавления единицы. Становится ясно, что наш алгоритм выполнится за очень короткий промежуток времени даже на самых сложных тестах.

    Попробуем посчитать число отличий для одного из примеров и предыдущего контрпримера к варианту решения №1:
    Схема Число отличий от других городов
    r/P,o/G,y/S,g/A,b/N
    r/G,o/P,y/S,g/A,b/N
    r/P,y/S,o/G,g/N,b/A
    r/P,o/S,y/A,g/G,b/N
    1+2+1+2+1 = 7 < — лучший вариант
    3+3+1+2+1 = 10
    1+2+1+3+3 = 10
    1+3+3+3+1 = 11
    r/P,o/G,y/S,g/A,b/N
    r/P,o/S,y/A,g/N,b/G
    r/S,o/G,y/P,g/N,b/G
    r/A,o/S,y/P,g/N,b/G
    r/G,o/S,y/P,g/A,b/N
    3+3+4+3+3 = 16
    3+2+4+2+2 = 13
    4+3+2+2+2 = 13
    4+2+2+2+2 = 12 < — лучший вариант
    4+2+2+3+3 = 14

    Собственно остается реализовать задуманное и нести к судьям. А здесь мое решение на C++.

    Accepted (0.012). Удачи!
    Поделиться публикацией

    Комментарии 35

      +6
      Если городов ОЧЕНЬ много, ответ мог бы быть такой.
      Пять-факториал — это совсем немного. Так что берём 120-местный массив и заполняем, сколько голосов отдано каждому из 120 вариантов. А затем уже проходом по этому массиву выясняем, кто победитель, макс. 120^2.

      Если городов мало (до 100), вероятно, ваш (лобовой) ответ действительно лучший.
        0
        Отличный вариант решения, большое спасибо. Сначала пугал алгоритм поиска победителя по вашему массиву, но разобрался и все встало на свои места.
        +1
        Для тех, кто легко справился с этой задачей, хочу предложить еще одну, которая когда-то мне очень понравилась.
        Есть N ящиков. Для каждого ящика известены w и p.
        где:
        w — вес ящика.
        p — вес который способен выдержать ящик не будучи раздавленным
        (вес ящика(ов), который можно поставить на него).

        Задача — построить башню из ящиков максимальной высоты.
          0
          Почему-то напомнило задачу про монеты, суть сводится к следующему:
          Есть монеты номиналом N1...Nk.
          Надо узнать, можно ли этими монетами набрать сумму M.

          Но возвращаясь к ящикам, я пока представляю только способ решения «в лоб», полным перебором…
            0
            Очень бы хотелось услышать решения, альтернативные моему.
            (это не полный перебор)
              0
              Есть подозрение, что ваша задача решается только полным перебором. Более красивых решений, пока, к сожалению, вывести не удается
              • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  Не подходит.
                  Нужно вниз ставить самый тяжёлый и самый стойкий.
                  Сортируем по p * w, убираем хрупко-тяжелые, пока не добъёмся условия задачи
                    0
                    Ваши решения не подходят. Как я ниже написал, задача сводится к задаче о рюкзаке.
              0
              Это задача сводится к задаче о камнях. (Есть n камней с массами M1,…, Mn нужно сказать, можно ли их разложить на 2 кучки равной массы)

              Известно что это NP полная задача. NP полная означает, что если вы найдёте для неё полиномиальное решение (т.е. не полный перебор), то вы докажете что P = NP, тем самым решите одну из важнейших задач человечества)

              Могу сразу сказать, что почти все учёные принимают на веру что P != NP. Только не знают как доказать. Так что, в принципе, полиномиального решения вы не найдёте. Можете не ломать голову)
              0
              Хотя вот интересная мысль пришла в голову:
              Решаем с помощью мультиграфа.
              У нас есть N вершин, каждый ящик — вершина.
              На 1м этам мы соединяем дугами только те ящики, которые могут выдержать друг друга, т.е. если ящик i выдерживает ящик j, то такая дуга есть. Каждую дугу мы при этом маркируем уникальным номером.
              На 2м этапе мы добавляем те дуги, цепочки которых нам позволят выдержать высоту в 2 ящика (вершины i->j->k), при этом мы эти 2 дуги (i->j и j->k) маркируем одним номером.
              На 3м — по аналогии, получаем цепочки, способные выдержать высоту 3 ящика (все дуги имеют один номер).
              И так далее, пока не окажется, что на следующем шаге мы теряем все дуги.

              Полученные цепочки с одним номером дуг и будут нашими башнями.

              Осталось рассмотреть частные случае, вроде когда из 1й цепочки получается 2 и более (скажем, на 2 ящика можно поставить 3м еще 2 разных ящика).
              Но в этом случае мы можем записать обе цепочки длиной 3 независимо друг от друга.

              В 1м приближении решение выглядит так. Завтра может дополню изображениями.
                0
                В фразе «Осталось рассмотреть частные случаи, вроде когда из 1й цепочки получается 2 и более» и кроется сложность задачи.

                А если из одной цепочки получается 10 или более? и так на каждом шаге?

                Представьте, что у вас 100 ящиков. Их вес колеблется от 1 до 10, а грузоподъемность от 100 до 200. Тогда получится, что башню высоты 10 можно построить из любых 10 ящиков, а это даст C(m,n) башен при n=100, m=10

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

                  К сожалению, в задаче есть некоторая детерминированность — если возможны 2 разных ответа, то по условию можно вывести только 1 вариант.
                  Если же нам надо вывести все возможные варианты — то в Вашем же примере так или иначе придется полностью перебрать все варианты.
                    0
                    Ясно, что если выводить все варианты, то их все нужно сгенерировать, а это — полный перебор. Поэтому в условии сказано — построить башню максимальной высоты. Т.е. достаточно вывести номера ящиков любой башни, высота которой равна максимальной.
                  0
                  Хотелось бы услышать ваше сведение данной задачи к задаче о рюкзаке
                • НЛО прилетело и опубликовало эту надпись здесь
                    0
                    Задача легко решается за O(N^2)
                    Добавим к p для каждого ящика его w. Теперь несложно доказать (но мне влом писать), что существует оптимальная башня в которой ящики идут сверху вниз в порядке возрастания p. Теперь посчитаем следующую динамику — какой наименьший вес имеет башенка из i ящиков если ящики можно выбирать из j первых. Пересчет очевиден.
                      0
                      Ваша предпосылка:
                      оригинал egork:
                      существует оптимальная башня в которой ящики идут сверху вниз в порядке возрастания p

                      не верна. Контрпример:
                      p    4   4   5   6  7
                      w    6   1   1   1  1


                      Я дал ссылку на статью в википедии. Посмотрите пункт «Задача о ранце с возможностью единичного выбора предмета». Примите стоимость предмета за 1. Добавляется дополнительное сравнение веса уже выбранных ящиков с P текущего ящика.
                        0
                        а вы заметили, что я к p прибавил w?
                          0
                          И да, задача о рюкзаке, где ценность всех предметов 1 — вполне себе решается :)
                            0
                            оригинал egork:
                            И да, задача о рюкзаке, где ценность всех предметов 1 — вполне себе решается :)

                            Само собой.

                            оригинал egork:
                            а вы заметили, что я к p прибавил w?

                            Вам следует ясней выражаться. Но вы правы. Ящики в оптимальной последовательности действительно будут расположены в порядке неубывания p+w (и в порядке неубывания p внутри групп с одинаковым p+w). Доказывается это действительно легко, по индукции. Ваше решение верное, и оно подтверждает утверждение, что эта задача является частным случаем задачи о рюкзаке.
                            В общем, вы молодец, поздравляю.
                          0
                          Все верно.
                          Сначала сортируем ящики по (p+w), затем динамикой получаем самое большое подмножество — это и будет ответ.

                          Доказательство не сложное — желающие могут потренироваться.
                          0
                          Ну я бы решал ее методом динамического программирования — рекурсия с запоминанием (кэшем).
                          Для каждого ящика ищем максимальную цепочку ящиков над ним с помощью рекурсии, и потом выбираем самую длинную. Алгоритм будет быстрый так как уже вычисленные данные будут просто в памяти.
                        • НЛО прилетело и опубликовало эту надпись здесь
                            +1
                            Ушёл решать
                              +3
                              Автор, извините, но мне ваша статья не понравилась. Заходя под кат я надеялся увидеть или сложную, действительно «олимпиадную» задачку, или простую задачку, но с неординарным решением, в общем, хоть что-то. В результате получил простую задачу решённую очевидным способом «в лоб». Возможно, я не прав, но что тогда вы хотели донести до читателей?
                                0
                                Я хотел развлечь тех, кому немного скучно, а клавиатура «чешется». Поверьте, не у всех такой скилл программирования олимпиадных задач, как у вас. Тем более задачу я выбирал случайным образом.
                                  0
                                  Автор, так держать. Мне твои статьи две последние статьи нравятся.
                                0
                                Не очень понятны качественные критерии решения. Чтобы в принципе работало? Ограничений на память и количество проходов нет?

                                Тогда очень простое в отладке и однозначное решение, хоть и объемное.
                                Поскольку данные упорядочены и по условию всегда фаворит, делаем хеш-массив [пара => сколько раз встречалось]. Т.е. ( r/P => 5, o/S => 3 ) и т.п.

                                Затем сформировать массив самых частотных сочетаний, только чтобы первая буква была уникальной. Это будет идеальная расстановка.
                                По каждому городу функция близости к идеальной расстановке — сколько из идеальных сочетаний нашлось в данном городе.

                                Опять же, помня, что есть явный фаворит из условия и возможность прочитать все в память и несколько раз пройти. Сейчас накидал решение на php — совпадает. Еще тестовые данные есть? :)
                                  0
                                  Проверка проводится по ряду тестов на сервере. Есть ограничение по времени работы программы (3 секунды), ну и наверное ограничение на память, хотя в условии об этом не говорится. Эта задача действительно достаточно простая, поэтому тут трудно превысить лимит времени или памяти. Здесь важно учесть все возможные подводные камни.
                                  Рекомендую вам свое решение перекинуть на C++, java или Pascal и отнести на проверку, сразу станет ясно насколько оно удачно.
                                    0
                                    Мне нравиться, как на gcj — оно тебе сгенирировало 300КБ городов и уже у себя сиди, решай. Есть 8 минут. Правда, для такой задачи условия были бы: есть n корзин, m городов, k проверок

                                    Ограничения:
                                    Часть А {n = 5, m <= 100, k = 100}
                                    Часть B {n = 25, m <= 10000, k = 100}
                                  0
                                  А вот не нужно каждый город с остальными сравнивать, ибо это сложность O(n^2).

                                  Достаточно заполнить матрицу 5х5, где строчки будут — цвета корзин, а столбцы — типы отходов. На пересечении целое число — кол-во городов, в которых в N'ом цвете корзины M'тый тип отходов.

                                  Заолняется матрица за линейное время, отличия в городе по ней считаются тоже линейно (О(n)).
                                    0
                                    Автор, давай что-нибудь на динамическое программирование, чтобы на самом деле мозги размять)
                                      0
                                      Спасибо, задача несложная, но интересно было :) Решил вторым способом.

                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                      Самое читаемое