Здравствуйте дамы и господа. У меня не получается решить вот эту задачу 306B - Optimizer и то не в первый раз. В тегах написано ,то что это задача на жадный алгоритм , но как их решать — я не знаю. Объясните , пожалуйста , как решаются задачи такого рода ? Заранее благодарен.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 160 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | Dominater069 | 154 |
| 8 | awoo | 154 |
| 10 | luogu_official | 151 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 11:12:38 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
Нельзя объяснить, "как решаются задачи такого рода". Потому что это задачи, а не упражнения. "жадный алгоритм" — это лишь одна из идей, которые используются при решении задачи, это не значит, что знание, что задача решается жадным алгоритмом, делает задачу очевидной.
Как решать задачу, пока не придумал.
Жадный алгоритм — применяем на каждом шаге оптимальное решение по некоторому критерию. Навскидку, не знаю верно или нет — сортируем отрезки по возрастанию li (конца отрезка), бежим по всем отрезкам, и каждый раз когда можно отрезок удалить согласно условиям — удаляем.
Хватанёте лишнего, например, в случае
3
1 4
2 4
3 4
Нет. Не хватану. :) Будут убраны отрезки 3,2..4,3..4 Удаление второго не пройдет по ограничениям.
Товарищ, вообще-то здесь надо удалить один отрезок — второй. Это три отрезка длины 4.
Нужно выбросить максимальное количество команд, а не оставить. Я и привожу алгоритм выбрасывания максимального количества команд — трех команд.
Здесь максимальное количество команд, которые можно выбросить — одна. А именно, вторая.
Вторая команда покрывает все значения. Выбросить максимально можно три команды — все кроме второй. "Задача оптимизатора программы Поликарпа — выбросить максимальное количество инструкций из его программы так, чтобы оставшиеся инструкции установили значение 13 в тех и только тех байтах памяти, что и программа до оптимизации."
Товарищ, читайте условие. 3 — это n, количество инструкций. Далее следуют три (!) инструкции, каждая из них имеет ДЛИНУ четыре, и начинаются они в точках 1, 2 и 3.
Да, спасибо. Я старый уже, читаю невнимательно :)
Только проверка перебором не войдет в ограничения. Нужно например дерево отрезков на минимум.
Пройдёт, ведь каждый отрезок мы переберём один раз.
То есть решаем задачу от обратного, выбираем какие оставить?
Изначально в моём решении все отрезки в статуе "непросмотрены". Потом каждый из них приобретает статус "взят" или "выброшен".
Да, понял.
Тогда получается что просто каждый раз оставляем отрезок с максимальным концом, и если их несколько, то максимальной длиной.
А, понял.
3.
Дальше будем перебирать все инструкции по порядку, и каждую брать или отклонять. Для начала берём самую первую нерассмотренную инструкцию (изначально это просто самая первая). И запоминаем, что мы обеспечили заполнение памяти до места pos = a_i + l_i.
4.
a. Если ещё есть инструкции, у которых a_j <= pos, то перебираем их всех и оставляем ту, у которой a_j+l_j максимально. Её добавляем в отмет, остальные отбрасываем, обновляем pos = a_j+l_j. Снова переходим к пункту 4.
b. Если таких инструкций нет, то забываем pos и переходим к пункту 3.
Удобно писать подобное с помощью стека, если правая граница текущего отрезка больше чем текущая правая граница, то закинем в стек(предварительно POP-ая отрезок на вершине стека, пока этот отрезок лежит в объединении добавленного отрезка и предпоследнего отрезка в стеке), иначе игнорим его. Несложно показать, что это находит оптимальное решение. 3722543
Рассмотрим самую левую из всех покрытых точек L. Естественно, это точка является началом какого-то отрезка, и для того чтобы ее покрыть нужно включить в ответ какой-либо из отрезков, начинающихся в этой точке. Очевидно, что выгоднее всего будет выбрать тот из них, который имеет наибольшую длину. Пусть мы выбрали отрезок [L,R]. Тогда все отрезки, целиком в него входящие, можно выбросить за ненадобностью, а отрезки [L1,R1] имеющие с ним пересечение (т.е. L < L1 < R < R1) урезать до [R,R1]. После этого получаем ту же задачу с меньшим числом отрезков и самой левой точкой >= R. Продолжаем применять описанную процедуру пока не покроем все интервалы.
Проделать это все удобно, если предварительно отсортировать все отрезки по левому концу, и при равенстве по длине. Тогда, в течение одного прохода, мы будем либо добавлять к ответу текущий отрезок, если он не покрывается предыдущим выбранным, либо игнорировать.
http://mirror.codeforces.com/contest/306/submission/3720123 Извиняюсь что код не отформатирован.
Сортируем все отрезки в порядке возрастания начальной ячейки. И в цикле - пропускаем все которые заканчиваются на уже покрытом отрезке. Для первого которые выходит за покрытый отрезок смотрим начало. Если оно дальше чем уже покрытый отрезок, то за точку старта берем его. Если не дальше, то за точку старта берем ячейку сразу за уже покрытым отрезком. Перебираем все команды начало которых не дальше чем точка старта, и выбираем среди них тот, который заканчивается дальше. и т.д. Решается в один проход, за O(m) Информация о n, и сбор данных о покрытых ячейках — в решении не нужно.
UPD. общая сложность (m*log m), за счет сортировки массива команд.
Покрытый отрезок — последний покрытый отрезок. Отрезок, который покрывает последняя оставленная команда.
Моё решение таково: Представим каждую команду как скобки (). Левая скобка — a[i], правая скобка — a[i]+l[i]-1.
1) Уберём все скобки, которые вложены в другие.
2) Заведём массив длины n, элементы которого будут хранить количество скобок, которые "покрывают" этот элемент.
3) Скобки, которые покрывают элементы, в которых записана единица, являются "нужными" — их удалить нельзя.
4) Остались скобки, которые не "покрывают" единицы. Понятно, что эти скобки лежат на пересечении с "нужными". Поступим жадно. Уберём все скобки, кроме нужных. Будем пытаться "заделать" пустое пространство между ними наиболее длинными скобками. Пометим эти наиболее длинные скобки как "нужные".
5) Все скобки кроме нужных — есть ответ.
Длинно, некрасиво, но думаю такое решение имеет место быть.