konkurs po programirane

U4stvate li v konkursa na PC magzine po programirane ili ne vi murzi
[линк]
ako ima nqkoi gotov s zada4ata tuk mojem da sravnim reziltatite

Moite rezultati
Pri
m = 5000
n = 5000000
re6enieto go polu4avam za 19 sec.

no pri
m = 100000
n = 5000000
- za 5 sec

a pri teb kak e ?

Vsyshtnost tva ne e osobeno chestno, nai-malkoto sravniavaite si
gi po e-maila, ne po forumi i po sedianki :))

Абе аз уж съм възпитаник на ФМИ-то и би трябвало да мога да чета такива отвлечени задачи, ама не би. Явно си трябва да си ходил по състезания като малък. Четох, четох, нищо не разбрах и заебах със заключението че явно съм тъп. Да бяха казали с две думи какво се иска, а не да разтягат някакви локуми.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

>Да бяха казали с две думи какво се иска, а не да разтягат някакви локуми.

нещо като разговори с клиент :) ама там ако искаш пари ще седиш и ще слушаш :)))

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

--
"Agile is a mindset, not a set of practices, rules, or tools."
Tom Poppendieck

Задача 1 от конкурса на PC Magazine & Musala Soft

МОЛЕКУЛИ

Световно известният молекулярен биолог Низю Стрингьов се сблъскал със следния проблем. Той изучава свойствата на белтъчните молекули в зависимост от срещането на известни или неизвестни до момента наредени комбинации от съставки. При тези изследвания му се сторило, че свойствата много силно зависят от срещанията на неизследвана до момента комбинация, между две известни комбинации. Съставките на белтъчните молекули са означени с буквите на латинската азбука. Всяка белтъчна молекула можем да разглеждаме като като низ от съставки с дължина N. Например, низът dabcccabc e описание на една възможна белтъчна молекула с дължина 9. В този смисъл, комбинациите от съставки също се представят с низове на латинската азбука.
Изследването на белтъчни молекули е трудна работа, като се има предвид, че съставките могат да са няколко десетки, а дължините на белтъчните молекули могат да достигнат няколко милиона. Помогнете на Низю Стрингьов в неговата сложна научно-изследователска работа. Напишете програма MOL.EXE, която по зададено описание на белтъчна молекула с дължина N и множеството от M известни комбинации от съставки, определя колкото може по-къс подниз от описанието на молекулата, който може да се разбие на три последователни части така, че лявата и дясната да са известни комбинации от съставки, а средната да е неизвестна.
Броят на буквите в азбуката няма да бъде по голям от 26, като за букви ще бъдат използвани малките латински букви. Дължината на молекулата N няма да бъде по-голяма от 5 000 000, а дължината на всяка известна комбинация ще бъде по-малка или равна на 10 000 и общата им дължина няма да надвишава 500 000.
В първия ред на входния файл MOL.INP са зададени числата M и N, разделени с един интервал. На втория ред, разделени една от друга с по един интервал са зададени известните комбинации от съставки, а на третия ред – описанието на молекулата.
В единствения ред на изходния файл MOL.OUT програмата трябва да изведе, разделени с по един интервал, четири цели числа L, F, S, T (1Ј F < S < T Ј N и T Ј L + F – 1 ) както следва: L e дължината на намерения низ от три комбинации от съставки, F e началната позиция на първата комбинация, S – на втората, а T – на третата.

Например, при входен файл

MOL.INP
3 9
da ab cabc
dabcccabc

два възможни изхода са

MOL.OUT
7 2 4 7

и

MOL.OUT
9 1 3 6

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


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

На мен пък ми се струва, че условията на нещата в реалното
програмиране е сто пъти по неясно от тези на състезанията,
там винаги има някои неща които не са много ясни, докато на
състезанията има 100% яснота...така че ми е много странно
това което си писал :)

хехе и на мен - много си е ясно условието.

виж мен тия задачи на PCmagazine не ме кефят, щото фащаш някой готов алгоритъм и си готов, а и са доста хамалски. Тия на Компютър ме кефят повече (Еврика).

Мда. Низьо Гъзов, пардон, Стрингов, да ми яде кобура. С други думи: последния да затвори вратата.
Очевидно е, че задачата може и по-просто да се зададе, но целта е кретенизЪма да завладее по-голяма част от участващите юнити. Лично аз не харесвам такива задачи, защото в тях от самолет се вижда, че Създателят им е човек с комплекси, чиято цел е да се погрижи минимално количество от напъващите се да разрешат задачата да не разбере за какво става дума.

Ми донякъде си прав....особенно, ако четеш условието от монитор, който работи на 50 херца :(( Пича, дето го е писал по-скоро се опитква да си предаде оригиналост и да се опита да и предаде нещо реално в нея, а не само суха математика.
Но този подход отдавна се е изтъркал и никой сериозен човек вече не му прави впечатление, освен някой първокурсник от ФМИ, дето е прекарал предните си години в дебрите на математиката и сега навлиза в програмирането.
Но като не ти се занимава с такива задачи, по-добре се занимавай с COM обектите. В тях има повече хляб.

тъпо парче си батка ...

има ли сайт на който се публикуват задачите от списание Computer ?

[линк]

Dobre pich, veroiatnostta da prihvanesh e mai dosta malka no vse shte
se opitam da ti obiasnia zashto uslovieto e dylgo. Takyv tip usloviq
se davat ne samo na tova systezanie, ami primerno i na ACM finalite,
ideiata e che kakto i v realniq jivot ne e lesna i zadachata na extract-vaneto
na cennata informaciq ot nenujnata. Osven tova imam edna molba kum teb,
sledvashtiq pyt se opitai da ne se izkazvash kato sto procenta selski
model.

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

доказано дебелоглав

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

но не се споменава нищо за времето за изпълнение ...
значи ще си пусна безкраен цикъл и после ще твърдя, че мойта програма е най добра понеже след 10^8 години ще върне най-верния отговор...

доказано дебелоглав

еи тая петата задача плаче за Prolog
дори съм я правил ама не си спомням къде съм затрил решението

доказано дебелоглав

ми обикновено се дава предварително конкретен лимит за времето, за да може човек да си прецени колко сложен алг. да направи.

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

Е доста крайно мнение...

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

Друг е въпроса и че АСМ е тийм-състезание - тоест за примерно 5 часа отбор от 3-ма човека има на разположение 7 задачи (и само един компютър!). По-важната част от състезанието е не точно кой алгоритъм ще приложиш и как ще го напишеш, а как ще координираш тийма и ще успееш да разграничиш лесно решимите задачи от по-трудните (обикновено има 1-2 почти нерешими и е добре да се оставят за последно). Някои от текстовете на задачи са по 2 страници но са лесни, други от по 2-3 реда са почти нерешими.

Та в това, че пичовете се опитват да правят задачите в стил АСМ, според мене не е никак зле.