Отправлено: 24.08.22 22:08. Заголовок: №5311 (27.115) ошибки в решениях и примере

Здравствуйте!

Во-первых, в примере в ответе представлена цепочка, у которой левая и правая стороны неправильно посчитаны:

Данные:

 
 7 
 15 
 12 
 5 
 1 
 4 
 15 
 5 
 

Ответ:

цитата:

В этой последовательности числа можно переставить следующим образом: {4, 5, 15, 12, 15, 5, 1}, при этом L = 4 (подпоследовательность {4, 5, 12, 15}) и M = 4 (подпоследовательность {1, 5, 12, 15}), так что R = min(4 ,4) = 4. Ответ: 4.

Только нельзя с двух сторон построить такую цепочку. Тут может быть несколько вариантов ошибки, но при заданных данных ответ 3, а не 4.

Во-вторых, все предложенные алгоритмы не учитывают ряд случаев.

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

Теперь у нас есть 2 варианта событий: когда в левой и правой сторонах одинаковое количество чисел, и когда в одной из сторон чисел на 1 больше.
1) Если у нас стороны одинаковой длины, то наличие перегородки ни на что не влияет и существует единственный ответ, это длина любой стороны.

2) Если у нас стороны разной длины, то есть 2 варианта:
2.1) Когда на концах каждой стороны стоит одинаковое число (наличие перегородки ни на что не влияет):
Пример данных (без перегородки)

 
 5 
 1 
 2 
 3 
 3 
 2 
 

Правильный ответ 2, но все алгоритмы выдают 3.

Пример данных (с перегородкой)

 
 6 
 1 
 2 
 3 
 2 
 3 
 2 
 

Правильный ответ 2, но все алгоритмы выдают 3.

2.2) Когда на каждом конце разные числа (стороны разной длины). И тут есть 2 варианта:
2.2.1) Без перегородки

 
 5 
 1 
 2 
 3 
 2 
 1 
 

Алгоритмы работают правильно.

2.2.2) С перегородкой

 
 6 
 1 
 2 
 3 
 2 
 2 
 1 
 

Правильный ответ 2, но все алгоритмы выдают 3.

 Отправлено: 31.08.22 16:28. Заголовок: beep пишет: Только ..

beep пишет:

цитата:

Только нельзя с двух сторон построить такую цепочку

Вы не поясняете, почему нельзя. Пример в задании показывает, что можно.

beep пишет:

цитата:

Тут может быть несколько вариантов ошибки, но при заданных данных ответ 3

И не поясняете, почему для приведенной в примере последовательности ответ 3, а не 4.

beep пишет:

цитата:

При строгом возрастании подряд не могут идти равные числа

В приведенных в примере подпоследовательностях тоже нет одинаковых чисел.
beep пишет:

цитата:

Перестановки подразумевают, что используются все члены множества.

В приведенной в примере перестановке исходной последовательности тоже используются все ее члены.

цитата:

чтобы они не мешали продолжению цепочки.

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

 Отправлено: 03.09.22 16:15. Заголовок: MDF пишет: В своих ..

MDF пишет:

цитата:

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

Здравствуйте! Действительно, я на автомате воспринял подпоследовательность как подстроку. Спасибо!