Задачата е към тема 8. Сетете се защо. Трябва да положите доста усилия и прочетете как се решават няколко алгоритъма за да съберете максималния брой точки, затова той е увеличен. Име на задачата oyler :) (така си я кръщавам, знам не се пише така на Английски)
Ако не можете да решите задачата в зададения й вид, опитайте да я решите да работи в случаите за изцяло ориентиран и неориентиран граф.
Езикът пак ли е Си? Или можем да избираме? Ако е - моля кажете поне компилатор, с който ще се тества...
Можете да избирате:
C/C++ - Visual Studio 2005
Java - 1.5
C#/CLI/Visual Basic/J# - Visual Studio 2005. Ако изберете някой от тези .NET езици, сложете Visual Studio 2003 или Visual Studio 2005 проекта в архива.
C/C++ - Visual Studio 2005
Java - 1.5
C#/CLI/Visual Basic/J# - Visual Studio 2005. Ако изберете някой от тези .NET езици, сложете Visual Studio 2003 или Visual Studio 2005 проекта в архива.
Ойлеров път или ойлеров цикъл? В условието, където се пояснява какво е ойлеров цикъл се описва ойлеров път: "Да се намери ойлеров цикъл в графът – т.е. път, който минава през всяко ребро по веднъж."
Цикъл се търси. Трябва първият и последният връх да са един и същи.
Задачата е порутващо трудна - чак неподходящо трудна. Имайте предвид. Не подценявайте условието. Затова ако решението работи в някои случаи - ще получите пропорционално точки за това. Т.е. различно от досегашните домашни, където искахме 100% успешни решения за да се получат точки.
Задачата е порутващо трудна - чак неподходящо трудна. Имайте предвид. Не подценявайте условието. Затова ако решението работи в някои случаи - ще получите пропорционално точки за това. Т.е. различно от досегашните домашни, където искахме 100% успешни решения за да се получат точки.
Какво е поносимото време за работа на алгоритъма?
"Да се намери ойлеров цикъл в графът – т.е. път, който минава през всяко ребро по веднъж."
Значи е достатъчно да намерим само един цикъл, а не всички възможни, ако съм разбрал правилно.
Да речем, за дадения в условието пример, се приема за вярно извеждането само на един от трите възможни отговора.
Да. Трябва да намерите произволен ойлеров цикъл
Здрасти, аз вече качих едно решение, но после му направих значително подобрение.
Ще мога ли да кача новия си файл?
Ще мога ли да кача новия си файл?
Може. Има ли проблеми с повторното качване?
Да.Просто след първоначлното качване вече не е възможно да се качва друг файл. За първите домашни беше възможно, и помня че и други са задавали този въпрос във форума.
Помня, че на предното домашно имаше нещо такова, но само някои се оплакваха - сега вече съм го оправил никой да не може да се оплаква. Препоплагам причина някои да не могат да качват е, че аз вече съм download-вал файлове на някои. Да погледна решенията все пак... btw, като измисляте алгоритъм, опитайте се да го докажете все пак. Може пък да не е верен :)
И още нещо. Нали всички знаете какво е мултиграф?
И още нещо. Нали всички знаете какво е мултиграф?
Дайте идея как бих могъл да си тествам алгоритъма с по-голям граф. Търсих в интернет за голям ойлеров граф, но не намерих. Ако някой е имал повече късмет(време) от мен и е намерил такъв, го моля да го сподели с мен и с останалите.
За първи път чувам някой да търси граф в интернет. Хайде да подхождате по-сериозно към заданията - пишете си генератори на графи. Условието за ойлеровост е лесно. Генерирате граф дето да отговораря на това условие. После някои насочени ребра ги направете ненасочени (може пак случайни) за да тествате останалата част от алгоритъма си.
Е все пак не ми се случва често да пиша задачи свързани с графи.
А мога ли да ползвам inline assembler-а
Силно препоръчвам това да не се прави. Компилаторите са достатъчно добри.
Ако все пак е много наложително - важното е Visual Studio 2005 да го компилира. За C++ сорсовете аз ще компилирам директно с cl - т.е. ако ми дадете проект с разни опции на компилатора - няма да го използвам, а ще изполвам мои си опции.
Ако все пак е много наложително - важното е Visual Studio 2005 да го компилира. За C++ сорсовете аз ще компилирам директно с cl - т.е. ако ми дадете проект с разни опции на компилатора - няма да го използвам, а ще изполвам мои си опции.
Някакъв проблем ако използвам GCC? Понеже изпитвам силна антипатия към MS компилаторите.
Аз също не изпитвам някакви симпатии към Microsoft (макар, че точно компилатора в 2005 не е лош, а имат и още добри продукти). По-добре би било за всички да се съобразяваме с потребителите (в случая с мен).
Най-добрият начин според мен за това е да се съобразяваме със стандартите. Един такъв е C++ стандарта. Не ви препоръчвам да използвате нещата специфично за gcc, а също така и нещата специфично за Visual Studio, т.к. може да подам опция на компилатора да ги изключи.
Най-добрият начин според мен за това е да се съобразяваме със стандартите. Един такъв е C++ стандарта. Не ви препоръчвам да използвате нещата специфично за gcc, а също така и нещата специфично за Visual Studio, т.к. може да подам опция на компилатора да ги изключи.
C99? POSIX?
За теб ще компилирам с:
gcc (GCC) 3.2.3 (mingw special 20030504-1)
Да знаеш, че е много бъгава версия. Не използвай long long.
gcc (GCC) 3.2.3 (mingw special 20030504-1)
Да знаеш, че е много бъгава версия. Не използвай long long.
Какво е ID-то на заданието????????
Пише го във първия пост oyler
Възможно ли е и моят код да бъде компилиран с minGW (GCC) ?
По някаква причина, когато компилирам с Visual Studio 2005, програмата забива (препълване на стека) . Знам, че проблема не е в кода, тъй като това се случва единствено при големи графи (максималния вход). За малки графи, програмата работи и във Visual Studio 2005.
Под minGW такъв проблем нямам, независимо от размера на входа.
По принцип е добре в този случай да направите решението итеративно. Мога да увелича максималния размер на стека, но правилното решение на този проблем е итеративна имплиминтация на алгоритъма.
С mingw ще компилирам само на хора, които по някаква причина, която не мога да fix-на не се компилират с Visual Studio 2005.
С mingw ще компилирам само на хора, които по някаква причина, която не мога да fix-на не се компилират с Visual Studio 2005.
Прощавайте за леко глупавия въпрос, но си изпратих файла с 1 час закаснение- има ли проблем?
Няма страшно. Проверката още не е започнала.
Изпратил съм домашното навреме. Но при големи графи и при мен гърми със stack overflow заради рекурсията. Кажете дали ще увеличите стека? А ако не, може ли още да се изпраща, за да мога да си кача итеративния алгоритъм ;-)
Ако имаш итеративен алгоритъм - качвай го днес.
Готово :-) Мерси за дадената възможност.
Здравейте. Днес изпратих решение на задачата за ойлеровия цикъл. Знам че е доста след крайния срок, но моля ако е възможно все пак да я проверите. Едва вчера успях да я довърша и не ми се иска времето което съм отделил да отиде на вятъра. Не видях вече да има публикувана идея за решение затова се надявам че няма да има проблем. Благодаря предварително.
Здрасти.Искам да попитам дали ще ми бъде провечена задачата???Самото решение съм го пратил преди 2 седмици ,но онзи ден видях ,че не съм си написъл факултетния номер и затова пратих същото решиние ,но този път в факултетния ми номер.
kakvo stana s rezultatite bre hora ot oileroviq cikul:)za6to ne dadohte pove4e vreme za mislene kato tolkova go bavite tova doma6no:)a i tazi zada4a toto7x7 napravo zabravete golqma 4ast da q predadat .... ne stiga 4e proektite sa si brutal ,a i doma6nite :)Ako celta e da ni pokajete kolko vi puka za tozi "kurs" se hvanete v ruce ... vupreki ,4e ve4e mnogo hora sa se otkazali psihi4eski,zaradi nekorektnostta i lo6ata organizaciq na prepodavatelite:)
Да, наистина! Какво стана с резултатите????
Наистина, какво стана?
Ами незнам ти трябва да каже ;-)
Вече минаха 2 седмици и все още няма никакви резултати. За какво го бързахте толкова само не мога да разбера 
Домашното си имаше срок, аз не съм отказвал закъснели решения, за какво бързане става дума. Контестации/поправяне на бъгове няма да има така, че не виждам причина да бързате. Освен това броят изпратени решения е повече от очакванията ми.
Are bre .... kakvo napravi s tova doma6no ... e nikakuv interes ne suzdavate u horata da u4at ,a u6kim ste prepodavateli :)ne stava taka hora ..... a trqbva da slujite za primer:)
Спокойно. Има време :-D До 8 Юли ;-) За къде си се забързал :-D
Все още не съм проверил всички работи, а и трябва да мине и тест за преписване, но бих казал, че има доста хора, които не разрешават правилно нито един тест - дори мултиграфи с всички ребра насочени (часто завършават с runtime) - явно доста хора не са разбрали частта за мултиграф, което не значи че ще получат право да изпратят повторно. В момента замислям известен брой тестове, които да ги генерирам като графи, а не като мултиграфи.
Оценяването на домашното е готово. Оценяването е върху набор от 50 теста - броят на точките е равен на броя верни теста в рамките на 2 секунди. Ако решението е било вярно, но бавно (за завършилите в рамките на 2 сек. тестове) - се прибавят още 5 точки. Това е отбелязано в рецензиите ако такова правило е приложено. Ако не е приложено - най-вероятно рецензията е празна. Тестването се проведе на Pentiurm M 1.86GHz с 1GB памет.
Решенията на java са получили половин секунда бонус.
Това, че няма максимум точки (постигантият максимум е 29) не значи, че никой няма да получи максимум точки от домашни - както казахме ще scale-нем точките от домашни така, че максимум бонус от домашни ще се получава например при поне 75 точки (или 60 или друг броя) събрани от всички домашни.
Забележете, че ако сте преписали или дали да препишат това домашно трябва да се запишете на https://learn.fmi.uni-sofia.bg/mod/forum/discuss.php?d=318 и да се откажете от всички бонус точки от домашни.
Тестовете са тук
Решенията на java са получили половин секунда бонус.
Това, че няма максимум точки (постигантият максимум е 29) не значи, че никой няма да получи максимум точки от домашни - както казахме ще scale-нем точките от домашни така, че максимум бонус от домашни ще се получава например при поне 75 точки (или 60 или друг броя) събрани от всички домашни.
Забележете, че ако сте преписали или дали да препишат това домашно трябва да се запишете на https://learn.fmi.uni-sofia.bg/mod/forum/discuss.php?d=318 и да се откажете от всички бонус точки от домашни.
Тестовете са тук
Искам да попитам колко е най-големият брой точки получен от тази задача? А и ще може ли да качите тестовете, с които сте тествали.
А и още нещо: Как може един алгоритъм с сложност 2N да е оценен с 18 точки, а алгоритъм с полиномиално време да е оценен с 19 (в случая - моя :-D)
А и още нещо: Как може един алгоритъм с сложност 2N да е оценен с 18 точки, а алгоритъм с полиномиално време да е оценен с 19 (в случая - моя :-D)
Така се е случило на тестовете, че алгоритъма за 18 точки е бил верен, а пък този "бърз" алгоритъм да не е бил толкова бърз или може да е бил грешен ;-)
Като си заговорихме за добри алгоритми - хубав алгоритъм би трябвало да е базиран на Matching или Maximum Flow, а не на random неща. Но 20-30 точки също не е зле - Maximum Flow трябва доста да се оптимизира за да влезне в лимита за време.
Като си заговорихме за добри алгоритми - хубав алгоритъм би трябвало да е базиран на Matching или Maximum Flow, а не на random неща. Но 20-30 точки също не е зле - Maximum Flow трябва доста да се оптимизира за да влезне в лимита за време.
Ами представи си моя алгоритъм се базира точно на максимален поток, а не на "random неща" както казваш ти. Ето статията на която се базира алгоритъма и ти ми кажи как става така че само 19 теста са били верни. (http://www.crt.umontreal.ca/~nikolaj/tutorials/arcrouting/miniplay/english/quizI_3.html)
Много хубаво се базира, но вероятно имаш бъг, защото на 31 теста завършва с грешен отговор (а има хора, които ги правят правилно).
Погледни няколко поста нагоре за тестовете
Погледни няколко поста нагоре за тестовете
Ти хубаво си сложил тестовете ама да беше сложил и верните отговори ;-) В момента съм на 21 тест и ми изкарва резултат в рамките на 1 сек на всичките тестове направени до сега.
И между другото тестовете са ти 51, а не 50 ;-)
П.П. Ще има ли възможност за контестация, т.е. ако има бъг да го фиксна и да ти го пратя отново?
И между другото тестовете са ти 51, а не 50 ;-)
П.П. Ще има ли възможност за контестация, т.е. ако има бъг да го фиксна и да ти го пратя отново?
Може. Няма да ти дам checker обаче за да си напишеш :-) И после ще получиш морално удовлетворение. Ако решиш 100% от тестовете и донесеш решението на защитата - ще получиш 1 точка повече на проекта.
нулевият тест не се брои в точките :-)
нулевият тест не се брои в точките :-)
Доколкото знам най-доброто, което може да се измисли при наличието на NP-пълна задача е намирането на евристика, най-често именно "random" решение. Нещо не разбирам, защо сега се оказва, че е трябвало не да решим задачата ефективно, а да напишем точно определен алгоритъм. Най-малкото това е некоректно.
Не виждам нищо некоректно в това да оценим задачите на база набор от тестове. По-обективна оценка от тази е само да даваме или 0 или максимум точки в зависимост от това дали работи за всички тестове или не.
Твоето random решение работи в над половината случаи, но не във всички. На колегата решението би трябвало да работи във всички, но вероятно поради бъг - това не е станало.
Задачата не е NP.
Твоето random решение работи в над половината случаи, но не във всички. На колегата решението би трябвало да работи във всички, но вероятно поради бъг - това не е станало.
Задачата не е NP.
Сега се зачетох в линка на колегата. Изглежда наистина има полиномиално решение на задачата. Това, разбира се, не значи, че евристичното решение е по-лошо.
Вижда ми се странно, че нито едно от изпратените решения не работи за последните тестове. Сигурно ли е, че описаните в тях графи са ойлерови?
Аз също недоумявам как точно става оценяването. Ако може да се кажат две думи за това как се образуват точките и какви са критериите за оценяване. Аз лично мисля, че съм написал доста добър алгоритъм и се чудя защо имам 28/50... Току що видях, че най-многото събрани точки са 29. Чудя се не е ли логично след като максимума точки за тази задача е 50 - най-доброто решение да получи 50?
Логично е да получите точки колкото сте изкарали. А накрая ще scale-нем нещата така, че 15 точки от домашни да са нещо съвсем постижимо и да не сте ощетени.
А може ли да сложиш и програмката(сорс) с която тестваш за вярност?
Поради бъг в checker-а, се установи че имаме победители - т.е. хора с по 50 точки на задачата. Предвиденият обезщетителен бонус 5 точки за вярно решение отпада като идея - т.к. на повечето хора точките са увеличени (това значи, че някои "загубват" до 5 точки).
Znachi shte imeme novi rezultati ?! Zashtot az kato si testvah reshenieto namerih dosta primera s koito se preborva moqta programa.
A imam 0/50.
A imam 0/50.
Не така мислеше моя checker. Трябваше да спазиш формата на изхода.
Ami togava shte predstavq pravilen izhod, za da budat oceneni polojenite usiliq.
Poneje nqkak si ne e chesno tolkova mnogo trud da ide na vqtura ?!
Promenen e samo izhoda.
Formata koito sum spazil e :
<vruh><sp><vruh><sp>...<vruh><sp> ,
kudeto <sp>/(' ') e <space>.
Ako i tova ne e verniq format, molq da go formalizirash po nqkakuv nachin.
Poneje ne sum razbral ot statiqta na zadanieto, propusnato e izrichnoto spomenavane na praznite mesta.
Reshenieto e kacheno na :
http://comtop.hit.bg/pranka/fn43745_oyler.rar
Poneje nqkak si ne e chesno tolkova mnogo trud da ide na vqtura ?!
Promenen e samo izhoda.
Formata koito sum spazil e :
<vruh><sp><vruh><sp>...<vruh><sp> ,
kudeto <sp>/(' ') e <space>.
Ako i tova ne e verniq format, molq da go formalizirash po nqkakuv nachin.
Poneje ne sum razbral ot statiqta na zadanieto, propusnato e izrichnoto spomenavane na praznite mesta.
Reshenieto e kacheno na :
http://comtop.hit.bg/pranka/fn43745_oyler.rar
I az imam greshen izhod. Popravih go i go ka4vam pak. Ako moje da buda ocenena pak? Sujalavqm za nevnimanieto!
А при това положение остава ли идеята със "scale-ването" на точките от домашни?
Да. На мен ми се струва разумно следното, въпреки че не сме взели решение как да е:
точките от домашни се делят на 5. И ако са над 15 - стават 15. Така при 75 и повече събрани точки от домашни, получавате 15 точки. В момента няма човек събрал 75 точки, но има две домашни, които Мило трябва да провери. И от там само максимумът е 70 (теоретично де... не ми се струва възможно някой да победи на играта във всички случаи... не знам как е оценяването там)
точките от домашни се делят на 5. И ако са над 15 - стават 15. Така при 75 и повече събрани точки от домашни, получавате 15 точки. В момента няма човек събрал 75 точки, но има две домашни, които Мило трябва да провери. И от там само максимумът е 70 (теоретично де... не ми се струва възможно някой да победи на играта във всички случаи... не знам как е оценяването там)