[C# Basic] Advanced Problem 8.* Longest Non-Decreasing Sequence

Ludmil.D 41 Точки

[C# Basic] Advanced Problem 8.* Longest Non-Decreasing Sequence

Write a program that reads a sequence of integers and finds in it the longest non-decreasing subsequence. In other words, you should remove a minimal number of numbers from the starting sequence, so that the resulting sequence is non-decreasing. In case of several longest non-decreasing sequences, print the leftmost of them. The input and output should consist of a single line, holding integer numbers separated by a space.

Тестовете както следва по условие:

7 3 5 8 -1 6 7 -> 3 5 6 7
1 1 1 2 2 2 -> 1 1 1
1 1 1 3 3 3 2 2 2 2 -> 2 2 2 2

за тест имам забелечка би трябвало очаквания резултат да е 3 4 5 6 7 8 16

l 11 12 13 3 14 4 15 5 6 7 8 7 16 9 8 - > 3 4 5 6 7 8 9

аз лично научавам допълнително за условието на задачата от тестовете т.е. :
1 1 1 2 2 2 -> 1 1 1 2 2 2 (очакван резултат от мен), но зададен 1 1 1 =>
има условие което не се споменава което се крие зад (non-decreasing subsequence) => под множеството е или нарастващо или равно, което очевидно отговаря на условието да е не намаляващо :)
за да стане още по ясно си добавих допълнителен тест:

1 11 1 12 1 13 1 3 1 14 1 - > 1 1 1 1 1 1

http://pastebin.com/JgMdw9L2

п.с. не намерих решения на този порблем за това си позволявам да пусна отделна тема.
edit: допълнителни тестове 1 2 3 1 1 1 - > 1 1 1 1 (като - most left) && Longest 1 2 3 4 4 4 4 -> 1 2 3 4 (most left) && Longes по идея на dim4o

Тагове:

17/04/2014 22:52:34 Programming Basics

ethanrox 6 Точки

По доста сходен начин мислех и аз, докато гледах условието на задачата, но реших, че за subsequence от равни елементи се броят само поредните.

Тоест от 1 1 1 2 2 2 1, моето решение ти дава 1 1 1, а не 1 1 1 1. А иначе, също смятам, че тряба на примера в задачата да връща 3 4 5 6 7 8 16.

17/04/2014 23:11:28

Ludmil.D 41 Точки

Решението ти определено е бързо и работи за нарастваща поредица но не хваща равните елементи моята зависва на 28-то число .. май няма пълно щастие

17/04/2014 23:45:32

HPetrov 822 Точки

Искам да те попитам защо пускаш цикъла да върти от последната стойност на комбинациите надолу? Смисъл има ли конкретно някакво значение дали ще си върви от 1 до max или обратно? А това, че ти увисва на 27-28 числа е малко кофти, да. Но като се замислиш колко итерации са за 2^28+ степен... :D

18/04/2014 01:47:39

Ludmil.D 41 Точки

Да правилно си забелязал започвам от последната комбинация = 2^(броя на турсените цифри). Комбинацията се представя като полученото число от горната формула (2^28 примерно) се преобразува до бинарно т.е. 11111.. и на всяка позиция за 1-цата взимам число от въведения списък 2^2 -> 111 oт arr[]{1 2 1} като идеята беше първото намерено да е отговора
(ама се оказа че не работи точно така защото отговора може и да е в последната половина т.е. при 000111 последните 111-ци да съдържат отговора)
Не си пазя кода преди модификацията ;/ но на кратко при него 1,1,2,2, -> 1,1,2,2 беше верния отговор

18/04/2014 21:07:58

vladislav_hadzhiyski 66 Точки

http://pastebin.com/RQEbLUMd Това е моето решение на задачката.

По отношение на тестовете редица като:

1 1 1 3 3 3 2 2 2 2 -> 2 2 2 2

Мисля че теста е сгрешен защото най- дългата ненамаляваща редица е 1 1 1 3 3 3.

18/04/2014 02:01:47

Ludmil.D 41 Точки

теста не е сгрешен за съжаление просто има условие което явно не е упоменато а се досещаме по него от тестовете (моя си логика :j ), но четвъртия тест със сигурност е сгрешен :) тест 4: 11 12 13 3 14 4 15 5 6 7 8 7 16 9 8 - > 3 4 5 6 7 8 9(вместо 9трябва да е 16 )

18/04/2014 21:11:39

dim4o 288 Точки

Според мен допълнителното условие за равните елементи е сложено за да усложни леко задачката, за която иначе си има много приятен и кратък алгоритъм. Проблема, е че няма съответствие между условието и примирете, а решението почва да изглежда малко изкуствено (поне при мен :). Не става ясно какъв е случая при 1 2 3 1 1 1. За мен е очевидно 1 1 1 1, но знае ли човек. За 1 2 3 4 4 4 4 също може да се зачудиш...

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

Това е другото ми решение. На по-различен принцип е. По-бавно е и направено само за ненарастващи редици, т.е. както си е по условието, но не и по примерите.

18/04/2014 14:53:45

Ludmil.D 41 Точки

1 2 3 1 1 1 - > 1 1 1 1 (като - most left) && Longest 1 2 3 4 4 4 4 -> 1 2 3 4 (most left) && Longest p.s. заслужава си *-та :D по моя схема де ;j иначе съм съгласен че си има елегантно решение при друго условие и зададени тестове :)

18/04/2014 21:15:10

dim4o 288 Точки

Да, заслужава си *. Даже може би ** даже. Другите ги реших от раз - само тази ме затрудни.

19/04/2014 00:52:31