Magic Strings Time Out

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

Пускам за тестове задачата Magic Strings на C# и се дъня с времето. От 16 теста 13 ми излизът извън времевия лимит. Четох във форума, че е имало проблем с тайминга при джава и допускам, че може да съществува същия и при С#. Или пък моето решение да е прекалено тежко.

Тук можете да го погледнете:
http://pastebin.com/sCnvmfi3

Ползвам осем цикъл с по четири елемента един в друг. Това предполага над 1000 комбинации, не знам това много ли е. За проверките използвам два временни масива и лист от стрингове, който после сортирам. Но доколкото знам тези елементи не са натоварващи. Необходимо ли е да оптимизирам програмата си и как може да стане?

След многобройни тестове в Judge системата открих къде е проблемът. Всъщност осемте цикъла отнемат съвсем малко време. Това, което дъни работата е:

for (byte j = 0; j < sequences.Count; j++) Console.WriteLine(sequences[j]);

Листът sequences е съставен от стрингове. Явно обхождането на лист с референтни типове е доста бавно. Затова предприех друг подход. Махнах листа и заложих азбучната подредба в самите цикли. Това стана много лесно - в началния съхраняващ масив размених местата на цифрите и вместо първоначалното {3, 4, 1, 5} го направих { 1, 4, 5, 3} Така програмата цикли през "теглото" на буквите в азбучен ред и като засече комбинация, която да отговаря на условието, просто я печата, без да товари паметта. Лесно се добавя един булев израз, който да засече дали има изобщо намерени такива числа и ако няма, да връща "No". Тук можете да видите ъпдейтнатия код:

http://pastebin.com/MjZyNBfv

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

Magic Strings Time Out