→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 02:39:39 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Как решать 1000?
Рассмотрим вначале слова четной длины. Заметим, что можем поменять местами любые две группы из двух символов, которыя начинается с четной позиции. А еще можем поменять местами символы в любой такой группе. Таким образом сортируем строки. Например: dcab => abcd. Если отсортированные строки совпали, то вычеркиваем их. Теперь для нечетной длины: важно, чтобы совпадали последние символы. Можно, например, приписать в конце '$' и решать для них задачу точно так же.
UPD: Ай, упало.
Так и решать, ищите баг.
А 500 расскажите, пожалуйста.
Переберём за 2h, какие горизонтали будем вычёркивать. Это можно сделать, например, при помощи битовых масок или рекурсивно.
Зафиксировав горизонтали, найдём все вертикали, в которых осталось что-то невычеркнутое (эти вертикали мы вычеркнуть обязаны).
Теперь, зная номера вертикалей и горизонталей, которые собираемся вычеркнуть, посчитаем отдельно для одних и для других, какое минимальное количество блоков нам понадобится использовать. Утверждается, что это можно делать жадно: перебираем линии в порядке увеличения номера и, если текущую линию обязательно вычёркивать, вычеркнем её, иначе — вычеркнем в том и только в том случае, если непосредственно перед ней мы вычеркнули хотя бы одну линию, но количество вычеркнутых линий не образует целое число блоков. То есть, например, если R = 4, то, если мы вычеркнули уже 7 горизонталей подряд, то вычеркнем и 8-ю, а если уже вычеркнули 8, то текущую (которую вычёркивать необязательно) вычёркивать не будем, т.к. предыдущие образуют два целых блока и нам ни к чему начинать третий.
Ответ — минимум по всем вариантам, которые мы перебрали.
Лучше использовать битовые маски, я писал рекурсивно, упало по TLE на самом большом тесте.
Совневаюсь, что дело именно в рекурсии. Не может же оно работать в 100 раз дольше. Можно посмотреть код, который таймлимитится?
В 100 раз то нет. Решение на битовых масках на больших тестах выполнялось порядка 200ms (может конечно и тут я не оптимально написал). Порядка 10 раз достаточно,чтобы программа упала по TLE. Ссылка на мое решение в TC: http://community.topcoder.com/stat?c=problem_solution&rm=316429&rd=15580&pm=12447&cr=22721234
По-моему у вас решение за 2^(r+c)*что-то. Такое точно не могло зайти
Вот тут неверно: 2^r. Перебираются только строки, столбцы не перебираются.
Точно. Не заметил слова return во втором форе.Тогда я бы винил огромное количество векторов строк, которые вы заводите. Рекурсивная функция будет вызвана 2^r * c раз (для любого выбора строк нужно будет сделать еще c вызовов для каждого столбца). Вы каждый раз передаете по значению новый вектор строк. Значит принимающая сторона его должна будет полностью скопировать. Получается, что будет существовать за все время как минимум 2^r * c таблиц. Итого расход памяти 2^r * r * c^2. А если учесть еще, что вы передаете по значению их всюду, то любое действие вызовет копирование таблицы, а потом её разрушение. Нужная константа наверняка наберется.
В принципе ясно, нужная константа на копировании появляется. Поэтому, постараюсь в будущем по возможности не передавать такие данные, а использовать битовые маски.
Повеселил сэмпл к третьей задаче:
{"topcoder", "redocpot", "doretopc", "cpotdoer", "harlemshake"}
Круче был бы такой сэмпл: {"topcoder", "otpcoder", "topcoder", "otpcoder","topcoder", "otpcoder","topcoder", "otpcoder","topcoder", "otpcoder", "**koloterrorita**", "redocpot", "doretopc", "cpotdoer", "otpcoder", "cpotoder", "dotopcer", "recpotod", "ercpotod", "pcreotod", "toercpod", "dopcreot", "odpcreot", "cpdoreot", "erodpcot", "tocpdore"}
Или такой :) {"topcoder", "topcoder", "topcoder", "topcoder", "topcoder", "dotheharlemshake", "pcreotod", "doretopc", "erodpcot", "dotopcer", "tocpdore", "toercpod", "redocpot", "otpcoder", doretopc", "erodpcot", "pcreotod", "doretopc"}