Уже через 10 минут начинается очередной СРМ. Как-то странно никто еще не создал пост. Давайте после контеста обсудим здесь задачи.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
Как 500-ку решать?
Почти как угодно с запоминанием. Например так.
Считаем динамику. Минимальная строка из первых (r-l+1) символа, которая 1. Больше отрезка [l;r] 2. Не меньше отрезка [l;r] 3. Любая по отношению к отрезку [l;r]
Понятно что эти три класса эквивалентны по дальнейшим действиям, поэтому из них надо брать минимальную.
Пусть у нас есть строка из цифр и '?'. Научимся за куб от длины выяснять, можем ли мы ее выложить данной колодой (вопросик означает, что на это место можно положить любую цифру). Перебираем куда положить верхнюю карту колоды, внутри динамика за квадрат — храним можем ли мы получить отрезок строки [l,r), используя верхние r-l карт колоды. Переходы очевидны. Если хотя бы для одного положения верхней карты получили D[0][len]=true, то строку выложить можно, иначе нет.
Теперь делаем стандартный поиск по ответу. Пусть lb — данная нам строка. Пока мы не можем ее получить, увеличиваем последний "не вопросительный" разряд, как только доходим до '9', меняем ее на '?' и переходим к следующему (при этой операции у нас число все время увеличивается). Если в какой-то момент нам надо увеличить несуществующий разряд, то надо вывалиться и сказать No Solution. Иначе в какой-то момент мы научились получать нашу новую строку lb (правда, в конце у нее несколько вопросиков). Теперь пробегаемся по вопросикам слева направо и перебираем для каждого можем ли мы поставить '0', '1' и т.д. Выбираем наименьший возможный вариант. То, что получилось в итоге — это ответ.
У меня такое же решение.
Эта часть делается за квадрат — нет нужды отдельно перебирать куда положить верхнюю карту.
Лучше расскажите как решать 1000.
Построить сеть из данного графа, добавив в него ребра из стока и истока в выделенные вершины очевидно неверно, и это совсем легко валится.
Запустить один поток, зафиксировать запустить другой тоже. Хотя устойчивым к перенумерации вершин тестом я это валить не научился.
почему-то многие писали послный треш. на что надеялись, интересно)
Я написал поток, осознал что он неправильный. Добавил немного треша и подумал что у кого-то будет халявный челлендж,но никто этой возможностью не воспользовался.
Очень хороший треш при наличии удачи иногда проходит, особенно в такой задаче) А +50 у кого-нибудь в комнате обычно большой роли не играет, а вот еще их может и не быть, а еще многие могут и -25 получить.
Судя по авторскому решению в практис руме, достаточно запустить код любого из участников 2 раза: один раз для (a1, a2) и (b1, b2), а второй раз для (a2, a1) и (b1, b2). Если оба раза ответ "Yes", то возвращаем "Yes", иначе — "No".
Не понятно, что при этом меняется. Как это работает на таком тесте: 1 2 N 2 7 N 3 4 N 3 6 N 3 7 O 5 6 N 7 8 N a1 = 1, a2 = 4, an = 50 b1 = 5, b2 = 8, bn = 50 Вроде с какой стороны не запускай поток все насытит и скажет Yes
!!!!!! ААА!!!
Впервые в жизни я написал авторское решение и не посабмитил его, думал подарю кому-то +50. Жадность сгубила меня!!!
а почему это так, можешь рассказать строго?
В моей комнате человек решал 250 так: обойдем граф бфсом и из достижимых выберем подмножество с наибольшим ксором. Казалось бы, это неправильно, но я не могу придумать тест. Кто-нибудь знает как такое ломать или это правильно?
Прошло? Или все-таки неправильно?
Таки упало. На таком тесте:
Я пока не понял, рандом ли это.
UPD: очевидно, это просто другие баги
Я тоже не придумал за челендж. Авторский тест который свалил такое же у меня в команте — цикл с какими-то непонятными числами. Вообще логично. На цикле видимо получается либо любые две точки либо отрезок.
У меня в комнате такое прошло.
можно дойти из 0-й вершины до любой достижимой и вернуться обратно. Тогда эта достижимая будет взята 1 раз, а остальные — 0. (и так с каждой достижимой вершиной; в нулевую в последний раз можно не возвращаться.)
А, да, клево, спасибо. Что-то я протупил.
Это правильно. Пусть есть простой путь 1 -> 2 -> 3 -> 4 -> 5. Тогда выберем последнюю вершину, которая должна быть в множестве с наибольшим ксором (пусть это 4) и сделаем так 1 xor 2 xor 3 xor 4 xor 3 xor 2 xor 1 (пройдем до нее и обратно). Очевидно, в общую ксор-сумму добавится только значение этой вершины. Если нужно добавить первую вершину, в конце в нее не возвращаемся (доходим только до 2й). Таким способом можно добавить любое множество вершин из простого пути. Если у нас есть несколько веток, выходящих из одной вершины, добавим все нужные вершины из каждой из них по отдельности. Очевидно, это обобщается на произвольное дерево.
Что-то я перемудрил с деревом, действительно можно просто дойти в любую вершину из 0 и вернуться.
Странно следующий SRM назначен на 10 октября. Какой-то большой перерыв. В первый раз такое вижу
там ТСО 1-3 октября, они наверно готовятся...