Codeforces Beta Round #35 (Div. 2) and Codeforces Beta Round #36 <p> Greetings to everybody. </p> <p> Today is an unusual day on Codeforces: two contests a day with quite small gap between them. The reason is that today the IX Regional team school programming contest is held in Saratov, and it was decided to use the tasks from it for Codeforces rounds. </p> <p> That's why there are many authors of today's tasks. I would like to thank the whole jury of the school contest for their excellent job. The following people are on the jury: <font color="#0000ff"><u><a href="http://codeforces.me/profile/RAD"><span lang="en-US">Artem Rakhov</span></a></u></font><span lang="en-US">, </span><font color="#0000ff"><u><a href="http://codeforces.me/profile/NALP"><span lang="en-US">Nickolay Kuznetsov</span></a></u></font><span lang="en-US">, </span><font color="#0000ff"><u><a href="http://codeforces.me/profile/natalia"><span lang="en-US">Natalia Bondarenko</span></a></u></font><span lang="en-US">, </span><font color="#0000ff"><u><a href="http://codef...

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 #36 <h3>General</h3><br>It was normal codeforces contest except the IO: input.txt/output.txt. I didn't know the IO change before contest began and I got upset. I used an unaccustomed fstream library in the contest, but I should use freopen as below code. (if C++)<br><br>&nbsp;&nbsp;&nbsp; freopen("input.txt", "r", stdin);<br>&nbsp;&nbsp;&nbsp; freopen("output.txt", "w", stdout);<br><br><br><h3>A Extra-terrestrial Intelligence </h3>Simple problem, calculate the interval length between first two '1's, then check if all interval lenghs are equal.<br>I failed to read the statement <i>"It’s guaranteed that the given record sequence contains at least three 1s"</i> at the beginning, then I stopped for a little.<br><br><br><h3>B Fractal </h3>This is also a simple problem, simple iteration is good because the input size is very small.<br>But I stuck at compilation error of vector&lt;string&gt; substitution, then I lost about 10 mins. This upset me. My C++ compiler MinGW outputs compilation error at...

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 »

Solutions to Codeforces Beta Round #41, A, B, C, D(Hamilton Cycle) A. Guilty — to the kitchen! Suppose that the maximum volume is x, and then we can derive several inequalities that x should satisfy. 1) For each index i, x*a[i]/(a[1]+a[2]+a[3]+...a[N])<=b[i], where "/" means float division; 2) x<=V Therefore, x=min(V, min(b[i]*(a[1]+a[2]+a[3]+...a[N])/a[i]) )=min(V, (a[1]+a[2]+a[3]+...a[N])*min(b[i]/a[i])). This implies that we can first find out the minimum value of b[i]/a[i], and then the answer is straightforward. B. Game of chess unfinished For each rook, we can calculate the positions that it can take. Note that the white king (or another rook) might serve as an obstacle and thus "protect" some positions from being taken by the current rook, even though these positions lie in the same row or column as the rook. For instance, consider a rook with "b2" and a white king with "b4", in which case all positions with "b5,b6,b7,b8" cannot be taken by this rook (however they may be taken by another rook or the white king). Similarly, we...

Full text and comments »

Codeforces Beta Round #36 (Problem D solution) <span class="Apple-style-span" style="border-collapse: collapse; font-family: arial, sans-serif; font-size: 13px; ">In the problem we have a game on an acyclic graph. Positions in the game (vertices&nbsp;of the graph) are pairs (n, m), where n and m are distances from the current position of the piece to the bottom and to the rights borders of the board. For every position (n, m) there are at most three moves: (n - 1, m), (n, m - 1), (n - k, m - k).&nbsp; The graph is acyclic, because at each move the sum n+m strictly decreases.</span><div style="border-collapse: collapse; font-family: arial, sans-serif; font-size: 13px; "><br>If the numbers n, m and k do not exeed, say, 1000, the problem is solved by easy dynamics on the acyclic graph, standard for such games. Let d(n, m) = 1, if the position (n, m) is winning, and d(n, m) = 0, if the position (n, m) is losing. The value of d(n, m) is calculated using the following considerations. If there exists a move from the current position to a ...

Full text and comments »

Codeforces Beta Round #17 <div class="from-renderer"><div style="margin: 0px; padding: 0px; font-family: verdana,arial,sans-serif; font-size: 12px; line-height: 20px;">Приветствую всех на <a href="../../../contests">Codeforces Beta Round #17</a>, который состоится&nbsp;<span class="Apple-style-span" style="font-family: arial,sans-serif; line-height: normal; font-size: 13px; border-collapse: collapse;"><a href="http://timeanddate.com/worldclock/fixedtime.html?year=2010&amp;month=06&amp;day=10&amp;hour=15&amp;min=00&amp;sec=0&amp;p1=0">10-го июня (четверг) 2010, 19:00 (UTC +4, Московское время)</a></span>. Этот контест буду представлять я.&nbsp;</div><div style="margin: 0px; padding: 0px; font-family: verdana,arial,sans-serif; font-size: 12px; line-height: 20px;">Хочется сказать отдельное спасибо&nbsp;<a href="../../../profile/MikeMirzayanov">Михаилу Мирзаянову</a>, который сделал проведение контеста возможным, <a href="../../../profile/RAD">Артёма Рахова</a>&nbsp;за помощь в тестировании авторских решений и&nbsp...

Full text and comments »

Complex FFT is not as bad as you think ... Probably. Hi everyone! As some of you _might_ already know, I don't like NTT. Primary reasons for this are: - I don't like modular arithmetic optimizations (Montgomery, etc). - I don't like NTT mods, and prefer good, old $10^9+7$. - I do like algebra of complex numbers. But, to my regret, the overwhelming mainstream in modern competitive programming is NTT. Primary reasons are: - It's allegedly faster. - It needs less memory. - It has no precision issues. - People don't like algebra of complex numbers. There is nothing I can do about the last, but today I'll address the first 3. Optimizing complex FFT was on my mind for quite some time, but I didn't really work on it _that much_ until the [blog](https://codeforces.me/blog/entry/142063) by [user:Qwerty1232,2025-04-24] on optimizing NTT has dropped, which motivated me to actually put some serious effort into this. In this blog, we will primarily focus on optimizations that are specific to complex arithmetic...

Full text and comments »

Codeforces Beta Round #36 (Problem B solution) In author's solution the fractal is built by a recursive function. Let ''a'' be a square $n^k \times n^k$&nbsp; result matrix. Write the recursive function&nbsp; fractal(x, y, k) filling a square part of the matrix with an upper left corner in (x, y) and a length of the side $n^k$, drawing the fractal of depth $k$. In case k = 0 put ''.'' at the current position. Otherwise you have to divide the part of the matrix into $n^2$ square parts with size&nbsp; $n^{k-1} \times n^{k-1}$, and fill them according to the model. If the corresponding symbol in the model is ''*'', fill the square with symbols ''*'',&nbsp; otherwise execute fractal(x1, y1, k-1) for (x1, y1) being the coordinates of the upper left corner of the new square.<br><br><div><span class="Apple-style-span" style="border-collapse: collapse; font-family: verdana,arial,sans-serif; font-size: 12px;"><a href="http://codeforces.me/profile/kdalex" title="Лейтенант kdalex" class="rated-user user-blue" style="font-family: arial; text-d...

Full text and comments »

Solutions to Codeforces Beta Round #36, A, B(Kronecker Product), D A. Extra-terrestrial Intelligence As the size n is no larger than 100, we can adopt a "vector<int>" to record the indices of "1" which appear in the given sequence. Then, we calculate the difference between every two neighbouring indices, and if they are the same, the answer is "YES"; otherwise is "NO". B. Fractal This problem reminds me of Kronecker Product, which is often mentioned in the theory of matrix. In fact, this problem just asks to simulate the operation of Kronecker Product as far as I consider. For the first provided example, if we replace '.' with integer "1" while '*' with integer "0", we will obtain a matrix [1 0 ; 1 1]. If you are familiar with Matlab, you can use the function "kron" to calculate the finla matrix, and by mapping "1" and "0" back to '.' and '*', you will find that it is just the answer!! This conclusion holds for all values of n and k. D. New Game with a Chess Piece This is a rather complicated problem... We might need do some pen and...

Full text and comments »

Solutions to Codeforces Beta Round #24, A, B, C, E A. Ring road This problem gives us a ring with n nodes and n directed edges, while aksing to reverse several edges to build a strongly connected ring (graph) at the minimum cost. We use Sr to denote the minimum cost. Without loss of generality, we can start with node 1, and implement a DFS. During this process, we may meet such a situation that no further nodes can be visited, if the currently being visited edge is not directed to the next node. Whenever this occurs, we just reverse the edge so that we can move on to the next node, while adding the cost of this edge to Sr. The above DFS in fact only provides one feasible way to build a strongly connected graph with a total cost of Sr. If we keep the edges reversed above as what their original directions are, but reverse the other edges instead, we will obtain another strongly connected graph (recall that this is a ring) with a total cost of St-Sr, where St denotes the sum of the cost of all the directed edges. Therefore, the fin...

Full text and comments »

Notes on Codeforces Beta Round #67, A, B, C, D [problem:75A] This is a "straightforward-implementation" problem. Eliminate all the zeros in each integer and check whether the sum equation still holds or not. [problem:75B] The main issue involved in this problem is how to correctly sort out the names and actions. After this, we only need to record the scores that every user can obtain, and output them in the required order. [problem:75C] At first, we should compute the GCD of the given two integers. As their common divisors must also be the divisors of GCD, the next step is to calculate all the divisors of GCD, and store them in the array S. Then, we sort S in a decreasing order, and for each query, we can directly enumerate S from the last element to the first one while stopping if we find the first element that falls into the interval. It seems that the above algorithm might lead to a risk of TLE. However, it turns out that the number of divisors of GCD cannot be very large, even if the maximum integer is up to ...

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 »

Notes on Codeforces Beta Round #54, A, B, C, D(Bucket Sort) A. Chat room Suppose that the given string is denoted as S while "hello" is denoted as T. We can solve the problem by adopting two pointers pS and pT, which point to string S and T, respectively. At first, both pS and pT are set to 0. Then, we increase pS by 1 until it reaches the end of string S. During this process, once it occurs that S[pS]=T[pT], we immediately increase pT by 1 as well. Note that when pT reaches the end of string T, we can break the loop. After all the characters in string S have been visited, and the loop is over (or we break the loop), we can check whether pT has arrived at the end of string T or not. If the answer is YES, it means that we can obtain "hello" from the original given string; otherwise we should output NO. B. Coins For any integer N, we can find all its prime divisors and write it in the form of N=p1^a1*p2^a2*...pn^an, where pi is a prime divisor while ai denotes the number of pi that N has. Intuitively, we may come up with such a sequence ...

Full text and comments »

Codeforces Beta Round #36 (Problem E solution) The problem is to divide edges of a graph into two groups forming two paths in the graph. Clearly, each path is contained in one connected component. So if the given graph has more than two connected components, the problem has no solution. The same we can say if the graph has more than four vertices of an odd degree. Indeed, each vertex in a path (even if the path contains some vertices more than once) have an even degree, exept the first vertex and the last vertex. So the union of two paths can contain no more than four odd vertices.<div><br></div><div>Now consider the cases:</div><div><br></div><div>1. One connected component, no vertices of an odd degree. So we have an euler cycle, which can be divided into two paths.</div><div><br></div><div>2. One connected component, two odd vertices. The same with an euler path instead of euler cycle. There is a tricky case of a graph with only one edge, which cannot be divided into two nonempty paths.</div><div><br></div><div>3. One connected ...

Full text and comments »

Codeforces Beta Round #36 (Problem C Tutorial) Imagine that we have successfully processed first $i-1$ bowls, i.e. we know height of the bottom $y_j$ for every bowl $j$ ($1 \le j &lt; i$). Now we are going to place $i$-th bowl. For each $j$-th already placed bowl, we will calculate the relative height of the bottom of $i$-th bowl above the bottom of $j$-th bowl, assuming that there are no other bowls. Lets denote this value by $\Delta_{i,j}$. It is obvious that height of the new bowl is equal to the maximal of the following values: $y_i=max(y_j+\Delta_{i,j})$.<br><br>Now I will describe how to calculate $\Delta_{i,j}$. Firstly, consider two trivial cases:<br><br>I. $r_i \ge R_j$: bottom of $i$-th bowl rests on the top of $j$-th. Then $\Delta_{i,j}=h_j$.<br>II. $R_i \le r_j$: bottom of $i$-th bowl reaches the bottom of $j$-th. Then $\Delta_{i,j}=0$.<br><br>Then there are three slightly more complicated cases. <br><br>1. $r_i &gt; r_j$: bottom of $i$-th bowl gets stuck somewhere between the top and the bottom of $j$-th,<br>touching i...

Full text and comments »

About the programming languages **This post is no longer relevant; it has become significantly outdated. You should read the post at [https://codeforces.me/blog/entry/121114](https://codeforces.me/blog/entry/121114)**. <p> Later you'll be introduced to the rules of the Codeforces contests, which differ from those of <a href="http://en.wikipedia.org/wiki/ACM-ICPC#Contest_rules">ACM-ICPC</a>, TopCoder, GCJ, and I hope they'll bring some difference to the world of programming competitions. Most of the official competitions will be carried out according to these rules, though there will be more traditional contests. For example, Codeforces Beta Round #1 will be carried out according to the familiar <a href="http://en.wikipedia.org/wiki/ACM-ICPC#Contest_rules">ACM-ICPC</a> rules. For some time testing will be based on Windows, but things might change in future, fortunately, the system supports testing on different platforms, even within one contest. </p> <p> At the present time the ...

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 »

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 #36 (Problem A Tutorial) <h1>A. Extra-terrestrial Intelligence</h1>This task is very easy, and I hope all of you have solved it. But let's talk about it.<br><br>Let input sequence is named as $a$, and its length is $n$. Then let's save sequence $x_1, ... , x_k$ is increasing order - all of positions, where $a_{x_i} = '1'$.<br><br>We must check if this sequence $x_1, ... , x_k$ is a arithmetic progression. We save variable $d = x_2 - x_1$ and check:<br>for all $1 \le i &lt; k$, is "$d = x_{i+1} - x_i$" correct.<br><br>If it's correct, output "YES", else "NO".

Full text and comments »

Два контеста codeforces в один день?? <p>Codeforces Beta Round #35 (Div. 2) 19.10.2010 11:00<br></p><p>Codeforces Beta Round #36              19.10.2010 14:00<br></p><p>Два разных контеста в течении 5 часов? (будет интересно)</p>

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 »