Задано таблицу N * M, в каждой ячейке которой написана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла к правому нижнему углу, если вам разрешено идти только вправо и вниз. Конкатенация букв в процессе движения образует строку. Будем считать, что эта строка — значение пути. Теперь рассмотрим все такие пути и отсортируем их значение в алфавитном порядке. Ваша задача: найти значение I-го пути в этом отсортированном списке.
Формат входных данных
Первая строка входного файла содержит два целых числа N (количество строк) и M (количество столбцов): 1≤N, M≤30. Следующие N строк содержат M строчных букв английского алфавита. Последняя строка входного файла содержит целое число I (1≤I≤1018). Формат результата
Выходной файл должен содержать одну строку — ответ на задачу.
Моя попытка решить:
1) использовать алгоритм "перебор з возвратом";
2) когда выбирается новый кандидат, то сравниваются символы из допустимых ячеек таблицы (учитывая допустимые направления).
Возникла проблема: а как сделать выбор, если оба направления (вправо, вниз) — допустимые и возможные кандидаты (ячейки таблицы) содержат одинаковые символы?..
Вопрос:
1) можно ли таким алгоритмом решит эту задачу, если "да", то как быть с выбором между одинаковыми кандидатами?
2) какой алгоритм (если указанный мною способ неверен) вместо перебора с возвратом может решить эту задачу эффективнее?
Здравствуйте, olimp_20, Вы писали:
_>Моя попытка решить: _>1) использовать алгоритм "перебор з возвратом"; _>2) когда выбирается новый кандидат, то сравниваются символы из допустимых ячеек таблицы (учитывая допустимые направления).
А ты когда заметил ограничение 10^18 не задался вопросом, успеет ли твой "перебор з возвратом" перебрать столько вариантов?
Ты извини, конечно, но ты довольно давно задаешь вопросы в этом форуме в виде "олимпиадных" задач, тебе тут с переменным успехом помогают разобраться, но прогресса никакого не видно, если честно. Зачем ты их вообще решаешь, с какой целью, может тебе совет какой-нибудь дать?
Удаляются ли дубли после сортировки? Если удаляются, то кроме перебора ничего не остаётся.
Если нет, то можно оптимизировать, потому что в каждой "ветке дерева" имеется определённое количество листьев. Типа такого:
У нас на старте два пути. На каждом пути по 126 вариантов. Нам нужен 18й, значит сразу идём в тот, который с "меньшей буквы". Потом опять развилка, направо 70 варианта, налево 56, нам нужен 18й, значит опять надо идти в меньший вариант. Итд.
Случай, когда на развилке направо и налево одинаковая буква, похитрее, значит надо делать выбор не из 2х ветвей, надо одновременно держать несколько равнозначных ветвей, сходу не скажу.
Здравствуйте, olimp_20, Вы писали:
_>Задано таблицу N * M, в каждой ячейке которой написана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла к правому нижнему углу, если вам разрешено идти только вправо и вниз. Конкатенация букв в процессе движения образует строку. Будем считать, что эта строка — значение пути. Теперь рассмотрим все такие пути и отсортируем их значение в алфавитном порядке. Ваша задача: найти значение I-го пути в этом отсортированном списке.
Ниже я буду демонстрировать ход мысли по исходной таблице
01234
0 pbbvb
1 jhzxz
2 zbvey
3 wgrgv
4 mlzgt
Когда мы стоим в верхнем левом углу прямоугольника M*N, то в нём есть C(M+N-2,M-1) разных путей до правого нижнего.
Вот мы в точке 00=p.
Если пойдём вправо к лексикографически меньшим путям, начинающимся на b, то зайдём в прямоугольник 4*5, в котором C(7,3)=35 путей > I=18. Идём туда.
pb..., 01
Вправо к b, 3*5, C(6,2)=15 < 18. Поэтому идём ко второму подмножеству путей, вниз к h, декрементируя I = 18-15 = 3.
pbh..., 11
Вниз к b, 3*4, C(5,2) > 3, идём туда.
pbhb..., 21
Вниз к g, 2*4, C(4,1) > 3, идём туда.
pbhbg..., 31
Вниз к l, 1*4, C(3,0)=1 < 3. Идём вправо к r, I := 3-1 = 2.
И так далее.
---
Здесь есть две тонкости.
Первая: нумерация путей.
Удобнее вести нумерацию с 0, тогда декремент будет ровно на мощность отбрасываемого подмножества. И проверка C(...) > I.
Если нумерация с 1, тогда проверка C(...) >= I, и декремент I := I-C(...)+1. Ну, или с самого начала сделать I:=I-1 и дальше всюду считать, что нумерация с нуля.
Вторая: если на развилке будет выбор из двух одинаковых букв. Вот это — реальная засада!
Здравствуйте, _DAle_, Вы писали:
_DA>Здравствуйте, olimp_20, Вы писали:
_>>Моя попытка решить: _>>1) использовать алгоритм "перебор з возвратом"; _>>2) когда выбирается новый кандидат, то сравниваются символы из допустимых ячеек таблицы (учитывая допустимые направления).
_DA>А ты когда заметил ограничение 10^18 не задался вопросом, успеет ли твой "перебор з возвратом" перебрать столько вариантов?
_DA>Ты извини, конечно, но ты довольно давно задаешь вопросы в этом форуме в виде "олимпиадных" задач, тебе тут с переменным успехом помогают разобраться, но прогресса никакого не видно, если честно. Зачем ты их вообще решаешь, с какой целью, может тебе совет какой-нибудь дать?
10^18 я видел, но действительно упустил: за это отдельное спасибо.
и мне нужна не помощь почитать книги: я их читаю, а мне нужна помощь — тип алгоритма для задачи, а я уже и почитаю, и поищу в интернете.
PS: раз решают задачи, значит это — необходимо...Разводить флуд не буду — не хочу быть заблокированным модератором.
Здравствуйте, T4r4sB, Вы писали:
TB>Удаляются ли дубли после сортировки? Если удаляются, то кроме перебора ничего не остаётся. TB>Если нет, то можно оптимизировать, потому что в каждой "ветке дерева" имеется определённое количество листьев. Типа такого:
TB> У нас на старте два пути. На каждом пути по 126 вариантов. Нам нужен 18й, значит сразу идём в тот, который с "меньшей буквы". Потом опять развилка, направо 70 варианта, налево 56, нам нужен 18й, значит опять надо идти в меньший вариант. Итд.
TB>Случай, когда на развилке направо и налево одинаковая буква, похитрее, значит надо делать выбор не из 2х ветвей, надо одновременно держать несколько равнозначных ветвей, сходу не скажу.
К>Вторая: если на развилке будет выбор из двух одинаковых букв. Вот это — реальная засада!
В этом случае картина выглядит так
a - b - xxx
| / | /
b - c - ###
| / |
y # ###
y # ###
y # ###
То есть, мы обходим вширь, и на первой диагонали встречаем одинаковые буквы b,b
Тогда идём на следующую диагональ, и там встречаем c,x,y — что соответствует путям abc..., abx..., aby... и соответствующим же прямоугольникам.
Проверяем гипотезы I < C1, C1 <= I < C1+C2, C1+C2 < I.
А что, если и там несколько лексикографических минимумов?
abc...
bd....
c.....
......
или, для полного ада,
abcde.
bcdf..
cde...
df....
g.....
......
Мы определяем, попал ли I в один из классов эквивалентности: abcde (2 прямоугольника), abcdf (2 прямоугольника), abcdg (1 прямоугольник).
И дальше будем следить за фронтом, выходящим из 2 точек, а не из одной. Например, если для f, получается такая картина
abcde.
bcdf+.
cde+..
df+..
g+....
Кстати, третья тонкость. Если есть одинаковые буквы на первой развилке, то гарантированно есть и разные пути с одинаковым текстом: abc..., abc...
Они засчитываются как один путь, или как разные?
Здравствуйте, olimp_20, Вы писали:
_>и мне нужна не помощь почитать книги: я их читаю, а мне нужна помощь — тип алгоритма для задачи, а я уже и почитаю, и поищу в интернете. _>PS: раз решают задачи, значит это — необходимо...Разводить флуд не буду — не хочу быть заблокированным модератором.
Ну как знаешь, просто ты начал вопросы задавать примерно 2 года назад. За два года, читая книги и решая задачи, люди (начиная с возраста старшеклассников где-то) выходят уже на относительно приличный уровень. У тебя, к сожалению, какого-то особого прогресса не видно. Видимо, надо что-то менять. На этом форуме, когда ты задаешь вопрос, обычно кто-нибудь рассказывает тебе правильное решение, иногда даже вместе с исходным кодом. Это хорошо, но, возможно, лучше тебе просто получать подсказки и "добивать" задачу самому.
Здравствуйте, Кодт, Вы писали:
К>Вторая: если на развилке будет выбор из двух одинаковых букв. Вот это — реальная засада!
Да в общем-то не такая уж большая засада. Просто на каждом шаге надо хранить все возможные текущие позиции, строить новый слой, затем вычислять количество сочетаний для каждого варианта, сортировать по буквам, находить нужную букву для продолжения, и все позиции этой буквы в текущем слое переносить на следующий шаг.
Здравствуйте, _DAle_, Вы писали:
К>>Вторая: если на развилке будет выбор из двух одинаковых букв. Вот это — реальная засада!
_DA>Да в общем-то не такая уж большая засада. Просто на каждом шаге надо хранить все возможные текущие позиции, строить новый слой, затем вычислять количество сочетаний для каждого варианта, сортировать по буквам, находить нужную букву для продолжения, и все позиции этой буквы в текущем слое переносить на следующий шаг.
AAAAA
AAAAA
AAAAA
AAAAA
AAAzA
Где M=N=30. Там комбинаторный взрыв получится, C(58,29), 1/2 путей содержат z, 1/2 — не содержат.
Замучаешься хранить все возможные позиции — особенно, если считать неуникальные пути.
Кстати, засада номер четыре.
Уже для M=N=35 мы выбежим из int64. (Отсюда и взято ограничение в задаче).
Этюд: написать функцию q(M,N,I) = max(-1, I-C(M+N-2,N-1))
которая возвращает сигнальное значение -1, если путь номер I попадает в подмножество лексикографически меньших, в прямоугольник размером M*N,
или декрементирует этот номер на размер множества,
и при этом не вовлекает арифметику большой (неограниченной) разрядности.
Для больших матриц и небольших номеров путей первая часть забега будет "всегда выбирать меньшее". Вот ради этого, собственно.
К>pb..., 01 К>Вправо к b, 3*5, C(6,2)=15 < 18. Поэтому идём ко второму подмножеству путей, вниз к h, декрементируя I = 18-15 = 3.
Зачем вычислять I = 18-15 = 3, если для h N=M=4, поэтому C(6,3)=20>18 и значит надо выбирать h?
То есть по формулах понятно, что выйдет, но саму идею, если бы уточнили, то очень был благодарен.
Здравствуйте, olimp_20, Вы писали:
К>>pb..., 01 К>>Вправо к b, 3*5, C(6,2)=15 < 18. Поэтому идём ко второму подмножеству путей, вниз к h, декрементируя I = 18-15 = 3.
_>Зачем вычислять I = 18-15 = 3, если для h N=M=4, поэтому C(6,3)=20>18 и значит надо выбирать h? _>То есть по формулах понятно, что выйдет, но саму идею, если бы уточнили, то очень был благодарен.
Вот мы стоим в вершине прямоугольника 4*5. Всего у нас путей, понятное дело, С(7,3)=35.
Если пойдём на b, то попадём в семейство путей в прямоугольнике 3*5, количеством 15 штук.
Если пойдём на h, то в семейство путей в прямоугольнике 4*4, количеством 20 штук.
Самое главное, что эти пути, будучи отсортированы, так и идут:
0) pbbv...
1) pbbv...
....
14) pbbz...
15) pbhb...
16) pbhb...
....
34) pbhz...
Путь номер 18 попадает во второе семейство: 18 >= 15.
И в этом семействе он будет иметь номер 18-15 = 3.
По большому счёту, нам неважно, сколько путей во втором семействе. Мы ровно один раз, на старте, сделаем проверку 0 < I < C(N+M-2,N-1), означающую, что мы не вылетели из семейства всех-всех-всех путей.
(Кстати, откуда взялась волшебная формула C(M+N-2,N-1). На тот случай, если непонятна магия. В прямоугольнике N*M вершин совершается N-1 переходов вниз и M-1 переходов направо, итого M+N-2 переходов. То есть, нужно разместить N-1 переходов вниз среди M+N-2 всех переходов).
Большое спасибо, за пояснение.
К>(Кстати, откуда взялась волшебная формула C(M+N-2,N-1). На тот случай, если непонятна магия. В прямоугольнике N*M вершин совершается N-1 переходов вниз и M-1 переходов направо, итого M+N-2 переходов. То есть, нужно разместить N-1 переходов вниз среди M+N-2 всех переходов).
К>То есть, мы обходим вширь, и на первой диагонали встречаем одинаковые буквы b,b К>Тогда идём на следующую диагональ, и там встречаем c,x,y — что соответствует путям abc..., abx..., aby... и соответствующим же прямоугольникам. К>Проверяем гипотезы I < C1, C1 <= I < C1+C2, C1+C2 < I.
Какое соответствие между abc..., abx..., aby.. и C1, C2?
Что Вы называете прямоугольником для abc..., abx..., aby...?
Здравствуйте, olimp_20, Вы писали:
_>Задано таблицу N * M, в каждой ячейке которой написана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла к правому нижнему углу, если вам разрешено идти только вправо и вниз. Конкатенация букв в процессе движения образует строку. Будем считать, что эта строка — значение пути. Теперь рассмотрим все такие пути и отсортируем их значение в алфавитном порядке. Ваша задача: найти значение I-го пути в этом отсортированном списке.
_>Формат входных данных _>Первая строка входного файла содержит два целых числа N (количество строк) и M (количество столбцов): 1≤N, M≤30. Следующие N строк содержат M строчных букв английского алфавита. Последняя строка входного файла содержит целое число I (1≤I≤1018). _>Формат результата _>Выходной файл должен содержать одну строку — ответ на задачу.
_>
_>
_>
Входные данные в файле input.txt
_>
Результат работы в файле output.txt
_>
_>
_>
5 5 _>pbbvb _>jhzxz _>zbvey _>wgrgv _>mlzgt _>18
_>
pbhbgrgvt
_>
_>
_>Примечания _>pbbvbzyvt pbbvxeggt pbbvxegvt pbbvxeyvt pbbvxzyvt pbbzveggt pbbzvegvt pbbzveyvt pbbzvrggt pbbzvrgvt pbbzvrzgt pbbzxeggt pbbzxegvt pbbzxeyvt pbbzxzyvt pbhbglzgt pbhbgrggt pbhbgrgvt pbhbgrzgt pbhbveggt pbhbvegvt pbhbveyvt pbhbvrggt pbhbvrgvt pbhbvrzgt pbhzveggt pbhzvegvt pbhzveyvt pbhzvrggt pbhzvrgvt pbhzvrzgt pbhzxeggt pbhzxegvt pbhzxeyvt pbhzxzyvt pjhbglzgt pjhbgrggt pjhbgrgvt pjhbgrzgt pjhbveggt pjhbvegvt pjhbveyvt pjhbvrggt pjhbvrgvt pjhbvrzgt pjhzveggt pjhzvegvt pjhzveyvt pjhzvrggt pjhzvrgvt pjhzvrzgt pjhzxeggt pjhzxegvt pjhzxeyvt pjhzxzyvt pjzbglzgt pjzbgrggt pjzbgrgvt pjzbgrzgt pjzbveggt pjzbvegvt pjzbveyvt pjzbvrggt pjzbvrgvt pjzbvrzgt pjzwglzgt pjzwgrggt pjzwgrgvt pjzwgrzgt pjzwmlzgt
_>Моя попытка решить: _>1) использовать алгоритм "перебор з возвратом"; _>2) когда выбирается новый кандидат, то сравниваются символы из допустимых ячеек таблицы (учитывая допустимые направления).
_>Возникла проблема: а как сделать выбор, если оба направления (вправо, вниз) — допустимые и возможные кандидаты (ячейки таблицы) содержат одинаковые символы?..
_> Вопрос: _>1) можно ли таким алгоритмом решит эту задачу, если "да", то как быть с выбором между одинаковыми кандидатами? _>2) какой алгоритм (если указанный мною способ неверен) вместо перебора с возвратом может решить эту задачу эффективнее
Проблема как я понял в коллизиях, т.е. тогда, когда есть равнозначные буквы в разных вариантах пути.
Путь есть функция на вход которой поступает массиф координат ячеек. Функция делает просмотр на один шаг в перед от каждой ячейки и если есть часть строки идущая по алфовиту первой, то рекурсивно вызывает сама себя с координатами этой ячейки. Если опять находиться коллизия, то функция рекурсивно вызывает сама себя с координатами ячеек участвующих в коллизии. И так до крайнего угла. Остается только последовательность реккурсивных
вызовов преобразовать в строку.
К>>То есть, мы обходим вширь, и на первой диагонали встречаем одинаковые буквы b,b К>>Тогда идём на следующую диагональ, и там встречаем c,x,y — что соответствует путям abc..., abx..., aby... и соответствующим же прямоугольникам. К>>Проверяем гипотезы I < C1, C1 <= I < C1+C2, C1+C2 < I.
_>Какое соответствие между abc..., abx..., aby.. и C1, C2? _>Что Вы называете прямоугольником для abc..., abx..., aby...?
Здесь мы получаем три семейства путей: начинающихся на abc, abx и aby. Упорядочим эти семейства лексикографически друг относительно друга.
Мощности этих семейств пусть будут C1, C2 и C3. В сумме, разумеется, C1+C2+C3 = C — мощность семейства путей из точки 'a'.
Наша задача — понять, в какое семейство попадает I.
[0..C) = [0..C1) | [C1..C1+C2) | [C1+C2..C1+C2+C3)
Ну и дальше, при работе с ними, — как обычно, вычесть левую границу интервала.
Кстати, тут есть интересная деталь.
Префикс abc можно получить двумя способами. Это значит, что семейство путей abc... содержит дубликаты путей.
Следовательно, мы должны, рассматривая прямоугольник с вершиной 'c', поделить индекс пополам.
Аналогично, в похожей ситуации
a b c
b c e
d
в точку e можно попасть 3 путями с одним префиксом abce. Соответственно, придётся делить на 3.
Если такая общая точка будет в 3-й диагонали, там делители 1, 4, 6, 4, 1. Ну и так далее — треугольник Паскаля.
Ну и для пущего ада, может возникнуть вот такая матрица
То есть, два эквивалентных семейства путей aaaaab..... получаются с разных направлений.
Или ещё какая-нибудь затейливая ситуация с семействами...
Поэтому алгоритм, в общих чертах, выглядит так:
Начинаем с однобуквенного префикса ('a') — ему соответствует одна вершина и два выхода из неё — вправо и вниз
— идём по лексикографически минимальным направлениям — получаем либо одну минимальную вершину, либо две (это у нас первая диагональ)
— если минимальных вершин более одной, то идём по всем выходам из них, собирая ещё более глубокие минимальные вершины, ну и подсчитывая их множители (привет динамическому программированию)
— до тех пор, пока у нас не будет самая-самая минимальная вершина одна штука.
Считаем мощность множества путей в прямоугольнике, умножаем на количество входных путей в неё, и сравниваем с I.
Если I меньше, — то делим его на множитель и уходим в прямоугольник. Ура.
Если I больше, — то вычитаем и возвращаемся на предыдущую диагональ, собирая на ней вершины "первая после минимума".
— если таких вершин нет, то откатываемся ещё на предыдущую диагональ, и т.д.
— если таких вершин несколько, — делаем всё то же самое, как и в первой ветви алгоритма
Рано или поздно мы натыкаемся на вершину, которая одна, и мощность прямоугольника которой, помноженная на мощность входного потока, превосходит текущее значение I.
К сожалению, с предыдущей матрицей этот алгоритм справится плохо. У него не хватит фантазии заметить, что оба варианта aaaaab одинаковы, с точностью до транспонирования, и поэтому мы будем трассировать все пути до самого финиша.
А это, очевидно, комбинаторный взрыв, экспонента на ровном месте.
Поэтому на каждом шаге нужно смотреть: если наши минимальные точки являются вершинами одинаковых по содержанию прямоугольников, с точностью до транспонирования, то следует объединять такие пары точек и считать их одной, с суммарным множителем.
И разумеется, слияние зеркальных точек не означает немедленно, что точка останется одна: например, если у нас две зеркальные пары, после слияния будет две минимальные точки, и придётся продолжить раскопки.
(Не знаю, ясно ли я объяснил, или надо ещё порисовать примеров?)
Предлагаю коллегам задуматься над ещё одним этюдом: как создать наиболее подлый нагрузочный тест.
"собирая ... минимальные вершины, ну и подсчитывая их множители": множители — это C(N+M-2, M-1), начиная с вершины и вниз-вправо?
К>Считаем мощность множества путей в прямоугольнике, умножаем на количество входных путей в неё —
мощность множества путей — это C(N+M-2, M-1), а количеством входных путей — это та же формула, но для предыдущего прямоугольника, опирающегося на вершину?
К>К сожалению, с предыдущей матрицей этот алгоритм справится плохо. У него не хватит фантазии заметить, что оба варианта aaaaab одинаковы, с точностью до транспонирования, и поэтому мы будем трассировать все пути до самого финиша. К>А это, очевидно, комбинаторный взрыв, экспонента на ровном месте.
К>Поэтому на каждом шаге нужно смотреть: если наши минимальные точки являются вершинами одинаковых по содержанию прямоугольников, с точностью до транспонирования, то следует объединять такие пары точек и считать их одной, с суммарным множителем. К>И разумеется, слияние зеркальных точек не означает немедленно, что точка останется одна: например, если у нас две зеркальные пары, после слияния будет две минимальные точки, и придётся продолжить раскопки.
aaaaab>>>> azzzz>>>>> azzzz>>>>> azzzz>>>>> azzzz>>>>>
bVVVVXXXXX
VVVVVXXXXX
VVVVVXXXXX
VVVVVXXXXX
aaaaab — в строке и столбце заканчиваются зеркальными точками?
Здравствуйте, olimp_20, Вы писали:
_>"собирая ... минимальные вершины, ну и подсчитывая их множители": множители — это C(N+M-2, M-1), начиная с вершины и вниз-вправо?
Нет, я имею в виду множители по входящим путям.
К>>Считаем мощность множества путей в прямоугольнике, умножаем на количество входных путей в неё — _>мощность множества путей — это C(N+M-2, M-1), а количеством входных путей — это та же формула, но для предыдущего прямоугольника, опирающегося на вершину?
Если бы так всё просто было, как треугольник Паскаля... Но нет.
Вот пример.
К точке X ведут три минимальных пути aaaaaaaaaX. Символ "·" пусть будет лексикографически больше "a".
На первом шаге у нас два "aa", на втором опять два, на третьем их уже три... на седьмом одна одинарная "aaaaaaaa" и одна двойная (произошло слияние), на восьмом сохранилась одна одинарная и одна двойная, на девятом они слились в одну тройную "X".
_>aaaaab — в строке и столбце заканчиваются зеркальными точками?
Да, — значками >>> и VVV я обозначил зеркально равные блоки, а XXX — это вообще симметричный квадратный блок (равный сам себе зеркальному).
Перекуём баги на фичи!
