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

@Jorka · Регистрация: 25.07.2020

Студворк — интернет-сервис помощи студентам

Вам дана нижнетреугольная матрица из n строк (i-й ряд состоит ровно из i элементов, расположенных в столбцах с номерами от 1 до i). В каждой ячейке матрицы записана маленькая латинская буква. Также у вас есть пустая строка s.

Вы стоите в ячейке с координатами (1, 1) (первая строка, первый столбец). На каждом ходу можно делать переход на одну ячейку ниже или на одну ячейку по диагонали вправо-вниз. То есть из ячейки с координатами (i,j) можно попасть в ячейки (i+1,j) или (i+1,j+1).

Каждый раз, когда вы попадаете в новую ячейку, к строке s в конец приписывается буква, стоящая в этой ячейке. Найдите лексикографически минимальную строку, которую можно получить при переходе из первой строки матрицы в последнюю (n-ю).

Формат входных данных
В первой строке задано число n(1≤n≤5⋅10**3).Затем идёт n строк, в i-й находится строка из i символов, отвечающая первым i столбцам i-й строки матрицы.

Формат результата
Выведите искомую строку.

Примеры
Входные данные
3
o
nu
mwb
Результат работы
onm
Входные данные
4
a
bb
czc
defr
Результат работы
abcd

Написал алгоритм, но там ошибка, понял как исправить, но не могу тупо реализовать это.

@TheCalligrapher · 03.09.2020, 01:04

Сообщение от Annemesski

Она и есть, классика жанра:

Рекурсия здесь совершенно нинафиг не нужна, не говоря уже о том, чтобы являться "классикой жанра". Решение задачи не требует никаких действий по стратегии "проб и ошибок" с необходимостью откатываться назад, по каковой причине никакой рекурсии тут не нужно вообще.

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

Тем не менее задача запросто решается в лоб одним проходом сверху вниз. Нужно лишь поддерживать набор "достижимых" клеток строки матрицы. Минимальный достижимый символ на текущей строке порождает две достижимых клетки на следующей строке. Если на какой-то строке матрицы окажется, что среди достижимых символов есть несколько минимумов, то все эти минимумы должны породить достижимые клетки на следующей строке.

Вот и все.

@Annemesski · 03.09.2020, 08:11

TheCalligrapher, рекурсивный алгоритм здесь напрашивается сам собой, понятное дело что он не единственный, учитывая что всякий рекурсивный алгоритм может быть представлен циклом (также верно и обратное), и может быть не самый эффективный, но для этой задачи он самый понятный и просто реализуемый. Вашу идею не понял (простите, туп) если не слишком лениво выразите кодом, ну или объясните на тривиальном предельном примере:

Code
1
2
3
4
5
6
7
8
9
10
11
12
входные данные:
12
a
bb
bbb
bbbb
..............
bbbbbbbbbbb
dfghjkrqwazc
 
ответ:
abbbbbbbbbba

тут ведь все символы "достижимы" и, вплоть до последней строки, все пути "возможны", так? Вроде да. Как по Вашему тут быть?

@TheCalligrapher · 03.09.2020, 09:39

Сообщение от Annemesski

рекурсивный алгоритм здесь напрашивается сам собой,

С одной стороны - вы правы. Действительно вероятность возникновения такой ситуации, когда нужно попробовать несколько путей, наталкивает на мысль о рекурсивном алгоритме. (Я, скорее всего, выразился слишком радикально в своем придыдущем сообщении, когда говорил про "нафиг не нужна").

С другой стороны, ситуация, когда ветвление нужно, т.е. когда на строке находится несколько минимумов, интуитивно выглядит "исключительной" и заводить рекурсию только ради нее не хочется. К тому же у обычной рекурсии (в частности - у вашей реализации) есть и еще один очевидный недостаток: она может и будет анализировать одни и те же подпути несколько раз.

На приведенном вами же примере это явление будет приводит к огромному взрыву ненужных рекурсивных поисков на каждом уровне рекурсии.

Сообщение от Annemesski

ну или объясните на тривиальном предельном примере:

Code
1
2
3
4
5
6
7
8
12
a
bb
bbb
bbbb
..............
bbbbbbbbbbb
dfghjkrqwazc

Вот именно для борьбы с последним недостатком я бы предложил алгоритм такого вида (нумерация строк и столбцов с 1)

1. Мы начинаем со строки i=1 и множества столбцов-кандидатов J={ 1 }

2. В текущей строке i просматриваем все текущие столбцы-кандидаты J и находим среди них все минимумы.

3. Для каждого найденного минимума j добавляем индексы j и j + 1 в множество столбцов-кандидатов Jnext - для следующей строки

4. Делаем ++i, J = Jnext и переходим на шаг 2.

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

В вашем экстремальном примере получится, что на каждой итерации все столбцы каждой строки будут попадать в множество кандидатов... (С кодом - возюкаюсь пока)

@zayats80888 · 03.09.2020, 09:50

Сообщение от TheCalligrapher

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

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

@TheCalligrapher · 03.09.2020, 10:02

Сообщение от zayats80888

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

Да, верно. 5 пункт не нужен.

@Annemesski · 03.09.2020, 10:21

Сообщение от TheCalligrapher

(С кодом - возюкаюсь пока)

Тож попробую повозиться с Вашим вариантом, пока моя рекурсия считает для максимальной глубины в этой задаче (5000) и да - просматривает все возможные подпути уже минут 5 (с учетом вывода в консоль текущей глубины) и пока крутится вокруг последних двух сотен

@TheCalligrapher · 03.09.2020, 10:30

Сообщение от Annemesski

выразите кодом

Вот как-нибудь так

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cassert>
#include <string>
#include <set>
#include <iostream>
 
int main()
{
  const unsigned N = 12;
  const char M[N][N + 1] = 
  {
    "a",
    "bb",
    "bbb",
    "bbbb",
    "bbbbb",
    "bbbbbb",
    "bbbbbbb",
    "bbbbbbbb",
    "bbbbbbbbb",
    "bbbbbbbbbb",
    "bbbbbbbbbbb",
    "dfghjkrqwazc"
  };
 
  std::string result;
  std::set<unsigned> J = { 0 };
 
  for (unsigned i = 0; i < N; ++i)
  {
    assert(!J.empty());
 
    unsigned j_min = *J.begin(), n_mins = 0;
 
    for (unsigned j : J)
    {
      if (j >= N)
        continue;
 
      if (M[i][j] < M[i][j_min])
      {
        j_min = i;
        n_mins = 1; 
      }
      else if (M[i][j] == M[i][j_min])
        ++n_mins;
    }
 
    assert(n_mins > 0);
 
    result += M[i][j_min];
 
    if (n_mins == 1)
      J = { j_min, j_min + 1 };
    else
    {
      std::set<unsigned> next_J;
 
      for (unsigned j : J)
        if (M[i][j] == M[i][j_min])
          next_J.insert({ j, j + 1 });
 
      J = std::move(next_J);
    }
  }
 
  std::cout << result << std::endl;
}

(Тут можно и нужно было избавиться от формирования следующего J на последней итерации, но я не стал)

@Annemesski · 03.09.2020, 11:19

TheCalligrapher, нет... так не сработает... такой алгоритм потеряется уже через строку, даже для приведенного примера он дает результат "abbbbbbbbbbc", а должен выдать "abbbbbbbbbba", по ходу деваться особо некуда и так или иначе придется пихать предположения в стэк.

Есть у меня одна индейка... пока обмозгую.

Первоначальный мой вариант - однозначный фейл - сложность O(2ⁿ).

@TheCalligrapher · 03.09.2020, 11:40

Сообщение от Annemesski

TheCalligrapher, нет... так не сработает... такой алгоритм потеряется уже через строку, даже для приведенного примера он дает результат "abbbbbbbbbbc", а должен выдать "abbbbbbbbbba"

Ой, это у меня в код вкрался глупый баг. Разумеется в строке 41 должно быть j_min = j;, а не j_min = i;

Еще раз, исправленная версия

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cassert>
#include <string>
#include <set>
#include <iostream>
 
int main()
{
  const unsigned N = 12;
  const char M[N][N + 1] = 
  {
    "a",
    "bb",
    "bbb",
    "bbbb",
    "bbbbb",
    "bbbbbb",
    "bbbbbbb",
    "bbbbbbbb",
    "bbbbbbbbb",
    "bbbbbbbbbb",
    "bbbbbbbbbbb",
    "dfghjkrqwazc"
  };
 
  std::string result;
  std::set<unsigned> J = { 0 };
 
  for (unsigned i = 0; i < N; ++i)
  {
    assert(!J.empty());
 
    unsigned j_min = *J.begin(), n_mins = 0;
 
    for (unsigned j : J)
    {
      if (j >= N)
        continue;
 
      if (M[i][j] < M[i][j_min])
      {
        j_min = j;
        n_mins = 1; 
      }
      else if (M[i][j] == M[i][j_min])
        ++n_mins;
    }
 
    assert(n_mins > 0);
 
    result += M[i][j_min];
 
    if (n_mins == 1)
      J = { j_min, j_min + 1 };
    else
    {
      std::set<unsigned> next_J;
 
      for (unsigned j : J)
        if (M[i][j] == M[i][j_min])
          next_J.insert({ j, j + 1 });
 
      J = std::move(next_J);
    }
  }
 
  std::cout << result << std::endl;
}

Сообщение от Annemesski

так не сработает... по ходу деваться особо некуда и так или иначе придется пихать предположения в стэк.

Все прекрасно работает. Множество J - это и есть заменитель "стека" в моей реализации. Больше никакого стека (и рекурсии) не нужно. Алгоритм однопроходный, как правильно заметил zayats80888, возвращаться назад нам никогда не нужно, поэтому "исторические" значения J нас не интересуют. Именно из-за этого соображения явно рекурсивные решения выглядят "подозрительно".

@Annemesski · 03.09.2020, 12:17

Сообщение от TheCalligrapher

Ой, это у меня в код вкрался глупый баг.

Это к нашей пикировке с Avazart выше по теме

Сообщение от TheCalligrapher

Множество J - это и есть заменитель "стека" в моей реализации.

виноват, теперь вкурил

C++
1
2
if (M[i][j] == M[i][j_min])
    next_J.insert({ j, j + 1 });

не разглядел insert, сразу уперся в

C++
1
J = std::move(next_J);

Новые блоги и статьи Все статьи Все блоги /
Море в объективе kumehtar 06.07.2026 Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .
В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .

@Jorka 11 / 10 / 5 Регистрация: 25.07.2020 Сообщений: 302

	Найти лексикографически минимальную строку, которую можно получить при переходе из первой строки матрицы в последнюю 01.09.2020, 18:08. Показов 5510. Ответов 29 Метки нет (Все метки) Вам дана нижнетреугольная матрица из n строк (i-й ряд состоит ровно из i элементов, расположенных в столбцах с номерами от 1 до i). В каждой ячейке матрицы записана маленькая латинская буква. Также у вас есть пустая строка s. Вы стоите в ячейке с координатами (1, 1) (первая строка, первый столбец). На каждом ходу можно делать переход на одну ячейку ниже или на одну ячейку по диагонали вправо-вниз. То есть из ячейки с координатами (i,j) можно попасть в ячейки (i+1,j) или (i+1,j+1). Каждый раз, когда вы попадаете в новую ячейку, к строке s в конец приписывается буква, стоящая в этой ячейке. Найдите лексикографически минимальную строку, которую можно получить при переходе из первой строки матрицы в последнюю (n-ю). Формат входных данных В первой строке задано число n(1≤n≤5⋅10**3).Затем идёт n строк, в i-й находится строка из i символов, отвечающая первым i столбцам i-й строки матрицы. Формат результата Выведите искомую строку. Примеры Входные данные 3 o nu mwb Результат работы onm Входные данные 4 a bb czc defr Результат работы abcd Написал алгоритм, но там ошибка, понял как исправить, но не могу тупо реализовать это. 0

@Annemesski 2689 / 1346 / 485 Регистрация: 08.11.2016 Сообщений: 3,734
	03.09.2020, 11:19
	TheCalligrapher, нет... так не сработает... такой алгоритм потеряется уже через строку, даже для приведенного примера он дает результат "abbbbbbbbbbc", а должен выдать "abbbbbbbbbba", по ходу деваться особо некуда и так или иначе придется пихать предположения в стэк. Есть у меня одна индейка... пока обмозгую. Первоначальный мой вариант - однозначный фейл - сложность O(2ⁿ). 0