Професионална програма
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 4482 Точки

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

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

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

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

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

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

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

0
Filkolev avatar Filkolev 4482 Точки

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

0
dim4o avatar dim4o 288 Точки

И аз нещо не мога да разбера и приема упътванията към тази задача. По-скоро ми изглеждат като евристики, отколкото като 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 4482 Точки

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

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.