1. Есть конечная последовательность натуральных чисел обладающая следующим свойством:
(*) Любой суффикс этой последовательности лексикографически( только числа вместо букв) больше этой последовательности, например:
a = {3, 6, 10, 3, 6, 11, 3, 6, 99}, какой суффикс ни возьми: 99 >a, {6, 99} > a, {3, 6, 99} > a, ... и т.д
Потом мы берем и записываем все сдвиги этой последоваетльности т.е.
{6,10,3,6,11,3,6,99,3}; {10,3,6,11,3,6,99,3,6}; ... и т.д
Потом сортируем эти сдвиги лексикографически и берем последние элементы, получаем некую перестановку начальной последовательности. Для а ,например: {99, 10, 11, 3, 3, 3, 6, 6, 6} и вот надо воостановить по ней исходную последовательность.

2. Усложнение задачи 1. дана конечная последовательность натуральных чисел и мы слева направо начинаем искать максимальные подпоследовательности обладающие свойством (*) т.е. например:
a = {3,56,78, 5,6,4,2,5,7,8,9,2,4,1} -> {{3,56,78,5,6,4}, {2,5,7,8,9},{2,4},{1}}
Затем как в (1) для каждой подпоследовательности записываем все сдвиги (для посл. длин n , будет n всевозможных сдвигов)
Потом берем все последовательности и сортируем в лексикографичесокм порядке и берем их последние элементы
Получаем новую последовательность, по ней надо восстановить исходную.

Помогут любые дельные идеи, реализую уже я их сам. 

Это сообщение отредактировал(а) urdnot - 28.10.2016, 18:06

А есть доказательство этого утверждения?

Наверное я не совсем понятно объяснил про сдвиги. Это все возможные вращения последовательности , например:
{3,5,6,1} ->  {5,6,1,3}
                      {6,1,3,5}
                      {1,3,5,6}
                      {3,5,6,1}
Поэтому на последней позиции окажутся все элементы последовательности, а лексикографическая сортировка перемешает их, т.е. получится перестановка исходной последовательности какая-то

Ааа... ок.
Нада подумать... как я понимаю, полный перебор тебя не устроит.

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

По подробнее распишу все же:
1.  {3,5,6,2}

2. Повороты:
     {5,6,2,3}
     {6,2,3,5}
     {2,3,5,6}
     {3,5,6,2}

3. Сортировка:   (*)
     {2,3,5,6}    
     {3,5,6,2}
     {5,6,2,3}
     {6,2,3,5}

4. Последние элементы: {6, 2, 3, 5} (**)
5. Моя идея:   мы знаем что (**) последние элементы (*) поэтому можеи воостановить частично (*)
     {2, ..., 6}
     {3, ... , 2}
     {5, ..., 3}
     {6, ..., 5}
По этим парам {6,2} ,{2,3}, {3,5}, {5,6} можем восстановить исходную последовательность с точность до поворота ( в мое задаче этого достаточно, потом надо будет просто вращать пока не получишь минимальную последовательность)


Это сообщение отредактировал(а) urdnot - 28.10.2016, 19:18

Вот сейчас подумал, с небольшой можификацией моя идея решает 1ую задачу, например:
a = {3,5,7,4,5,5} исходная последовательность (*)

Отсортированные сдвиги (**):
{3,5,7,4,5,5}
{4,5,5,3,5,7}
{5,3,5,7,4,5}
{5,5,3,5,7,4}
{5,7,4,5,5,3}
{7,4,5,5,3,5}

Последовательность по которой надо восстановить исходную {5,7,5,4,3,5}

1. {3,...,  5}   ->  {5, 3}  (часть иходной последовательности)
    {4,...., 7}   -> {7,4}
    {5,...., 5}   - >{5, 5}
    {5, ..., 4}  -> { 4,5}
    {5,..., 3}   ->  {3,5}
    {7, ..., 5}  ->   {5,7}
Мы знаем что за 3 следует 5 (3 одна поэтому никаких проблем), за 4 следует 5 (тоже нет проблем), за 5 может идти 3,5,7 , но мы знаем что (**) отсортировано поэтому 3,5,7 сортируем и последовательновписываем после пятерок, с 7ой никактх проблемю Получаем:

2. {3, 5, ..., 5}   - >  {5,3,5}
    {4, 5, ...., 7}   ->   {7,4,5}
    {5, 3, ...., 5}   - > {5,5,3}
    {5, 5, ...., 4}   ->  {4,5,5}
    {5, 7, ...., 3}   ->   {3,5,7}
    {7, 4, ...., 5}  ->    {5,7,4}
Дальше проделываем тоже самое и получаем нужную последовательность с точность до поворота (этого достаточно)

Но вот в усложненном варианте такой подход не дает нужный результат. 
Например исходная последовательность: {3,3,6,3,3} разобьется на {{3,3,6}, {3}, {3}} Затем после сдвигов и сортировок:
{3}
{3}
{3,3,6}
{3,6,3}
{6,3,3}
Получаем последовательность из последних элементов: {3,3,6,3,3}
Получаем пары:
{3, ... , 3}  -   {3, 3} ложная пара тройка зациклена на себе
{3, ..., 3}  -   {3, 3} снова ложная
{3, ..., 6}  -  {6,3}
{3, ..., 3}  - {3,3}
{6, ...., 3} -  {3, 6}

{3, 3, ..., 3}  - неверно
{3, 3, ..., 3}  - неверно
{3, 3, ..., 6}
{3, 6, ..., 3}
{6,3, ..., 3}


Это сообщение отредактировал(а) urdnot - 28.10.2016, 20:12

Тогда обрати внимание на то, что последовтельность, отвечающая исходным условиям, состоит из группы подпоследовательностей, каждая их которых лексикографически больше и не длиннее предыдущей, а её элементы образуют неубывающую последовательность. В твоём примере это три подпоследовательности {3,6,10},{3,6,11},{3,6,99}. 

В твоём примере: конечный набор состоит из чисел 99, 10, 11, 3, 3, 3, 6, 6, 6}.
Если подпоследовательность одна - это 3,3,3,6,6,6,10,11,99.
Если две - придётся рассматривать длины первой последовательности от 8 до 5.
Для, скажем, 7, у нас возможны какие варианты?
Для простоты рассмотрим вторую группу, из 2 элементов. Первый может быть 3,6,10 или 11. Он не может быть 99, т.к. тогда не найдём второго - ведь он должен быть не меньше.
Если он 11, то второй - только 99. Если он 10, то второй 11 или 99. Если 6, то второй 6,10,11 или 99. Если 3, то второй 6,10,11 или 99 (3 быть не может, иначе не останется двух троек для первой группы). Т.е. всего-то 11 вариантов перебрать... а всего вариантов будет порядка сотни.

Добавлено через 1 минуту и 27 секунд

Или {{3,3,6}, {3,3}}.

Можно придумать последовательность которая не будет этому удовлетворять: a = {3,5,     90,85,83,82,81 /*убывает*/   ,    50,51,52,53,54,55,56,57,58  /*длинее предыдущей*/} но тем не менее дуовлетворяет исходному условию: {58} > a, {57,58} >a, .., {83,82,...,58} > a, и т.д. Или я просто не правильно понял?
Насчет {3,3,6,3,3} -> {{3,3,6},{3},{3}}. {3,3} не удовлетворяет потому что ее суффикс {3} меньше ее самой. {3} < {3,3}

Это сообщение отредактировал(а) urdnot - 28.10.2016, 21:00

(*) {99, 10, 11, 3, 3, 3, 6, 6, 6}  -  это то что на вход подается, (**) {3,6,10,3,6,11,3,6,99}  -  это то что каким то образом надо восстановить (просто я знаю это потому что сам ее преобразовал и получил (*)). a = {3,6,10,3,6,11,3,6,99} - целиком удовлетворяет условию о суффиксах ее разбивать не нужно, т.е. {99} > a, {6,99} > a, {3,6,99} >a, {11,3,6,99} >a, {6,11,3,6,99} ,..., {6,10,3,6,11,3,6,99}>a. Точнее когда последовательность цеиком удовлетворяет условию о суффиксах, я понял как решать и выше написал, но вот когда последовательность нужно разбивать как с {3,3,6,3,3} там не понимаю как.

Это сообщение отредактировал(а) urdnot - 28.10.2016, 21:24

Про суффикс суффикса речи нигде не было...

Извини, я тебя запутал, {3,3,6,3,3} это я привел пример для 2ой усложненной задачи, там сперва последовательность бьется на максимальные части для которых верное условие с суффиксами (обозначю его (+)). т.е вот берем a = {3,3,6,3,3} возьмем а целиком для него (+) не выполнено потому что {3} < a, дальше берем {3,3,6,3} тоже не выполено {3} < {3,3,6,3}, далее {3,3,6} - выполнено: {6} > {3,3,6} ; {3,6} > {3,3,6} отделяем {3,3,6} от a, получаем {3,3,6} и остаток от а - {3,3}, для него проделываем тоже,  проверяем целиком (+) - не выполнено т.к. {3} < {3,3}. Наконец берем {3} для нее (+) выполнено отделяем от {3,3} получаем остаток {3} и полностью {{3,3,6}, {3}, {3}}

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