[Data Structures] Exam 13 Sept 2015
Здравейте, тъй като наближава изпита по структури от данни, започнах да се подготвям решавайки изпита, който беше даван на миналата инстанция на курса. Тъй като в този курс най-вече се учим да използваме подходящи структури от данни, за конкретната ситуация, за да имаме максимално добра оптимизация, е изключително важно времето, за което минават тестовете, и затова е изключително важно да няма random лагвания на Judge конкретно за този изпит, но ето какво се случва. Тъй като не съм сигурен дали проблема се проявява от самия Judge или от конкретно моето решение, нека започна малко от по-назад. Първо, задачата не е трудна за реализация, тънкостите се проявяват в 1-3 теста, където има тест на това колко бързо ни работят структурите(ако видите начина на оценяване, ще ви е ясно, че дори и един тест е критично важен за крайния резултат). Та общо взето важния момент, който забелязвам е, че трябва да се използват такива структури, че хем бързо да добавяме игри, хем после, когато ги търсим по prefix да са ни сортирани, за да можем максимално бързо да ги извлечем. Затова в Хеш Речник добавям играта заедно с нейната парола, и в SortedSet пазя имената на регистрираните игри, за да мога после максимално бързо да извлека по даден префикс. Добавяйки обаче в този SortedSet, който се имплементира върху подредено дърво, вече при командата RegisterGame аз имам сложност, която не е константа ами е log(n). И ETO какво се получава в джъдж, тестовете, които съм задраскал са с променен код, но останалите са с един и същ код, и е факт, че 2 пъти получвам 100 точки, но повече пъти не ги получавам. Та общо взето пиша тук, за да попитам дали използваните стуктури и алгоритъм от мен не е "стабилен", и затова да се получава това разминаване и евентуално ако е нещо свързано със самия джъдж, да бъде нещо като "бъг репорт". Тук оставям и целия си код ако се интересувате от друга част свързана с него.
Честно казано, дори не знаех за сложността на Substring метода :D. Иначе за тези Prefix Trees и Tries, не съм ги ползвал до сега и затова може би не съм разгледал варианти с тях, благодаря за предложението. Щом Substring е с линейна сложност, мислиш ли, че това може да създава проблем от гледна точка на бързодействие на програта при сравняване на префикса с играта(по конкретно тук: if (game.Substring(0, prefix.Length) == prefix)). Също забелязах, че има метод .StartsWith(), но не съм сигурен дали той е по-оптимален от Substring. Ще се радвам да чуя мнението ти.
Абе, човек, няма по-оптимален начин да вземеш парче от низ. Щом е префикс задължително трябва да изциклиш символ по символ от първия до N без 1 дължина на префикса. И префиксното дърво ще се държи така при запазване на префиксите сигурно. Обаче едно е при всяко търсене да циклиш 0..N-1, друго е веднъж и после само да луукъпваш.
Ясно, значи сега ще се поразровя да видя как стоят нещата и ще си изгледам недоизгледаните лекции от курса, в които предстои да се говори за prefix tree. :)