SRM 504.5 - Div. 1 - Problem 2 - Оценка сложности Решил написать отдельным постом, потому что соответствующая ветка переполнена и вряд ли кто-то в ней заметит.<div><br></div><div>Сразу хочется сказать - пост нацелен на то, чтобы показать людям, которые ругаются, что контест - маздай, автор контеста - бяка, и как вообще можно давать задачи с непонятной оценкой сложности (типа второй), что они не правы, и после непродолжительных размышлений оказывается, что сложность алгоритма - O(n^2*log(максимальное число)), пусть и с бОльшей константой, нежели при простом бинарном поиске. Этим как раз и хороша задача - она проверяет, действительно ли кодер умеет оценивать сложность, или только знает набор стандартных шаблонов.</div><div><br></div><div>Пусть C - это разрыв между максимальным и минимальным числами в нашем наборе, числа могут быть любыми. После не более чем n-1 шагов работы жадного алгоритма (взять минимальное число и проделать, что написано в задаче) мы получаем новое значение разрыва C^ &lt; C*(1-1/n). Почему так? Очевидно, что минима...

Full text and comments »

Complexity of an algorithm <p>Hi Everyone.<br><br>I know i shouldn't have written a blog post for this . But since there is no other way . I am doing it here . <br><br>I am (like most/or at least some other people here) new to this fantastic world of problem/puzzle solving programming . And i face a very serious problem here.<br><br>Most of the time when i start solving a problem. I start coding .. submit it .. and then find out that my solution exceeds the time limit. <br><br>For example :<br><br>I was participating in the topcoder SRM 504.5 in div 2(obviously). And i was trying to solve the jackpot problem.<br><br>the problem statement is at :<br><br><a href="http://www.topcoder.com/stat?c=problem_statement&amp;pm=11432">http://www.topcoder.com/stat?c=problem_statement&amp;pm=11432</a><br><br>Now during the course of 75 mins i was unable to solve even this basic(now i know) problem, spending all the time to find an effective and fast way to solve it. I was shocked to look at the possible solution . It was stra...

Full text and comments »

об оценке результатов соревнования по программированию <!--[if gte mso 9]><xml> <w:WordDocument> <w:View>Normal</w:View> <w:Zoom>0</w:Zoom> <w:PunctuationKerning/> <w:ValidateAgainstSchemas/> <w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid> <w:IgnoreMixedContent>false</w:IgnoreMixedContent> <w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText> <w:Compatibility> <w:BreakWrappedTables/> <w:SnapToGridInCell/> <w:WrapTextWithPunct/> <w:UseAsianBreakRules/> <w:DontGrowAutofit/> </w:Compatibility> <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel> </w:WordDocument> </xml><![endif]--><!--[if gte mso 9]><xml> <w:LatentStyles DefLockedState="false" LatentStyleCount="156"> </w:LatentStyles> </xml><![endif]--><!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Обычная таблица"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-par...

Full text and comments »