Помощ за задача "Subsequences"


0

Здравейте,

Мъча една задача от 1 час и не разбирам защо не ми дава пълния брой точки. Ако може някой да погледне. На всякакви идеи и помощ ще съм благодарен. Прилагам линк към задачата: Subsequences и към решението ми: my solution.






Отговори



14

Задачата се решава с техника наречена динамично оптимиране. На всяка стъпка ние намираме най-доброто решение до момента, като следващите решения се базират на него. Сега, относно самата задача:

В случая, имаме 2 редици. Решението ще построим във форма на матрица. Нанасяме двете числови редици - едната по хоризонталата, другата - по вертикалата. Използваме примера от условието:

Знаем, че за да имаме обща подредица, трябва да имаме и общи(еднакви) числа. Започваме да попълваме таблицата ред по ред/колона по колона като проверяваме дали текущите две числа съвпадат. В такъв случай предприемаме дадено действие в зависимост от резултата.

Започваме с нещо лесно. "-" символа означава нищо. Ходим колона по колона. Въпросът е: Нищо и нищо имат ли обща подредица или по-скоро - числата равни ли са(нищо равно ли е на нищо)? Отговорът логично е не, тъй като имаме видима липса на числа за сравнение, следователно записваме 0 на текущата позиция, тъй като това е най-дългата възможна намерена подредица до момента. Местим се една колона надясно. Проверяваме: Нищо равно ли е на 24? Отговорът отново е не. Тъй като числата не са равни(или по-скоро едното липсва), няма как да имаме по-голяма намерена подредица чрез тези 2 стойности. В такъв случай, взимаме последното най-голяма намерено решение до момента като резултат. Това е числото, което се намира в миналата колона, а именно - 0. Записваме резултата(0) на текущата позиция. Продължаваме така до последната колона за реда. Тъй като сравняваме Нищо с число, винаги ще получаваме 0. След попълването на първия ред, таблицата изглежда така:

Очевидно, решението за цялата първа колона е аналогично, тъй като сравняваме цялата втора редица отново с нищо. Резултат:

Тук вече започва самото решение.

Сравняваме всяко едно число от първата редица(всяка една колона) с първото число от първата колона(13). Установихме, че най-дългата редица между нищо и 13 е 0. Изместваме се една колона надясно. Сравняваме 13 и 24. Те не са равни, следователно взимаме най-доброто решение, намерено до момента. Тук има малка тънкост, обаче. Къде точно се намира това решение. В зависимост от клетката, която проверяваме, ние знаем кои са двете най-добри вече намерени решения за двете редици поотделно, без да включваме текущото число.

1. Клетката директно отгоре на търсената показва каква е най-дългата текуща намерена редица, без да използваме текущото число от реда от втората редица.

2. Клетката директно вляво на търсената показва каква е най-дългата текуща намерена редица, без да използваме текущото число от колоната от първата редица.

Тъй като търсим оптимален резултат, ние взимаме по-голямото от двете числа и го записваме в текущата търсена клетка. Ако двете стойности са еднакви, няма значение коя ще вземем.

В нашия случай, проверяваме кое е по-голямото число - 0 или 0. Тъй като са равни, няма значение и просто записваме 0.

Минаваме на следващата колона - 13 равно ли е на 13? Отговорът този път е да! Щом намерим равентство, взимаме стойността, която се намира отгоре-вляво на текущата клетка и добавяме едно към нея. Обосновката е следната: в клетката отгоре-вляво се намира най-дългата намерена стойност без да използваме текущите 2 числа. Щом текущите 2 числа са равни обаче, то би следвало че текущата редица е с 1 по-дълга от предишната. Пресмятаме числото и го записваме. В нашия случай имаме 0 + 1 = 1. Резултат:

Продължаваме с този алгоритъм докато не попълним цялата таблица. Клетката най-долу вдясно показва крайния резултат, тъй като в него участват напълно и двете редици. 


Най-дългата редица е 4. Как да разбереш коя е, обаче, няма да обяснявам, че стана достатъчно дълго.

Редът и колоната с "-"(или нищо) се правят за улесняване на изчисленията, иначе трябва да се правят много излишни проверки. Последователността на решаване може да бъде и обърната(увеличаваме числата във втората редица, а държим тези в първата константни).

Съжалявам за форматирането. 1 час си играх да правя таблици в отговора и в крайна сметка пак не ги визуализира правилно. Ще се опитам да го пооправя.

Тъй като kon.simeonov е предоставил решение, аз няма да пиша такова. Ще ти дам само референция към авторското решение на дадената задачата, което обаче е на C++, както и тестовете - Февруари 2015 - Динамично оптимиране.


от zhulien (785 точки)


1

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

Междувременно открих една грешка при мен - проверявам диагонално предишната клетка, което е излишно, но и не влияе на резултата, та в крайна сметка ако разкоментираш принтирането на клетките на матрицата ми, ще видиш, че получавам точно това, което и ти. Разликата между моето решение и твоето предложение е, че аз нямам "-" редове, а просто правя проверки да не излезна от матрицата, когато проверявам горна или лява клетка. Така че все още се чудя защо някои тестове не минават и ако се справя с проблема, ще споделя как :)

Мерси отново за изчепрателния отговор!

P.S:
Намерих видео с решение на задачата и видях, че аз не съобразявам случая, когато имам повтарящи се числа в редицата и съответно задачата ми работи само в частен случай(грешна е :Д). 


от antoanelenkov (1047 точки)


2

Мога да ти дам решение, което съм писал, но ми е малко трудно да го обясня, без да рисувам екселски таблици :D

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace sequences { class Program { static char[] split = { ' ' }; static void Main(string[] args) { ulong n = ulong.Parse(Console.ReadLine()); ulong m = ulong.Parse(Console.ReadLine()); string[] first = Console.ReadLine().Split(split); string[] second = Console.ReadLine().Split(split); ulong[,] answer = new ulong[n + 1, m + 1]; for (ulong i = 1; i <= n; i++) { for (ulong j = 1; j <= m; j++) { if (first[i - 1] == second[j - 1]) { answer[i, j] = answer[i - 1, j - 1] + 1; } else { answer[i, j] = Math.Max(answer[i-1, j], answer[i, j-1]); } } } Console.WriteLine(answer[n,m]); } } }

P.s. ако искаш, пиши на лично :)
P.s.2. кпк-то ми е на ниво :D


от kon.simeonov (5238 точки)