$$ |\frac{z-z'}{z}|^2 \leq \max\limits_{\alpha,\beta}\left(1+
\sin\frac{\alpha}{2} \sin \frac, where $x_1 = \cos \alpha$, $y_1 = \sin \alpha$, $x_2 = \cos \beta$ and $y_2 =
\sin \beta$.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | maspy | 150 |
| 3 | Um_nik | 145 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | nik_exists | 133 |
| 7 | DNR | 133 |
| 9 | AmShZ | 130 |
| 10 | Dominater069 | 129 |
→ Find user
→ Recent actions
You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:
305— search for 305, most probably it will find blogs about the Round 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
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...
2.
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><...
**Automated Method (beta testing)**
3.
[Tutorial] Supporting Priority-Queue-like Undoing on DS _Good morning!_
In this blog, I will present an online algorithm that can perform priority-queue-like undoing on a data structure, given a few assumptions. I will also present and solve a generalization of that problem.
For context, I highly recommend reading this blog that shows how to solve the easier problem of queue-like undoing. That blog gave me the inspiration for the trick I will describe here, but I will still try to write this blog so that it can be understood without it. Thank you [user:Noam527,2023-01-08] for introducing such a great trick to the competitive programming community.
[[Tutorial] Supporting Queue-like Undoing on DS](https://codeforces.me/blog/entry/83467)
Acknowledgment
-----------------
Huge thanks go to [user:peltorator,2023-02-20] for hosting a [blog contest](https://codeforces.me/blog/entry/110840). His generous prize of $300 got many people to write blogs on new, interesting ideas, and it was one of the main reasons I wrote this blog. I'm...
$d$ $\alpha_{opt}$ $\beta$ , is larger, the worst case is either $\lambda=0$ or $\lambda=1$. Therefore, if
we set $$\beta=\frac{1, , we want $\beta$ to be as small as possible, or $\frac{1}{\beta
}=\min(1-d\alpha, f(\alpha, 0), f, ; all we have to show is that there is some value $\beta$ such that for any two
operations $i, The complexity analysis is very similar; all we have to show is that there is
some value $\beta, This means that $\beta=O(d)$ and so our final complexity becomes $O(dnT(n)\log
n)$.
4.
Theoretical grounds of lambda optimization Hi everyone!
This time I'd like to write about what's widely known as "Aliens trick" (as it got popularized after 2016 IOI problem called [Aliens](https://ioinformatics.org/files/ioi2016problem6.pdf)). There are already some articles about it here and there, and I'd like to summarize them, while also adding insights into the connection between this trick and generic Lagrange multipliers and Lagrangian duality which often occurs in e.g. linear programming problems.
Familiarity with a [previous blog](https://codeforces.me/blog/entry/98524) about ternary search or, at the very least, definitions and propositions from it is expected.
Great thanks to [user:mango_lassi,2022-01-01] and [user:300iq,2022-01-01] for useful discussions and some key insights on this.
Note that although explanation here might be quite verbose and hard to comprehend at first, the algorithm itself is stunningly simple.
Another point that I'd like to highlight for those already familiar with "Aliens tr...
pick this element and pick top $\beta$ elements in the sorted list. Since we
sorted the elements by, $$\begin{align} h(\alpha) &= h(\alpha, 0),\\ h_{\lambda_1}(\beta) &=
\max\limits_\alpha[h(\alpha, $$h_{\lambda_1}(\beta) = \max\limits_{|B|=\beta} [f(A, B)-\lambda_1|A|] +
\lambda_1 a,$$, $$t(\lambda_1, \lambda_2) = \max\limits_{\alpha,\beta}[h(\alpha,\beta
)-\lambda_1 (\alpha-a, Let $h(\alpha,\beta) = \max f(A, B)$ subject to $|A| = \alpha$ and $|B| = \beta
$, then
5.
Dirichlet convolution. Part 1: Fast prefix sum computations Hi everyone!
Suppose that you need to compute some sum of a number-theoretic function that has something to do with divisors:
$$\begin{gather}
\sum\limits_{k=1}^n \varphi(k) = ? \\
\sum\limits_{k=1}^n \sum\limits_{d|k} d^2 = ?? \\
\sum\limits_{x=1}^n \sum\limits_{y=1}^x \gcd(x, y) = ?!?
\end{gather}$$
As it turns out, such and many similar sums can be computed with Dirichlet convolution in $O(n^{2/3})$, and in this article we will learn how.
Let $f(n)$ and $g(n)$ be two [arithmetic functions](https://en.wikipedia.org/wiki/Arithmetic_function). Let $F(n)$ and $G(n)$ be their prefix sums, that is
$$\begin{matrix}
F(n) = \sum\limits_{i=1}^n f(i), & G(n) = \sum\limits_{j=1}^n g(j).
\end{matrix}$$
We need to compute a prefix sum of the [Dirichlet convolution](https://en.wikipedia.org/wiki/Dirichlet_convolution) $(f * g)(n)$. In this article, we will consider some general methods, and show how to do so in $O(n^{2/3})$ if we can compute prefix sums of $F(n)$ and $G(n)$ in ...
O\left(\frac{n^\beta}{i^\beta}\right) + \sum\limits_{j=1}^l
O\left(\frac{n^\alpha}{j^\alpha}\right, $$ n^{\beta} = n k^{\alpha + \beta - 2} \implies \boxed{k = n^{\frac{1-\beta
}{2-\alpha-\beta}}} $$, )$ in $n^\beta$ for $0 \leq \alpha, \beta < 1$. What is the optimal splitting
pair $(k, l)$? Note, In particular, for $\alpha=0$ and $\beta=1/2$ we get $k=n^{1/3}$ and
$l=n^{2/3}$, making for the, Let's now assume that we can compute $F(n)$ in $n^\alpha$ and $G(n)$ in $n^\beta
$ for $0 \leq, Okay now, but what if $\alpha$ and $\beta$ are roughly the same, and also
reasonably huge? For
6.
Combinatorial species: An intuition behind generating functions Hi everyone!
The usage of generating functions is quite common in competitive programming these days. But it seems to happen so, that they're mostly presented as a way to simplify formal manipulation with polynomial coefficients, rather than something meaningful. But there actually is a meaning to all of this, and today I'm going to shed a light on it.
Alongside the blog post we'll uncover the combinatorial meaning of
- The addition $F(x)+G(x)$,
- The multiplication $F(x)G(x)$,
- The exponent $\exp F(x)$,
- The logarithm $\log F(x)$,
- The sum of the infinite geometric progression $\frac{1}{1-F(x)}=1+F(x)+F^2(x)+\dots$,
- The general composition $F(G(x))$
for the generating functions $F(x)$ and $G(x)$ and the underlying structures they represent.
### Prerequisites
- Basic notion of set theory (cardinality of sets, mappings, bijections, cartesian product, disjoint union, etc);
- Polynomials and formal power series (representation, convolution formula, power seri...
**Def. 10**. Two structures $\alpha, \beta \in F(A)$ are **equivalent** if
there is a bijection
7.
Linear Basis (Xor Basis Extended) As part of the graduation requirements for my school, I have to complete a simple research project, so I decided to do something related to data structure and algorithms. I believe I have come out with a data structure that maintains the basis of vectors in $(\mathbb{Z}/m\mathbb{Z})^d$, where $m$ **may not be prime**. Since this was related to competitive programming, I think it is a good idea to share it here. Hopefully, this algorithm is actually novel :P
I would like to thank:
- [user:icypiggy,2021-12-26] for being my research mentor and tolerating my dumb questions
- [user:rama_pang,2021-12-26] and [user:adamant,2021-12-28] for their helpful suggestions and comments
Please comment under the blog or message me on codeforces if any parts are unclear or wrong. Also, I hope that some LGMs can help solve the open problems in this blog.
# Introduction
Maintaining the basis of vectors in $(\mathbb{Z}/2 \mathbb{Z})^d$, also known as the xor basis algorithm is a well-studie...
, \lambda_d \in (\mathbb{Z}/m\mathbb{Z})$ such that $\sum\limits_{k=z+1}^d
(\mu_k+\beta\mu_k') A_k, Let $V=\sum\limits_{k=z}^d \mu_k A_k$ and $\mu_{z}=\alpha+\frac{k}{A_{z,z}} \
beta$ where $0 \leq, }{A_{z,z}} \beta) A_z + \sum\limits_{k=z+1}^d \mu_k A_k= \alpha A_z +
\sum\limits_{k=z+1}^d (\mu_k
8.
Codeforces Beta Round #80 <p>Hi all!</p><p>Now it's time for 80th Codeforces Beta Round.</p><p>The authors of the contest are: <span class="Apple-style-span" style="font-family: verdana, arial, sans-serif; font-size: 12px; "><a href="http://codeforces.me/profile/Alex_KPR" title="Подполковник Alex_KPR" class="rated-user user-red" style="font-family: arial; text-decoration: none !important; font-weight: bold; color: rgb(0, 0, 204); ">Alex_KPR</a></span>, <span class="Apple-style-span" style="font-family: verdana, arial, sans-serif; font-size: 12px;"><a href="http://codeforces.me/profile/winger" title="Подполковник winger" class="rated-user user-red" style="font-family: arial; text-decoration: none !important; font-weight: bold; color: rgb(0, 0, 204); ">winger</a></span>, <span class="Apple-style-span" style="font-family: verdana, arial, sans-serif; font-size: 12px;"><a href="http://codeforces.me/profile/RAD" title="Штаб, RAD" class="rated-user user-admin" style="font-family: arial; text-decoration:...
Codeforces Beta Round #80,
Now it's time for 80th Codeforces Beta Round.
Announcement of Codeforces Beta Round 80 (Div. 1 Only)
Announcement of Codeforces Beta Round 80 (Div. 2 Only)
9.
Nimbers and Sprague-Grundy theorem Hi everyone!
Today I'd like to write about the so-called Grundy numbers, or nimbers. I will start by providing a formal recap on the Sprague-Grundy theorem and then will advance to the topic that is rarely covered in competitive programming resources, that is I will write about nimber product and its meaning to the game theory.
_I was asked to add the following to the blog: THANK SIR MASTER [user:ADAM_GS,2022-06-12] FOR GREAT AND VALUABLE REVIEW SIR_
## Prerequisites
Familiarity with the following concepts:
- Basic [set theory](https://en.wikipedia.org/wiki/Set_theory) notion: [union](https://en.wikipedia.org/wiki/Union_%28set_theory%29), [cartesian product](https://en.wikipedia.org/wiki/Cartesian_product) and [symmetric difference](https://en.wikipedia.org/wiki/Symmetric_difference) of sets, [set of all subsets](https://en.wikipedia.org/wiki/Power_set) denoted as $2^A$, etc;
- [Groups](https://en.wikipedia.org/wiki/Group_%28mathematics%29) and [fields](https://en.wiki...
**Claim 10**. Let $a=2^{2^\alpha}$ and $b = 2^{2^\beta}$, where $\alpha \neq \
beta$. Then $a \cdot
10.
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...
$$ \left\{e_{\beta} + 10^5 \left(a^{n-1-i} \mod p \right) e_{\alpha_i} \Big| 0
\leq i < n\right, \alpha_i \equiv 0 \pmod{p} $$ The set $$ \left\{(\alpha_0, \dots,
\alpha_{n-1}, \beta) \Big| \beta
11.
Codeforces Beta Round #97 <p</p><p</p><p</p><p</p><p</p><p</p><p</p><div>Всем привет!</div><div><br /></div><div>В пятницу, 9 декабря в <a href="http://timeanddate.com/worldclock/fixedtime.html?day=9&month=12&year=2011&hour=19&min=0&sec=0&p1=166">19:00 MSK</a> состоится Codeforces Beta Round #97, автором которого являюсь я. Это мой второй полноценный раунд на Codeforces и надеюсь, что не последний :)</div><div><br /></div><div>Спасибо [[user:maksay,2011-12-08]], [[user:Shtrix,2011-12-08]], [[user:it4.kp,2011-12-08]], [[user:RAD,2011-12-08]] и [[user:Delinur,2011-12-08]] за помощь в подготовке раунда, тестировании задач и переводе условий.</div><div><br /></div><div>Удачи на раунде!</div><div><br /></div><div><b>UPD: </b>По техническим причинам раунд переносится на 5 минут вперед.</div><div><br /></div><div><b>UPD 2: </b>По причине большого числа участников и большого количества тестов, результаты появятся не скоро.</div><div><br /></div><div><b>UPD 3: </b>Тестирование завершено, результа...
Codeforces Beta Round #97, Beta Round #97, автором которого являюсь я. Это мой второй полноценный раунд на
Codeforces и надеюсь
Announcement of Codeforces Beta Round 97 (Div. 1)
Announcement of Codeforces Beta Round 97 (Div. 2)
12.
Kőnig's and Hall's theorems through minimum cut in bipartite graphs Hi everyone!
There is a [well-known result](https://en.wikipedia.org/wiki/Kőnig%27s_theorem_%28graph_theory%29) about bipartite graphs which is formulated as follows:
> In any **bipartite graph**, the number of edges in a **maximum matching** equals the number of vertices in a **minimum vertex cover**.
Knowing it you can easily find the size of a minimum vertex cover in a given bipartite graph. But what about actually recovering such cover? Well... There is an algorithm to it, but it's lengthy and not very motivated, so I constantly forget its details. However, there is a simple alternative, which is easily reproduced from scratch, even if you forget specific details.
Besides, there is another [well-known result](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem) which is formulated as follows:
> A **bipartite graph** has a **perfect matching** if and only if every subset $\alpha$ of one part has a neighborhood $\beta$ in the other part such that $|\beta| \geq |\al...
has a neighborhood $\beta$ in the other part such that $|\beta| \geq |\alpha|$., subset $\alpha$ of one part has a neighborhood $\beta$ in the other part such
that $|\beta| \geq, vertices) $\beta \subset B$ of any $\alpha \subset A$ is such that, $ for which $|\beta| \geq k|\alpha|$ does not hold., $$ |\beta| \geq k |\alpha|. $$
13.
RSHF — a Rating and Report System (Beta) # TL-DR
##### https://rshf.net/ (not adapted for mobile)
##### https://chromewebstore.google.com/detail/rshf/jmpohmlhicdbghkhageaiefhenmkdfcg
(the most recent version will be available at https://github.com/welcome-to-the-sunny-side/rshf-extension)
<br>
# TS-DR
<img src="https://i.ibb.co/NdgvgPLG/logo.png" alt="RSHF logo" style="float:right;width:300px !important;height:auto;margin-left:30px; margin-bottom:6px;">
Simply put, RSHF offers the ability for users to form groups that have their own self-contained rating, report and moderation systems. Deeper visual integration with the Codeforces website is offered through a browser extension. More details on each of these components follow:
### Groups
Group members are partitioned into three tiers:
1. Admins
2. Moderators
3. Members
Their roles and responsibilities closely match what you might think they do: Admins and Moderators process reports and take appropriate actions in response. Admins have additi...
RSHF — a Rating and Report System (Beta), ratings would only mean anything if enough people joined it). We intend to run
RSHF inbeta for a, We intend to run RSHF in beta for a month or so, to iron out unexpected bugs
and make everything
14.
Codeforces Raif Round 1 Editorial [problem:1428A]
------------------
Setter: [user:bensonlzl,2020-10-17]
Prepared by: [user:errorgorn,2020-10-17]
<spoiler summary="Hint 1">
Consider when $x_1=x_2$
</spoiler>
<spoiler summary="Hint 2">
Consider when $x_1 \ne x_2$
</spoiler>
<spoiler summary="Solution">
We consider 2 cases.
The first is that the starting and ending point lie on an axis-aligned line. In this case, we simply pull the box in 1 direction, and the time needed is the distance between the 2 points as we need 1 second to decrease the distance by 1.
The second is that they do not lie on any axis-aligned line. Wabbit can pull the box horizontally (left or right depends on the relative values of $x_1$ and $x_2$) for $|x_1-x_2|$ seconds, take 2 seconds to move either above or below the box, then take another $|y_1-y_2|$ seconds to move the box to $(x_2,y_2)$.
</spoiler>
<spoiler summary="Code (C++)">
```c++
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::...
Such cutting is optimal as suppose we have $2$ pieces of length $\alpha$ and $\
beta$, and $\alpha+2
Tutorial of Codeforces Raif Round 1 (Div. 1 + Div. 2)
15.
Kapun's algorithm I'd like to share this one unpopular but awesome algorithm that I only heard a mention of once. Kapun's algorithm finds a hash collision for moduli as large as $10^{18}$. I know, we have *lots* of algorithms that do much better than that (and I'm writing an article on that at the moment, keep tuned), but Kapun's algorithm is really surprising in its simplicity. That its correctness is so difficult to prove is of more surprise even.
Here we go.
A polynomial hash of a string $s$ is defined as
$$
H(s) = s_0 b^0 + s_1 b^1 + s_2 b^2 + \dots + s_{n-1} b^{n-1} \pmod M.
$$
We want to find two strings with the same polynomial hash using only two characters: $0$ and $1$.
We can reformulate this problem in another way. Let $a_i = b^i \mod M$, then we want to find two distinct subsets of $a$ with the same sum modulo $M$. Now *forget about the modulus*: let's just find two subsets with the same sum.
Firstly, when is this possible? There are $2^n$ possible subsets and $n(M - 1) -...
Kapun's algorithm necessarily succeeds if $R > \alpha + n^{\beta \ln n}$, where
$\alpha, \beta$ are
16.
My CP Course "Zero to Hero" is now open for pre-registration! Having had a ton of experience with CP, I have decided that I could share my knowledge the best with the world by making a course! This course currently has lessons designed for people of many levels, from newbies to low masters.
Currently, I have opened pre-registration. I'm currently just trying to get an idea of how many people would be interested in such a course (and also to catch possible bugs on the website).
Here is the course website: http://course.williamlin.io/
100 lucky winners who pre-register will be given beta access to the course for free! Pre-registration won't be open for long though, so be sure to do it quick!
**Update:**
Thanks to every who pre-registered! The pre-registration assessment proved to be tough, and we decided to offer spots for beta access even for those who did not pass the test! Look out for an email from [email protected] for your decision letter, as well as solutions and more opportunities to gain beta access to the course!
**Up...
decided to offer spots for beta access even for those who did not pass the
test! Look out for an email, winners who pre-register will be given beta access to the course for free!
Pre-registration won't be, 100 lucky winners who pre-register will be given beta access to the course for
free! Pre, Congrats to the people who were selected to be part of the beta course:
17.
CHelper 4.4 I would really appreciate any new ideas of what new features to add
I would also appreciate donations: [Yandex.Money](https://money.yandex.ru/embed/shop.xml?account=410011732687384&quickpay=shop&payment-type-choice=on&writer=seller&targets=CHelper&targets-hint=&default-sum=100&button-text=03&successURL=), [PayPal](https://www.paypal.me/CHelper)
Seems like no one tried beta verion — I would really appreciate feedback
**4.4.3b3**
- All supported sites are updated
- New Google Code Jam is now supported
- You can now inline any file (feature best used for DCJ, which is not here this year, but I hope will return)
------
**4.4.1b2**
Support for interactive tasks added. By default you would interact using user input, but you can write your own interractor
------
**4.3.1**
Task format is changes to JSON. I would recomment backing up your project before updating
------
**4.2.2**
- Critical bug fix
- CHelper Beta is no longer supported. You can sel...
&successURL=), [PayPal](https://www.paypal.me/CHelper) Seems like no one tried
beta verion — I, - Critical bug fix - CHelper Beta is no longer supported. You can select Beta
channel of CHelper, Fix for USACO parsing. Currently on beta channel, Seems like no one tried beta verion — I would really appreciate feedback
18.
Codeforces Beta Round #97: разбор <p>Представляю разбор задач Codeforces Beta Round #97. Если есть какие-то вопросы или пожелания --- пишите в комментариях.</p><h3>[[problem:136A]] (A Div 2)</h3><div><br /></div><div>В этой задаче нужно было просто считать перестановку и вывести обратную к ней. Для этого просто при считывании <i>i</i>-го по счету числа, которое равно <i>a</i> поместим <i>i</i> в ячейку массива с номером <i>a</i>. После этого выведем полученный массив.</div><div><br /></div><div>Сложность решения $O(N)$.</div><div>[cut]</div><div><h3>[[problem:136B]] (B Div 2)</h3></div><div><br /></div><div>Легко понять, что ответ всегда определяется однозначно. Для того чтобы его найти, можно ввести аналог операции вычитания без переноса разрядов. От каждого разряда числа <i>c</i>, записанного в троичной системе счисления отнимем соответствующий разряд числа <i>a </i>и результат вычитания в каждом разряде возьмем по модулю 3. Полученное число и будет искомым <i>b</i>, таким что <i>a tor b = c</i>.</div><div><br /></di...
Codeforces Beta Round #97: editorial, Codeforces Beta Round #97: разбор,
Here is the editorial of Codeforces Beta Round #97. If you have any questions
or suggestions
,
Представляю разбор задач Codeforces Beta Round #97. Если есть какие-то вопросы
или пожелания
Tutorial of Codeforces Beta Round 97 (Div. 1)
Tutorial of Codeforces Beta Round 97 (Div. 2)
19.
Young Tableaus and the Hook Length Formula Boring backstory of this blog
-----------------------------
In 300IQ contest 3, there [was a problem](https://codeforces.me/gym/102538/problem/D) where you had to count the number of permutations with two disjoint longest increasing subsequences. We VCd this contest while practising for ICPC, and didn't solve this problem during the contest, so I was very interested to see how it could be solved. Turns out the solution uses something called Young diagrams, and unless you already know what they are, the editorial is impossible to understand.
I asked if someone knew about Young diagrams on the competitive programming discord, and got linked [a paper](https://github.com/enkerewpo/OI-Public-Library/blob/master/IOI%E4%B8%AD%E5%9B%BD%E5%9B%BD%E5%AE%B6%E5%80%99%E9%80%89%E9%98%9F%E8%AE%BA%E6%96%87/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F2019%E8%AE%BA%E6%96%87%E9%9B%86.pdf) from the Chinese IOI selection camp, written by [user:yfzcsc,2021-12-22]. If you can speak chinese, you shoul...
sets $A$ and $B$. If $\alpha = \max A$ and $\beta = \max B$, we claim that
\begin{equation} p(A, B, Now, we are done, as \begin{equation} \sum_{a \leq \alpha, b \leq \beta}
\frac{1}{n} \sum_
20.
Basis change in linear recurrences Hi everyone!
Today I'd like to write about Fibonacci numbers. Ever heard of them? Fibonacci sequence is defined as $F_n = F_{n-1} + F_{n-2}$.
It got me interested, what would the recurrence be like if it looked like $F_n = \alpha F_{n-p} + \beta F_{n-q}$ for $p \neq q$?
<hr>
**[Timus — Fibonacci Sequence](https://timus.online/problem.aspx?space=1&num=1133)**. The sequence $F$ satisfies the condition $F_n = F_{n-1} + F_{n-2}$. You're given $F_i$ and $F_j$, compute $F_n$.
<hr>
Using $L(x^n) = F_n$ functional, we can say that we essentially need to solve the following system of equations:
$$1 \equiv \alpha x^{-p} + \beta x^{-q} \pmod{x^2-x-1}.$$
To get the actual solution from it, we should first understand what exactly is the remainder of $x^n$ modulo $x^2-x-1$. The remainder of $P(x)$ modulo $(x-a)(x-b)$ is generally determined by $P(a)$ and $P(b)$:
$$
P(x) \equiv r \mod(x-a)(x-b) \iff \begin{cases}P(a) = r,\\ P(b)=r.\end{cases}
$$
Therefore, our equation a...
$$ \begin{matrix} \alpha = \dfrac{b^{-q}-a^{-q}}{a^{-p}b^{-q} - a^{-q}b^{-p}},
& \beta = \dfrac{a, $$ \boxed{\begin{matrix} \alpha = \dfrac{a^q-b^q}{a^{q-p} - b^{q-p}}, & \beta =
\dfrac{a^p-b^p}{a, $$1 \equiv \alpha x^{-p} + \beta x^{-q} \pmod{x^2-x-1}.$$, Multiplying numerators and denominators by $a^q b^q$ for $\alpha$ and $a^p b^p$
for $\beta$, we get, Substituting it back into $\alpha$ and $\beta$, we get, } $$ Therefore, we have a system of equations $$ \begin{cases} \alpha a^{-p}
&+& \beta a^{-q} &=& 1, } + \beta F_{n-q}$ for $p \neq q$?, } + \beta a^{-q} = 1,\\ \alpha b^{-p} + \beta b^{-q} = 1. \end{cases} $$ The
determinant of this
21.
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 ...
So, in "Super-Chess", A would be rated about **649** points higher (because
$\sigma(649/\beta, This can be written mathematically in terms of the sigmoid function as
$\sigma(\Delta / \beta
22.
Трассировка вектора В этом году проходил BSUIR Open XIV, мне было очень приятно съездить в Минск и на само соревнование. Но еще больше мне понравилась задачу, которую я туда предложил. В целом я не видел эту идею раньше, но она кажется достаточно простой, чтобы появиться раньше на каких-нибудь соревнованиях. Так что если вы знаете, где раньше встречалась это идея, то поделитесь, пожалуйста.
**Задача.** (*BSUIR OPEN XIV*) Дано клеточное поле $100 \times 100$, в котором между некоторыми клетками проведены стены, также стены проведены по границе поля. Луч запускается из центра клетки $(r,c)$ в направлении $(x,y)$. Требуется определить, в какой клетке он окажется, пройдя расстояние $\sqrt{x^2+y^2}$, если луч отражается от стен.
Решение задачки
------------------
Взглянем на вектор $(x,y)$ и посмотрим, в каком порядке он пересекает вертикальные и горизонтальные линии сетки. В точке $(0,0)$ пересечение с линиями сетки учитывать не будем, но будем учитывать пересечения в точке $(x,y)$, причем по формал...
, \beta)$, then the resulting string $s(x,y,\alpha,\beta)$ may differ from
$s(x,y)$. However, it is, Так, если запускать вектор не из точки $(0,0)$, а из произвольной точки
$(\alpha, \beta)$, то может
23.
A (Somehow) Simple (Randomized) Algorithm for Frobenius Form of a Matrix Hello everyone!
I'd like to share a simple algorithm for computing the [Frobenius form](https://en.wikipedia.org/wiki/Frobenius_normal_form) (or called rational canonical form) of a matrix. Before stating what is the algorithm, let me first give some applications.
## Matrix Exponentiation
We know that one can compute the matrix exponential of a matrix $A^K$ in $O(N^3 \log K)$ time,
via binary exponentiation.
If one knows how to compute the characteristic polynomial $p(T)$ of $A$ in $O(N^3)$ time, then one can first use the [Cayley–Hamilton theorem](https://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theorem) to reduce the problem into computing
$$ \sum_i r_i A^i, $$
where $r_i$ is the coefficient of
$$ \sum_i r_i T^i = T^K \bmod p(T). $$
This reduces the time to $O(N^4 + N^2\log K)$, or even $O(N^4 + N\log N\log K)$ if you use FFT to speed up the computation of $T^K \bmod p(T)$.
Some sqrt tricks can further reduce the time to $O(N^{3.5} + N\log N \log K)$, but i...
V_2 \subset \cdots \subset V_\ell = V, $$ where $V$ is the whole space. Let $\
beta = \{v_1,Av_1,\dots, $, so this columns only contains one $1$ in $[A]_\beta$. The only problem is
that the column for each, Under our chosen basis, the matrix looks like $$ [A]_\beta = \begin{pmatrix}
C_1 & 0|* & \cdots
24.
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> (Павел Кунявский) и <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> (Макс Ахмедов). Соревнование проходит одновременно в двух дивизионах. Суммарно вам будет предложено 7 различных задач с вариациями в разных дивизионах, по 5 в каждом дивизионе. Мы надеемся что все смогут показать свой результат и решить как можно больше задач. <div><br>Мы хотим поблагодарить <a href="http://codeforces.me/profile/RAD" title="Штаб, RAD" class="rated-user user-admin" style="font-family: ...
Codeforces Beta Round #73
Announcement of Codeforces Beta Round 73 (Div. 1 Only)
Announcement of Codeforces Beta Round 73 (Div. 2 Only)
25.
GoForGold Camp 2024 — Wrap I just returned from the **1st** edition of the [**GoForGold** camp](https://codeforces.me/blog/entry/135929) in India 🇮🇳, where I had the privilege of teaching some of the brightest Indian students as they prepare for the upcoming ICPC World Finals.
After organizing camps in [Syria](https://codeforces.me/blog/entry/118493), [Uzbekistan](https://www.linkedin.com/feed/update/urn:li:activity:7144180416655118336/), Azerbaijan, and [Croatia](https://codeforces.me/blog/entry/134097), this was yet another incredible experience of helping students push closer to their competitive programming goals.
A highlight of this trip was witnessing the unique approach of Newton School of Technology. They brought teachers right from industry to university to fill the gap — a truly innovative structure that left a lasting impression.
Congratulations to the top three winners in Div. 1:<br>
🥇 [404_solution_not_found](https://codeforces.me/team/168505): [user:P.V.S...
/B56ZO_pNCaHoAc-/2/1734087095586?e=1735171200&v=beta
&t=RCtXMGvANjp2aVEgTJyMzTxA4YVPHLA61VnnecvcIzQ
26.
Anti-hash test. Hi everyone! I wan't to share some interesting fact about how we're going to challenge almost every solution, that uses polynomial hashes modulo 2^64. We'll hack any solution, regardless of it's base (!), the only thing we need, that it's using int64 with overflows --- like many coders write hashing.
Keywords: Only today, only for you, ladies and gentlemen: we're gonna challenge [user:Petr,2012-07-19]'s solution in problem [problem:7D] from Codeforces Beta Round #7!
Is it interesting? Welcome reading after the cut.
[cut]
Firstly, for the most impatient of you. Here's the source of the generator:
~~~~~
const int Q = 11;
const int N = 1 << Q;
char S[N];
for (int i = 0; i < N; i++)
S[i] = 'A' + __builtin_popcount(i) % 2;
// this function in g++ returns
// number of ones in binary representation of number i
~~~~~
Let's try solutions of two CFBR #7 winners on this test: Petr Mitrichev's and Vlad Epifanov's.
[user:vepifanov,2012-07-18] solution doe...
задаче [problem:7D] с Codeforces Beta Round #7!, -19]'s solution in problem [problem:7D] from Codeforces Beta Round #7!, Берём и стравливаем на таком тесте решения двух победителей Codeforces Beta
Round #7 — Петра
27.
Разбор Codeforces Beta Round #13 Представляю разбор Codeforces Beta Round #13. Если будут какие-то вопросы или замечания - прошу писать в комментариях.<div><br></div><div>[cut]</div><div><b>Задача A.</b></div><div>Достаточно просто перебрать все основания системы исчисления, просуммировать цифры числа по всем основаниям, а затем найти наибольший общий делитель полученной суммы и числа А-2 (количество оснований систем исчисления) и сократить полученную дробь на найденный НОД. Сложность алгоритма O(A).</div><div><br></div><div><b>Задача B.</b></div><div>Эта задача оказалась довольно неприятной для реализации, но все что нужно было сделать - аккуратно проверить выполнение трех пунктов, данных в условии. В вычислениях рекомендуется использовать целочисленную арифметику, делать все проверки при помощи векторных и скалярных произведений.</div><div><br></div><div><b>Задача C.</b></div><div>Заметим, что существует неубывающая подпоследовательность, которую можно получить из данной за минимальное количество ходов и у которой в...
Codeforces Beta Round #13 editorial, Разбор Codeforces Beta Round #13,
Let me introduce an editorial to Codeforces Beta Round #13. If you have any
questions or
, Представляю разбор Codeforces Beta Round #13. Если будут какие-то вопросы или
замечания - прошу
Tutorial of Codeforces Beta Round 13
28.
Osijek Competitive Programming Camp 2023 winter — wrap Hi everyone!
<center><a href="https://ocpc.mathos.unios.hr"><img src="https://ocpc.mathos.unios.hr/images/ocpc.svg" height="100px"></a></center>
<center>
<b>Sponsored by</b><br>
<a href="https://www.janestreet.com/join-jane-street/open-roles/?type=students-and-new-grads&location=london">
<img src="/predownloaded/ee/f2/eef26616a3661c658d1545f18ed21fabb14d5871.svg" height="50px" style="margin: 5px 5px 5px 5px;">
</a>
<a href="https://www.think-cell.com/osijek2023"><img src="/predownloaded/97/88/97887beeb75a4601259414b36ecee0160c29d027.svg" height="40px" style="margin: 5px 5px 5px 5px;"></a>
<a href="https://pinely.com/">
<img src="/predownloaded/0a/0f/0a0f3f67435d1f6e467bc7203d4a2090ba8f92cc.svg" height="50px" style="margin: 5px 5px 5px 5px;">
</a>
</center>
The [Osijek competitive programming camp](https://ocpc.mathos.unios.hr) (also see the [announcement](https://codeforces.me/blog/entry/110945) on Codeforces) just concluded last Sunday, on February 26, and I'd lik...
, indeed, a bit raw at the moment, as, to my knowledge, it's only in the beta
as a service for
29.
Avito Cool Challenge 2018 Editorial [problem:1081A]
Idea: [user:yjq_naiive,2018-12-17] Developer: [user:yjq_naiive,2018-12-17]
<spoiler summary="Hint">
1 sounds like the minimum value we can get. Why? Is it always true?
</spoiler>
<spoiler summary="Solution">
When $n \leq 2$, we can do nothing.
When $n \geq 3$, since $1<\frac{n}{n-1}<2$, $n-1$ isn't a divisor of $n$, so we can choose it and get $1$ as the result.
</spoiler>
<spoiler summary="Code (yjq_naiive)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
if (n == 2) {
puts("2");
} else {
puts("1");
}
return 0;
}
~~~~~
</spoiler>
[problem:1081B]
Idea: [user:yanQval,2018-12-17] Developer: [user:yanQval,2018-12-17]
<spoiler summary="Hint">
Consider the number of people wearing hats of the same color.
</spoiler>
<spoiler summary="Solution">
let $b_i=n-a_i$ represent the number of people wearing the same type of hat of $i$-th person.
Notice that the person wear...
$ be $\alpha=\beta\theta$. Since $\alpha=pq'=\beta\theta=r's$, by Lemma 3 $q'$
and $r'$ should also
30.
Codeforces Beta Round 79 <p>Hello!</p><p>I'm, Valeriy Samojlov, graduating student of SPbSU,
present you codeforces beta round 79. Today you will meet with boy Gerald and will help him to solve some living problems. </p><p>Today we have usually cost of problems in both divisions: 500 - 1000 - 1500 - 2000 - 2500.</p><p>It my first codeforces round, I hope, problems will be interesting.</p><p><span class="Apple-style-span">I want to thank Artem Rakhov (</span><span class="Apple-style-span" style="border-collapse: collapse; font-family: verdana, arial, sans-serif; font-size: 13px; "><a href="http://codeforces.me/profile/RAD" title="Штаб, RAD" class="rated-user user-admin" style="font-family: arial; text-decoration: none !important; font-weight: bold; color: rgb(0, 0, 204); ">RAD</a></span><span class="Apple-style-span">) for big help with preparation of problems, Makar Krasnoperov (<span class="Apple-style-span" style="border-collapse: collapse; font-family: verdana, arial, sans-serif; font-size: 13px...
Codeforces Beta Round 79,
I'm, Valeriy Samojlov, graduating student of SPbSU, present you codeforces beta
round 79
, beta round 79. Today you will meet with boy Gerald and will help him to solve
some living problems
Announcement of Codeforces Beta Round 79 (Div. 1 Only)
Announcement of Codeforces Beta Round 79 (Div. 2 Only)
31.
User Lists Hello,
We are launching new feature on Codeforces, in early beta mode. I hope it will be useful to many active users of the web-site. Now you can create, manage and use the "user lists".
Partially, it is a kind of generalization of "friends." You can create a list of users interesting to you (you can create many lists) and, using the list, filter the results of rounds, quickly analyze what problems are solved in the problemset, etc. This feature is a helpful tool for coaching — I'm using it. By combining in a list of all practicing students, it is easy to pick up problems that have not been solved (and even not attempted) by any student.
A user list has name and a pair of two relatively secret keys & mdash; one for view/usage and one for editing. For example, here is the key to view a list of ACM-ICPC students at Saratov State U for autumn of 2015: 15c68c2cf878267d59373d1...
I remind you that the functionality is in early beta mode & mdash; there may be
some issues. We, We are launching new feature on Codeforces, in early beta mode. I hope it will
be useful to many
32.
Codeforces Beta Round #69 <div><div>Hi all!</div><div><br></div><div>Glad to see you on the Codeforces Beta Round #69. As you suspect, it's not an usual contest.</div><div><br></div><div>Every division has 5 problems. Some problems are in both divisions; other are meant for certain division. But from the participant's point of view there are no striking differences from other rounds.</div><div><br></div><div>Please notice that such an experiment is the first one, so some technical troubles and unexpected problems are possible. Please treat with understanding if it occurs.</div><div><br></div><div>Also: the costs of the problems in the first division are 500-1000-1500-2000-<b>2000</b>. In the second division the costs are classic: 500-1000-1500-2000-2500.</div><div><br></div><div>The round was prepared by <span class="Apple-style-span" style="border-collapse: collapse; font-family: verdana,arial,sans-serif; font-size: 13px;"><a href="http://codeforces.me/profile/Alex_KPR" title="Майор Alex_KPR" class="rated...
Codeforces Beta Round #69
Announcement of Codeforces Beta Round 69 (Div. 1 Only)
Announcement of Codeforces Beta Round 69 (Div. 2 Only)
33.
Can You Solve the Following Minimization Problems? I've spent some time on the following problem, which is quite generic (and is similar to many well-known problems):
You are given $2n$ pairs of integers $(x_i, y_i)$, where $1 \leq x_i, y_i \leq M$. Your goal is to choose exactly $n$ of them, such that their pointwise sum $(X, Y)$ (that is, you sum each coordinate on its own), minimizes the cost function $f(X, Y)$. What is the best time complexity you can achieve, given some properties about the function $f$?
Since the time complexity can depend on both $n$ and $M$, the order in which the best complexity is determined is:
1. Polynomial in $n$ and in $\log M$.
2. Polynomial in $n$ and in $M$.
3. $O(\binom{2n}{n})$ (applicable to all of them).
Try to solve each of the following variations, with varying difficulties. **This post is purposed for all levels**, and I'll try to write solutions that can be understood by all levels (except maybe for the advanced problems).
I'm interested to know if you have any other variat...
real $\alpha, \beta$ such that $(X,Y)$ is the solution that minimizes the cost
function $g_{\alpha, The idea would be to sweep through all slopes / pairs of $\alpha, \beta$ and
find the optimal
34.
Codeforces::Тренировки <p> Как говорится "Мы строили, строили и, наконец, построили". Или во всяком случае близки к этому. </p> <p> 19-го января 2012 года в 12:00 мы открываем подпроект "Тренировки" (по-английски мы назвали его "Gym", т.е. спортзал). Если коротко, то его цель предоставить сервис для того, чтобы на Codeforces вы могли не только участвовать в соревнованиях и обсуждать их, но и удобно тренироваться и тренировать. </p><p> В самом деле, при всем разнообразии online judges в мире, толкового сервиса для проведения тренировок не существует. Что хочется от такого сервиса: </p> <ol> <li> Наличие базы виртуальных контестов, составленных преимущественно из прошедших официальных соревнований. </li><li> Возможность интегрировать результаты прошедших соревнований в виртуальные контесты, чтобы была возможность тренироваться "против" официальных участников. </li><li> Возможность в любое время дня и ночи поучаствовать в тренировке, не боясь, что что-то сломается и се...
Conclusion
In conclusion I want to add that this is not even a beta yet, but we will
, "2010 Codeforces Beta Round #1 (the training)", but even there a coach will
also be, ;2010 Codeforces Beta Round #1 (тренировка)", но и там тренеры тоже будут
вычищать неадекватные
35.
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 <...
1. ~Vincella,2024-11-01 2. ~SUPERLWR-beta,2024-11-01 3. ~BlackLily,2024-11-01 4
Announcement of Codeforces Round 983 (Div. 2)
36.
[Beta] Harwest — Git wrap your submissions this Christmas! Hi beautiful people of Codeforces! Hope you'd all be doing fine and keeping safe.
I'd like to start by mentioning that it's been a while since I graduated from university ever since which I haven't completely been able to indulge myself in competitive coding in the same way I did back in my university. But I sure haven't forgotten those days.
I had some time off from work recently and decided to spend my time giving back to the community from where I have learned so much.
In the thought of so, I've built this tool which I like to call [`Harwest`](https://github.com/nileshsah/harwest-tool) (a play on the word Harvest since the package name wasn't available anymore :'D)
It's one of those tools which I would have loved to have during the time when I used to practice rigorously on this platform.
**Harwest** allows you to manage all the submissions that you've made on Codeforces, or on other OJs (WIP) into one single Git repository which you can then push to your personal Github...
[Beta] Harwest — Git wrap your submissions this Christmas!, I haven't got a chance to extensively test Harwest much and hence the term [Beta
]. It seems to be
37.
Codeforces Beta Round #72 <p>Приветствую всех на Codeforces Beta Round #72.</p><div>Авторами этого соревнования являются: <a href="http://codeforces.me/profile/HolkinPV">Холкин Павел</a>, <a href="http://codeforces.me/profile/NALP">Николай Кузнецов</a> и <a href="http://codeforces.me/profile/Alex">Калужин Александр</a>. Соревнование проходит одновременно в обоих дивизионах. Вам будут предложены задачи различного уровня сложности, и мы надеемся, что каждый участник справится со всеми трудностями и решит как можно больше задач.</div><div><br></div><div>Мы выражаем благодарность <a href="http://codeforces.me/profile/RAD">Артему Рахову</a> и <a href="http://codeforces.me/profile/it4.kp">Павлу Кузнецову</a> за помощь в подготовке раунда, <a href="http://codeforces.me/profile/Delinur">Марии Беловой</a> за перевод условий и <a href="http://codeforces.me/profile/MikeMirzayanov">Михаилу Мирзаянову</a> за прекрасную систему.</div><div><br></div><div>Главным персонажем сегодняшних задач стане...
Codeforces Beta Round #72
38.
Editorial of Codeforces Round 917 (Div. 2) [problem:1917A]
Author: [user:zidder,2023-12-24] <br>
Preparation: [user:_LeMur_,2023-12-24] <br>
Editorial: [user:zidder,2023-12-24] <br>
Official solution: [submission:238752794] <br>
<spoiler summary="Hint 1">
What is the minimum product that we can get, when one of the given numbers is equal to $0$.
</spoiler>
<spoiler summary="Hint 2">
How is the absolute value of the integer changed, when we apply the given operation on that integer?
</spoiler>
<spoiler summary="Hint 3">
We can always make the product as small as possible with at most $1$ operation.
</spoiler>
<spoiler summary="Solution">
First, let's find the minimum product we can get. If one of the numbers is or becomes $0$, then the product will be $0$. Otherwise, all the numbers don't change their sign during the operation. So the initial product won't change its sign as well. Also, we can note that the absolute value will not increase after an operation. That means if the initial product is negative...
$a_i = x \cdot 2^{\alpha}$ and $a_j = y \cdot 2^{\beta}$ for some $\alpha$ and
$\beta$. It is
Tutorial of Codeforces Round 917 (Div. 2)
39.
Разбор задач Looksery Cup 2015 **UPD.** Появился разбор задачи Е. Мы просим прощения за задержку, он получился действительно трудоемким, и, чтобы как-то загладить свою вину, мы публикуем несколько интерпретаций решения.
**A. Определение лиц**
Автор: [user:Monyura,2015-06-06]
Для решения этой задачи следует перебрать все квадраты 2х2 и проверить, что переставив буквы можно получить слово "face". Это можно удобно сделать, например, отсортировав буквы квадрата в алфавитном порядке и проверив, что отсортированное множество равно "acef"(Отсортированный порядок букв слова "face").
**B. Вечеринка в Looksery**
Автор: [user:Igor_Kudryashov,2015-06-06]
При любом раскладе существует такое множество людей, что, если они придут и разошлют сообщения своим контактам, то каждый сотрудник получит количество сообщений отличное от того, что указал Игорь. Покажем как построить это множество. Рассмотрим 2 случая.
Ни одно из чисел, предложенных Игорем, не равно нулю. Тогда если никто не придет на вечеринку, то всем ...
Так как точки $c$ и $d$ лежат внутри окружности с хордой $ab$, то $\alpha+\beta
<\pi$, аналогично
Tutorial of Looksery Cup 2015
40.
New Online Judge Platform — csacademy.com Hello, Codeforces!
We are glad to invite all of you to test out our new Online Judge platform at [csacademy.com](http://csacademy.com). We're a Romanian based start-up that focuses on online education. Up until this point we've been working on creating a new environment for competitive programming contests.
Our first beta round took place in January and it was an IOI-style contest of medium difficulty. You can have fun solving the problems in our [archive](https://csacademy.com/contest/arhiva/). Pay attention though, it is necessary to have an account in order to solve any problems on our website. You can connect via Facebook or Google+, or you can simply create a new account by providing a valid email address. Once you have an account you can choose a username, but all Codeforces handles are already reserved (so no [user:tourist,2016-03-02] for the locals :D). We have created for you the possibility of connecting your Codeforces user [here](https://csacademy.com/accounts/profile...
programming contests. Our first beta round took place in January and it was an
IOI-style contest of medium, **EDIT**: The [editorial](https://csacademy.com/blog/2016/03/04/beta-round-2/)
is ready, **EDIT2**: We're hosting [Beta Round
#3](http://codeforces.me/blog/entry/43901)., - For the best user experience we recommend using Google Chrome. We are still in
beta and we didn't, Our [second beta round](https://csacademy.com/contest/beta-round-2/) will take
place on [Friday, Наш [второй раунд](https://csacademy.com/contest/beta-round-2/) состоится в
[пятницу, 04.03.2016 в
41.
Exponential Length Substrings in Pattern Matching Hi all,
I would like to share with you a part of my undergraduate thesis on a Multi-String Pattern Matcher data structure. In my opinion, it's easy to understand and hard to implement correctly and efficiently. It's (relatively) competitive against other MSPM data structures (Aho-Corasick, suffix array/automaton/tree to name a few) when the dictionary size is specifically (uncommonly) large.
I would also like to sign up this entry to [user:bashkort,2024-10-04]'s [Month of Blog Posts](https://codeforces.me/blog/entry/133806):-) Many thanks to him and peltorator for supporting this initiative.
#### Abstract
This work describes a hash-based mass-searching algorithm, finding (count, location of first match) entries from a dictionary against a string $s$ of length $n$. The presented implementation makes use of all substrings of $s$ whose lengths are powers of $2$ to construct an offline algorithm that can, in some cases, reach a complexity of $O(n \log^2n)$ even if there are $O...
^{\beta}$. The point we want to fit on $NT$'s graph would lead to $3\beta +
\alpha = 2$. The easiest
42.
Codeforces Beta Round #32 (Div. 2, Codeforces format) <img src="http://assets.codeforces.com/happy_birthday_cake.gif" style="float:left;margin:0.5em;width:160px;">
<p class="MsoNormal"></p><p class="MsoNormal">Attention, participants from the Division 1! As a test feature, you can participate in Codeforces Beta Round #32 <b>"out of competition"</b>.</p><p class="MsoNormal"><br></p><p class="MsoNormal">Everybody knows, that the 2nd of October - birthday of <a href="http://en.wikipedia.org/wiki/Mohandas_Karamchand_Gandhi">Mohandas Gandhi</a>. We dedicate today's round to him, and many other great people who were born on <a href="http://en.wikipedia.org/wiki/2_October">October 2</a> :)</p><p class="MsoNormal"><br></p><p class="MsoNormal">Round was prepared by <a href="http://codeforces.me/profile/MikeMirzayanov">Mike Mirzayanov</a>, <a href="http://codeforces.me/profile/Nerevar">Matov Dmitry</a> and <a href="http://codeforces.me/profile/e-maxx">Max Ivanov</a>.<br></p><p class="MsoNormal">Special thanks to <a href="http:/...
Codeforces Beta Round #32 (Div. 2, Codeforces format), participate in Codeforces Beta Round #32 "out of competition"., ;width:130px;">
Внимание участникам Дивизиона 1! В Codeforces Beta Round #32 в
Announcement of Codeforces Beta Round 32 (Div. 2, Codeforces format)
43.
Unlabeling combinatorial species (cycle index series) Hi everyone!
In my [previous blog](https://codeforces.me/blog/entry/103979), I wrote about how generating functions can be used to enumerated labeled species. In this blog, I want to continue the topic by writing about how one can account for different kinds of symmetries when counting different combinatorial structures. Ultimately, we will end up deriving and hopefully understanding the analogue of [Pólya enumeration theorem](https://en.wikipedia.org/wiki/Pólya_enumeration_theorem) in species.
Difficulty: ★★★★☆
Prerequisites:
- Familiarity with combinatorial species (see my [prev. blog](https://codeforces.me/blog/entry/103979)), OR
- Very good intuition with enumerative combinatorics, genfuncs and recap below.
I will try to use plain language rather than formulas as much as possible, as it seems to be the preferred format for readers.
## Recap
Below is a very brief recap of the most important things from the previous article. I tried to keep it as informal as p...
We say that two structures $\alpha, \beta \in F(A)$ are **equivalent** if one
can be obtained from
44.
CodeDrills Beta Contest #3 [Team Contest] Announcement Hello Codeforces!
CodeDrills will be hosting its first team contest [CodeDrills Beta Contest #3](https://codedrills.io/contests/beta-contest-3) on [Sunday, 7th March, 2021 9:00 PM — 10:30 PM IST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=CodeDrills+Beta+Contest+%233&iso=20210307T21&p1=438&ah=1&am=30).
There will be 4 or 5 problems to be solved in 1.5 hours.
**Contest Details**
- Contest Link — https://codedrills.io/contests/beta-contest-3
- Date & Time — [7 Mar 2021, Sunday, 21:00 IST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=CodeDrills+Beta+Contest+%233&iso=20210307T21&p1=438&ah=1&am=30)
- Duration — 1.5 Hours
- Will follow standard ICPC scoring system (20 minutes penalty and 1 point per problem)
**Registration**
You will need to create a team on the contest page in order to participate. Team size can be upto 3. While creating the team, add the registered emails of other users to invite them to join your team. They will get an i...
CodeDrills Beta Contest #3 [Team Contest] Announcement, - Contest Link — https://codedrills.io/contests/beta-contest-3 - Date & Time —
[7 Mar 2021, Sunday, Hello Codeforces! CodeDrills will be hosting its first team contest [CodeDrills
Beta Contest
45.
THE EPIC OF CODEFORCES For an entire 23 hours the world lost its shining gem: Codeforces. Just before the greatest site in the universe went down, I finally was finished with not-participating in the Educational Round 70 and made my last not-submission at not-contest time. I instinctively rushed to the greatest server of all time, the most shining pinnacle of pseudointellectualism: Proof by AC. Now was the time to make memes. Of course, this involves orzing many great and talented geniuses. (If you were unaware, it is a civic duty.) As a natural consequence, one must look at the friends' standings, to figure out how much to orz. Only logical, right?
But suddenly, while refreshing the almighty Friends Standings page (orz), DISASTER STRUCK!!!!!!!!!!
We encountered unknown technical issues, the website is temporarily unavailable. It is not yet possible to give any predictions when it will be repaired. Sorry about it.
For the rest of the ...
. Never mind the fact that Codeforces was still in beta and hadn't even reached
version 1 yet. CODEFORCES
46.
CF-Predictor — Know your rating changes! <spoiler summary="UPD 2 Sep 2018">
I've deployed an update today. If you face any issues with CF-Predictor, please let me know :)
</spoiler>
Hi guys! As I mentioned on previous contest I'm working on tool that predicts rating changes. I'm happy to present it now!
A huge amount of your nerve cells die every time when you wait for a rating update on Codeforces. Stop this! From now you could use this service, it calculates approximate rating changes for every contestant.
The most interested thing for you is extension. It partly modifies the contest standings page and shows approximate rating changes for every contestant. It is available for three browsers:
[](https://chrome.google.com/webstore/detail/rating-predictor-for-code/ocfloejijfhhkkdmheodbaanephbnfhn)
[. If a player with a high rating plays against a player with a low rating, we would expect the higher rated player to win more, on average.
Now let's define what rating is. If player A has rating $a$ and player B has rating $b$, then player A should have a $\sigma(\frac{a-b}{\beta})$, where $\beta = \frac{400}{\ln 10} = 173.7178$, and $\sigma()$ is the sigmoid function $\sigma(z) = \frac{1}{1+e^{-z}}$.
This formula looks scary, but it's just a formal way of writing the one you might be familiar with. This formula expands/simplifies to:
$$\frac{1}{1 + e^{-\frac{a-b}{400 / \ln 10}}}$$
$$= \frac{1}{1 + 10^{\frac{b-a}{400}}}.$$
You're probably more familiar with the last equation above. If you are 400 points weaker, you'd have a 1 to 10 ($\frac{1}{11...
player A should have a $\sigma(\frac{a-b}{\beta})$, where $\beta =
\frac{400}{\ln 10} = 173.7178$, and, $$L(x) = \mathbb{E}_y\left[ \sigma\left(\frac{x-y}{\beta}\right) \right] =
\displaystyle\int_, $$g = \sqrt{ \beta^2 + \frac{\pi}{8} \sigma_y^2 },$$, So we need to calculate the **expectation** of the likelihood
$\sigma\left(\frac{x-y}{\beta}\right, Then the chance that we win this game is just $\sigma\left(\frac{x-y}{\beta
}\right)$.
48.
JHelper 0.18 Hi, Codeforces.
[Changelog](https://github.com/AlexeyDmitriev/JHelper/wiki/Changelog):
* 0.18
* CopyAction now regenerates output file
* 0.17
* Support for inline inlining for topcoder
* 0.16.4
* Support for WSL
* 0.16.3
* Support CLion 2020.1
* 0.16.2
* Support CLion 2019.1
* 0.16
* Auto switching to a file when changing task
* Auto selecting task when changing a file
JHelper is plugin for writing contests in C++. You may inline code from your own prewritten library so that you can submit only used code. Besides, it allows to test on tests you've added.
it's planned that you'll be able to parse a problem/contest and have all samples tests automatically added.
It's available for [CLion](https://www.jetbrains.com/clion/)
Plugin is completely free. IDE price is 89$/year, but it's free for students, have 30-days free trial and often you can use EAP(smth like beta)-versions for free.
You may download the plugin using JetBrains p...
trial and often you can use EAP(smth like beta)-versions for free.
49.
Useful substitutions with generating functions Hi everyone!
Today I would like to write about some identities that might come handy when using generating functions to solve competitive programming problems. I will also try to include some useful examples about them.
#### Some notation
For brevity, we will sometimes skip the specific bounds in indexed sums, meaning that the summation happens among all _valid_ indices. Please also read the information below if you're not familiar with generating functions, or want to brush up on some aspects.
<spoiler summary="Definitions and notation">
Let's briefly recall that, for a sequence $a_0, a_1, \dots$, it's **ordinary generating function** (OGF) is defined as a formal power series
$$
F(x) = \sum\limits_k a_k x^k,
$$
and its **exponential generating function** (EGF) is defined as
$$
F(x) = \sum\limits_k a_k \frac{x^k}{k!}.
$$
Generating functions are used because it's very simple to represent convolutions with them.
For two sequences $a_0, a_1, \dots$ and $b_...
would be of the form $\frac{1-\alpha t^{k+1} - \beta
t^{k+2}}{1-(1+t)-(1+t)^2}$. Then substitute $t
50.
Codeforces Beta Round 76 - Analysis <p>At first I tell about the contest at all.<br></p>My problems in the contest were A-div2, B-div2, C-div2/A-div1, E-div2/C-div1, D-div1. I wanted to make only div.2 round, but then we decided to give you seven problems at both divisions. <a class="rated-user user-admin" href="../../../profile/MikeMirzayanov" title="Штаб, MikeMirzayanov">MikeMirzayanov</a> prepared the problem about milk pouring and <a class="rated-user user-orange" href="../../../profile/anonymous" title="Майор anonymous">anonymous</a> gave E-div1 problem. Also <a class="rated-user user-admin" href="../../../profile/RAD" title="Штаб, RAD">RAD</a> gave some advices to complicate problems Azembler and Flags a bit.<br><p>And now let's start analysis.<br><br><br><b>Problem A (div.2) - Restoring Password</b><br><br>Password was very easy to restore. You should just iterate over groups of 10 characters in the first string and over all codes. Then, if some number's code is equal to the group - print t...
Codeforces Beta Round 76 - Analysis, Codeforces Beta Round 76 - разбор задач, /standings">Beta Round 60, а добавить все сложные случаи в претесты., ://codeforces.ru/contest/65/standings">Beta Round 60.
Tutorial of Codeforces Beta Round 76 (Div. 2 Only)
51.
CP Editor 2.0.3 : Everything you wanted is here Check : https://cpeditor.github.io
==================
Hi Guys !
Around a week ago, I released the first version of CP Editor. If you are reading about CP Editor for first time. I request you to read my [previous blog](https://codeforces.me/blog/entry/71673) first.
Many user liked it and I got many suggestions about enhancements and some bug reports as well. I liked your over whelming response, it made me happy. Now it's time for me to make you happy.
Enough talking, let's get into what's new in CP Editor 2.0. It is a big release and hence a long blog ;-)
##### Dark theme
Last time there was a dark theme but it only made the editor dark. So, it wasn't truly dark theme. Now with this new release CP Editor packs a system-wide dark theme. Have a look here
##### Dependency Updates
Just like any other software, CP Editor also have a long acyclic dependencies, and over the weeks many were updat...
##### Beta and Nightly, `Help => Use Beta` will enable you to get update notifications for Beta
releases of application
52.
Codeforces Beta Round #7 Контест перенесен на 15 минут. <div><br></div><div>Спасибо всем за участие в Codeforces Beta Round #7. Надеюсь, вам понравилось. В комментариях предлагаю обсудить задачи и систему. Пожалуйста, выскажите ваше мнение, особенно если вы заметили какое-то неадекватное поведение системы. И как всегда я с интересом прочту предложения по улучшению.</div><div><br></div><div>С сегодняшнего контеста рейтинг по дивизионам для общих контестов будет считаться отдельно по двум таблицам положений участников. То есть подсчет рейтинга будет эквивалентен проведению двух контестов отдельно для каждого дивизиона по общим задачам.</div><div><br></div><div><div>Еще момент. Мне бы хотелось, чтобы кто-то взял на себя разбор задач прошедшего раунда. Это надо сделать на русском и английском языках. Разумеется вы должны сдать задачи либо на контесте, либо в дорешивании. Если у вас есть желание это сделать - пишите в комментариях. Ваш пост будет опубликован на главной и позже доступен по спец. ссылк...
Codeforces Beta Round #7
Announcement of Codeforces Beta Round 7
53.
Tutorial on FFT/NTT — The tough made simple. ( Part 2 ) <h1> Welcome to Part 2</h1>
Firstly, I am assuming that you have been through the [Part 1](http://codeforces.me/blog/entry/43499) of this blog.
Okay so in hindsight I now see the drawbacks there were in my explanation of the roots of unity and how the divide and conquer works in FFT.
<b>So in this blog I would be aiming to give you a visual intuition of what really FFT exploits over the trivial classical DFT. Also I would be covering up NTT and sharing a nice trick that I got to know about while learning NTT.</b>
<h2> Visual Intuition of FFT $\rightarrow$ </h2>
The part of converting the polynomial from coefficient form to point value form in $N\cdot \log_2 N$ instead of the trivial $N^2$ would be elaborated upon in this section as I find the dry mathematical explanation to be rigorous but not intuitive. In the notation below I have referred to $n$ complex $n^{th}$ roots of unity as powers of $w_n^{1} = e^{2\pi \cdot i/n}$
Assume that you have a $8$ terms ($7$ degre...
Lemma 2 $\rightarrow$ Another key observation is that $(r^c)^{\alpha} = (r^c)^{\
beta}$ where
54.
Alternative editorial for 973D This is my version of the editorial for problem D of [contest:2013]. It was motivated by [user:GrishinD,2024-09-24]'s great blog about his solution and presents a slower yet interesting alternative. I wanted to try this exercise to improve my thinking process and maybe become a div1 codeforcer along with [user:GrishinD,2024-09-24] !
I first had a dynamic programming approach and got TL. Then I tried to work with binary search. I used a constructive algorithm inside the search to check for the validity of the current value. My solution got AC but I wasn't convinced by the correction and I wanted to understand in depth.<br>
This blog explains my solution and brings a comprehensive proof. I'll first describe my algorithm and intuition, and then go through the proof.
# Statement
Your are given an array $a_1,a_2,…,a_n$ of the length n
You can perform any number (possibly, zero) of operations on the array.
In one operation, we choose a position $i (1 \leq i \leq n-1)$ and per...
criterion, so $beta$ is still the largest minimum possible.
It is possible to search for $alpha$ and, enough in a[1]. This writes as : $a[1] \geq beta$ and $a[2] + (a[1] - beta)
\geqbeta$, which is, obtainable (denoted $beta$) can be found with binary search in
$\mathcal{O}(n*log(n))$. Then I bring the, # III — Formal proof of $alpha$-$beta$, $$(H_k) : (\forall i, 1 \leq i \leq k, \sum_{j=1}^{j=i}{a[j]} \geq i * beta)
\iff (beta=min_{i \in, $(H_1)$ : after one step, $a^{(k)}[1]$ was either set to $alpha \geq beta$ or
kept as $a[1] \geq, $[A \Leftarrow B]$ Suppose the right part of $(H_{k+1})$. If
$\sum_{j=1}^{j=k+1}a[j] < (k+1)*beta, $\sum_{j=1}^{j=k+1}{a[j]} \geq (k+1)*beta \iff \sum_{j=1}^{j=k+1}{a[j]} - k*beta
\geqbeta \iff, - The columns $1$ to $i$ can be rearranged using the operation to be all
greater than $beta$.
, At the end of the loop, $beta$ is an admissible minorant iff the first column
is greater or equal, By induction, $\sum_{j=1}^{j=k}a^{(k)}[j] \geq k*beta$ and $a^{(k+1)}[k+1] =
alpha \geqbeta$,, For $i=n$ to $i=2$, if $a[i] < beta$:
- $a[i] := beta$
- $a[i-1] := a[i-1] - (beta - a[i])$, For a value $beta$ to be an admissible minimum of $\tilde{a}$ is equivalent to
this statement, Previous parts showed that we can find $alpha$ and $beta$ with a constructive
algorithm starting, The intuition is then that we can apply the $alpha$-algorithm and then the $beta
$-algorithm to get, ], ..., a[k]$ to be larger than $beta$. If $a[k+1] \geq beta$, the right part
of $(H_{k+1})$ is true, cout << alpha - beta << endl; } } ~~~~~, if(valid) low = beta; else high = beta; } beta = low;, low = mn; high = mx; while(low+1 < high) { beta = (low + high) / 2
Tutorial of Codeforces Round 973 (Div. 2)
55.
Codeforces Beta Round #17 Tutorial <a href="http://codeforces.me/blog/entry/447">Contest discussion</a><br><b><br>Problem A. Noldbach problem<br><br></b>To solve this problem you were to find prime numbers in range $[2..N]$. The constraints were pretty small, so you could do that in any way - using the Sieve of Eratosthenes or simply looping over all possible divisors of a number.<br>Take every pair of neighboring prime numbers and check if their sum increased by $1$ is a prime number too. Count the number of these pairs, compare it to $K$ and output the result.<br><br><b>Problem B. Hierarchy</b><br>[cut]<br>Note that if employee, except one, has exactly one supervisor, then our hierarchy will be tree-like for sure.<br>For each employee consider all applications in which he appears as a subordinate. If for more than one employee there are no such applications at all, it's obvious that $-1$ is the answer. In other case, for each employee find such an application with minimal cost and add these costs to get the answer.<br...
Codeforces Beta Round #17 Tutorial, Разбор задач Codeforces Beta Round #17
Tutorial of Codeforces Beta Round 17
56.
Codeforces Beta Round #13 <div>Приветствую всех на Codeforces Beta Round #13, который состоится в четверг, 6 мая в 18:00 по московскому времени. Автором задач этого контеста буду я. </div><div>Хочется сказать отдельное спасибо <a href="http://codeforces.me/profile/MikeMirzayanov">Михаилу Мирзаянову</a>, который сделал проведение контеста возможным, <a href="http://codeforces.me/profile/Shtrix">Роману Едемскому</a> и <a href="http://codeforces.me/profile/maksay">Андрею Максаю</a> за помощь в тестировании авторских решений, а так же <a href="http://codeforces.me/profile/Nerevar">Дмитрию Матову</a> за перевод условий на английский язык. Надеюсь, задачи вам понравятся.</div><div><br></div><div>Желаю чтобы число 13 оказалось для вас счастливым!<br></div><div><br></div><div><div><b>UPD: </b>Поздравляю <a href="http://codeforces.me/profile/ivan.metelsky">Ивана Метельского</a>, который стал победителем решив все 5 задач!</div><div>Задачи можно посмотреть <a href="http://codeforces.me/contest...
Codeforces Beta Round #13
Announcement of Codeforces Beta Round 13
57.
Beta Round #4 — csacademy.com Hello, Codeforces!
We are happy to announce that we're going to host a new contest at [csacademy.com](http://csacademy.com). Once again we'd like to thank all our users for the great feedback they provide. We try to listen to your advice and improve our platform with each competition.
Our [Beta Round #4](https://csacademy.com/contest/beta-round-4/) will take place on [Tuesday, Apr/26/2016 16:00 (UTC)](http://www.timeanddate.com/worldclock/fixedtime.html?msg=CSAcademy+Beta+Round+4&iso=20160426T16&p1=1440&ah=2). If you want to take part in this round you need to [register](https://csacademy.com/contest/beta-round-4/) before the contest begins. You can access the chat room for this round [here](https://csacademy.com/contest/beta-round-4/#chat) (login required). Initially we were planning on having two divisions starting with this round. After taking a closer look at the rankings we decided it's too early to separate our users. So this round will be a Div1 + Div2, with 3 easy tasks a...
Beta Round #4 — csacademy.com, [Beta Round #4](https://csacademy.com/contest/beta-round-4/) will take place
on [Tuesday, Apr/26/2016, #### Platform changes since Beta Round #3:, **EDIT**: The [editorial](https://csacademy.com/blog/2016/04/26/beta-round-4/)
is ready, Our [Beta Round #4](https://csacademy.com/contest/beta-round-4/) will take
place on [Tuesday, Apr
58.
Rockethon 2015 Editorial (This is a beta version of editorial. It will be changed later)
I hope everybody enjoyed the contest. Here we'll present some of the author's solutions to the problems together with some other approaches that we came up with. The editorial is prepared by Lasha Lakirbaia, Anton Lomonos, and Ievgen Soboliev.
A — Game
==================
(developed by Ievgen Soboliev & Eldar Bogdanov, editorial written by Lasha Lakirbaia)
The problem can be solved with dynamic programming technique. Let $winner[a][b][move]$ denote who wins if both players play optimally and the first has a balls left in his box, the second has $b$ balls left in his box and move defines who is to move next. To determine the value of $winner[a][b][move]$, we should consider all the possible moves the next player can make and see whether any of them lead into the position $winner[x][y][move2]$ in which this player can win with optimal play. Thus, values of winner can be defined recursively.
Ok it was a jok...
(This is a beta version of editorial. It will be changed later)
59.
Beta Round #8 — csacademy.com Hello, Codeforces!
We are happy to announce that we're going to host a new contest at [csacademy.com](http://csacademy.com). Our [Beta Round #8](https://csacademy.com/contest/beta-round-8/) will take place on [Saturday, July/02/2016 16:00 (UTC)](http://www.timeanddate.com/worldclock/fixedtime.html?msg=CS+Academy+Beta+Round+%238&iso=20160702T16&p1=1440&ah=2). If you want to take part in this round you need to [register](https://csacademy.com/contest/beta-round-8/) before the contest begins. Just like the [previous rounds](https://csacademy.com/contests/), this will be a Div1 + Div2. Due to the feedback we've got during the past couple of weeks we decided to change the format, by adding an extra easy problem. So this round will consist of **7** tasks of varied difficulty.
#### Platform changes since Beta Round #7:
- We redesigned the homepage. It now includes a global chat, latest blog entries, future contests and top leaderboard.
- We launched a new lessons section:
1. [Intro...
Beta Round #8 — csacademy.com, [csacademy.com](http://csacademy.com). Our [Beta Round
#8](https://csacademy.com/contest/beta-round-8/) will, [Бета раунд #8](https://csacademy.com/contest/beta-round-8/) пройдёт в
[Субботу, 02.07.2016 в 12:00, #### Platform changes since Beta Round #7:, ://csacademy.com). Our [Beta Round #8](https://csacademy.com/contest/beta
-round-8/) will take place on [Saturday, ://csacademy.com/blog/#beta-round-8) has been published.
60.
Beta Round #3 — csacademy.com Hello, Codeforces!
We are happy to announce that we're going to host a new contest at [csacademy.com](http://csacademy.com). There were plenty of users who helped us by providing lots of feedback after the last round. We'd like to help everybody for their support :)
Our [Beta Round #3](https://csacademy.com/contest/beta-round-3/) will take place on [Tuesday, Mar/22/2016 17:00 (UTC)](http://www.timeanddate.com/worldclock/fixedtime.html?msg=Beta+Round+%233&iso=20160322T17&p1=1440&ah=2). If you want to take part in this round you need to [register](https://csacademy.com/contest/beta-round-3/) before the contest begins. Just like the previous round, the difficulty will be moderate (similar to a Codeforces Div. 2)
#### Contest format:
- You will have to solve **5** tasks in **2** hours.
- There will be full feedback throughout the entire contest.
- Tasks will not have partial scoring, so you need to pass all test cases for a solution to count (ACM-ICPC-style).
- Tasks will ha...
Beta Round #3 — csacademy.com, after the last round. We'd like to help everybody for their support :) Our [
Beta Round #3](https, #### Platform changes since Beta Round #2:, **EDIT**: The [editorial](https://csacademy.com/blog/2016/03/22/beta-round-3/)
is ready, ://csacademy.com/contest/beta-round-3/) ;), Our [Beta Round #3](https://csacademy.com/contest/beta-round-3/) will take
place on [Tuesday, Mar, Наш [бета-раунд #3](https://csacademy.com/contest/beta-round-3/) состоится во
[вторник, 22.03.2016
61.
Codeforces Beta Round #98 (Div. 2) <p>Всем привет!!!</p> <p>Осталось меньше 11 часов до начала Codeforces Beta Round #98 (Div. 2). Этот раунд для вас подготовил я, идеи задач мне подкинул [[user:MikeMirzayanov,2011-12-15]]. По традиции [[user:RAD,2011-12-15]] проследил за тем, чтобы я не посадил багов и написал нормальные условия, а [[user:Delinur,2011-12-15]] перевела условия на английский язык. За что им всем спасибо!</p> <p>Если вы решите поучаствовать в раунде вам придётся помочь мальчику Поликарпу и его однокласснику Иннокентию во всех трудностях с которыми они сталкиваются. Чем лучше вы им поможете, тем более высокое место займёте.</p> <p>Надеюсь задачи окажутся интересными не только участникам из Div. 2, но и участникам с рейтингом больше 1699.</p> <p>Продолжу небольшое повествование о себе (начало в предыдущей записи в блоге). Кроме программирования я очень люблю спорт. В течении нескольких лет до того как я начал писать код, я достаточно серьёзно занимался академической греблей. А до этого я занимался практичес...
Codeforces Beta Round #98 (Div. 2)
Announcement of Codeforces Beta Round 98 (Div. 2)
62.
Editorial — Mathmania, Codefest' 18 ### Shooting Game
Let $P_{A}$ and $P_{B}$ be the probability of Alice and Bob hitting the target respectively. Then the chances of Alice winning the game are:
<br></br>
<br></br>
<center> $P_{A} + (1-P_{A})(1-P_{B})P_{A} + (1-P_{A})^{2}(1-P_{B})^{2}P_{A} + ...$ </center>
which equals $\frac{P_{A}}{1-(1-P_{A})(1-P_{B})}$ using GP formula.
Similarly, for Bob it would be $\frac{(1-P_{A})P_{B}}{1-(1-P_{A})(1-P_{B})}$.
Equating both we get, $P_{B} = \frac{P_{A}}{1-P_{A}}$. Return -1 in case you get $P_{B}$ greater than 1.
### SolveForTrisha
Let $x$ be an $n^{th}$ root of unity. Then, $x^{n} = 1$. So, $x^{n}-1 = 0 $ has roots $1,\alpha_{1},\alpha_{2} . . . . \alpha_{n-1}$.
We can write this as follows :
<br></br>
<br></br>
<center> $\frac{(x^{n}-1)}{(x-1)} = (x-\alpha_{1})(x-\alpha_{2})(x-\alpha_{3}) . . . . (x-\alpha_{n-1}) $ </center>
Placing $x = 1,-1$ in the above equation and multiplying them, one can get the desired result.
<br></br>
If $n$ is even the expres...
Let $\alpha = cm+\frac{em(m+1)}{2} $ and $\beta = \frac{dm(m+1)}{2}+fm$.
63.
Russian AI Cup 2017 — CodeWars Hey everyone!
Good news — Russian AI Cup 2017 has started! This competition is being held for the sixth time, and this time, hopefully, we will make happy all the fans of the RTS game genre — you will be controlling 500 vehicles of 5 different types at once. The task is to destroy the opponent!
Try yourself in creating an artificial intelligence, it's simple and fun. Go to [Russian AI Cup site](http://russianaicup.ru) and enter the battle. Good luck!
[cut]
### What is it?
**Russian AI Cup** — largest annual artificial intelligence programming contest in Russia, and third open competition for talented IT-specialists that is part of Mail.Ru Group strategy of forming and developing competitive Russian IT-industry on a global scale.
Following programming languages are supported: C++, C#, Java, Pascal, Python 2, Python 3 и Ruby. Anyway, as previously, we are ...
fourth weeks will be beta-testing weeks, this time it is possible that the
system is unstable, and
64.
Codeforces Round 986 (Div. 2) Hello Codeforces!
-----------------
I am glad to invite you to [contest:2028], which will start on [contest_time:2028]. **Note the slightly unusual start time.**
The contest will run for 2 hours and have 6 tasks. The contest will only be rated for those with a rating not higher than 2099, but we welcome higher rated users to participate out of competition.
Holding the contest would have been impossible without:
- [user:flamestorm,2024-11-09] for insanely excellent coordination, without whom this round would certainly not happen.
- [user:Vince729,2024-11-09] and [user:swagchicken,2024-11-09] for lots of discussions about the problems and proposing other problem ideas :)
- [user:conqueror_of_tourist,2024-11-09], [user:BucketPotato,2024-11-09], [user:Dominater069,2024-11-09], [user:sstrong,2024-11-09], [user:triple__a,2024-11-09], [user:xiaowuc1,2024-11-09], [user:lucasxia01,2024-11-09], [user:n0sk1ll,2024-11-09], [user:nikilrselvam,2024-11-09], [user:thanhchauns2,2024-11-0...
1. [user:SUPERLWR-beta,2024-11-10] 2. [user:mychecksdead,2024-11-10] 3.
[user:sweet_dream,2024-11
Announcement of Codeforces Round 986 (Div. 2)
65.
Beta Round #6 — csacademy.com Hello, Codeforces!
We are happy to announce that we're going to host a new contest at [csacademy.com](http://csacademy.com). Our [Beta Round #6](https://csacademy.com/contest/beta-round-6/) will take place on [Tuesday, May/31/2016 16:00 (UTC)](http://www.timeanddate.com/worldclock/fixedtime.html?msg=CS+Academy+Beta+Round+6&iso=20160531T16&p1=%3A&ah=2). If you want to take part in this round you need to [register](https://csacademy.com/contest/beta-round-6/) before the contest begins. Just like the [previous two rounds](https://csacademy.com/contests/), this will be a Div1 + Div2, with 6 tasks of varied difficulty.
#### Platform changes since Beta Round #5:
- We added virtual contests. Now you can simulate a past round easily with a single click in the [contests page](https://csacademy.com/contests/).
- Contestants source code is now public. Go to any scoreboard and click on a check mark.
- The online editor now support an "Open file" button. No more copy paste when trying to...
Beta Round #6 — csacademy.com, [csacademy.com](http://csacademy.com). Our [Beta Round
#6](https://csacademy.com/contest/beta-round-6/) will, #### Platform changes since Beta Round #5:, ://csacademy.com). Our [Beta Round #6](https://csacademy.com/contest/beta
-round-6/) will take place on [Tuesday, ://csacademy.com). Наш бета [раунд #6](https://csacademy.com/contest/beta
-round-6/) состоится во, ://csacademy.com/blog/#beta-round-6) has been published.
66.
Codeforces achievements Hi!
I'd like to introduce my project to Codeforces community. My project's name is 'Codeforces achievements' and as you can probably guess it is about achievements! Your achievements on Codeforces site. For those who do not like my long posts I should mention that the link to the site is at the end of this post.
Introduction
==================
Last summer I left my last job, so I have quite a lot of spare time which I could invest in my hobby. Also I decided to learn something more or less new for me (for last several years my job was to write desktop software for Windows), so I decided to put my hands on some modern popular web-framework. At that point I chosen Python and Django, cause it was matching one position I applied. So I had a time and I wanted to learn Django. The best way to learn something is to practice in it, so I started looking for the idea for the site to create (didn't want to write yet another forum engine). Luckily at that point I ran into [user:I_love_...
I should say that the project is in the beta stage at the moment, there is a
lot to be done, I just
67.
[AtCoder] Unofficial HHKB Programming Contest 2020 Editorial ### [A – Keyboard](https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_a)
<spoiler>
Basically, just do what it says in the problem statement. The function to turn a character uppercase is `std::toupper(t)` in C++, `Character.toUpperCase(t)` in Java, `t.toUpperCase()` in Kotlin, or `t.upper()` in Python.
</spoiler>
### [B – Futon](https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_b)
<spoiler>
Iterate through every row and column. If the current square is `.`, look at the neighbor to the right, if it's also `.`, increment the answer. Likewise the neighbor downward. There is no need to look leftward or upward as those positions would already have been counted.
</spoiler>
### [C – Neq Min](https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_c)
<spoiler>
Initiate an array of booleans indexed over $[0, 1 + \max p]$. Maintain a pointer $j$ starting at index $0$.
Iterate through $p$. In each iteration, mark the corresponding index as "true", then use ...
Let $\alpha := N - A + 1$ and $\beta := N - B + 1$. It can be noted that,
disregarding overlaps
68.
1 In this blog we prove a Ramanujan-type identity:
$S(n_1, n_2, n_3) := \sum\limits_{n_1 \in \mathbb{Z}}(-1)^{n_1}\sum\limits_{(n_2, n_3) \in \mathbb{Z}^2}\frac{1}{\sqrt{n_1^2 + (n_2+0.5)^2+(n_3+0.5)^2}\sinh{(\pi\sqrt{n_1^2 + (n_2+0.5)^2+(n_3+0.5)^2})}} = 1$. (1)
<spoiler summary="Magic code">
~~~~~
from math import *
ans = 0
for n1 in range(-100, 101):
ans1 = 0
for n2 in range(-100, 101):
for n3 in range(-100, 101):
p = n1**2 + (n2+0.5)**2 + (n3+0.5)**2
q = sqrt(p)
r = sinh(pi*q)
ans1 += 1/(q*r)
print(ans1, n1)
ans += (1 if n1%2==0 else -1) * ans1
print(ans)
~~~~~
</spoiler>
First, we consider a 4D [lattice sum](https://mathworld.wolfram.com/LatticeSum.html):
$U(n_1, n_2, n_3, n_4) := \sum\limits_{(n_1, n_2, n_3, n_4) \in \mathbb{Z}^4} \frac{(-1)^{n_1+n_4}}{n_1^2 + (n_2+0.5)^2 + (n_3+0.5)^2 + n_4^2}$. We will show later that $U(n_1, n_2, n_3, n_4)$ equals to $\pi$ (code shown belo...
checking Table 1 in the paper, $U(n_1, n_2, n_3, n_4) = 8\beta(0)\beta(1)$,
where $\beta(s) := \sum
69.
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 ...
That's it, see you at Codeforces Beta Round#1.
,
Вроде все, до встречи на Codeforces Beta Round #1.
70.
A little bit of classics: dynamic programming over subsets and paths in graphs <i>Author thanks </i><a href="../../../profile/adamax" title="Капитан adamax" class="rated-user user-yellow">adamax</a><i> <span class="short_text" id="result_box"><span style="" title="">for translation this article into English.</span></span></i><br><br><b>Introduction</b><br>After <a href="http://codeforces.me/blog/entry/331">Codeforces Beta Round #11</a> several participants expressed a wish to read something about problems similar to <a href="http://codeforces.me/contest/11/problem/D">problem D</a> of that round. The author of this article, for the purpose of helping them, tried searching for such information, but to his surprise couldn't find anything on the Internet. It is not known whether the search was not thorough or there's really nothing out there, but (just in case) the author decided to write his own article on this topic.<br><br>In some sense this article may be regarded as a tutorial for the <a href="http://codeforces.me/contest/11/problem/D">problem D</a> from Beta R...
/contest/11/problem/D">problem D from Beta Round #11.
71.
Beta Round #5 — csacademy.com Hello, Codeforces!
We are happy to announce that we're going to host a new contest at [csacademy.com](http://csacademy.com). From now on we're going to have a competition every two weeks, so here we go:
[Beta Round #5](https://csacademy.com/contest/beta-round-5/) will take place on [Monday, May/09/2016 16:00 (UTC)](http://www.timeanddate.com/worldclock/fixedtime.html?msg=CSAcademy+Beta+Round+5&iso=20160509T16&p1=1440&ah=2). If you want to take part in this round you need to [register](https://csacademy.com/contest/beta-round-5/) before the contest begins. Just like the [previous round](https://csacademy.com/contest/beta-round-4/), this will be a Div1 + Div2, with 6 tasks of varied difficulty.
#### Platform changes since Beta Round #4:
- **IMPORTANT:** When the contest starts the page will automatically load the tasks and open the first problem for you. Please don't refresh the page, as this will probably overload the server.
- We fixed the editor buttons bug. Now you can s...
Beta Round #5 — csacademy.com, #### Platform changes since Beta Round #4:, **EDIT**: The [editorial](https://csacademy.com/blog/2016/05/09/beta-round-5/)
is ready, [Beta Round #5](https://csacademy.com/contest/beta-round-5/) will take place on
[Monday, May/09
72.
Checklist for OI problems **Update 2018.11.01**: [user:Rezwan.Arefin01,2018-11-01] made a very cool webapp which contains identical problemset, but with more usability. Thank you very much! [You can check it here.](http://codeforces.me/blog/entry/62898#comment-468763)
**Note: There was some updates in 2018.10.05.** See [here](https://codeforces.me/blog/entry/59422?#comment-462081) for changes!
Hello! APIO 2018 is near the end, and IOI 2018 is in this September. I hope you are preparing it well!
I'm here to present my OI problem checklist :
I used this to train myself in IOI 2015~2016, and to train Korean IOI 2017 Team (probably 2018 too). For long it was in the "beta" phase, but I think it's now good enough to share!
This problemset contains about 300 ~ 400 hard and interesting problems, with appropriate judge links given. (If there is problem in judging, maybe [user:ojuz,2018-05-12] can help that..)
[Google Docs Link](https://docs.goog...
). For long it was in the "beta" phase, but I think it's now good enough to
share!
73.
Школьная индивидуальная олимпиада #3 (ЗКШ 2010/11) - Codeforces Beta Round #45 (ACM-ICPC Rules): разбор задач <b>Задачи A и B</b> не представляли идейной сложности, поэтому начнем сразу с C.<br><br><b>Задача C</b><br><br>Положим $\beta = \alpha / 10$. Тогда заданные числа - это $a_1 = [\beta]$, $a_2 = [2 \beta]$, $a_3 = [3 \beta]$, ... $a_n = [n \beta]$ и нужно определить $[(n + 1) \beta]$ ([x] - целая часть числа). Данные равенства эквивалентны системе неравеств: $a_n \le n \beta < a_n + 1$, $n = \overline{1, n}$. Выбирая максимум по левым частям и минимум по правым, получим неравество вида $A \le n < B$. Теперь осталось сравнить целую часть числа $A / (n + 1)$ и $B / (n + 1)$. В случае если B поделилось нацело, нужно вычесть из правой части единичку, т.к. справа неравенство строгое.<br><br><b>Задача D</b><br><br>Создадим векторы $v_i$, в первый из которых $v_1$ будем складывать позиции единичек, в $v_2$ - двоек, в $v_3$ - троек, и т.д. Их можно заполнить за один проход по данной последовательности. Количество перестановок - это количество единичек, или размер первого вектора. Мысленно ...
School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta
Round #45 (ACM-ICPC, Школьная индивидуальная олимпиада #3 (ЗКШ 2010/11) - Codeforces Beta Round #45
(ACM-ICPC Rules,
Problem C
Put $\beta = \alpha / 10$. Then the given numbers are $a_1, Положим $\beta = \alpha / 10$. Тогда заданные числа - это $a_1 = [\beta]$, $a_2
= [2 \beta]$, $a_3
74.
Online judge with IOI problem went public Hello everyone.
Two years ago there was a post titled "Submitting IOI problems" and [my comment](/blog/entry/10967#comment-161620) there. I offered everyone to contact me via PM on Codeforces to get the access and be able to solve problems from past IOIs (starting with IOI 2003). What was important here is that [user:PavelKunyavskiy,2016-06-12] and me took effort and made the system as similar to what was used on particular IOI as we could, including:
1. Original tests from archives
2. Tests grouping and correct subtasks scoring where applicable — you won't get 54 points if there are subtasks for 40 and 60 points — just like on IOI.
3. Interactive problems with interactive I/O (say, "Aliens" from IOI 2007 or "Maintain" from IOI 2003)
4. Partial scoring where you can get only a fraction of points per test, like "Reverse" from IOI 2003 or "Hotter Colder" from IOI 2010.
5. "Encode-decode" problems, where your solution is executed several times in separate processes, ...
Unfortunately, it's still a beta version and there are still some issues: no
problem statements are
75.
Original Gym contest: Geometry Special 2018 Hi Codeforces,
As I mentioned before, as part of my Master's thesis, besides my [book](https://vlecomte.github.io/cp-geo.pdf) I am organizing a contest with exclusively geometry problems to showcase some types of problems or techniques that I think could be cool to see in the future in ICPC and other contests.
It will take place this Sunday 08:00 UTC in the Gym (the link will be [http://codeforces.me/gym/101793](http://codeforces.me/gym/101793), registration should open 6h before and remain open during the contest). There will be 4 problems to solve in 3 hours.
The problem should be particularly relevant for students participating to the ICPC. But the problems will be _very hard_, so I think they can be interesting to everyone with a sufficient level in geometry.
The problems will be roughly sorted by estimated difficulty, but please read all the problems, as you might find that you feel more interested by one of the "harder" problems. The statements will be given all tog...
his amazing support during my whole thesis), [user:Nicolas16,2018-05-05] for
beta-testing the
76.
Beta Round #7 — csacademy.com Hello, Codeforces!
We are happy to announce that we're going to host a new contest at [csacademy.com](http://csacademy.com). Our [Beta Round #7](https://csacademy.com/contest/beta-round-7/) will take place on [Sunday, June/12/2016 09:00 (UTC)](http://www.timeanddate.com/worldclock/fixedtime.html?msg=CS+Academy+Beta+Round+7&iso=20160612T09&p1=%3A&ah=2). If you want to take part in this round you need to [register](https://csacademy.com/contest/beta-round-7/) before the contest begins. Just like the [previous rounds](https://csacademy.com/contests/), this will be a Div1 + Div2, with 6 tasks of varied difficulty.
#### Platform changes since Beta Round #6:
- We added a new comment section/task.
- We added a new editorial section/task.
- We started working on rewriting the editorials and also adding official implementations to the articles.
#### Contest format:
- You will have to solve **6** tasks in **2** hours.
- There will be full feedback throughout the entire contest....
Beta Round #7 — csacademy.com, #### Platform changes since Beta Round #6:, ). Наш [бета раунд #7](https://csacademy.com/contest/beta-round-7/) состоится в
воскресенье, [12.06.2016, ://csacademy.com). Our [Beta Round #7](https://csacademy.com/contest/beta
-round-7/) will take place on [Sunday, ://csacademy.com/blog/#beta-round-7) has been published.
77.
rating-Aware problem recommender _Hi, I'm AmirMohammad (commonly known as **Danet**). Naturally, as a non-native speaker, the translation and editing process involved some assistance and **AI**. If you spot any technical or linguistic errors, I would be grateful if you pointed them out!_
#### personalized problem suggestions using reference sets
In competitive programming, one of the most common hurdles is selecting the right problems to practice. Standard random generators often suggest problems that are either too trivial or completely out of your league.
To solve this, we have been developing **@Lemiown_Bot**, a Telegram bot designed to suggest Codeforces problems precisely tailored to your current rating and learned topics. While standard bots pick uniformly from a rating range, our approach uses a **Reference Set** of high-rated users to ensure the quality and relevance of the suggested problems.
---
**The Reference Set ($S$):**
...
**Beta Testing**
78.
Kouprin Challenge: Best interview problem for a software developer Hello everyone! There is a challenge. :)
In short, here’s what you need to do:
1. Build [DevilutionX](https://github.com/diasurgical/DevilutionX) — a cross-platform port of Diablo 1 + Hellfire — and learn how to run it (you’ll need an original copy of the game for this).
2. Create a multiplayer Hellfire character and get familiar with the game.
3. Start timing from the moment you open the source code: you need to figure out how to obtain several rings called Obsidian Ring of the Zodiac.
4. Verify that these rings are valid in the vanilla build, do not mutate, do not disappear, and do not crash the client.
5. You may not use AI.
In terms of format, this task would be similar to a problem at Challenge24 finals. But I consider it the best interview problem for a software engineer that I’ve known in the last 10 years: it tests your ability to quickly understand an unfamiliar codebase, come up with an optimal solution, and implement it.
The full version of the task descripti...
ideas, solutions, and beta testing. Thanks to the guys working on DevilutionX
— though I don’t
79.
[Educational] Combinatorics Study Notes (3) Hello Codeforces!
Today I'll be writing about what I have learnt about combinatorics, which played, and, in my opinion, will still be playing an important role in both Codeforces and CP (short for competitive programming).
However, combinatorics is such a great subject that made that impossible for me to write it all in one blog. So, this is just the third blog, which is friendly to beginners. If you are interested, please, pay attention to this account and I'll give posts as series for a long term.
If you have found some mistakes in the text, or if you have some questions about the topic, please, leave a comment, and I'll check it weekly and reply. Also, if you find some grammar mistakes, a kind comment will be also welcomed.
### Previous Blogs
- [Combinatorics (1)](https://codeforces.me/blog/entry/110376)
- [Combinatorics (2)](https://codeforces.me/blog/entry/110390)
### Content
1. [Homework]((https://codeforces.me/blog/entry/110390)) Tutorial
2. Catalan Seq...
$$G(x)=\dfrac{P(x)}{(1-\alpha x)(1-\beta x)}=\dfrac{A}{1-\alpha x}+\dfrac{B}{1-\
beta x}$$, $$a_n=A\alpha^n+B\beta^n$$, $F_0=A+B=0,F_1=A\alpha+B\beta=1.$, $a_0=A+B=1,a_1=A\alpha+B\beta=1.$, So $F_n=\dfrac{\alpha^n-\beta^n}{\sqrt5}$., Solution: $\alpha=\dfrac 12+\dfrac{\sqrt3i}{2},\beta=\dfrac
12-\dfrac{\sqrt3i}{2}$.
80.
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>
: Table1 updated : in Future!!!
<br /><br /><b>UPD </b> : Table2 updated :
CF # 118 ...to... CF # 169
added .<br /><br />
</p><hr /><br /></p>
<div align="justify">
<br /><br /><b><s...
">
# A , B
<http://daedalusinfinity.blogspot.com/2010/06/codeforces-<B>beta</B>-round-16.html>
81.
Codeforces FAQ (unofficial) (This FAQ may be outdated. Please refer to official <a href="http://codeforces.me/help">help</a>).<br><br>
I'm sure we won't need this post after Codeforces comes out of beta,
but meanwhile it could be useful :) Feel free to suggest what should be
added here.<br>
<br><h3 align="center"><b>Competitions: general</b></h3><span class="comment-content-22873"><b>Q.</b> What are the rules of these contests?<div><b>A.</b> Read <a href="http://codeforces.me/blog/entry/456">this</a>.</div></span><br><div><b>Q. </b>What languages are supported? What are the compiler options and run command lines? What is the configuration of judge servers?<br>
</div><b>A.</b> <span class="comment-content-11692">The judge machines are Core 2 Duo, 2.67 Ghz (E6750). </span>The full list of supported languages and compiler options can be found in <a href="../79">this post</a><br><br><b>Q.</b> How do I hack other's solutions?<br><b>A.</b> First lock
your own solution in the main ('problems') tab. Then in you...
I'm sure we won't need this post after Codeforces comes out of beta, but
meanwhile it could be
82.
CHelper3.0beta13 **UPD5:** обновите плагин! Формат Codeforces несколько изменился
**UPD4:** новая версия:
TopCoder fix for UNIX
RCC support
Better non-English characters support
**UPD3:** новая версия:
TopCoder alternative protocol
Force locale setting to include Locale.setDefault(Locale.US) in generated file
**UPD2:** в ближайшее время новые бета версии будут распространятся только через plugin repository. При перезапуске Idea, насколько я знаю, плагины обновляются автоматически. Если это по какой-то причине не работает можно скачать свежую версию плагина [здесь](http://plugins.intellij.net/plugin?pr=idea&pluginId=7091). Поставить можно либо старым способом (копированием в папку config/plugins), либо Settings -> Plugins -> Install plugin from disk...
Внимание! Это beta версия, которую не очень много тестировали. Используйте на свой страх и риск!
Скачать можно [здесь](http://code.google.com/p/idea-chelper/downloads/detail?name=chelper3.0beta2.jar) **updated**
Основные и...
Внимание! Это beta версия, которую не очень много тестировали. Используйте на
свой страх и риск!
83.
AI Cup 2019 Hello everyone!
Mail.Ru Group announces start of the annual artificial intelligence programming championship — [AI Cup 2019](https://russianaicup.ru/).
AI Cup — open artificial intelligence programming contest. Test yourself writing a game strategy! It’s simple, clear and fun!
This year's theme is — platformer. We are waiting for you on [our site](https://russianaicup.ru/)! The site is already open, you can start implementing your strategies.
Eighth AI Cup championship is named CodeSide. You are to program an artificial intelligence to control a team of units. Your strategies will compete with each other in the Sandbox and the championship. Currently availiable programming languages: C++, C#, F#, D, Go, Java, Kotlin, Scala, Python, Ruby, Rust. The Sandbox is already open. Good luck!
Currently the championship is in beta-test mode, and on December 7th Sandbox will start working officially!
 — a diverse roster of high-quality programming competitions by Department of Computer Science and Engineering, IIT Varanasi is excited to present **Mathmania**.
Mathmania is a mathematical puzzle contest where a sound knowledge of mathematics together with computational thinking will be essential to solve problems. The motivation behind Mathmania is to provide a platform for the inquiring mind to dwelve into unfamiliar areas and learn new concepts in an exciting way.
The contest will take place at **Topcoder**. This contest will be an individual event with a duration of 3 hours, from [Sep/1/2018 12:30 UTC](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Mathmania+-+Codefest%2718&iso=20180901T18&p1=1045&ah=3). The contest will be **unrated** for both Div1 and Div2 participants but will be a long match which will consist of interesting mathematical challenges covering almost all domains of Mathematics, rang...
Go to Topcoder Arena – arena.topcoder.com(Beta) or setup Topcoder Java Applet*,
you will be able to
85.
About Solving Simple Recursions **Summary: This blog talks about solving two kinds of simple recursions: $F(n+1)=aF(n)+b$ and $F(n+1)=aF(n)+bF(n-1)$**
###### 1. Preliminary Knowledge
(1) The solution of recursion $F(n+1)=aF(n)$ is $F(n)=a^{n-1}F(1)$.
(2) The solution of recursion $F(n+1)=F(n)+a$ is $F(n)=(n-1)a+F(1)$.
(3) The recursion $F(n+1)=kF(n)$ is the same as $F(n)=kF(n-1)$, also $F(n+1)=aF(n)+bF(n-1)$ is the same as $F(n)=aF(n-1)+bF(n-2)$ in this blog.
###### 2. Solving $F(n+1)=aF(n)+b$, $a, b$ are constants, $a>1$
**The main idea is to create another function G(n) that satisfy $G(n)=kG(n-1)$ with constant k, solve G(n), and then solve F(n).**
$F(n+1)=aF(n)+b$
$F(n+1)=aF(n)+\frac{ab-b}{a-1}$
$F(n+1)=a(F(n)+\frac{b}{a-1})-\frac{b}{a-1}$
$F(n+1)+\frac{b}{a-1}=a(F(n)+\frac{b}{a-1})$
Let $G(n)=F(n)+\frac{b}{a-1}$ we have
$G(n)=aG(n-1)$
$G(n)=a^{n-1}G(1)$
$F(n)+\frac{b}{a-1}=a^{n-1}(F(1)+\frac{b}{a-1})$
$F(n)=a^{n-1}(F(1)+\frac{b}{a-1})-\frac{b}{a-1}$
###### 3. Solving $F...
$F(n)=\frac{\alpha^{n-1}(F(2)-\beta F(1))-\beta^{n-1}(F(2)-\alpha
F(1))}{\alpha-\beta}$, Let $\alpha, \beta$ be two real numbers that satisfy $\alpha+\beta=a, \alpha\
beta=-b, \alpha\le
86.
What is Codeforces? <div>
<img src="http://codeforces.me/cache/images/codeforces-logo.png" style="float: left;margin:1em;">
<div>I noticed long ago, that all the websites about computer
programming contests work on Web 1.0 principles. But the 21st
century has come, the 30th International Programming Contest took
place, and Google celebrated its 10th anniversary. Something has to
be done! As Software-as-a-Service is conquering the world, contests
administrators are still copying tests into judge systems. Something
has to be done!</div>
<div>[cut] </div>
<div>Codeforces' aim is to offer you a convenient platform to
organize, run and discuss programming contests. It will be a bit of
a social network website, more than a news portal and more than an
online judge. Being absolutely independent from me, you will be able
to organize and run a contest. You will decide on your own if to
make it open to the whole world or if it will be a contest...
to the end of February I will be able to run the first beta-contests.
87.
Trolling on IZhO (math) At the recent IZhO in mathematics there were unusual problems, many of which trolled the majority of participants.
P2 was solved by a trick, and many failed to find it.
I also did not solve it: during the contest I acted too technically, which did not help. My approach was an attempt to squeeze the desired number between given ones, which is a stronger statement (but, as it turned out, equivalent) that I managed to prove after the contest.
---
**Problem.**
Let $n$ be a positive integer for which there exist positive integers $a$ and $b$ such that
$$
\lfloor a\sqrt{10} \rfloor = n = \lfloor b\sqrt{11} \rfloor.
$$
Prove that there exists a positive integer $c$ such that
$$
n = \left\lfloor c(11\sqrt{10} - 10\sqrt{11}) \right\rfloor.
$$
---
**Official solution**
Denote
$$
\alpha = \sqrt{10}, \quad \beta = \sqrt{11}, \quad
\gamma = 11\sqrt{10} - 10\sqrt{11}.
$$
$$
\gamma = \frac{\sqrt{110}}{\sqrt{10} + \sqrt{11}}
= \frac{1}{\alpha} + \frac{1}{\be...
$$ \frac{b}{n+1} < \frac{1}{\beta} \le \frac{b}{n}. $$, $$ n \le b\beta < n+1 $$
88.
Computing Jordan canonical form # Computing Jordan canonical form
**Definition 1** *root subspace* for $\lambda$ is the subspace satisfying $\lambda$ $\exist k, (\mathcal{A}-\lambda\mathcal{I})^k\alpha=0$
**Lemma 1** The sum of different root subspace is direst sum
*proof*
$f(x)$ is the characteristic polynomial's factor of $\lambda_1$ , $g(x)$ is the remaining part
Now $f(x)$ is annihilator for $W_{\lambda_1}$
because the whole characteristic polynomial is annihilator, but $g(x)$ cannot annihilate $W_{\lambda _1}$ (consider the diagonal of the matrices)
we have $(f(x),g(x))=1$ now we claim that $g(\mathcal{A})$ is invertible. There exist $u(x)g(x)=1 \bmod f(x)$
so $u(\mathcal{A})g(\mathcal{A})=\mathcal{I}$
to prove $W_{\lambda_1}\oplus W_{\lambda_2}\dots\oplus W_{\lambda_t}$ we only need to prove vector $0$ have only one representation.
say $0=u_1+u_2+\dots+u_t$ . applying $g(\mathcal{A})$ to both side yield $g(\mathcal{A})u_1=0$ . Then applying $u(\mathcal{A})$ gives the result. $...
Firstly I thought if $\beta$ is linearly independent with all
$\mathcal{A}\alpha$ , $C(\beta)$ and, now choose in $X_2$ $\beta =$
89.
Рейтинг Codeforces <p class="MsoNormal">Как некоторые уже успели заметить –
на сайте появился рейтинг участников соревнований.
Пока он тоже находится в состоянии beta, но
выглядит вполне адекватным. Вот как он
считается.[cut]</p> Каждый человек характеризуется своим
рейтингом, числом <i style="">
<span style="">R</span></i> . Если у человека <i>A</i>
рейтинг равен <i>R</i>
<sub>
<span>
<i>A</i></span></sub> , а у человека <i>B</i> равен <i>R</i>
<sub>
<span>
<i>B</i></span></sub> , то формула<p class="MsoNormal" style="text-align: center;">
<img src="http://upload.wikimedia.org/math/b/2/b/b2b35a42d6c3a2e0d4f07106d0cb4ef0.png">
<br></p>
<p class="MsoNormal">дает вероятность того, что <i>A</i>
окажется выше <i>B</i> в итоговом рейтинге.
Кстати, здесь все оче...
to Codeforces. For now it is in beta too, but it looks very adequate. Here's
how it is, рейтинг участников соревнований. Пока он тоже находится в состоянии beta, но
90.
Codeforces Beta Round #87 <p></p><div>Welcome to <b>Codeforces Beta Round #87</b>!</div><div><br></div><div><span class="Apple-style-span">The mysterious author of today's match (which turns out to be me) have prepared seven problems for you (five in each division). Since I can't spoil you any of the problems yet, for now I can safely say that I like all of today's problems. The problem statements are wonderfully crafted (and translated) with the help of both </span><span class="Apple-style-span" style="font-family: verdana, arial, sans-serif; font-size: 12px; line-height: 20px; background-color: rgb(255, 255, 255); "><a class="rated-user user-admin" href="http://codeforces.me/profile/RAD" title="Штаб, RAD" style="font-family: arial; text-decoration: none !important; font-weight: bold; color: rgb(0, 0, 204); ">RAD</a></span><span class="Apple-style-span"> and</span><span class="Apple-style-span" style="font-family: verdana, arial, sans-serif; font-size: 12px; line-height: 20px; background-color:...
Codeforces Beta Round #87
Announcement of Codeforces Beta Round 87 (Div. 2 Only)
91.
Codeforces Beta Round #57 (Div. 2) Hello!<br><br>I am glad to invite you to participate in Codeforces Beta Round #57 (Div. 2).<br>Today's Contest was prepared by <a href="http://www.codeforces.com/profile/aryobarzan">Amir Goharshady</a> and <a href="http://www.codeforces.com/profile/LGM">Me</a>.<br><br>We are thankful to <a href="http://www.codeforces.com/profile/MikeMirzayanov">Mike Mirzayanov</a> , <a href="http://www.codeforces.com/profile/RAD">Artem Rakhov</a> , <a href="http://www.codeforces.com/profile/Gerald">Gerald Agapov</a> , <a href="http://www.codeforces.com/profile/mjn">Mohammad Javad Naderi</a> , <a href="http://www.codeforces.com/profile/mr.ilchi">Saeed Ilchi</a> and Maria Belova.<br><br>Today's contest is dedicated to <a href="http://en.wikipedia.org/wiki/Nasir_al-Din_al-Tusi">Khaje Nasir Tusi</a> (Great Persian mathematician) since today is the national day of engineering in Iran.<br><br><div align="center"><img style="width: 136px; height: 199px;" src="http://upload.wikimedia.org/wikipedia/commons/b/b6...
Codeforces Beta Round #57 (Div. 2)
92.
Solving D.TediousLee Using Recurrence in O(log n) **_This Problem was given by [user:DeadlyCritic,2020-06-24]_ as a challenge**
###### Statement:
Given [problem:1369D] solve it for $10^{18}$ without using Matrix Exponentiation.
###### Solution:
In order to maximize the number of Claws, the basic idea is to keep track of $no. of$ $nodes$ with no child at any $k^{th}$ $level$.
So, max no of nodes that can be painted yellow for any $nth$ level is given by:
\begin{equation}\operatorname{sum}=4 *\left(\sum_{i=0}^{\left(\frac{n-2}{3}\right)} a_{((n-2) \% 3+3 i)}\right)\end{equation}
where, $a_{i}=$ no of nodes with no child at $i^{th}$ level
Now in order to get $a_{i}$ we use this recurrence:
\begin{equation}f(x)=2 * f(x-2)+f(x-1)\end{equation}
Linear recurrence like this can be solve using characteristic equation, i will not get into details for the sake of keeping this blog short!
Here is the equation:
\begin{equation}\begin{array}{c}
f(x)-2 * f(x-2)-f(x-1)=0 \\\\
r^{n}-2 * r^{n-2}-r^{n-1}=0 \\\\
r^{n-2}\lef...
Now, \begin{equation}a_{n}=\alpha r_{1}^{n}+\beta r_{2}^{n}\end{equation} is
the general term of
93.
Codeforces Beta Round #99 <p>Hello.<br /><br />Today round is prepared by me. My name is Mikhail Tikhomirov, i am fourth grade student at mech.-math. dep. of MSU, also i work as developer-researcher at Yandex.<br /><br />I want to thank Artem Rakhov ([[user:RAD,2011-12-24]]) for valuable help and thoughtful coordination, Maria Belova ([[user:Delinur,2011-12-24]]) for great-as-always translating statements into English, and also[[user:MikeMirzayanov,2011-12-24]] for letting us all get together today. =)</p><p>Round will be for both divisions. Every division will have five problems as usual, some of them will be the same, some will be not.</p><p>Score distribution:</p><p><b>Div1: 500-1000-2000-2000-2500.</b></p><p><b>Div2: 500-1000-1500-2000-3000.<br /></b></p><p>Today round is the last round in 2011. I want to thank Codeforces team, everyone who invented, prepared or helped in preparing problems this or past years, and those, who help developing the project. Codeforces now is not just a platform for programming ...
Codeforces Beta Round #99
Announcement of Codeforces Beta Round 99 (Div. 1)
Announcement of Codeforces Beta Round 99 (Div. 2)
94.
Codeforces Beta Round #22 (Div. 2) <p>
Welcome all to Codeforces Beta Round #22</p>
<p>
Note that at this time registration is possible during the
round. The contest will begin at 19:00 MSK.
</p>
<p>
Today I am an author of the problems. I would like to thank <a href="http://codeforces.me/profile/MikeMirzayanov">Mike Mirzayanov</a> for help in contest preparations, <a href="http://codeforces.me/profile/homo_sapiens">Edvard Davtyan</a> and <a href="http://codeforces.me/profile/NALP">Nickolay Kuznetsov</a> for writing the verification solutions, and <a href="http://codeforces.me/profile/Julia">Julia Satushina</a> for translating statements into English.
</p>
<p>
Good luck on the contest!
</p>
<p> <b>UPD</b>: The contest is over. Thank you all for participating!<br><a href="http://codeforces.me/contest/22">
Problems</a><br><a href="http://codeforces.me/contest/22/standings">
Results</a><br>
Winner <a href="http://codeforces.me/profile/Kasparyanm_Mihail">Kasparyanm_Mihail</a> gains +203 to rating a...
Codeforces Beta Round #22 (Div. 2), Codeforces Beta Round #22 (Див. 2),
Welcome all to Codeforces Beta Round #22
,
Приветствую всех на Codeforces Beta Round #22
Announcement of Codeforces Beta Round 22 (Div. 2 Only)
95.
New Era of CP: Introducing 1v1 Blitz Style Showdowns Hey CF Community,
=================
Competitive Programming has always been a solo grind — countless hours of solving problems, climbing the rating ladder, and pushing your limits. But what if we made it more dynamic, personal, and real-time competitive?
Introducing a new format that redefines the CP experience: **1v1 Blitz Style Showdowns**.
#### What Is a Blitz Style Showdown?
- A unique format where users can schedule a battle, and others from across the globe can join in.
- Players can set a desired rating range to match with suitable opponents.
- Both participants receive the same set of problems under a strict time constraint.
- The blitz mechanism makes it even more intense — only one player can solve a problem.
- Global leaderboard is created based on user performance(Currently Beta version).
#### Features of Our Platform
- **Solo Battles**: Practice in a contest-like environment with a time based point-decay system.
- **Room Battles**: Compete with your C...
#### Still in Beta — Your Feedback Matters This is a bold new experiment, and
we’re starting small
96.
Dynamic Programming Playlist Hello everyone,
I just started my [YouTube channel] (https://www.youtube.com/channel/UCnZ5rC2_JY0EuYMGMiAbISg) in which I have started posting videos related to competitive programming.
My first playlist is on [Dynamic Programming] (https://www.youtube.com/playlist?list=PLzVLIdIx9dQxwAN5mMkzdvK2B4rV8879j)
and I will be uploading solutions for 16 DP problems in the month of May (with videos coming every second day.)
This playlist is aimed at those who have a conceptual understanding of what DP is and want to raise their DP problem solving level so that they are able to solve medium level DP problems (of CF rating from 1600 to 2000).
Please have a look at my channel and consider subscribing if you like the content.
I have also uploaded a general video on how to get better at Dynamic Programming which should be helpful for all skill levels:
[How to get better at Dynamic Programming] (https://www.youtube.com/watch?v=WV5vI_p0L9Q)
The problem list is as under:
1) **Fl...
13) **The Least Round Way (Beta Round 2 B Rated 2000)** — Grid DP
97.
Codeforces Beta Round #88 <p>Hello everybody! My name is Gerald Agapov. I study at Saratov State University. Today I present you the set of, I hope interesting, problems. Good luck to all!<br /></p><div><span style="font-family: verdana , arial , sans-serif;font-size: 12.0px;line-height: 20.0px;background-color: rgb(255,255,255);">And also a warm thanks </span><span class="Apple-style-span" style="font-family: verdana , arial , sans-serif;font-size: 12.0px;line-height: 20.0px;background-color: rgb(255,255,255);"><a class="rated-user user-admin" href="http://codeforces.me/profile/RAD" style="font-family: arial;text-decoration: none;font-weight: bold;color: rgb(0,0,204);" title="Штаб, RAD">RAD</a></span><span style="font-family: verdana , arial , sans-serif;font-size: 12.0px;line-height: 20.0px;background-color: rgb(255,255,255);">, </span><span class="Apple-style-span" style="font-family: verdana , arial , sans-serif;font-size: 12.0px;line-height: 20.0px;background-color: rgb(255,255,255);"><a class=...
Codeforces Beta Round #88
Announcement of Codeforces Beta Round 88
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/04/2026 01:40:15 (h1).
Desktop version, switch to mobile version.
Supported by
