Codeforces Beta Round 94 <p>Привет всем!<br /><br />Рад приветствовать вас на очередном, 94, раунде Codeforces. Надеюсь, что несколько более раннее время проведения раунда не скажется отрицательно на ваших успехах =)<br /><br />Автором задач сегодняшнего раунда являюсь я, выпускник СПбГУ, Валерий Самойлов. Это мой второй раунд на Codeforces. Надеюсь, что сегодня никто не пожалеет о своём участии. Большое спасибо RAD, который оказал неоценимую помощь при подготовке задач. Также спасибо Марии Беловой, переведшей условия на английский язык.</p><p>В этом раунде будет необычная разбалловка:</p><p>Див-1:&nbsp;1000 - 1500 - 1500 - 2000 - 2500</p><p>Див-2:&nbsp;500 - 1000 - 2000 - 2500 - 2500</p><p>Прошу не пугаться, все не так уж страшно =)</p><p><br /></p><p>Раунд завершен, всем спасибо за участие!</p><p>Разбор ожидается завтра.</p><h1>Победители:</h1><h2>Дивизион 1:</h2><p>1.&nbsp;<a class="rated-user user-red" href="http://codeforces.me/profile/Egor" style="font-family: arial;text-decoration: none;font-weight: bol...

Full text and comments »

Codeforces Beta Round #94 Editorial <h3><a href="http://codeforces.me/problemset/problem/129/A">DivII A. Печеньки</a></h3><p>Самый лёгкий способ решить задачу &mdash; сперва посчитать всю сумму чисел, и затем посчитать количество чётных разностей между этой суммой и каждым числом. Однако маленькое наблюдение позволит написать решение немного эффективней: помимо суммы ($sum$) посчитаем также, сколько среди данных чисел есть чётных ($even$) и нечётных ($odd$). Тогда, если сумма нечётна, то ответ &mdash; $odd$, иначе &mdash; $even$. Время $O(n)$, память $O(1)$.<br /></p><h3><a href="http://codeforces.me/problemset/problem/129/B">DivII B. Шнурки и шестиклассники</a></h3><p>Маленькие ограничения позволяют нам написать решение &laquo;в лоб&raquo;. Будем хранить данный граф в матрице смежности, и симулировать происходящее. Также будем хранить степень каждой вершины отдельно, чтобы быстро находить детей, которые связаны только одним шнурком. Тогда при каждой итерации удаляем все вершины со степенью 1 и все грани, которые соединя...

Full text and comments »

Problem D of Beta Round 94 <div>Today's contest had some pretty interesting problems; I particularly liked <a href="http://codeforces.me/contest/128/problem/C">Problem C</a> and <a href="http://codeforces.me/contest/128/problem/D">Problem D</a>. I'm going to describe my solution to D which I think is quite nice (and results in simple code). I don't doubt that there are even easier solutions to the problem, so please enlighten me if you have one :).</div><br /><div><h3>Impossibility</h3><div>Let us denote the sequence by $a_1, \ldots, a_n$ and assume it has been sorted already. We can note immediately that there are some easy cases we can rule out. If $n$ is odd, by a parity argument it is impossible. Moreover, let $m = a_n - a_1$, i.e. the range of the values. If $m = 0$ it is impossible since $n \ge 3$, and if $m &gt; n/2$ it is impossible since we cannot get from $a_1$ to $a_n$ and back going around the circle. Now that these cases are out of the way we move on to the actual algorithm.</div><div><br /></div>...

Full text and comments »

Useless CP Information #8: Are LGMs Overrated? Alright, clickbait title aside, how do tourist and jiangly get to 4000 rating? In chess, real life ratings cap out at around 2900, and even on online sites like Lichess, [the highest bullet players are 3300-3400, and just around 3000 for the other modes](https://lichess.org/player). Also, anecdotally, if rating is correct, the model predicts that someone who is 2940 should beat me 99.1% of the time. I have a gut feeling I beat more than 0.9% of GMs and LGMs in round 1105 and round 1108. <spoiler summary="Review on rating models if you forgot"> Rating represents win probability. In a match, for every 400 points player A is rated higher than player B, player A is 10 times more likely to win (exponentially). - If player A is rated 400 points higher than player B, then out of 11 games, player A should win 10 and player B should win 1. - If player A is rated 800 points higher than player B, then out of 101 games, player A should win 100 and player B should win 1. This can be ...

Full text and comments »

Codeforces Beta Round #57 (Div. 2) <p class="MsoNormal" style="margin-bottom: 12pt; line-height: 12.5pt;"> Здравствуйте!<br> <br> Я рад пригласить вас принять участие в Codeforces Beta Round #57 (Div. 2).<br> Сегодняшнее соревнование подготовили <a href="http://www.codeforces.com/profile/aryobarzan">Amir Goharshady</a>&nbsp;и <a href="http://www.codeforces.com/profile/LGM">я</a>.<br> <br> Мы благодарим <a href="http://www.codeforces.com/profile/MikeMirzayanov">Михаила Мирзаянова</a>,&nbsp;<a href="http://www.codeforces.com/profile/RAD">Артема Рахова</a>,&nbsp;<a href="http://www.codeforces.com/profile/mjn">Mohammad Javad Naderi</a>,&nbsp;<a href="http://www.codeforces.com/profile/mr.ilchi">Saeed Ilchi</a>&nbsp;и Марию Белову.<br> <br> Сегодняшний контест посвящен&nbsp;<a href="http://ru.wikipedia.org/wiki/%D0%90%D1%82-%D0%A2%D1%83%D1%81%D0%B8,_%D0%9D%D0%B0%D1%81%D0%B8%D1%80_%D0%B0%D0%B4-%D0%94%D0%B8%D0%BD">Khaje Nasir Tusi</a>,&nbsp;сегодня в Иране день техники.</p><p class="MsoNormal" style="marg...

Full text and comments »

ALL CodeForces Rounds Tutorial <html> <body> <br /><br /> >>>>>>>**Hi I just Say Really Sorry For Delay in UPD This Blog...!**<br /><br /><br /> <u>This is not Complete</u> , but i try to find <b>all Tutorial codeforces round</b> and posted here , thanks in advance :D <br /><br />This post will <b> <span class="Apple-style-span" style="border-collapse: collapse;color: rgb(255,0,0);font-family: verdana , arial , sans-serif;font-size: 12.0px;"> UPD</span></span></b> after each contest . <span>If anyone have or writes any editorial that's</span> <b> <span> <span class="Apple-style-span" style="border-collapse: collapse;color: rgb(255,0,0);font-family: verdana , arial , sans-serif;font-size: 12.0px;"> not in here</span></span></b> , Plz post here for ALL . <br /><br /><b>UPD </b> &nbsp;: Table1 updated : in Future!!! <br /><br /><b>UPD </b>&nbsp;: Table2 updated : CF # 118 ...to... CF # 169 added .<br /><br /> </p><hr /><br /></p> <div align="justify"> <br /><br /><b><s...

Full text and comments »

Notes on Codeforces Beta Round #94 Div-2, A, B, C, E (Pascal Triangle) [problem:129A] We can compute the sum of all the integers. Then, we enumerate each element and test whether their difference is even or not. [problem:129B] A straightforward implementation problem. We can use BFS to find out all the nodes whose degree is exactly one. The answer is just the total number of BFS. [problem:129C] Note that at the eighth second, all the positions are definitely safe. Therefore, it is sufficient to check whether we can survive within the first eight seconds. One feasible solution is to record and update all the safe positions at each second. If we can survive after eight seconds, it means that we can always reach the right upper corner; otherwise not. [problem:129E] In fact we might obtain some more clear observation if we consider the length and width of each rectangular in an independent perspective. For instance, for the length, the rectangulars can only have positions at (1, 2, 3,... n-1). As there are exactly $k$ rectangulars, we ...

Full text and comments »

Codeforces Beta Round #94 Problem B Is there a better suffix array solution for this [problem](http://codeforces.me/contest/128/problem/B) ?<br> This is my [solution](http://codeforces.me/contest/128/submission/31181378), but I think is very inefficient <br> Is there a better solution with suffix array? <br> there is no editorial for this round <br> I hope someone can help me! <br> Thanks!

Full text and comments »

Поправочные коэффициенты и инфляция рейтинга <P>Результат последнего контеста оказался для меня довольно неожиданным, поэтому я решил собрать немного больше информации о возможностях изменения рейтинга CF. Если профиль участника позволяет наблюдать историю изменения&nbsp;его рейтинга, то у меня получились "профили контестов", в которых отражены рост или падение каждого участника конкретного соревнования.<BR>[cut]<BR><A href="http://codeforces.me/blog/entry/102">Формула расчёта&nbsp;рейтинга Codeforces</A> подразумевает сохранение суммы очков всех участников до и после раунда за счёт поправочных коэффициентов. На основании же обработанной мной информации получилась такая табличка:</P> <TABLE style="WIDTH: 100%" border=1> <TBODY> <COLGROUP> <COL width="20%"> <COL width="20%"> <COL width="20%"> <COL width="20%"> <COL width="20%"> <TBODY> <TR> <TD>ID контеста</TD> <TD>Суммарный рейтинг до соревнования</TD> <TD>Суммарный рейтинг после соревнования</TD> <TD>Разность конечного и исходного суммарных рейтингов</TD> <TD>Коли...

Full text and comments »