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

[Homework] Algorithms - Combinatorial Algorithms

Здравейте колеги,

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

6
Структури от данни и алгоритми 29/09/2015 14:19:59
djc_bg2015 avatar djc_bg2015 922 Точки

Здравей Филип,

Няма да откажа малко помощ по задачата със змията. Вчера около 3-4 часа умувах и стигнах до решение което връща 75 точки и гърми по време в 4тия тест. Подходил съм по следния начин:

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

Би ли ме посъветвал , какъв е правилният начин да се подходи към задачата?

Поздрави и благодаря за отделеното време. :)

1
28/09/2015 08:14:27
Filkolev avatar Filkolev 4486 Точки

Здравей,

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

Друго не мога да видя като оптимизация. Аз съм ползвал списък със символите и хешсет с клетки (не правя матрица, но и паметта тук не е съществена). Не мисля, че твоят стрингбилдър е проблемен. Пробвай да видим дали ще мине с тази оптимизация; вероятно, все пак елиминираш 3/4 от рекурсивните извиквания.

2
djc_bg2015 avatar djc_bg2015 922 Точки

Много ти благодаря за помощта! 100/100.

Жалко, че неможах да се сетя вчера, защото доста се чудих как мога да намля рекурсивните извиквания...

:)

0
Filkolev avatar Filkolev 4486 Точки

Аз тая задача 2 дни я мислих. Кубовете днес ще ми е трети ден. Доста по-трудни са от задачите, които до момента са давани по изпити в СофтУни

0
Ivaka127 avatar Ivaka127 20 Точки

Относно задача 5 от Combinatorial Algorithms.
Предложението на колегата от лекцията да разделим повтарящите се елементи по групи, ми се стори удачно и реших да го имплементирам.
http://pastebin.com/abj7bgYT

2
29/09/2015 21:41:02
mihayloff14 avatar mihayloff14 825 Точки

Здравейте,

захванах се тези дни да правя задачата Snakes на C++. Стигнах до евентуално решение, но когато събмитна в judge ми дава compile time error, докато при мен се build-ва.

Да не би в judge да не се поддържа C++ 11? Ползвал съм unordered set (SortedSet в C#), което е част от новата версия.

0
Filkolev avatar Filkolev 4486 Точки

И аз съм имал подобни проблеми, нещо по настройките на компилатора май беше. Исках да ползвам нещо от С++ 11 и не стана, наложи се да препиша част от решението. 

0
mihayloff14 avatar mihayloff14 825 Точки

Мисля че това ще бъде доста сериозен проблем за хората пишещи на C++ защото това на практика ги орязва от гледна точка на ползване на качествени структури от данни.

Иначе това се оправя на GCC компилатора като му се сложи един флаг: -std=c++

0
01/10/2015 15:05:21
Filkolev avatar Filkolev 4486 Точки

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

0
Filkolev avatar Filkolev 4486 Точки

Колеги, уж реших задачата с кубовете, обаче е доста бавна, малко чийтнах и вдигнах времето в джъджа от 0.75 секунди на 10 секунди, за да мине... 

Предложения как може да се ускори? Ето докъде я докарах: http://pastebin.com/TrXdet7X

Ползвам алгоритъма за генериране на пермутации с повторения, за да намеря всички потенциални кубове. Въртя по три оси получения куб и добавям различните му варианти в хешсет от стрингове (това са числата, слепени със запетая). Ако сред пермутциите получа куб, който го няма в хешсета, увеличавам брояча.

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

2
Ivaka127 avatar Ivaka127 20 Точки

Браво, колега. Доста просто и бързо решение. Ето го и моето: http://pastebin.com/UgaexVZ7
Мислех си, че с къстъм обекти ще успея да оптимизирам, но явно със string е доста бързо.
Само това въртене например RotateXY не е ли напрактика RotateZ, тоест въртене по Z оста.

0
Filkolev avatar Filkolev 4486 Точки

Абе не е никак бързо, защото ми трябват 10 секунди, а авторското минава за под 1.

Осите могат по различни начини да се разглеждат. XY е равнина, но може да се мисли като оста Z, YZ = X, XZ = Y. Просто като си го представях ми беше по-лесно да си представям равнините.

0
byclops avatar byclops 126 Точки

Решението ти минава за 0.784 s, само трябва да преместиш реда в който добавяш намериения куб в HashSet-a няколко реда по-надолу, след  проверката дали комбинацията вече е открита:

 

       private static void Permute(List<string> array, int start = 0)
        {
            var current = string.Join(",", array);
//            MarkUsedCubes(current);

            if (!Used.Contains(current))
            {
                MarkUsedCubes(current);
                CubesCount++;
            }

 

2
Filkolev avatar Filkolev 4486 Точки

Помислих още малко върху задачата със змиите и стигнах до още една оптимизация.

Освен че елеминирам на първата стъпка три от посоките и започвам винаги надясно, спирам да въртя змията, получавайки змии, които започват в други посоки. Така единствено флипвам змията (осева симетрия спрямо оста Х), след което разменям началото и края й и ползвам въртенето само за да стигна до вариант, който започва надясно, който също флипвам. За всяка намерена змия маркирам още 3 изоморфни, докато преди маркирах по 15.

Така минава за 1.76 секунди и заема доста по-малко памет, 67.5 МБ (в сравнение с 3.2 секунди и 240 МБ на предишното ми решение).

Ето и кодът: ЛИНК

2
byclops avatar byclops 126 Точки

Браво! И аз след много мислене и лутане стигнах до подобно решение. Първо генерирам змията, която върви само надясно, след което започвам да я разклонявам надолу.
 В крайна сметка намерих кои форми на змията трябва да запазвам по метода проба-грешка защото така и не успях да го изведа теоритично.

Имах проблеми с променливите от референтен тип и рекурсията, непрекъснато изкачаха някакви необясними проблеми, и в крайна сметка се получи един тюрлю гювеч с типовете данни:)

В крайна сметка го докарах до 1.69 секунди и 40.37 MB.

Ето го и моето решение: http://pastebin.com/w6bzxvBf

2
Filkolev avatar Filkolev 4486 Точки

Добавих и още една мини-оптимизация - както викам рекурсивно генериране на змия надолу само ако размерът е по-голям от 1, така смятам най-малкия възможен размер, при който да викам генериране наляво (той е 2 - надясно, надолу, след което наляво) или нагоре (3 - надясно, надолу, надясно, след което нагоре). Това смъкна още 0.4 секунди, без да оказва влияние на паметта. Едитнах кода от линка по-горе, може да погледнеш какво имам предвид.

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

0
mihayloff14 avatar mihayloff14 825 Точки

Как решихте проблема с генерирането на невалидни позиции (тоест такива в които земята се изяжда. Например SRDLU) ?

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

Чудя се дали има по умно решение.

Освен това, последния тест от judge ми минава за 8.7 секунди и заема 300 МБ памет. Това и при вас ли е така ?

0
02/10/2015 17:05:57
Ivaka127 avatar Ivaka127 20 Точки

Ползвам булева квадратна матрица{2 * n - 1), в която отбелязвам кое е заето и кое е свободно. Самите ходове пазя в друг масив.

При мене последният тест е точно обратно 20МБ памет и 15сек, демек таймаутва и не минава.

0
02/10/2015 18:24:27
byclops avatar byclops 126 Точки

Аз лично проверявам от къде съм минал с помощта на един List<Tuple<int, int>>, в който си слагам координатите на посетените точки. Преди това пробвах с List<int[]>, но не се получи, понеже масивите в листа не бяха статични, а се променяха като задам нови стойности в масивите от които съм ги копирал.

Първоначалната ми идея беше за Stack<int[]>, но и това не сработи по същата причина.

 

0
Filkolev avatar Filkolev 4486 Точки

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

ПП Авторското решение (на Наков) минава за около 7.5 секунди и 270 МБ. Според мен имаш място за оптимизация, може би ако не си елиминирал първоначално другите три посоки, за да оставиш в първата клетка само надясно.

0
02/10/2015 19:00:10
ppbaev avatar ppbaev 157 Точки

http://pastebin.com/BgADtaxz

Здравейте, ето още едно решение. Пазя позициите на змията в матрица, като започва от средата. Въртя змията със стрингбилдери. 

 Memory: 26.27 MB Time: 1.139 s

4
Ivaka127 avatar Ivaka127 20 Точки

Супер резултат, колега.
При мене Памет: 70.10 MB Време: 1.553 s
Аз тръгнах малко по друг път. Изчислявам релативен път (при него имам само три посоки - forward, left, right), вместо четири, както при абсолютния RDLU. Така с този релативен път и с три негови производни (огледален, обратен и обратен-огледален) покривам всички възможно варианти.

 

http://pastebin.com/ANXvq4Yz

0
02/10/2015 19:57:51
Hristo_Penchev avatar Hristo_Penchev 388 Точки

Някой разбра ли защо итеративното решение за пермутациите работи? Подкарах го, гледайки хинта, но изобщо не мога да си обясня какво се случва. А го мислих цяла вечер.

2
deyan.boikliev avatar deyan.boikliev 4 Точки

И аз имам същия въпрос. Доста неинтуитивно ми изглежда и бих се радвал, ако някой го обясни. Доста време го мислих, но така и не достигнах момент, в който да си кажа "да бе, колко е просто  всъщност".

По-конкретно ме интересува каква е идеята зад тези опеации:

  if i is odd, then let j = p[i] otherwise let j = 0

...

while (p[i] is equal to 0) do {
    let p[i] = i
    increment i by 1
} 

 

0
Filkolev avatar Filkolev 4486 Точки

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

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

0
deyan.boikliev avatar deyan.boikliev 4 Точки

Дам, ясна е схемата, все пак не съзерцавам кода с надежда изведнъж да ми светне лампичката :D.
Разписал съм сигурно няколко листа освен дебъгването, но все още не виждам идеята зад този алгоритъм, който очевидно работи.

0
bozhidarpetrov avatar bozhidarpetrov 1 Точки

Здравейте,

Понеже нямам опит с Judge системата, дали някой е писал задачата за змията на Java? Каквото и решение да пусна не минава тест 3 и 4. Накрая взех едно от решенията на колегите на C# и го написах на Java и пак същия ефект. Времетраенето и паметта са в допустимите граници според резулатите...

Някой ако има идея да сподели :)

 

0
14/10/2015 06:26:14
Filkolev avatar Filkolev 4486 Точки

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

Коментар по кода ти - in.close() - не го прави. Името на променливата също бих го променил.

0
bozhidarpetrov avatar bozhidarpetrov 1 Точки

Здравей,

Какво значи да изтегля тестовете? Извинявай, но не съм запознат с Judge. Някъде мога да видя с какви параметри го пуска Judge? Има ли как да дадеш броя змии за N = [1..15], че за N > 6 е трудно да се проверяват решенията.

Благодаря

0
Filkolev avatar Filkolev 4486 Точки

Към всяка задача в джъдж има качени ресурси - условие, авторско решение и др. За тази задача са качени и тестовете, т.е. може да видиш на състезателните тестове какво се подава като вход и какво се очаква като изход.

1