Codeforces Beta Round #33 (personal participation commentaries) I would like to write participation commentaries of Beta Round #33. I'm sorry my English may be poor.<br><br><h3>A What is for dinner?</h3>The problem is quite easy, but the problem statement is a little hard so I got as many as 2WAs. This made me upset a little.<br><br><br><h3>B String Problem</h3>This problem is also easy if we know warshll-floyd algorithm. But I confused the specification. I translated the statement "<i>According to the game rules, with each move Valera can change one arbitrary character A_i in one of the strings into arbitrary character B_i...</i>" as "<b>each string can be moved at most one time</b>" by mistake, and I spend much time in wrong and heavy coding, then I got 1WA.<br><br><br><h3>C Wonderful Randomized Sum</h3>Simple DP Problem. Let dp[n]:=(maximum sum using only "prefix multiplication" operation if an input sequence is a[1],a[2],...,a[n]). Each dp[n] can be calculated by as follow.<br><br><blockquote>&nbsp;&nbsp;&nbsp; dp[0]=0;<br>&...

Full text and comments »

Codeforces Beta Round #73 <p>Приветствуем всех на первом летнем раунде - Codeforces Beta Round #73</p><div>Авторами этого соревнования являемся мы: <a href="http://codeforces.me/profile/kuniavski" title="Полковник kuniavski" class="rated-user user-red" style="font-family: arial; text-decoration: none !important; font-weight: bold; color: rgb(0, 0, 204); ">kuniavski</a>&nbsp;(Павел Кунявский) и <a href="http://codeforces.me/profile/Zlobober" title="Майор Zlobober" class="rated-user user-orange" style="font-family: arial; text-decoration: none !important; font-weight: bold; color: rgb(0, 0, 204); ">Zlobober</a>&nbsp;(Макс Ахмедов). Соревнование проходит одновременно в двух дивизионах. Суммарно вам будет предложено 7 различных задач с вариациями в разных дивизионах, по 5 в каждом дивизионе. Мы надеемся что все смогут показать свой результат и решить как можно больше задач. <div><br>Мы хотим поблагодарить <a href="http://codeforces.me/profile/RAD" title="Штаб, RAD" class="rated-user user-admin" style="font-family: ...

Full text and comments »

Train Better with ThemeCPs (+ Website)! Hello Codeforces! I am excited to share with you my competitive programming innovation which successfully propelled me to master (2100+)! This is the **<span style="color:black;">Theme</span><span style="color:red;">CP</span>** training method, which stands for **Themed <span style="color:red;">C</span>odeforces <span style="color:red;">P</span>rogressions**. Use at your discretion -- your Codeforces practice may get too effective and addictive!  **Want to read this blog in document form (with images)? Check out the following Google Doc!** https://tinyurl.com/themecp #### What is **<span style="color:black;">Theme</span><span style="color:red;">CP</span>**? **<span style="color:black;">Theme</span><span style="color:red;">CP</span>** is an experimental training system wherein users train on a perpetual ladder for ratings in **[<span style="color:gray;">900</span>, <span style="color:black;">3</span><...

Full text and comments »

Codeforces Beta Round #33. Разбор D <div><h2 style="text-align: center;">Разбор задачи&nbsp;"D. Рыцари".<br></h2><h1 style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 1.8em; font-weight: bold; font-family: verdana, arial, sans-serif; line-height: 20px; "><span class="Apple-style-span" style="font-family: 'Times New Roman'; font-weight: normal; line-height: normal; font-size: medium; ">Обозначим количество заборов окружающих опорную точку номер i через cnt</span><span class="Apple-style-span" style="font-family: 'Times New Roman'; font-weight: normal; line-height: normal; font-size: medium; "><font class="Apple-style-span" size="3"><span class="Apple-style-span" style="font-size: 13px;">_i</span></font></span><span class="Apple-style-span" style="font-family: 'Times New Roman'; font-weight: normal; line-height: normal; font-size: medium; ">. Также обозначим через cnt</span><span class="Apple-st...

Full text and comments »

Codeforces Round #983 (Div. 2) ### Hello Codeforces! $\newline$ <spoiler summary="From AkiLotus"> > "<span style="color: red">K</span>aleidoscopic, this place still is. How long have I been away...?" Hi. Akik<span style="color: red">a</span>ze a.k.a. AkiLotus here. Four years have passed, lo<span style="color: red">n</span>g enou<span style="color: red">g</span>h huh? I h<span style="color: red">o</span>pe that after all these times, I am not too rusty to set good tas<span style="color: red">k</span>s for yo<span style="color: red">u</span> to enjoy, starting with <span style="color: red">t</span>his <span style="color: red">o</span>ne! <strong>See yo<span style="color: red">u</span> in the round!</strong> <span style="color: #ec3e9d"><i>"Waeeguyehy" is coming soon.</i></span> </spoiler> It's been a while, today [user:AkiLotus,2024-07-29] and I are delighted to invite you to participate in [contest:2032]. This round will be <strong>rated</strong> for all participants with a rating lower than <...

Full text and comments »

Codeforces Beta Round #33 (Codeforces format) <img src="http://assets.codeforces.com/photos/misc/saratov-su3-2010.JPG" style="float:left;margin:1em;width:150px;"><div><div>Good morning, day, evening, night to you.</div><div><br></div><div>Welcome to the wonderful randomized contest, which is prepared for you by team Saratov SU 3&nbsp;(<a href="http://www.codeforces.ru/profile/homo_sapiens">Davtyan Edvard</a>, <a href="http://www.codeforces.ru/profile/HolkinPV">Kholkin Pavel</a>, <a href="http://www.codeforces.ru/profile/KudryashovIA">Kudryashov Igor</a>).</div></div><div><br></div><div><div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-family: verdana, arial, sans-serif; font-size: 12px; line-height: 20px; ">Thanks to <a href="http://www.codeforces.ru/profile/Julia">Julia Satushina</a>, <a href="http://www.codeforces.ru/profile/RAD">Artem Rakhov</a> and <a href="http://www.codeforces.ru/profile/nerevar">Dmitry...

Full text and comments »

Hackers ranking (beta) ### FAQ **What is this?** Have you ever wondered who is the best hacker on Codeforces? Here is simple solution, which would try to answer for your problem! I would like to introduce new system of grading hackers in rounds. [cut] <p></p> <b>How does it work?</b> The whole rating system is based on <a href="http://en.wikipedia.org/wiki/Elo_rating">Elo rating</a>. The problem is how to measure user's performance in each round. **Yes, how?** The whole system is now in phase of testing, so some solutions may be changed (and probably will be changed :)). So let's consider some user during some round. Let's call him Bob. **I want to choose another name, may I?** No. **Ok.** So, let's say that Bob solved three problems: A, B and C (Bob is pretty sad), but also hacked one solution for B and had one unsuccessful hack attempt. Bob doesn't know that his solution for C won't pass system tests. How would we know if it was good or bad? At first, we will look at al...

Full text and comments »

Discussions Of CodeForces Round <h2 style="text-align: center;"><u>CodeForces Round</u></h2><div><u><br></u></div><div><a href="http://codeforces.me/blog/entry/84">CodeForces Beta Round 1</a><br></div><div><br></div><div><a href="http://codeforces.me/blog/entry/97">CodeForces Beta Round 2</a></div><div><br></div><div><a href="http://codeforces.me/blog/entry/141">CodeForces Beta Round 3</a></div><div><br></div><div><a href="http://codeforces.me/blog/entry/158">CodeForces Beta Round 4</a></div><div><br></div><div><a href="http://codeforces.me/blog/entry/196">CodeForces Beta Round 5</a></div><div><br></div><div><a href="http://codeforces.me/blog/entry/220">CodeForces Beta Round 6</a></div><div><br></div><div><a href="http://codeforces.me/blog/entry/239">CodeForces Beta Round 7</a></div><div><br></div><div><a href="http://codeforces.me/blog/entry/258">CodeForces Beta Round 8</a></div><div><br></div><div><a href="http://codeforces.me/blog/entry/276">CodeForces Beta Round 9</a></div><div><br></div><div><a href="ht...

Full text and comments »

Problem Set Analysis Of CodeForces <b>Tutorial Links:<span class="Apple-tab-span" style="white-space:pre"> </span>&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;</b><div><a href="http://codeforces.me/blog/entry/85">Code Forces Beta Round 1 Tutorial</a><br><br><a href="http://codeforces.me/blog/entry/109">Code Forces Beta Round 2 Tutorial</a><br><br><a href="http://codeforces.me/blog/entry/107">Code Forces Beta Round 2 Another Tutorial</a><br><br><div>Code Forces Beta Round 3 Tutorial:</div><div><br><a href="http://codeforces.me/blog/entry/178">Code Forces Beta Round 4 Tutorial</a><br><br></div><div><a href="http://codeforces.me/blog/entry/213">Code Forces Beta Round 5 Tutorial</a></div><div><br></div><div>Code Forces Beta Round 6 Tutorial</div><div><br></div><div>Code Forces Beta Round 7 Tutorial</div><div><br></div><div>Code Forces Beta Round 8 Tutorial</div><div><br></div><div><a href="http://codeforces.me/blog/entry/283">Code Forces Beta Round 9 Tutorial</a><br><br></div><div>Code Forces Beta Round 10 Tutorial</div...

Full text and comments »

Codeforces Beta Round #33. Разбор E <h2 align="center">Разбор задачи "E. Помощник"</h2><p><br></p><p align="justify">Для решения задачи, во-первых, необходимо было аккуратно считать входные данные и для удобства перевести все времена, заданные в формате $day, hour, minute$<em> </em>в минуты. Это можно было сделать, используя формулу $newTime = (day - 1) * 24 * 60 + hour * 60 + minute$. </p><p align="justify"><br></p><p align="justify">Во-вторых, необходимо подсчитать количество свободных для решения задач минут, имеющихся у Валеры на протяжении всей сессии. Кроме того, для каждой свободной минуты $j$ нужно определить $t_j$ --- номер этой минуты с начала сессии.</p><p align="justify"><br></p><p align="justify">Далее для каждого студента следует посчитать величину $deadline_i$ --- такую наибольшую свободную минуту с начала сессии, что если Валера закончит выполнять задание в эту минуту, то он получит вознаграждение от соответствующего студента. Очевидно, что если во время сдачи экзамена $i$-ым студентом, Валера не будет сп...

Full text and comments »

Solutions to Codeforces Beta Round #33, A, B, C, D A. What is for dinner? The problem in fact asks to find out the minimum number in each row. As the number of rows is not quite large, less than 1000, we can adopt an array to record the minimum integer in each row, i.e., whenever a new integer is added to some row, we compare it with the previously stored integer and update the entry with the smaller one. Finally, we add up the minimum integer in each row together, and obtain the possibly "maximum amount of crucians". By comparing it with k, we select the smaller one as the output. B. String Problem Well, I got stuck in this problem for a quite long time, until I realized that not only can we change letter A into B or B into A, but also we can change both A and B into some other letter C, which may achieve a smaller sum of money... This problem can be solved based on graph, where a letter is viewed as a node. The solution can be summarized as the following several steps: 1) Whenever a possible changing from letter A to B...

Full text and comments »

On the mathematics behind rolling hashes and anti-hash tests This blog assumes the reader is familiar with the basic concept of rolling hashes. There are some math-heavy parts, but one can get most of the ideas without understanding every detail. The main focus of this blog is on how to choose the rolling-hash parameters to avoid getting hacked and on how to hack codes with poorly chosen parameters. # Designing hard-to-hack rolling hashes ## Recap on rolling hashes and collisions Recall that a rolling hash has two parameters $(p, a)$ where $p$ is the modulo and $0 \leq a < p$ the base. (We'll see that $p$ should be a big prime and $a$ larger than the size $\left|\Sigma\right|$ of the alphabet.) The hash value of a string $S = s_0 \dots s_{n-1}$ is given by $$ h(S) := \left(\sum\limits_{i=0}^{n-1} a^{n-1-i} s_i\right) \mod p $$ For now, lets consider the simple problem of: given two strings $S, T$ of equal length, decide whether they're equal by comparing their hash values $h(S), h(T)$. Our algorithm declares $S$ and $T$ t...

Full text and comments »

Blog collection <p>________________________________________________________________________________________<br><br></p><h3><b>Puzzle</b></h3><ul><li><a href="http://codeforces.me/blog/entry/66">Red and Black hair</a>, </li><li><a href="http://codeforces.me/blog/entry/112">The 12 chairs and diamonds</a></li><li><a href="http://codeforces.me/blog/entry/228">Monty Hall Problem</a></li></ul><br><br><h3>Useful <br></h3><ul><li><a href="http://codeforces.me/blog/entry/70">Petr Mitrichev, 3 days in Sao Paulo Training Camp 2010</a></li><li><a href="http://codeforces.me/blog/entry/512">Useful links</a></li><li><a href="http://codeforces.me/blog/entry/529">Problem Set Analysis Of CodeForces</a></li><li><a href="http://codeforces.me/blog/entry/546">Discussions Of CodeForces Round</a></li><li><a href="http://codeforces.me/blog/entry/1492">ALL CodeForces rounds Tutorial</a></li><li><a href="http://codeforces.me/blog/entry/1534">Online Judge Locator</a></li><li><a href="http://codeforces.me/blog/entry/170...

Full text and comments »

October Schedule <img src="http://assets.codeforces.com/images/oct2010.png" style="float:left;width:150px;margin:1em 2em 1em 1em;"> Pay attention that on the "Contests" page the October schedule is available. Key dates are: <div><ul> <li>Oct. 7&nbsp;- Codeforces Beta Round #33</li> <li>Oct. 11&nbsp;- Codeforces Beta Round #34 (Div. 2)</li> <li>Oct. 19&nbsp;- Codeforces Beta Round #35 (Div. 2) and Codeforces Beta Round #36</li> <li>Oct. 25&nbsp;- Codeforces Beta Round #37</li> <li>Oct. 30&nbsp;-&nbsp;Codeforces Beta Round #38 (ACM-ICPC Rules)</li> </ul> <div>Now from the contests page you can go directly to the link to &nbsp;<a href="http://timeanddate.com/">timeanddate.com</a>&nbsp;to see the beginning of a contest in your time zone </div></div><div><br></div> <div>Look for updates&nbsp;- it can be changed and widen.</div><div><br></div> <div>Wish you high rating,</div><div>MikeMirzayanov and the Codeforces team</div>

Full text and comments »

Codeforces Beta Round #33. Разбор A <h2>Разбор задачи "A. Что у нас на ужин?"</h2><p align="justify"><br></p><p align="justify">Решение задачи достаточно тривиальное. Необходимо было завести массив , в котором для каждого ряда зубов хранилось бы значение остаточной жизнеспособности самого больного зуба в этом ряду (самым больным зубом в ряду назовем тот, у которого минимальная остаточная жизнеспособность). </p><p align="justify"><br></p><p align="justify">Таким образом мы определим для каждого ряда зубов максимальное число карасиков, которых Валерия сможет съесть, используя этот ряд (больше съесть Валерия не сможет, так как в этом случае жизнеспособность самого больного зуба станет отрицательной). </p><p align="justify"><br></p><p align="justify">Зная эти величины, нужно просто просуммировать их и в качестве ответа выдать минимум из суммы и общего числа карасиков, имеющихся в наличии у Валерии .</p>

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 »

Codeforces Beta Round #33. Разбор B <div>It was assumed a such solution. Firstly, if the lengths of strings were not equal, obviously the answer is -1. In the other case for all positions we search for all letters and try to make changes to the current letter. To make it quick, we will precalc a matrix Z[26][26], in which the сell (i, j) - is the minimum cost of change of i-th the letter of the alphabet to j-th. It can be done for example by&nbsp;Floyd algorithm. If at some position there is no possible letter, the answer is -1. In the other case, we should sum the answer for all positions and write the resulting string.</div>

Full text and comments »

Codeforces Beta Round #33. Разбор B Решение сложностью O(length(string) * Z), где Z = 26. Для решения данной задачи, необходимо было знать алгоритм Дэйсктры, а лучше всего Флойда, т. к. Z = 26, то предпроцессинг за O(Z^3) - не сильно усложнит время выполнения нашей программы. Итак, после чтения строк необходимо сравнить длины строк, и если они не равны, то можно смело выводить -1, т.к. существовать не может. Далее во время считывания символом на которые можно производить замены, ставим в соответствие дугу соответствующей длины, ясно что если при чтении используются только маленькие латинские буквы, то количество вершин в нашем графе будет &lt;= 26 (количество маленьких букв в латинице). После того как мы считали наши переходы следует запустить Флойда(алгоритм поиска кратчайшего пути из одной вершины в другую). После того как мы знаем минимальные стоимости наших замен, то смело пробегаем строкам и ищем на какой символов нам выгоднее всего заменить, его стоимость прибавляем к нашему ответу, при этом изменяя содержимое наши...

Full text and comments »

HELP IN Registration system problem In the registration system problem from Code forces beta round #4 it is given that the number of character in a string are not more than 32.but when i use a string of size exactly 32 character i get a wrong answer on 13 test case.and if i use s[33] my solution is accepted.can i know where I am going wrong This is my code- [Your text to link here...](https://codeforces.me/contest/4/submission/86627694)

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 »