Codeforces Beta Round #96: editorial <h3><a href="http://mirror.codeforces.com/contest/133/problem/A">A. HQ9+</a></h3> <p>The problem described <a href="http://progopedia.com/language/hq9-plus/">HQ9+</a> programming language and asked whether the given program will print anything. Given the extraordinary simplicity of the language, it was enough to check whether the program contains at least one of the characters H, Q and 9.</p> [cut] <h3><a href="http://mirror.codeforces.com/contest/133/problem/B">B. Unary</a></h3> <p>A lovely language <a href="http://progopedia.com/language/brainfuck/">Brainfuck</a> has dialects for literally every occasion; I guess one could write a whole round about it (not Unknown Language Round, of course, it's too well-known for it), but this time I used it in one problem only.</p> <p>The solution is quite simple: all you have to do is to follow the described procedure of transforming code from Brainfuck to Unary. If your language has built-in long arithmetics, the solution is straightforward: replace characte...

Full text and comments »

Codeforces Beta Round #96 <p>В субботу 3 декабря состоится Codeforces Beta Round #96, мой первый классический раунд на Codeforces. Чтобы несколько сгладить переход от неизвестного языка к известным, я сделала раунд тематическим, и тема эта, разумеется, языки программирования :-)</p> <p>Спасибо [[user:MikeMirzayanov,2011-12-02]], [[user:maksay,2011-12-02]] и [[user:RAD,2011-12-02]] за помощь в подготовке задач.</p> <p>Удачи на раунде!</p> <p>P.S. Баллы за задачи: первый дивизион &mdash; 500-1500-1500-2000-2500, второй дивизион &mdash; 500-1000-1500-2500-2500.</p> <p>P.P.S. Разбор задач <a href="http://mirror.codeforces.com/blog/entry/3302">здесь</a>.</p>

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 »

string.h functions tutorial Here are the some of the  lesser know string.h functions<div><br /></div><div><div><br />strtok</div><div><a href="http://www.cplusplus.com/reference/clibrary/cstring/strtok/">http://www.cplusplus.com/reference/clibrary/cstring/strtok/</a><br /></div><div>This is the most useful functions. It is used to split a string based on some pattern string.</div><div><pre style="margin-top: 0.0px;margin-bottom: 0.0px;padding-top: 0.0px;padding-right: 0.0px;padding-bottom: 0.0px;padding-left: 0.0px;color: rgb(0,128,0);font-size: 12.0px;background-color: rgb(255,255,255);">char * strtok ( char * str, const char * delimiters );</pre><pre style="margin-top: 0.0px;margin-bottom: 0.0px;padding-top: 0.0px;padding-right: 0.0px;padding-bottom: 0.0px;padding-left: 0.0px;color: rgb(0,128,0);font-size: 12.0px;background-color: rgb(255,255,255);"><br /></pre></div><div>char *word;</div><div><br /></div><div>char s[] = &quot;The book, Game of thrones is very good. Read it.&quot;;</div><div>char delim[] = &quo...

Full text and comments »

Notes on Codeforces Beta Round #96, Div2-A, B, C, D, E, Div1-D [problem:133A] If the given string contains the required characters except for '+', the answer is yes. [problem:133B] We can construct the binary sequence according to the requirement, and then calculate its value in decimal form. [problem:133C] Inverse the binary form and then compute the value... [problem:133D] This is in fact a straightforward implementation problem, but we should complete some pre-processing in order to avoid TLE. The main issue that might lead to TLE is that we have to move to one of the four corners within one group. One group may consist of many squares with the same color, and according to DP and CP pointers, after we enter such a group, we must first determine the corner and then move to the next square (or group). This sub-problem can be solved based on DP algorithm. For instance, we use $dp[0][i][j]$ to denote that if we are in the $i$-th row and $j$-column and facing to the right, then we should move to position $dp[0][i][j]$, which...

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 »

Topics Problems Good Day to you! While a lot of us, when he begins to start competitive programming he found difficult to found problems on some topics in the beginning to practice of it, and same thing for a lot of ICPC Communites that they have started. These are some topic not advanced and videos, problems and articles on them. <br> <spoiler summary="Prefix Sum & Frequency Array"> [Wonderful Coloring](https://mirror.codeforces.com/contest/1551/problem/B1) [Do Not Be Distracted](https://mirror.codeforces.com/contest/1520/problem/A) [Letter](https://mirror.codeforces.com/problemset/problem/43/B) [Pangram](https://mirror.codeforces.com/problemset/problem/520/A) [Andryusha and Socks](https://mirror.codeforces.com/contest/782/problem/A) [Count Numbers](https://mirror.codeforces.com/group/c3FDl9EUi9/contest/262795/problem/A) [Count Characters](https://mirror.codeforces.com/group/c3FDl9EUi9/contest/262795/problem/B) [Range Sum Query](https://mirror.codeforces.com/group/c3FDl9EUi9/contest/262795/problem/E) [Count a's](https...

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 »

Поправочные коэффициенты и инфляция рейтинга <P>Результат последнего контеста оказался для меня довольно неожиданным, поэтому я решил собрать немного больше информации о возможностях изменения рейтинга CF. Если профиль участника позволяет наблюдать историю изменения&nbsp;его рейтинга, то у меня получились "профили контестов", в которых отражены рост или падение каждого участника конкретного соревнования.<BR>[cut]<BR><A href="http://mirror.codeforces.com/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 »