Здравей,

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

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

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

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

:)

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

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

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

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

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

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

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

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

Решението ти минава за 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++;
            }

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

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

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

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

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

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

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

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

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

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

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

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

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

http://pastebin.com/ANXvq4Yz

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

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

  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
} 

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

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

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

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

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

Здравей,

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

Благодаря

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