Софтуерно Инженерство
Loading...
+ Нов въпрос
mihayloff14 avatar mihayloff14 825 Точки

Algorithms Sample Exam

Здравейте,

Днес се захванах да решавам примерния изпит, който пуснаха за правене в judge.

Забелязах некоректност в последната задача Line Inverter. Решението което е описано в презентацията дава 100 точки в judge, но не работи коректно при някои случаи. Например ако имаме дъска:

WBB
WBB
WBB

Решението ще отнеме 5 хода, а реално би трябвало да са 1. Причината е, че решението винаги първо инвертира редовете вместо колоните. Според мен, по оптимален вариант е да се инвертират колоните или редовете първи в зависимост от това колко пъти ще се наложи инвертиране въобще.

Ще споделя решенията на задачите си по-късно.

Тагове:
0
Структури от данни и алгоритми 09/11/2015 17:24:16
Filkolev avatar Filkolev 4501 Точки

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

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

Не сме обявили официално, че задачите са качени, защото е възможно да има подобни пропуски, а и има доста време за подготовка все още. Ако намерите някакви недоразумения, споделяйте.

В допълнение за задачата, значение откъде се почва има само ако клетка (0, 0) е бяла. Ако е черна броят преобръщания винаги ще е сборът на броя бели клетки в първи ред + броя бели клетки в първа колона. Когато клетката в горния ляв ъгъл е бяла, общият брой преобръщания ще е 1) сумата на броя бели клетки в първа колона + броя черни клетки в първи ред (ако започнем с колоните) или 2) сумата на броя бели клетки в първи ред + броя черни клетки в първа колона (ако започнем с редовете).

0
09/11/2015 18:09:30
Filkolev avatar Filkolev 4501 Точки

@Kamigawa откри още една неточност в тази задача. Да се взимат само редовете или колоните започващи с бели клекти не гарантира оптимално решение. Ако примерно в първи ред/колона имаме преимуществено бели клетки, то по-изгодно е да се инвертира първо първи ред/колона, което намалява общия брой инвертирания след това. Става въпрос за тест 6, където досега отговорът беше 26, а лесно може да се види, че са достатъчни 10 стъпки.

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

0
Filkolev avatar Filkolev 4501 Точки

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

0
dim4o avatar dim4o 289 Точки

И аз нещо не мога да разбера и приема упътванията към тази задача. По-скоро ми изглеждат като евристики, отколкото като greedy algo. Преди да ги видя реших задачата по някакъв мой си измислен начин: на всяка стъпка вземам реда или колоната с най-голям брой бели полета и давам invert: http://pastebin.com/je1TVrcy Решението е доста грубо, защото има излишни действия и нечисти методи, но пък се вписва в ограниченията. Знам как да му намаля сложността, но не го правя, защото не съм убеден 100% в коректността на логиката, въпреки че минава всички тестове.

0
moholovka avatar moholovka 169 Точки

Вчера на подготовката я решихме по подобен начин. Според мен максималният брой операции е N и ако след тях имаме бяло, няма решение. Иначе си е чисто greedy нямаме зависимост на стъпките една от друга и понеже гоним минимален брой стъпки съответно взимаме тази с най-много инвертвания.

0
moholovka avatar moholovka 169 Точки

Може ли да пак да помоля за тестовете на Bridges, иска ми се да пробвам малко по различно решение от показаното, но ми дава грешки, а не мога да измисля подходящи тестове.

0
Filkolev avatar Filkolev 4501 Точки

Има линк към архива в страницата на курса.

0