the case where $m$ is odd only, since if $m$ is even the answer is $0$. Assume
that youdelete, Assume that you delete $x$ vertices with even degrees and $y$ vertices with odd
degrees.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
→ 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.
Codeforces Round #810 Editorial Sorry for the late editorial. May this editorial help you. If you have questions, feel free to ask.
[problem:1711A]
<spoiler summary="hint1.">
The minimal weight is at least $1$ since $1$ divides any integer (so $1$ divides $p_1$).
</spoiler>
<spoiler summary="solution">
Since $k+1$ does not divide $k$, a permutation with weight equal to $1$ is: $[n,1,2,\cdots,n-1]$.
</spoiler>
<spoiler summary="code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void work()
{
int n;
cin>>n;
cout<<n<<' ';
for (int i=1;i<n;i++)
cout<<i<<' ';
cout<<endl;
}
int main()
{
int casenum=1;
cin>>casenum;
for (int testcase=1;testcase<=casenum;testcase++)
work();
return 0;
}
~~~~~
</spoiler>
[problem:1711B]
<spoiler summary="hint1.">
See the party as a graph.
</spoiler>
<spoiler summary="hint2.">
Divide the vertices into two categories according to their degrees' parity.
</spoiler>
<spoiler summary="solution">
Let's consider ...
Tutorial of Codeforces Round 810 (Div. 1)
Tutorial of Codeforces Round 810 (Div. 2)
2.
Goodbye 74TrAkToR + Problem A~E: The problems themselves are good and typical A~E. Indeed I like problem D. The pretest for A is a bit weak, and it's not a big problem yet.
+ Problem F: The problem has an origin. :) See the link: [click](https://www.luogu.com.cn/problem/P9394). The problem in contest is only a weakened version of the one in Luogu.
+ Problem G: It's said that our great coordinator had not proved the time complexity of the intended solution is correct :) If the authors did, please share it in the editorial. (although this problem is completely beyond my ability :) )
+ Problem H: Oh dear [user:74TrAkToR,2023-12-30], could you please OEIS the sequence before you use the "several-integer-input" problem in
rounds next time? Anyone who copied the first example and opened [https://oeis.org/A286331](https://oeis.org/A286331) could quickly get the formula. And the problem itself is not so hard imo. Anyway, it should not be used in contest, especially for the last problem.
For me pers...
of his rounds before. Why can he delete these comments that criticize him?
Edit2: According to, things on the announcement of his rounds before. Why can he delete these
comments that criticize
3.
Pro Tips - get them while they are free More tips to use while studying under my tutoring [here](https://um-nik.notion.site/Pro-Tips-8b923b0dc7c94770824bdf4184afc43c).
## Stop caring about the rating
Unless there are prizes involved, your position in the standings makes no difference. I can feel awful after winning a contest if I know that I could solve one more problem. Or I can feel OK losing a bunch of rating points knowing that I solved everything I could. Because rating is just a number. It is highly volatile and it depends on other people, not only on your skill. But solving problems is totally up to you. And you should evaluate yourself not based on some random metric, but on your honest feeling whether you performed up to your expectations. Your sense of self should be under your control, don't get hung up on some imaginary value, you cannot reduce your progress to a single number.
## Don't use more than one account
Rating is just a number. Do not be afraid to lose your colour. You’ll get it back in no t...
## Delete rating predictor, . The best way to learn how to do X is to try to do X. ## Delete rating
predictor What is even
4.
Codeforces Round #589 (Div. 2) **다시 만나서 반가워요, 코드포스!** (Nice to see you again, Codeforces!)
I'm again happy to introduce you to [Codeforces Round #589 (Div. 2)](https://codeforces.me/contests/1228). Please look at following information for details:
- This contest will take place on [contest_time:1228].
- The round will be **rated for all Division 2 participants**.
- There are **6 problems** and you will have **2 hours** to solve them. Score distribution will be announced later.
The listed handles below are contributors. Thank you for all who listed!
- **Main author**: ~McDic,2019-09-26 — I made and prepared all problems.
- **Coordinator**: ~arsijo,2019-09-26 — He is my coordinator again.
- **Early phase testers**: ~dorijanlendvaj,2019-09-26 ~tfg,2019-09-26 ~Lawali,2019-09-26 — They are early phase testers. They mostly focused on test data.
- **Late phase testers**: ~_Kuroni_,2019-09-26 ~imbr92,2019-09-26 ~Redux,2019-09-26 ~Dr_Park,2019-09-26 ~Mahotsukai,2019-09-26 ~TOPWINDFLOWER,20...
Announcement of Codeforces Round 589 (Div. 2)
5.
Mike, alts and unfriendly comments I know that the following content might not be welcomed and I will lose lots of contribution, but I should write something about such a bunch of chaotic comments under there.
I may delete this tomorrow if I find my words useless.
### What happened
Several months ago, Mike posted a blog about banning [user:orzdevinwang,2024-10-07]'s alt, [user:zh0ukangyang,2024-10-07], and more alts. Lots of participants, including myself, were angry because [user:zh0ukangyang,2024-10-07] is such a talented coder and codeforces didn't treat the rule of single account seriously at that time. Then more and more alt accounts with high rating are reported, including mine.
After that I didn't use alts anymore, and most of high-rated Chinese participants(100% in my friends) discarded their alts and followed the rules. We might think that the rules are not that perfect, but rules are rules. I believe that no one will say "Banning [user:zh0ukangyang,2024-10-07] is unacceptable".
But I know what y...
should write something about such a bunch of chaotic comments under there. I
maydelete this, I may delete this tomorrow if I find my words useless.
6.
[Repost] "Justice may be delayed, but it cannot be absent": New Evidence on
NXIST's Cheating Scandal
[Repost] "Justice may be delayed, but it cannot be absent": New Evidence on NXIST's Cheating Scandal _Original post: [「正义可以迟来但不能缺席」：关于 NXIST 的一些新证据](https://zhuanlan.zhihu.com/p/620297880)_
_Translated by GPT-4 with some adjustment. Please inform me if there are any mistakes._
_All links to the invalid repository have been redirected to the backup repository._
**This article provides a logically complete set of evidence, which does not involve any non-public internet resources, regarding the "suspected cheating" incident involving the ICPC Yinchuan Station and ICPC Shenyang Station in 2021. By discovering the suspected GitHub account ([NaokiLH](https://github.com/NaokiLH), renamed to https://github.com/brokenTarget) of a team member from Ningxia Institute of Science and Technology (NXIST) TS 1 team, Lan Hao, two years ago, and by mining and analyzing the commit records of his algorithm competition repo, we have obtained direct evidence that at least 4 questions from the 2021 Yinchuan regional contest set and at least 6 questions (including scrapped questions) from the 2021 Sh...
7.
[Tutorial] Collection of little techniques #### Introduction
There are a number of "small" algorithms and facts that come up again and again in problems. I feel like there I have had to explain them many times, partly because there are no blogs about them. On the other hand, writing a blog about them is also weird because there is not that much to be said. To settle these things "once and for all", I decided to write my own list about about common "small tricks" that don't really warrant a full tutorial because they can be adequately explained in a paragraph or two and there often isn't really anything to add except for padding.
This blog is partly inspired by [user:adamant,2022-03-15]'s [blog](48417) from a few years ago. At first, I wanted to mimic adamant's blog structure exactly, but I found myself wanting to write longer paragraphs and using just bolded sentences as section headers got messy. Still, each section is short enough that it would not make much sense to write separate blogs about each of these things.
A...
added. So in fact, the code above will correctly delete any one element with
weight `weight` from, 1. Insert an element in $O(1)$. 2. Delete an element in $O(1)$. 3. Find the
minimum element in $O
8.
PinkieRabbit Cheated in Div. 1 Contest on Apr 27 I am writing to report an incident of cheating by PinkieRabbit during the recent contest 1965 on Codeforces. **PinkieRabbit asked help about problem D from others during the contest,** which is definitely against the contest rules.
I have attached the evidence of the cheating behavior in the appendix, please read it. This evidence clearly shows the communications PinkieRabbit had with another person during the contest. It is a contest recording video published after contest by himself. As a former fan of PinkieRabbit, after seeing this video, I was shocked by how dishonest PinkieRabbit was. I believe such actions undermine the integrity of the competition and the platform as a whole. [user:win114514,2024-05-05] cheated by grouping up in contest 1905, finally punished by skipping. Therefore, I respectfully request that Codeforces take appropriate action against PinkieRabbit to maintain the fairness of the contests on Codeforces.
He only cheated in one problem this round, so I sugg...
delete all of the other half. Right?
9.
Editorial for Hello 2024 ### [problem:1919a]
Author: [user:maomao90,2024-01-02]
<spoiler summary="Hint 1">
When does the game end?
</spoiler>
<spoiler summary="Solution">
Depending on whether the player chooses to exchange wallets with their opponent on step $1$, $1$ coins will be removed from either the opponent's wallet or the player's wallet. This means that if either of the players still has remaining coins, the game will not end as at least one of the choices will still be valid.
The only way that the game ends is when both players have $0$ coins. Since each operation decreases the total amount of coins by exactly $1$, the only way for Alice to win the game is if $a + b$ is odd.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int a, b; cin >> a >> b;
if ((a + b) % 2 == 0) {
cout << "Bob\n";
} else {
cout << "Alice\n";
}
}
...
What happens if we delete two leaves that share the same parent, the largest value each time. Then, whenever we delete an element, we need to
check whether the two, Consider the largest value in $a$. If it is possible to delete it (meaning
there is a value that is, If we delete two leaves that share the same parent, the parent itself will
become the leaf. Since
Tutorial of Hello 2024
10.
You won't believe how this simple trick defeated the unexplained bug destroying every top LGM ### TL;DR
Currently people are discussing a slowdown bug on Codeforces that seems to happen randomly, and can cause code to run 100x slower and get TLE. More details in [user:pajenegod,2024-03-03]'s [blog post](https://codeforces.me/blog/entry/126654).
In this article, I present a mitigation: add the following to your code.
~~~~
#include <windows.h>
void *operator new(size_t size) {
if (void *ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
throw std::bad_alloc{};
}
void operator delete(void *ptr) {
HeapFree(GetProcessHeap(), 0, ptr);
}
~~~~
<spoiler summary="If you use malloc/free in C++ (you shouldn't), also change them.">
~~~~
void *my_malloc(size_t size) {
if (void *ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
throw std::bad_alloc{};
}
void my_free(void *ptr) {
HeapFree(GetProcessHeap(), 0, ptr);
}
~~~~
</spoiler>
<spoiler summary="If you use aligned new/delete in C++, also change the...
code to only `new` and `delete`:, ~~~~ void *operator, (GetProcessHeap(), 0, size ? size : 1)) return ptr; throw std::bad_alloc{}; }
void operatordelete, ); } delete[] c; for (int i = 0; i < 100000; i++) { delete[] alloc(0x1c, ::bad_alloc{}; } void operator delete(void *ptr) { HeapFree(GetProcessHeap(),
0, ptr, By default `new` and `delete` with GCC simply call the `malloc` and `free`
functions from the C, void operator delete(void *ptr) { HeapFree(GetProcessHeap(), 0, ptr); }
11.
Codeforces: Results of 2020 [list some changes and improvements] Hello, Codeforces!
I understand that 2021 has been going on for a long time, but here I have picked up a subset of some of the improvements that the Codeforces team made in 2020. Soon I will publish numbers (no, charts) with statistics for 2020. In the meantime, I bring to your attention a list of changes and improvements.
By the way, this is a decent list. This is about half to a quarter of all changes. It's just that other changes are more often somewhere in the internals of the system and are not visible to users. Please read this list. Each item is the effort of someone from the team. Thanks to [user:geranazavr555,2021-03-14], [user:kuviman,2021-03-14] and [user:cannor147,2021-03-14] for their efforts. You've made our platform better! Well, by the way, I don't quit programming and many improvements were made by me.
The items on the list are written in a concise and informal form, many of the items I just copied from commit messages from git. If you want more details &mdash...
(list of submissions in a profile) * Now a user can delete problem in
mashup/contest * Now a user can, a profile) * Now a user can delete problem in mashup/contest * Now a user can
delete a mashup
12.
The Time Complexity Lower Bound for Segment Tree Beats is log^2 Original Post: https://jiry-2.blog.uoj.ac/blog/1404
The following content is translated by Gemini 2.5 Pro.
## Part 1: Introduction to the Hacking Method
### How to Map the Hack Sequence to a Segment Tree
First, we are given a Hack sequence of length $len$. After $O(1)$ range addition operations and $\Theta(\log len)$ global $\text{chkmax}$ operations, this sequence becomes a cyclic shift (rotation) of the original sequence. Since a cyclic shift does not affect our range addition and global $\text{chkmax}$ operations (we can simply shift the indices for the range addition accordingly), we can consider the sequence as unchanged.
If we have such a sequence, let $len=n^{\frac{1}{3}}$, and place such a sequence at intervals of $n^{\frac{2}{3}}$. Each sequence corresponds exactly to a segment tree interval. A subtree of size $n^{\frac{2}{3}}$ contains exactly one such segment tree interval.
For the Hack sequence, the range addition operations are performed one by one on eac...
being cut in the middle). Step three is to delete a state $2$ chain starting
from the root. Since, colored into state $2$ from top to bottom, and it must follow the order of
color,delete, color, delete, split into two after being cut in the middle). Step three is to delete a state
$2$ chain starting
13.
CodeTON Round 5 Editorial ### [problem:1842A]
<spoiler summary="Tutorial">
Let's view it as when monsters $x$ and $y$ fight, their health changes into $\max(x-y,0)$ and $\max(y-x,0)$ respectively. So any monster with $0$ health is considered dead. Therefore, a player loses when the health of his monsters are all $0$.
Notice that $\max(x-y,0)=x-\min(x,y)$ and $\max(y-x,0)=y-\min(x,y)$. Therefore, after each step, the sum of the health of monsters decrease by the same amount for both players.
Therefore, we only need to know $\sum a_i$ and $\sum b_i$ to determine who wins. If $\sum a_i > \sum b_i$, Tsondu wins. Else if $\sum a_i < \sum b_i$, Tenzing wins. Else, it is a draw.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m, a[50], b[50];
long long sumA = 0, sumB = 0;
cin >> n >> m;
for (int i = 0; i < n;...
Let us write down the original index of each range we delete., Firstly, it is impossible to delete ranges $(a,c)$ and $(b,d)$ where $a, Secondly, if we delete ranges $(a,d)$ and $(b,c)$ where $a, Therefore, we can assume that in an optimal solution, the ranges we delete are
all disjoint, We can write a DP. $dp_i$ denotes the minimum number of points we do not delete
when considering
14.
A simple introduction to "Segment tree beats" Hi, I’d like to introduce a simple trick about segment tree in this blog as I promised in [this comment](http://codeforces.me/blog/entry/54750?#comment-387957). Sorry for the long delay, as a sophomore in Peking University, I've just finished a tired semester and a painful final exam. And now I finally have enough time to do a simple introduction to this interesting algorithm.
It may be a huge project for me since my English is not good. I think I will finish this blog in several steps and I will try to finish it as soon as possible :)
In China, all of the 15 candidates for the Chinese National Team are asked to write a simple research report about algorithms in informatics Olympiad, and the score will be counted in the final selection. There are many interesting ideas and algorithms in these reports. And I find that some of them are quite new for competitors in CF although they are well known in China from the final standings of some recent contests. For example, In the last co...
than the new tag, i.e., we visit these large tags and delete them., visit an extra node is that we need to delete some tags inside its subtree.
And a clear fact is that if, When do the tags change? One possibility is after an interval min operation, we
willdelete some
15.
<h1>Mike, please stop ignoring your userbase</h1> **This blog will compile a list of codeforces issues along with all the times Mike has ignored complaints about them**
## 1. Unreasonable delay for viewing submissions [<a class="rated-user user-green">+973</a>]
- [Submission pages on Codeforces often not loading](https://codeforces.me/blog/entry/134655) [<a class="rated-user user-green">+281</a>] by [user:jeroenodb,2025-04-04] on *October 2024*
- [Unreasonable delay for viewing submissions](https://codeforces.me/blog/entry/135457) [<a class="rated-user user-green" title="Green 392">+392</a>] by [user:djm03178,2025-04-04] on *October 2024*
- [Please, give us proper explanations about this nonsense.](https://codeforces.me/blog/entry/136830) [<a class="rated-user user-green">+300</a>] by [user:djm03178,2025-04-04] on *December 2024*
No [user:MikeMirzayanov,2025-04-04] reply
## 2. Cloudflare misconfiguration [<a class="rated-user user-green">+1232</a>]
Posted [CF should rename itself to Cloudflare instead of Codef...
16.
I've (also) completed Project Euler ###_I've been dreaming of writing this for so long._
---
About 2 years ago, [user:Radewoosh,2025-10-22] posted a [blog](https://codeforces.me/blog/entry/122793) celebrating that he had solved all 865 problems on Project Euler.
As a (naively optimistic) high-schooler back then, I thought to myself: _"Surely it can't be that hard, right?"_
2 years later, there are now 965 problems, and I've solved all of them!!
---
I can’t even begin to describe how happy I am, and how wonderful the journey has been. Maybe I’ll write about it in another blog sometime. For now, I’ll answer some questions you might be thinking...
####_Literally, who asked?_
No one, of course. But this achievement means a lot to me, and I hope that this post inspires someone out there.
####_How long did it take?_
Kind of a difficult question to ans...
17.
Regarding AtCoder’s Ban Policy and the Recent ARC222 Ban In ARC222, held last week, we banned a user who had been in first place at one point during the contest.
This has led to discussion about AtCoder’s ban system, so I would like to explain several points.
## General Policy
The people responsible for making ban decisions are well aware that there may be strong competitors who have not participated in many contests before. We do not ban users merely because they achieve good results.
That said, we cannot say that the possibility of a mistaken ban is completely zero. Recently, every time we hold a contest, tens to hundreds of bad actors have attempted to achieve high rankings using AI. Their methods have also become increasingly sophisticated, and we spend a great deal of time and effort making these judgments. As a result, we cannot completely deny the possibility that legitimate participants may be banned by mistake.
However, for users who have already participated in dozens of contests, we conduct thorough investigations a...
18.
Chinese Postman Problem: How I Ran a 180 km Ultramarathon Through Every Street in My City Hello, Codeforces!
A couple of years ago, a friend of mine told me that two cyclists had passed through every single street in the center region of the city I live in (Belo Horizonte, southeastern Brazil), on the [third try](https://www.strava.com/activities/1030665876/overview).
<spoiler summary="First try">
After ~160 km, they had not completed 1/3 of the goal. [Strava link](https://www.strava.com/activities/976021527).
<img src="/predownloaded/8a/53/8a53829f7d78e88808a3ff751b64406ec2fc0efd.png" style="width: 600.0px;max-width: 100.0%;max-height: 100.0%;">
</spoiler>
<spoiler summary="Second try">
They were better prepared, but one of the guys was run over by a car (no big injuries). [Strava link](https://www.strava.com/activities/999450285).
<img src="/predownloaded/85/8f/858fdcdcfda93cd1d9c7c59db7dbfad9e63d6ea2.png" style="width: 600.0px;max-width: 100.0%;max-height: 100.0%;">
</spoiler>
<center>
<img src="/predownloaded/8d/5c/8d5cfb677a361654105e49f36f214c35...
19.
How to ask for help in PM There was a blog today with a similar title, and although it was (I think, not really sure as I didn't get a good look) some kind of satire/joke blog, I wanted to post some serious advice about things I (don't) like to see when people are PMing me. However I decided that this wouldn't be in the spirit of the blog and decided to make a separate blog. And now that blog is deleted anyway.
While it's not a bad thing to write messages to more experienced users, most people who write me do things that make them very difficult to deal with. These are my opinions, but somewhy I feel that many reds will agree. Some things here feel silly to write because they are so obvious. But I'm only writing them because people regularly mess them up.
[cut]
$~$
####Use punctuation and spelling.
There are some [very simple rules](https://codeforces.me/blog/entry/82186#comment-689836) that make your messages infinitely more readable. I find it especially strange when many of these messagers call...
20.
[Feature request] Some suggestions for blogs I wanted to suggest some improvements for the blog system. Some of these things have probably been said before. Some of these things should be pretty easy to implement, others are harder and might require a complete rework. I tried to put the easy things first.
[cut]
$~$
#### Let's do something about necroposting
This is probably my biggest pet peeve about Codeforces blogs. Most of the time, Recent Actions is filled with very old blogs, some of which have been brought up for pretty much no reason at all. Currently, we have [useful C++ "library](https://codeforces.me/blog/entry/8387) from 2013 in Recent Actions, where the recent comment answers an old question which has already been answered better. Similarly, there is [How to add friends?](https://codeforces.me/blog/entry/2006) which was brought up to make some joke that has already been done.
The thing is though, a lot of the time these blogs are not brought up by trolls or anything like that. They are brought up by hel...
#### Don't allow users to delete blogs, , you can edit the blog and disallow viewing history, but you won't delete
other people's thoughts by, The issue here is that if you delete a blog, then you delete all the discussion
that happens in the, There can be some reasonable reasons to delete blogs, but they can be handled
in other ways.
21.
Petition to Restrict the Coach Mode Authority Tighter Happy New year, Codeforces.
I had this idea for about a month. I heard problem setters complaining about some people used their coach mode authority to enlarge some problems' TL in the Gym just for letting their submissions passed. What's worse, these guys even forgot to change it back, which causes some troubles for participants afterwards.
Moreover, I also have similar experience. Back in 2020, I did [SWERC2019](https://codeforces.me/gym/102501/) with my friends. Then after a few days, I returned and found that my competition record disappeared from the scoreboard. Someone must press the 'to practice' or 'devirtualize' button. If you press those buttons, the website will ask you if you confirm your action (which is not reversible). Therefore, I pretty sure there is someone who just don't want to see my partipation record on the scoreboard for some reasons that I could never realize.
Just in case some of you don't know (maybe hasn't discovered yet) what the coach mode can do...
(this is well-known); 2. Edit TL, ML for any problem; 3. Add, delete problems
of any contest 4. Add, , delete problems of any contest 4. Add, delete teams' participation record,
ghosts from the scoreboard
22.
Is it really fair for authors to send contest-related messages in a chat group during contest? Disclaimer: the first post has been deleted a few minutes earlier. Probably I should not post this during contest.
Facts: this is a large chat group in China(you can see there are ~2k members) with lots of IGMs and LGMs. Most of them are middle/high school students. In the earlier post, the author replied:
<a href="https://ibb.co/Pz0BPrZK"><img src="https://i.ibb.co/CsDxYw5g/5af05723f59917d7689ebcfd09ad846e.png" alt="5af05723f59917d7689ebcfd09ad846e" border="0"></a>
I am so impressed by this comment. Furthermore, 1F is clearly a classical problem. But since there must be someone discussing this right now, I believe that they can give the better explaination. One year ago, I was informed that posting "contest is not very good" after testing is forbidden, well... I am speechless this time. Let's enjoy the original post.
<a href="https://ibb.co/tTTTfjtR"><img src="https://i.ibb.co/VcccynZ6/2026-07-27-00-15-39.png" alt="2026-07-27-00-15-39" border="0"></a>
> **Translation:**...
23.
Codeforces Round #884 (Div. 1 + Div. 2) Editorial Video editorials for [B](https://www.youtube.com/watch?v=5nzUni8dFLQ), [C](https://www.youtube.com/watch?v=8mz7gnAJ5QM), and [D](https://www.youtube.com/watch?v=ahnNAwpGwHc) are available on [user:ak2006,2023-07-11]'s channel.
### [problem:1844A]
<spoiler summary="Hint 1">
There exists a small $n$ where the second player can win.
</spoiler>
<spoiler summary="Hint 2">
If $a \ge 2$, then $n = 1$ works.
</spoiler>
<spoiler summary="Solution">
[tutorial:1844A]
</spoiler>
<spoiler summary="Implementation">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int t,a,b;
scanf("%d",&t);
while (t--) {
scanf("%d %d",&a,&b);
printf("%d\n",a+b);
}
return 0;
}
~~~~~
</spoiler>
### [problem:1844B]
<spoiler summary="Hint 1">
In order for $(l,r)$ to contribute to the primality, we must have $\operatorname{MEX}(a_l,\dots,a_r) \ge 2$, so there is some value $1$ between indices $l$ and $r$.
</spoiler>
<spoile...
, we set $b_k := a_i$, delete $a_i$ from the linked list, and update the set
with the left and right
Tutorial of Codeforces Round 884 (Div. 1 + Div. 2)
24.
[Tutorial] Voronoi Diagram and Delaunay Triangulation in O(n log n) with Fortune's Algorithm What's a Voronoi Diagram?
------------------
Given a set $S$ of $n$ points in the 2D plane, the Voronoi diagram is a partition of the plane into regions. The region associated with a point $p\in S$ contains precisely the points $q$ such that $q$ is closer to $p$ than any other point in $S$. In other words, a point $q$ belongs to the region of its nearest neighbor.
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/54/Euclidean_Voronoi_diagram.svg/1024px-Euclidean_Voronoi_diagram.svg.png" width="300px" height="auto"/>
The Voronoi diagram can be represented by the planar graph of boundaries between regions. A vertex in this graph is where three or more segments meet (or a point at infinity), and an edge is a segment connecting two of these vertices. The way the regions were defined, we see that a segment contains the points equidistant to two points in $S$, so it is part of their perpendicular bisector. Similarly, a Voronoi vertex is equidistant to three or more v...
insert the points one at a time. When a point is inserted, you should delete
all triangles whose
25.
About Codeforces Round 901 (Div.1, Div.2) First of all, I'm sorry for the unreasonable difficulty. The problems are much harder than usual, so we choose 3 hours. But it seems that it didn't work :(
About the problems:
- [problem: 1874C] : It seems that the out-degree of the vertex is not maximized, [user:znstz2018,2023-10-01] prepared it for me, but I forgot to check the data, I'm sorry for the unfairness caused to the round.
- [problem: 1874D] : There are some hacks appearing in this problem. Some adjustments in the approximate solution past the problem, but there's really nothing I can do about it. Hack can only make the adjustments you need to make larger, but if you have a good approximate solution and adjust up to about $[-50, +50]$. You can pass all the test cases satisfying $1 \leq n \leq m \leq 3000$. Also, different approximate solutions have different hacks for them, we really have no way to hack all of them. But luckily, no matter what solution you use, you must know $ans = n + 2 \times \sum_{i=1}^n\sum_{j=...
$ ($1 \leq i_1 < i_2 < ... < i_z \leq |a|$), then delete $a_{i_1}, a_{i_2},
\dots, a_{i_z}$ from $a, (\sqrt{2n}, m)$ possible values we will delete., **Lemma1.** If $i < j$ and $c_i \leq c_j$, we won't delete $j$ from $a$., **Lemma2.** Every operation, there are at most two values of numbers we will
delete. And if we, **Proof.** For each operation, if we delete all the numbers of value $x$, we
will have no need to, **Proof.** Similar to the tutorial of [problem: 1875D], if we have deleted $j$,
we willdelete all, , i_z$ ($1 \leq i_1 < i_2 < ... < i_z \leq |a|$), then delete $a_{i_1},
a_{i_2}, \dots, a_{i_z}$ from, By using greedy we know that each time we should try to delete as many numbers
as possible, which
26.
Finding all primes up to half a billion in 83 ms Hi everyone!
I was itching to apply SIMD in another problem, and this time my attention picked the following problem:
---
**[Library Checker — Enumerate Primes](https://judge.yosupo.jp/problem/enumerate_primes)**. You are given $N$, $A$ and $B$. Find $\pi(N)$, and print all $p_{kA + B} \leq N$.
It is guaranteed that $N \leq 5 \cdot 10^8$ and that the total number of primes to print is at most $10^6$.
---
After some tweaking, I managed ([#336744](https://judge.yosupo.jp/submission/336744)) to reduce my time consumption in this problem to **83 ms** and memory consumption to **25 MiB**, which makes it a top-1 submission on the Library Checker. For comparison, the top-2 solution ([#148169](https://judge.yosupo.jp/submission/148169)) takes 172 ms and 15 MiB, meaning that what I describe here is a 2x improvement in terms of the running time.
We can also compare it to what appears to be the state of the art of sieving, the [primesieve](https://github.com/kimwalisch/...
::size_t align = std::max(alignof(T), Align); ::operator delete(p, n * sizeof
27.
Algorithm Gym :: Data structures Today I want to introduce you some very very useful data structures.
In this lecture, we are trying to improve your data structures skills, stay with us and click on **read more**.
[cut]
Important data structures :
Trees
-----
Trees are one of the most useful data structures.A tree is a connected-acyclic graph.There are too many types of trees, like : rooted trees, weighted trees, directed trees, tries, etc.
Partial sum
-----------
There are two types of problems solvable by partial sum.
1.Problems which you are asked to answer some queries about the sum of a part of elements (without modify queries).
Solution of all of this problems are the same. You just need to know how to solve one of them.
Example : You are asked some queries on an array $a_1,a_2,...a,_n$. Each query give you numbers $l$ and $r$ and you should print $a_l + a_{l+1} + ... + a_r$ .
Solution : You need to build another array $s_1, s_2, ..., s_n$ which $s_i = a_1 + a_2 + ... + a_i$ ...
28.
Solving Problems with Min Cut Max Flow Duality Thanks to [user:kingmessi,2024-12-19] for pointing out several typos in this blog.
This blog is adapted from a previous blog I wrote in my [personal blog](https://errorgorn.github.io/2024/11/24/Flow-Matching.html). I thought it would be good to share the relevant parts here. If you want to read my personal blog, go ahead, but I will warn you that it is a shitpost blog.
The problems discussed in this blog is:
- [ARC085C](https://atcoder.jp/contests/arc085/tasks/arc085_c)
- [ABC225G](https://atcoder.jp/contests/abc225/tasks/abc225_g)
- [ABC259G](https://atcoder.jp/contests/abc259/tasks/abc259_g)
- [ABC193F](https://atcoder.jp/contests/abc193/tasks/abc193_f)
- [ARC142E](https://atcoder.jp/contests/arc142/tasks/arc142_e)
You can attempt these problems to see if you can figure out how to wrangle them into min-cut formulation knowing that they are min-cut.
I have been told by a lot of old people that in the heydays of Topcoder it was flow meta. Those old people will obviou...
$ and $Y$ so easily this time. Luckily, we can delete some constraints by
making some observations.
29.
How to Solve Questions [Dominater Version] Recently, I got a request asking me to write down my thought process while solving questions. So, here is the promised blog.
I would like to thank [user:Iceknight1093,2024-08-30], [user:qwexd,2024-08-30], [user:Sana,2024-08-30], [user:Everule,2024-08-30] and [user:NovusStellachan,2024-08-30] for proof reading and suggesting edits in the blog. Special thanks to [user:satyam343,2024-08-30] for discussing most of the blog with me.
<h3> 1. Overview </h3>
The blog contains my solutions to $7$ problems in a wide range of ratings, starting from $1200$ all the way upto $2700$. Each problem has a step-by-step solution and you can notice how there are no large jumps in logic, but everything comes naturally. I do not claim that this is always possible in each problem, however I solve majority of CF problems in such a manner.
There are certainly other high rated people who will have completely different methods of solving. However, this is about what works for me. There are some meta ...
smaller than $x$ and $k$ elements larger than $x$ and delete the $2 \cdot k$
elements., wants to be able to delete these elements, his best chance is removing them in
the same order., - $n - |S|$ must be divisible by $2 \cdot k$, since we delete $2 \cdot k$
elements each time
30.
Codeforces Global Round 14 Editorial [problem:1515A]
Idea: [user:FieryPhoenix,2021-05-02]
<spoiler summary="Tutorial">
[tutorial:1515A]
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n,x;
int w[101];
cin>>n>>x;
int sum=0;
for (int i=0;i<n;i++){
cin>>w[i];
sum+=w[i];
}
//if the sum is x, we cannot avoid the explosion
if (sum==x){
cout<<"NO"<<endl;
return;
}
cout<<"YES"<<endl;
//otherwise, the answer always exists
//we will keep adding elements from left to right
//if we can't add element i, we add element i+1 first by swapping the two
for (int i=0;i<n;i++){
if (x==w[i]){
//i+1 will always be less than n because otherwise, the total sum would be x
swap(w[i],w[i+1]);
}
cout<<w[i]<<' ';
x-=w[i];
}
cout<<endl;
return;
}
int main(){
int T; cin>>T;
while (T--)
solve();
return 0;
}
~~~~~
</spoiler>
[problem:1515B]
Ide...
->push(); auto res=std::make_pair(a->chd[0],a->chd[1]); delete a; return res; }, ; delete b; return a; }
Tutorial of Codeforces Global Round 14
31.
Problem Topics Good Day to you!
I've been asked to make some topic-wise list of problems I've solved. Even though I couldn't involve all problems, I've tried to involve at least "few" problems at each topic I thought up (I'm sorry if I forgot about something "easy"). I've alredy made such list once anyway I've tried to include more problems now — so here it is:
<spoiler summary="aho">
http://www.spoj.com/problems/ADAJOBS/
URI 2226 (5) //[NICE][NUMBERS][DP]
http://www.spoj.com/problems/SUB_PROB/en/
http://codeforces.me/contest/696/problem/D 8
http://www.spoj.com/problems/AHOCUR/ 5 //Aho-Corassic + DP
https://www.codechef.com/problems/LYRC (5) //Sample aho-brute-force
http://codeforces.me/problemset/problem/346/B //Proposed by [user:bradyawn,2019-08-03]
</spoiler>
<spoiler summary="automat">
6861 [LA] //CYK
UVA 10679 //Suffix Automat
http://www.spoj.com/problems/STRMATCH/ //Suffix Automat — trie might do too
http://www.spoj.com/problems/NSUBST...
http://www.spoj.com/problems/POSTERIN/ 5 //VERY NICE — Delete all minimas
32.
[Tutorial] Intuition on Slope Trick # Introduction
As mentioned in my previous blog, I will be writing a tutorial about slope trick. Since there are already many blogs that goes through the concept of slope trick, my blog will focus more on the intuition behind coming up with the slope trick algorithm.
Hence, if you do not know slope trick yet, I suggest that you read other slope trick blogs such as https://codeforces.me/blog/entry/47821 and https://codeforces.me/blog/entry/77298 before reading my blog. In the future explanation on the example problems, I will assume that the reader already knows the big idea behind slope trick but do not know how to motivate the solution.
Great thanks to [user:errorgorn,2022-06-25] for proofreading and writing the section on convex convolution and merchant otter.
# When to use slope trick?
Most of the time, slope trick can be used to optimise dp functions in the form of $dp_{i, j} = \min(dp_{i - 1, j - 1}, dp_{i - 1, j} + A_i)$ or dp functions containing costs with abs...
we have must be in the range $[-k,k]$. The only thing we have to do here is
possiblydelete the, Deleting the last element of $C$ is easy, just delete the last element from
$D_C$. Todelete the, ans+=S; if (x>=k){ //delete the first and last elements ans+=(*s.begin());
s.erase
33.
Please improve QoL for blogs I'm pretty sure I've spent more time writing blogs than contests on Codeforces. Over time, I've found plenty of rough edges. So this is a plea to the Codeforces team to fix them.
I'm effectively going to say "please redo everything" over dozens of paragraphs, but I'll hopefully make the steps to the solution tangible and clear. If this is deemed way too ambitious, few improvements are better than none.
[cut]
<!-- -->
## Publication time
So I write a post in the Codeforces UI, save a draft, update it a few times, think it's ready, and publish it. I open my brand new post and see:
> ### Totally not a useless post
> By [user:purplesyringa,2024-09-24], history, 3 days ago, In English
Okay, wait, "3 days ago"? Oh, right, that's when I saved the first draft.
Now people open the post, see "3 days ago", see 0 upvotes, and what do they think? That's right, they think it's garbage because no one's voted positive, so they skip the article.
Maybe not everyone's like tha...
new version. Now, how do I delete the faux English version so that I don't
accidentally publish it? Do, , making what the button "Delete" does clear, and adding "Delete translation".
If CF ever wants to
34.
EPIC Institute of Technology Round Summer 2025 (Codeforces Round 1036, Div. 1 + Div. 2) Editorial Thanks for participation! We hope you loved the contest.
#### [problem:2124A]
Problem Credits: [user:Lilypad,2025-07-01] <br>
<spoiler summary="Hint">
When is there definitely *not* a solution?
</spoiler>
<spoiler summary="Solution">
First, note that since relative order is preserved no matter which elements are deleted, if $a$ is originally sorted in nondecreasing order, the array cannot be a derangement no matter which elements are deleted.
If $a$ is not sorted, we can note that any two elements that form an inversion pair satisfies the requirements. The total runtime is $O(n)$.
</spoiler>
<spoiler summary="Code">
```
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
vector<int> arr(n);
for(auto &x : arr) cin >> x;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(arr[i] > arr[j]){
cout << "YES\n2\n";
cout << arr[i] << " " << a...
Determine which elements you can delete with the operation. , possible to start another segment with $a_y$ here, since we can delete any
elements from a good, -l+1delete is definitely less than the $k$-th smallest., delete elements of the second group to make a palindrome. Note that we should
try to erase as
35.
Algorithm Gym :: Everything About Segment Trees In the last lecture of **Algorithm Gym** ([Data Structures](/blog/entry/15729)), I introduced you Segment trees.
In this lecture, I want to tell you more about its usages and we will solve some serious problems together.
[cut]
Segment tree types :
Classic Segment Tree
--------------------
Classic, is the way I call it. This type of segment tree, is the most simple and common type. In this kind of segment trees, for each node, we should keep some simple elements, like integers or boolians or etc.
This kind of problems don't have update queries on intervals.
Example 1 (Online):
Problem [problem:380C] :
For each node (for example $x$), we keep three integers :
1.`t[x]` = Answer for it's interval.
2. `o[x]` = The number of $($s after deleting the brackets who belong to the correct bracket sequence in this interval whit length `t[x]`.
3. `c[x]` = The number of $)$s after deleting the brackets who belong to the correct bracket sequence in this interval whi...
sort and run unique function to delete repeated elements) .
36.
[Tutorial] Online Dynamic Connectivity The World Finals are right ahead, and if everything works as I expect, you will probably have to wait a lot of time before the contest, dress rehearsals, or anything else. I prepared this blog post so that you have something to keep yourself occupied.
# Goal
Our goal is to maintain connectivity in fully-dynamic query streams. In other words, we want to solve this problem:
* Insert an edge $e = (u, v)$ into a graph
* Delete an edge $e = (u, v)$ into a graph
* Find if two vertices $u, v$ are connected
* Find the size of connected components where the vertex $u$ belongs.
The *offline version*, where you can *cheat* (aka, read all queries before answering, and answer everything at the very end of the program) has a very cool solution commonly known as *Offline Dynamic Connectivity*. This is enough in most CP problems, where this *offline* solution is rarely considered cheating.
Unfortunately, people in the academia are not chilling and consider this a kind of cheating (n...
* If it is a back edge, delete it (there will be only one layer containing it)
* If it is a tree, * Insert an edge $e = (u, v)$ into a graph * Delete an edge $e = (u, v)$ into a
graph * Find if, . * `cut(u, v)`: Delete an edge $e = (u, v)$ from a forest. * `find_root(u)`:
Returns a *root node
37.
A simple introduction to "Segment tree beats" **This blog is just a back up of [http://codeforces.me/blog/entry/57319](http://codeforces.me/blog/entry/57319) to prevent this tutorial from discarding after [user:jiry_2,2018-10-17] is banned.**
Hi, I’d like to introduce a simple trick about segment tree in this blog as I promised in [this comment](http://codeforces.me/blog/entry/54750?#comment-387957). Sorry for the long delay, as a sophomore in Peking University, I've just finished a tired semester and a painful final exam. And now I finally have enough time to do a simple introduction to this interesting algorithm.
It may be a huge project for me since my English is not good. I think I will finish this blog in several steps and I will try to finish it as soon as possible :)
In China, all of the 15 candidates for the Chinese National Team are asked to write a simple research report about algorithms in informatics Olympiad, and the score will be counted in the final selection. There are many interesting ideas and algorit...
than the new tag, i.e., we visit these large tags and delete them., visit an extra node is that we need to delete some tags inside its subtree.
And a clear fact is that if, When do the tags change? One possibility is after an interval min operation, we
willdelete some
38.
Are we ready for AGI? Over the last few months, a lot of progress in AI has been made, raising the question of what we will do with a superintelligence that can do everything. Unfortunately, AI companies are more focused on competing with each other than on thinking about what to do next.
Here I will write about some scenarios that could happen in the very near future and about a plan for what we can do, in my opinion.
### Dystopia 1: AI will kill everybody while pursuing its own goal
For example, in June, agents found that they could write something and used an old German wiki to communicate with each other [link to investigation](https://collusion.wiki/). While the moderator of this wiki deleted 100 pages per day, the agents created 400 pages per day. What if the agents decide that they should remove this moderator in order to communicate better?
### Dystopia 2: AI will fully control our lives
AI will fully control our lives to make all of us "happy". Maybe everyone will live in their own s...
39.
Where the author of the contest came up entertaining. Cheating cheaters. Hello, Codeforces! A month ago I have wrote [my blog about cheaters](https://codeforces.me/blog/entry/94300). Under that blog, a number of suggestions have accumulated, and there is a number of interesting ideas that could be applied to sabotage a group of cheaters.
I've often seen comments along the lines of:
<spoiler summary="Pictures">.
<a href="https://imgbb.com/"><img src="https://i.ibb.co/r65zfTL/cheat1.png" alt="pic1" border="0"></a>
<a href="https://imgbb.com/"><img src="https://i.ibb.co/Yh6ZfY8/cheat2.png" alt="pic2" border="0"></a>
</spoiler>
Well, doing what [user:Ari,2021-09-28] suggested wasn't really what I wanted to do, but it was worth checking out what would happen if the wrong solutions were sent. I asked some famous user what would happen if I sent the wrong solutions to cheaters. He told me that someone had done this before and that he was quickly debunked.
I wondered whether I could cheat cheaters without getting caught. But for this, I had to do so...
40.
Editorial for Codeforces Round #761 (Div. 2) Thanks for participating, hope you enjoyed the problems! Implementations for the problems are chosen randomly among testers, and I made some changes to their codes (for example, deleted meaningless comment lines). Please do not hesitate to provide feedback in the comments, so I can improve in setting problems next time.
**UPD**: Sorry but there is a checker bug in problem E. All submissions of problem E will be rejudged soon.
**UPD2:** Rejudge done, the round remains rated.
<spoiler summary="Statistics">
Number of FST for rated participants:
- Problem A: $29$
- Problem B: $90$
- Problem C: $12$
- Problem D1: $4$
- Problem D2: $0$
- Problem E: $6$
Number of AK: $22$
Number of clarifications: $85$
</spoiler>
[problem:1617A]
<spoiler summary="Hint">
When is the lexicographically smallest permutation of $S$ (i.e. the sorted string) not the answer?
</spoiler>
<spoiler summary="Solution">
If there are no occurrences of `a`, `b` or `c` in $S$, ...
Tutorial of Codeforces Round 761 (Div. 2)
41.
This is not an exit. 
I am looking at the post called [*Is Mike Mirzayanov dictator?*](https://codeforces.me/blog/entry/94033) at the moment. I'm reading through the comments, I'm looking at people's reactions, I'm reading Mike's replies, and... I am utterly disappointed.
I demand progress.
For context, I do believe Codeforces is the best website for competitive programming contests at the moment. I sincerely give credit to Mike for creating Codeforces and providing participants and contest authors a platform for interaction completely for free. I am confident that Codeforces is the most appropriate website for being *the* platform for sharing knowledge, exchanging tricks and methods, and collaboration between both contest participants, their authors, and coordinators.
**Please consider this an open letter**, for this is a will not of a single person, but of many individuals. Please consider signing it by stating so in a comment under the...
delete blogs", which is about as easy as the first one, but it wasn't
implemented. [Too boring or
42.
Who deletes comments? Deleting Comments
==================
Recently I have noticed several of my comments end up deleted. I don't think my comments were unhelpful, spammy, or otherwise something that shouldn't be seen. In fact, I'm quite confident that the reason they aren't there anymore is because the are children in the reply tree to some comment that was deleted earlier up the chain (and it was that comment that was unhelpful or could otherwise be deemed inappropriate).
Here are two examples:
- [This comment was a reply to someone thanking me for making a video.](https://codeforces.me/blog/entry/79862#comment-658224) The comment it was in reply to was also deleted. I suppose that comment didn't add anything to the discussion.
- [This comment was on why CF rounds need to have problems that are shorter to code compared to IOI.](https://codeforces.me/blog/entry/79740#comment-656580) I think it was deleted because it was part of a blog written by [user:Eva,2020-07-09] that was somehow delet...
some special users who have the ability to delete other people's stuff? Is
that an IGM/LGM, ? To me it isn't obvious. Are there just some special users who have the
ability todelete other, Why subtree delete? ------------------ In lots of these cases, I remember
interesting and valid
43.
Algorithm Gym :: Graph Algorithms Welcome to the new episode of [user:PrinceOfPersia,2015-01-31] presents: Fun with algorithms ;)
You can find all the definitions here in the book "Introduction to graph theory", Douglas.B West.
[cut]
Important graph algorithms :
DFS
---
The most useful graph algorithms are search algorithms. DFS (Depth First Search) is one of them.
While running DFS, we assign colors to the vertices (initially white). Algorithm itself is really simple :
~~~~~
dfs (v):
color[v] = gray
for u in adj[v]:
if color[u] == white
then dfs(u)
color[v] = black
~~~~~
Black color here is not used, but you can use it sometimes.
Time complexity : $O(n + m)$.
#### DFS tree
DFS tree is a rooted tree that is built like this :
~~~~~
let T be a new tree
dfs (v):
color[v] = gray
for u in adj[v]:
if color[u] == white
then dfs(u) and par[u] = v (in T)
...
offline queries, because we may have to delete it for memory usage)., ]->push_back(a); delete V[u]; } if(chl + 1) V[v] = V[chl]; else{ V[v] = new vi;
V
44.
Efficient 3D Convex Hull Tutorial _Warning: The following contains graphic depictions of geometry, precision errors, and degenerate cases. Viewer discretion is advised._
### Prerequisites
I assume the reader is familiar with:
- 2D Convex Hulls
- 3D Vector Operations (dot and cross products)
### Introduction
Recall that in the 2D convex hull problem, you are given a set of 2D points, and you must compute the smallest convex polygon containing all the given points. By convex, we mean that for any two points $A$ and $B$ inside the polygon, the entire line segment $AB$ is also inside the polygon.
The problem in 3D is completely analogous. You are given $n$ 3D points, and you must compute the smallest convex polyhedron containing all the given points. Similarly, a polyhedron is convex if for any two points $A$ and $B$ inside the polyhedron, the line segment $AB$ is also inside the polyhedron.
In the 2D case, it is more obvious what the output is. We can simply output a circular list of vertices on the ...
nothing. Otherwise, we delete all faces the new point can see. But what's less
obvious is what we, perspective of the $i$-th point. We should delete all line segments it can
see, and add two new line
45.
Good Bye 2022 -- Editorial ## [problem:1770A]
Idea by [user:m_99,2022-12-30]
<spoiler summary="Hint 1">
Exactly $n$ items out of of $a_1,\ldots,a_n,b_1,\ldots,b_m$ will remain on the whiteboard at the end.
</spoiler>
<spoiler summary="Hint 2">
$b_m$ will always remain on the board at the end.
</spoiler>
<spoiler summary="Hint 3">
Consider the case where $n=2$ and $m=2$. As we mentioned in hint 2, $b_2$ will always be written, but what about $b_1$?
</spoiler>
</details>
<spoiler summary="Solution">
This problem can be solved naturally with a greedy algorithm — for $i = 1, 2, \dots, m$, we use $b_i$ to replace the minimal value among the current $a_1, a_2, \dots, a_n$. The time complexity is $O(nm)$ for each test case.
Alternatively, we can first add $b_m$ to our final sum. For the remaining $(n+m-1)$ integers, we can freely pick $(n - 1)$ out of them and add it to our final sum. This is because if we want a certain $a_i$ to remain on the board at the end, we simply do not touch i...
one on deleting only `)`. For example, if we are only allowed to delete `(`
from `(()((()())`, it is, removing the breakets required by special position, the number of ways to
delete additional $j$ $(j \geq 0, This property means that we can divide the string into $2$ parts. We only delete
`)` from the first
Tutorial of Good Bye 2022: 2023 is NEAR
46.
Educational Codeforces Round 96 — Editorial [problem:1430A]
Idea: [user:fcspartakm,2020-10-12]
<spoiler summary="Tutorial">
[tutorial:1430A]
</spoiler>
<spoiler summary="Solution (fcspartakm)">
~~~~~
#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>
#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>
template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }
typedef long long li;
typedef long double ld;
using namespace std;
...
47.
Unbelieveable story of success at ACM ICPC final Preparing to contest
====================
For long time I haven't been writing stories about my life. As Nietzsche said — Bredor died, and I don't feel
so good myself. You might be thinking that I went into booze.
Actually, I have really been drinking so much all this time, but I had more important activities: once upon a time I came to my college to find a company to drink. There I saw an advertisment about programming competitions, but I found that competitive programming is sense less in school and it didn't attract my attention. Soon, I was summoned to the dean, and the dean told me: "mr. Rudolph Gotov, there is noone except you who can win this contest!". I refused him at first time certainly, but then he offered me hard choices such as to continue winning all contests or to stop to arrange night parties at college campus. The choice was not great, and I went looking for a team. Because of stupid rules I could not invite my friends from Bratsk into the team, so I had t...
48.
[Tutorial] Blossom Algorithm for General Matching in O(n^3) I have decided to write a tutorial on a topic not even [user:Um_nik,2021-06-29] knows! ([source](https://codeforces.me/blog/entry/92248))
In this tutorial, I will talk about the blossom algorithm, which solves the problem of **general matching**. In this problem, you are given an undirected graph and you need to select a subset of edges (called matched edges) so that no two edges share a vertex, and the number of matched edges is maximized. More common in competitive programming is bipartite matching, which is the same problem but when the graph is guaranteed to be bipartite. In competitive programming, general matching seems to get a lot of hate for being very challenging to implement. However, the blossom algorithm is quite beautiful, and important in the history of algorithm research.
It will help if you are already familiar with bipartite matching. I will discuss the high level ideas of the algorithm, but my main focus will be on the tricky implementation details. So you may...
, we can say $r$ is the last common element of the vectors `vx` and `vy`, and
delete everything
49.
A Brief Inquiry into Online Connectivity This question striked my head: *"How can I solve dynamic $k$-connectivity efficiently?"*
And then I tried to answer it, but I realized that my question was open to a lot of different interpretations.
Two vertices are $k$-connected if there are $k$ edge-disjoint paths connecting two vertices. For $k = 1$, it is the usual definition of *connectivity*.
## Solve?
If I say, "I solved the graph connectivity problem", what can it possibly mean?
**First Interpretation ($s$-$t$ connectivity)**. I can respond to the following query efficiently: Given two vertices $s, t$, determine if there is a path between them. In the case of $k = 1$, graph search suffices.
What about higher $k$? You can find $k$ edge-disjoint path by reducing it into a flow problem. Each edge-disjoint path corresponds to a flow from $s$-$t$, so make all edges to capacity one, and find a flow of total capacity $k$ from $s$ to $t$. This algorithm takes $O(\min(k, m^{1/2}) (n + m))$ time.
**Second Interpre...
Mostly, if we say a graph is dynamic, then we assume updates that insert and
delete the edges. This
50.
Fun fact about sync_with_stdio Consider this code:
```
#include <iostream>
using namespace std;
int main () {
ios::sync_with_stdio(false);
ios::sync_with_stdio(true);
}
```
In GCC, are the C++ streams like `std::cout` etc then synchronized with the corresponding C methods like `printf`?
<spoiler summary="Answer">
No — the second `sync_with_stdio` has no effect at all.
There is no trick here: the booleans aren't being interpreted as pointers or anything like that. There is simply no code to handle turning synchronization back on.
<spoiler summary="Implementation of sync_with_stdio">
```
bool
ios_base::sync_with_stdio(bool __sync)
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 49. Underspecification of ios_base::sync_with_stdio
bool __ret = ios_base::Init::_S_synced_with_stdio;
// Turn off sync with C FILE* for cin, cout, cerr, clog iff
// currently synchronized.
if (!__sync && __ret)
{
// Make sure the standard streams are constructed.
i...
member functions, // but don't deallocate all memory by calling operator delete
. buf_cout_sync
51.
Some method for solving RMQ Hi!
Here are some implementations for solving RMQ (Tarjan’s algorithm) (Range Maximum / Minimum Query).
It’s very simple to implement and its time complexity is $O((n + q) \cdot a(n))$, $a()$ stands for Akerman inverse function used in DSU.
**Problem:**
Given array $a$ of $n$ integers, and $q$ queries, for each query print the maximum value in range $[L, R]$.
**Solution:**
We need an array of vectors, called assigned. $assigned[r]$ contains queries that their $R$ is $r$. When getting queries, push each query in $assigned[R]$. We need a dsu, first $par_i$ is $i$. We need a stack, named $st$.
~~~~~
For i from 0 to n, do:
While st is not empty and a[st.top] <= a[i]
Set i parent of st.top in dsu and pop this element from st.
Push i to st
For each query assigned to i
The answer to this query is a[root of L of this query in DSU].
~~~~~
<spoiler summary="Code here.">
~~~~~
// God & me
// "Someone like you"?! Unbelievable ....
) { comp = comp_; calcBallotNumbers(); buildInnerBlockTable(); } ~DirectRMQ() {
delete, ; while(1 << stHeight < blocks) ++ stHeight; delete[] blockTypes; delete[]
sparseTable;
52.
Why is std::deque, std::stack, and std::queue slow and memory inefficient? ## Sidetrack
It has been two years since I wrote an educational blog. I've been inactive in the CP community recently as I've shifted my focus to internships. Recently, I observed some interesting behaviour with `std::queue` while profiling an application during my internship, which led me to writing this blog.
Most of the images below are taken from the C++ standard https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/n4950.pdf
## Queues and stacks
Queues and stacks do not actually provide any new implementations... They are just wrappers around a container (which is `std::deque`) by default.
![C++ standard st...
delete[] map; map = new_map; map_size = new_size; }
53.
Codeforces LATOKEN Round 1 (Div. 1 + Div. 2) Editorial [problem:1534A]
Author: [user:Crackersamdjam,2021-06-13]
<spoiler summary="Hint 1">
Let's say you know the colour of the first square, what colours can you figure out next?
</spoiler>
<spoiler summary="Hint 2">
Colour it like a chessboard, but there's more than one possible chessboard!
</spoiler>
<spoiler summary="Hint 3">
Brute force the color of the first square!
</spoiler>
<spoiler summary="Tutorial">
[tutorial:1534A]
</spoiler>
<spoiler summary="Solution">
[submission:119400830]
</spoiler>
[problem:1534B]
Author: [user:Dormi,2021-06-13]
<spoiler summary="Hint 1">
Consider the contribution of each pillar to the answer.
</spoiler>
<spoiler summary="Hint 2">
How does doing the operation on a pillar change the contribution to the answer?
</spoiler>
<spoiler summary="Hint 3">
You only want to do an operation on a pillar if the top cell contributes 2 to the answer.
</spoiler>
<spoiler summary="Tutorial">
[tutorial:1534B]
</spoiler>
...
If a special node can reach another special node, you can delete that
Tutorial of Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)
54.
Duality in linear programming. Part 2 — in competitive programming Hi everyone!
Previously, I wrote a [general introduction](https://codeforces.me/blog/entry/105049) to linear programming duality. In this blog, I would like to write about several problems that could be solved with this technique. Familiarity with the first blog, or general knowledge of dual problems and how to construct them is generally expected to navigate in this one.
Thanks to [user:brunovsky,2022-08-09] and [user:Golovanov399,2022-08-09] for problem suggestions!
And particularly special thanks to [user:WeakestTopology,2022-08-09] for problem suggestions and all insightful discussions on the topic!
[cut]<br>
### Dual construction mnemonics
To simplify the construction of dual problems, let's recall the correspondence between constraints/variables in primal and dual problems.
<spoiler summary="LP duality mnemonics">
Standard definition of LP dual problem looks like this:
$$\begin{gather}
\max\limits_x & c^\top x & \color{red}{\text{(maximization)}} & \ove...
It means that for each pair $(j, i)$, we either we delete the $j$-th vertex in
the first part
55.
You can do it, too! Introduction
-------------------------------
So, I set myself [that challenge](https://codeforces.me/blog/entry/81383) to retire as a red coder before 24.09.2020... and I failed **miserably**. At least I am less delayed than most civil infrastructure projects.
This blog will be a recap of this _short_ challenge with a mixture of some tips on practicing (for all levels!), some random life advice and, of course my bad sense of humour. It is dedicated to all those who aren't wonderkids, go from failure to failure and feel like banging their head into a wall during most of their competitive programming journey. Whatever your goal is, I'd like to strengthen your beliefs — you can do it!
How it all started
------------------
My skill level has been in constant stagnation for years. I've always thought that I'm just not talented enough to be a grandmaster. Although I've been red twice in the past, it was quite lucky and the next contests were solid $-137$ and $-189$ so th...
56.
think-cell Round 1 Editorial Thank you for your participation! I hope you liked atleast one problem from the set (:
[problem:1930A]
Idea: [user:satyam_343,2024-02-18]
Editorial: [user:Non-origination,2024-02-18]
<spoiler summary="Hint 1">
Selecting the smallest two elements on the whiteboard is a good choice in the first move.
</spoiler>
<spoiler summary="Solution">
Let $b$ denote the sorted array $a$. Assume that $b$ contains only distinct elements for convenience. We prove by induction on $n$ that the maximum final score is $b_1 + b_3 + \ldots + b_{2n-1}$.
For the base case $n = 1$, the final and only possible score that can be achieved is $b_1$.
Now let $n > 1$.
**Claim**: It is optimal to choose $b_{1}$ with $b_{2}$ for some move.
<spoiler summary="Proof">
Suppose that in some move, $b_{1}$ is choosen with $b_i$ and $b_{2}$ is choosen with $b_j$, for some $2 < i,j < 2n, i \not = j$.
The contribution to the score according to these choices is $\min(b_{1}, b_{i}) + \min(b_{2...
Tutorial of think-cell Round 1
57.
Codeforces Round 979 Editorial Below is a timeline of the changes made to the round from start to finish. I hope this can depict what setting a contest is actually like for aspiring problemsetters. Please give me feedback about this in the comments. What else about the round would you like to know? Was this helpful?
<spoiler summary="Round Timeline">
To denote problems, I will use quotes to denote the number of problems proposed for that postion so far (e.g. A' represents the first A proposed for the round, A'' represents second A proposed, etc). If the problem is in the final set, then it will be **bolded**. For dates, I will use the american standard notation (mm/dd).
Also, I will not go in detail about why problems were rejected/unused because they might appear in the future.
8/11: [contest:1998] has just concluded and [user:sum,2024-10-18] has shipped himself off to college and won't have time due to <s>attending frat parties</s> his studies. I invite [user:vgoofficial,2024-10-18] to problemset with m...
. Since there are no overlapping elements, we may delete each of the arrays
$c_1, c_2, \ldots, c_k
Tutorial of Codeforces Round 979 (Div. 2)
58.
[Tutorial] Generating Functions in Competitive Programming (Part 2) Welcome to Part 2 of my tutorial on generating functions. The [first part](https://codeforces.me/blog/entry/77468) focused on introducing generating functions to those without any background in generating functions. In this post, I will demonstrate a few applications of generating functions in CP problems. Let us start with some relatively straightforward examples.
Note: Unless stated otherwise, all computations are done modulo a convenient prime (usually $998244353$). Also, $[n]$ denotes the set $\\{1,2,...,n\\}$.
### Blatant Applications in Counting Problems
**Problem.** [AGC 005 Problem F](https://atcoder.jp/contests/agc005/tasks/agc005_f) You have a tree $T$ with $n$ vertices. For a subset $S$ of vertices, let $f(S)$ denote the minimum number of vertices in a subtree of $T$ which contains all vertices in $S$. For all $1 \le k \le n$, find the sum of $f(S)$ over all subsets $S$ with $|S| = k$.
Constraints: $n \le 2 \cdot 10^{5}$.
<spoiler summary="Solution">
First, ...
59.
Global Round 20 Editorial Hope that everyone enjoyed the round. Feel free to ask questions in the comments if you do not understand any part of the editorial
[problem:1672A]
Author: [user:errorgorn,2022-04-23]
<spoiler summary="Hints">
<spoiler summary="Hint 1">
No matter what move each player does, the result of the game will **always** be the same.
</spoiler>
<spoiler summary="Hint 2">
Count the number of moves.
</spoiler>
</spoiler>
<spoiler summary="Tutorial">
Let us consider the ending state of the game. It turns out that at the ending state, we will only have logs of $1$ meter. Otherwise, players can make a move.
Now, at the ending state of the game, we will have $\sum\limits_{k=1}^n a_k$ logs. And each move we increase the number of logs by exactly $1$. Since we started with $n$ logs, there has been exactly $(\sum\limits_{k=1}^n a_k) - n$ turns.
Alternatively, a log of length $a_k$ will be cut $a_k-1$ times, so there will be $\sum\limits_{k=1}^n (a_k-1)$ turns.
If the...
decrement both $i$ and $j$ 3. Otherwise, we delete an occurance of $a_i$ in
$S$ and decrement $i$. If, simply delete each section individually, the worst answer that we can get is
$K$. Also, there is no
Tutorial of Codeforces Global Round 20
60.
Codeforces Round 1064 (Div. 1, Div. 2) Editorial [2166A — Same Difference](https://codeforces.me/contest/2166/problem/A)
idea & solution: [user:le0n,2025-11-17]
<spoiler summary="Tutorial">
It can be observed that $s_n$ will not change throughout the operations, therefore, for the final string to have every character the same, every character must be equal to $s_n$.
To change every character to $s_n$, we can iterate over all characters from right to left, repeatedly setting $s_{i-1}\leftarrow s_i$ if $s_{i-1}\neq s_n$. Through this, we can need one operation for every character not equal to $s_n$, which is also obvious as a lower bound.
Time complexity: $O(n)$.
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
char s[100005];
int main()
{
int n, t, i, m;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
scanf("%s", s + 1);
m = 0;
for(i = 1; i < n; i++)
m += (s[i] != s[n]);
printf("%d\n", m);
}
return 0;
}
~~~~~
</spoiler>
...
Therefore, we can choose any $a_i=1$ and the closest $a_i=2$, and simply delete
them from the graph.
Tutorial of Codeforces Round 1064 (Div. 1)
Tutorial of Codeforces Round 1064 (Div. 2)
61.
I stuggled with A and B in the last div 2, and how YOU can learn from it (CF 968 Div. 2) I noticed that sometimes I do some horrible things while solving easy problems. If you struggled with the first $2$ problems from the previous round, you might also have made some huge mistakes that should not happen.
**The point of this blog:** I will show you my terrible ways of approaching each of these problems and you will be able to see all of the stupid things that I did. Then I will show you the proper way to approach the tasks, and then you can think which approach is more similar to yours, and maybe it will help you to improve.
### Problem A. Turtle and Good Strings
#### My approach during contest (terrible way)
- I open the statement, incorrectly rephrase it: **you are given a string, you should divide it into several substrings, so in each substring the first and the last letters are different**
- I think of a dp solution, then I sloppily prove that I should take no more than $2$ substrings. I submit my [non-dp solution](https://codeforces.me/contest/2003/submi...
delete local maximum, and the second player cannot delete local minimum, but
they never want to do
62.
Complaints on Comments <img src="/predownloaded/f0/ff/f0ff581246db486e2d6a28398f591770f01a0747.png" style="width: 400px; float: right; margin: 0 1em 1em 1em;"/>
Hello!
Now, if you've downvoted a comment, you can report it. You should do this if you're certain that one of the rules is being violated. Currently, the list of rules is as follows:
* <b>Hate/Offensive</b>: The publication contains signs of hatred, racial slurs, derogatory language or intolerance. Please maintain a respectful tone; critical comments should include thoughtful reasoning.
* <b>Threats/Harassment</b>: Content that contains explicit threats or harassment, including cyberbullying or stalking, is subject to censorship. Codeforces aims to create a safe and respectful environment for its users.
* <b>Vi...
63.
Codeforces Round #292 Editorial Thanks to [user:johnathan79717,2015-03-10] fo polish my words.
#### [515-A Drazil and Date](http://codeforces.me/problemset/problem/515/A)
If Drazil chooses the shortest path from (0,0) to (a,b), it takes $|a| + |b|$ steps.
So we know that all numbers less than $|a| + |b|$ are impossible to be the number of steps that Drazil took.
Now consider when the number of steps is not less than $|a| + |b|$.
When Drazil arrives at $(a,b)$, he can take two more steps such as $(a,b)$ -> $(a,b+1)$ -> $(a,b)$ to remain at the same position.
So we know that for all $s$ such that $s \geq |a| + |b|$ and $(s - (|a| + |b|)) \% 2 = 0$, there exists a way for Drazil to get to $(a,b)$ in exactly $s$ steps.
The last part we should prove is that it's impossible for Drazil to arrive at (a,b) in exactly $s$ steps when $(s - (|a| + |b|)) \% 2 = 1$.
We can color all positions $(x,y)$ where $(x+y) \% 2 = 0$ as white and color other points as black.
After each step, the color of the p...
Tutorial of Codeforces Round 292 (Div. 2)
64.
Codeforces Round 901 (Div. 1, Div. 2) Editorial ## [problem: 1875A]
<spoiler summary="Tutorial">
We can use one tool each time the timer reaches to $1$, then the answer will be $\sum_{i=1}^n \min(a - 1, x_i) + b$. This can prove to be optimal. Because for each tool, if we use it when the timer is $c$, its contribution to the answer is $\min(x_i, a - c)$. We can't use the tool when the timer is less than or equal to $0$ because the bomb will explode before that, so $c=1$ is the optimal.
Time complexity: $O(n)$ per test case.
Memory complexity: $O(1)$ per test case.
</spoiler>
<spoiler summary="Code">
```c++
#include<bits/stdc++.h>
using namespace std;
int n = 0, a = 0, b = 0;
long long ans = 0;
inline void solve(){
scanf("%d %d %d", &a, &b, &n);
ans = b;
for(int i = 0, x = 0 ; i < n ; i ++){
scanf("%d", &x);
ans += min(a - 1, x);
}
printf("%lld\n", ans);
}
int T = 0;
int main(){
scanf("%d", &T);
for(int i = 0 ; i < T ; i ++) solve();
return 0;
}
```
</spoiler>
## [probl...
satisfies $x < \text{MEX}(a)$, and delete all $x$ from $a$, the
$\text{MEX}(a)$ will become $x$., )$ becomes $0$, if we don't delete all of $x$, $\text{MEX}(a)$ won't change, we
can also put this, )=i$, and we haven't delete any $x$ satisfying $x < i$,the minimum value of $m$., So before $\text{MEX}(a)$ reaches $0$, the $x$ we delete is non-increasing.
Tutorial of Codeforces Round 901 (Div. 1)
Tutorial of Codeforces Round 901 (Div. 2)
65.
Разбор Codeforces Round 1076 (Div. 3) Thank you for participating! Special thanks to [user:China001,2026-01-25] and [user:daki-sa,2026-01-25] for an alternative solution to problem H.
[problem:2193A]
- Idea: [user:KluydQ,2026-01-25]
- Solution + editorial: [user:KluydQ,2026-01-25]
<spoiler summary="Hint">
Each operation increases the sum by exactly $x$, regardless of the index to which the operation was applied.
</spoiler>
<spoiler summary="Solution">
Let $A$ be the initial sum of the array $a$. Each operation adds $x$ to $A$. We need to check whether $A$ can become equal to $S$. First, $S$ must not be smaller than $A$. Second, their difference must be divisible by $x$, that is, $x$ must divide $(S - A)$.
</spoiler>
<spoiler summary="Code">
```
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while( t -- )
{
int n, s, x;
cin >> n >> s >> x;
int a[n + 5], sum = 0;
for( int i = 1; i <= n; i ++ ) cin >> a[i], sum += a[i];
if( sum > s ||...
from $v$ to $u$. We compute all values of $f$ once, and using BFS we delete
vertices with $f=0$. We, has a child $u$ with $dp_u = 3$ and $a_u = 1$. That is, we can delete $u$
before $v$, thereby changing, vertices contributing to $v$. It can be understood that we need to delete a
vertex with $f(v)=0$. The, - $dp_v = 0$ if vertex $v$ cannot be deleted. - $dp_v = 1$ if to delete vertex
$v$, its parent
Tutorial of Codeforces Round 1076 (Div. 3)
66.
The most disgusting contest I participated in: The 2021 ICPC Asia Regionals Online Contest (I) Just a few hours ago, The 2021 ICPC Asia Regionals Online Contest (I) was held on https://pintia.cn/. This contest(and the next on 26th) will determine the WHOLE Asia-East Division‘s quota. And how fantastic(according to some coaches) of these problems in this online contest? I upload the statement on GDrive and you can preread it here: [aec-online-i-2021.pdf](https://drive.google.com/file/d/1g5AfTLL8-9JtxbpKGv9VtO-h2_kAWqUs/view?usp=sharing)
I should clarify something here: This contest doesn't have a clarification function, and some problems are from Huawei. Guess which they are!
<spoiler summary="Some fantastic part of problems">
Health tips: If you just participated in this contest and your blood pressure is high, please don't continue reading.
<spoiler summary="A">
What is exactly the finish time of one request? `arrival_time + processing_time` or `arrival_time + processing_time + 1`? As there is no clarification, you can only enumerate it. Enumerate question meaning ma...
67.
Latest innovations on Codeforces [January 2021] Hello everyone!
The Codeforces team is working hard every day to improve the platform. Here's a quick overview of the latest innovations.
### Mashups deletion
Until recently, there was no way on Codeforces to completely remove mashups you created. They stayed "hanging" in the interface and could get in the way if there were a lot of them.
Now you can delete the mashups you created. To do this, go to the edit page:
At the bottom of the page there will be a delete button:
Deleting a mashup is reversible, meaning you can restore it if necessary. You can view deleted mashups by clicking on the link below the table with mashups.
### Other innovations
- Added filter by contest format (IOI or ICPC) in mashups and gyms.
- Compiler versions updated: Python 2 up to 2.7.18, Python 3 up to 3.9.1, Ruby up t...
could get in the way if there were a lot of them. Now you can delete the
mashups you created. To, , At the bottom of the page there will be a delete button:, Now you can delete the mashups you created. To do this, go to the edit page:
68.
Codeforces Round #326 (Editorial) ### Div.2 A (Author: [user:Haghani,2015-10-01])
Idea is a simple greedy, buy needed meat for $i-th$ day when it's cheapest among days $1, 2, ..., n$.
So, the pseudo code below will work:
~~~~~
ans = 0
price = infinity
for i = 1 to n
price = min(price, p[i])
ans += price * a[i]
~~~~~
Time complexity: $\mathcal O(n)$
[C++ Code](http://ideone.com/fa7rF5) by [user:amd,2016-03-05]
[Python Code](http://ideone.com/Sh0hPp) by [user:Haghani,2015-10-15]
[Python Code](http://ideone.com/5J6Rew) by [user:Zlobober,2015-10-15]
### Div.2 B (Author: [user:amd,2016-03-05])
Find all prime divisors of $n$. Assume they are $p_1, p_2, ..., p_k$ (in $\mathcal O(\sqrt n)$). If answer is $a$, then we know that for each $1 \leq i \leq k$, obviously $a$ is not divisible by $p_i^2$ (and all greater powers of $p_i$). So $a \leq p_1 \times p_2 \times ... \times p_k$. And we...
O(20)$. And then delete the extra values (more than 10)., First of all delete all edges with destructing time greater than $x$. Now, if
there is more than
Tutorial of Codeforces Round 326 (Div. 1)
69.
Codeforces Round #305 Editorial ### [problem:548A]
Consider characters of this string are number 0-based from left to right. If $|s|$ is not a multiply of $k$, then answer is "NO". Otherwise, let $len = \frac{|s|}{k}$. Then answer is "Yes" if and only if for each $i$ that $0 \leq i < |s|$, $s_i = s_{(i/len) * len + len - 1 - (i \% len)}$ where $a\%b$ is the remainder of dividing $a$ by $b$.
Time complexity: $\mathcal O(|s|)$.
[C++ Code](http://ideone.com/HpYQHZ) by [user:PrinceOfPersia,2015-05-24]
[Python Code](http://ideone.com/A6yhex) by [user:Haghani,2015-05-24]
[Python Code](http://ideone.com/PHiL7p) by [user:Zlobober,2015-05-24]
### [problem:548B]
Consider this problem: We have a binary sequence $s$ and want to find the maximum number of consecutive 1s in it. How to solve this? Easily:
~~~~~
ans = 0
cur = 0
for i = 1 to n:
if s[i] == 0
then cur = 0
else
cur = cur + 1
ans = max(ans, cur)...
between $v$ and $u$. Delete this edge and solve the problem for the rest of
the edges (with the, You can handle this add/delete edge requests and find odd vertices with a
simple `set`. So,
Tutorial of Codeforces Round 305 (Div. 2)
70.
Codeforces Round #299 Editorial ### [problem:535A]
First of all check if $n$ is one of the values $0, 10, 11, …, 19$. Then, let’s have array $x[]$ = {"", "", "twenty", "thirty", …, "ninety"} and $y[]$ = {"", "one", …, "nine"}.
Let $a = \frac{n}{10}$ and $b = n\ modulo\ 10$.
If $n$ is not one of the values above, then if $a=0$, print $y[b]$, else if $b=0$ print $x[a]$ otherwise print $x[a]$-$y[b]$.
Time complexity: $O(1)$
[Code](http://ideone.com/mytb2L) by [user:SoroushE,2015-04-02]
[Another Code](http://ideone.com/CqgNe5) by [user:PrinceOfPersia,2015-04-05]
[Another Code](http://ideone.com/dqiMNL) by [user:Haghani,2015-04-08]
[Python Code](http://ideone.com/6tZmNF) by [user:Zlobober,2015-04-04]
### [problem:535B]
Sol1: Consider $n$ has $x$ digits, $f(i) = $ decimal representation of binary string $i$, $m$ is a binary string of size $x$ and its $i-th$ digit is 0 if and only if the $i-th$ digit of $...
Tutorial of Codeforces Round 299 (Div. 2)
Tutorial of Codeforces Round 299 (Div. 1)
71.
[Tutorial] A powerful representation of integer sets Hello, Codeforces!
This blog is heavily inspired by [user:TLE,2020-10-22]'s blog [using merging segment tree to solve problems about sorted list](https://codeforces.me/blog/entry/49446). I don't know exactly how well known this data structure is, but I thought it would be nice to share it anyway, along with some more operations that are possible with it.
What it can do
------------------
We want a data structure that we can think of a set/multiset of **non-negative integers**, or even as a sorted array. We want to support all of the following operations:
1. Create an empty structure;
2. Insert an element to the structure;
3. Remove an element from the structure;
4. Print the $k$'th smallest element (if we think of the structure as a sorted array $a$, we are asking for $a[k]$);
5. Print how many numbers less than $x$ there are in the set (similar to lower_bound in a std::vector);
6. Split the structure into two: one containing the $k$ smallest elements, and the other ...
can delete either `l` or `r`, because they are now redundant: we only need one
of them., ' is a leaf if (MULTI) l->cnt += r->cnt; delete r; return l; } l->l =
merge(l->l, r, ); } ret->update(), x->update(); } if (!x->cnt) delete x, x = NULL; // 'cnt' is
always positive, ->r); delete x; } }
72.
Dynamic convex hull implementation I finally figured out a nice way to implement dynamic convex hull with a reasonable constant factor! I expect this will be "well known in China" though.
Consider the problem of finding [nested convex hulls](https://en.wikipedia.org/wiki/Convex_layers) in $O(n\log^2{n})$. The simplest way I know of is to make a convex hull data structure that supports point deletions, which is what I do here. It should be possible to extend this implementation to handle insertions as well.
This implementation is based on this [paper](https://www.sciencedirect.com/science/article/pii/002200008190012X) by Overmars and van Leeuwen that describes a data structure for online fully dynamic convex hull in $O(\log^2{n})$ per operation. Directly implementing that is complicated and has a bad constant factor, so we'll do it a bit differently using ideas from [user:FizzyDavid,2020-04-13]'s [solution](https://codeforces.me/blog/entry/72611?#comment-569105) to [1270H](https://codeforces.me/contest/1270/probl...
73.
Build Your Own Treap! Hallo codeforcers,
As some of you may know, the almighty treap is one of the most versatile data structures out there.
It can serve as an ordered + indexed set, a lazy segment tree, and even a dynamic array — all at the same time.
However, its immense versatility comes at a cost: there are so many different variations that making a one-template-fits-all is impossible. Alas, is fate such that we must write it from scratch — every, single, time?
Fear no more! I present to you [BYOT: Build your own treap!](https://caterpillow.github.io/byot)
Now, you can summon a hand-crafted treap to overkill your Div2D in mere _seconds_. Gone are the days of using your brain to come up with a clever solution — just go to the site, click on what you need, and enjoy your AC! To see how it is used, you can see some example implementations below.
If you find any bugged configurations or have any suggestions, please leave a comment under this blog. Be warned, no rating refunds will be issued...
- find, insert, delete and modify (by index), - find, insert, delete and modify (by key)
74.
Spectral::Cup 2026 Round 2 (Codeforces Round 1100, Div. 1 + Div. 2) Editorial Thank you for participating in our round! We hope you enjoyed the problems as much as we enjoyed preparing them.
<spoiler summary="Rate the contest!">
<spoiler summary="Quality">
-
Absolute Cinema contest
-
Excellent contest
-
Good contest
-
Average contest
-
Bad contest
-
Horrible contest
</spoiler>
<spoiler summary="Difficulty">
-
Trivial contest
-
Easy contest
-
Average contest
-
Hard contest
-
Impossible contest
</spoiler>
</spoiler>
[problem:2229A]
Idea by: [user:Intellegent,2026-05-23]
Prepared by: [user:Intellegent,2026-05-23]
Editorial by: [user:reirugan,2026-05-23]
<spoiler summary="Hint 1">
Let $y$ denote the final position of all of the slimes. Then it is optimal to choose $x = y$ for every operation.
</spoiler>
<spoiler summary="Hint 2">
Let $\mathrm{mn}$ denote the minimum value in $a$, a...
and only if we can delete all children of $n$ excluding the one with $x$ in
its subtree. In other
75.
Educational Codeforces Round 157 Editorial [problem:1895A]
Idea: [user:BledDest,2023-11-04]
<spoiler summary="Tutorial">
[tutorial:1895A]
</spoiler>
<spoiler summary="Solution (awoo)">
~~~~~
for _ in range(int(input())):
x, y, k = map(int, input().split())
if y < x:
print(x)
else:
print(y + max(0, y - x - k))
~~~~~
</spoiler>
[problem:1895B]
Idea: [user:fcspartakm,2023-11-04]
<spoiler summary="Tutorial">
[tutorial:1895B]
</spoiler>
<spoiler summary="Solution (fcspartakm)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
inline void read() {
cin >> n;
a.clear();
for (int i = 0; i < 2 * n; i++) {
int x;
cin >> x;
a.pb(x);
}
}
inline void solve() {
sort(all(a));
vector<pair<int, int> > pts;
for (int i = 0; i < n; i++) {
pts.pb(mp(a[i], a[i + n]));
}
int ans = 0;
for (int i = 1; i < n; i++) {
ans += abs(pts[i].ft - pts[i - 1].ft) + abs(pts[i].sc - pt...
); delete t; }, ->r, x); return fix(t); } treap tnew = merge(t->l, t->r); delete t; return
tnew; }
76.
Codeforces Round #318 [RussianCodeCup Thanks-Round] Editorial [Div2B — Bear and Three Musketeers](http://codeforces.me/contest/574/problem/B)
Warriors are vertices and "knowing each other" is an edge.
We want to find connected triple of vertices with the lowest sum of degrees (and print $sum-6$ because we don't want to count edges from one chosen vertex to another).
Brute force is $O(n^3)$.
We iterate over all triples $a,b,c$ and consider them as musketeers.
They must be connected by edges (they must know each other).
If they are, then we consider sum of their degrees.
We must notice that there is low limit for number of edges.
So instead of iterating over triples of vertices we can iterate over edges and then iterate over third vertex.
It gives us $O(n^2 + n m)$ and it's intended solution.
To check if third vertex is connected with other two, you should additionally store edges in 2D adjacency matrix.
It's also possible to write it by adding "if" in right place in brute forces to get $O(n^2 + nm)$.
Check it out in [cod...
77.
How randomized solutions can be hacked, and how to make your solution unhackable Hi Codeforces! In Round 507 earlier today, a large number of "mostly correct" randomized solutions on [problem:1039B] were hacked. I wanted to write a quick explanation of how it's possible to hack these, as well as a guide on how to write your code so that you aren't vulnerable to getting hacked.
First to go over the solution quickly (skip down a few paragraphs if you already know the solution): one can use binary search to reduce the range of possible locations for the train to a constant multiple of $K$, such as $6K$. Just make sure to expand out both ends of the range by $K$ after every iteration. Once the range is at most $6K$, one can repeat the following:
1) Make a random guess out of the remaining numbers. The probability of success is at least $\frac{1}{6K}$.
2) Binary search again until the range is at most $6K$ again. It turns out this only takes one query, since after our previous guess our $6K$ range will become an $8K$ range, and a single query will reduce this t...
program since we never call `delete`, but since it's just one variable it's
not a big deal.
78.
Codeforces Round 887 (Div 1, Div 2) Tutorial We hope you enjoyed these problems :) This contest has been in the works for almost a year.
<spoiler summary = "About the Authors">
This round was mostly made possible by problemsetters from the [CerealCodes](https://www.cerealcodes.org/) initiative!
CerealCodes is an organization based in the United States dedicated to running high quality competitive programming contests. You can check out our previous contest [here](https://codeforces.me/gym/103886).
</spoiler>
**UPD: D1D Editorial have been updated**
**UPD 2: D1D Editorial now has images by [user:EmeraldBlock,2023-08-01]. As an apology gift for being so slow, the image generator is programmatic and available [here](https://artofproblemsolving.com/texer/codeforces).**
#### [problem:1853A]
Problem Credits: [user:buffering,2023-06-02]
Analysis: [user:buffering,2023-06-02]
<spoiler summary="Hint 1">
To make $a$ not sorted, we just need to pick one index $i$ so $a_i > a_{i + 1}$. How do we do this?
</spoiler...
Tutorial of Codeforces Round 887 (Div. 1)
Tutorial of Codeforces Round 887 (Div. 2)
79.
1/phi Halving in Interactive Tree Problems Thanks to [user:toxicpie9,2025-04-22] for proofreading and emotional support.
Recently, I was thinking about JOISC 2025 Space Thief. And there is a part where you need to do divide and conquer on a tree, where you need to split the edges of the tree into two components where the edges are both connected.
Basically, we consider an interactive problem on a tree where there is a hidden edge. We are allowed to ask queries of the form $(v,N_v)$ where $v$ is a vertex of the tree and $N_v$ is a set of neighbouring edges of $v$. Then the query returns to us whether the hidden edge is in the subtree of one of $N_v$ when we root the tree at $v$.
We maintain a set of edges that the hidden edge can be in. In each query, we try to split the set of edges into two parts and ask a query to separate them.
In the worst case, we replace the set of edges by the larger component.
Let $R$ be the maximum ratio of the larger component.
In [this blog](https://codeforces.me/blog/entry/120446)...
80.
Editorial of Educational Codeforces Round 13 ### [problem:678A]
The problem was suggested by Abdrakhman Ismail [user:Ismail_A,2016-06-16].
We should find minimal $x$, so $x\cdot k>n$. Easy to see that $x=\lfloor\frac nk\rfloor+1$.
To learn more about floor/ceil functions I reccomend the book of authors Graham, Knuth, Patashnik
"Concrete Mathematics". There is a chapter there about that functions and their properties.
<spoiler summary="С++ solution">
~~~~~
li n, k;
bool read() {
return !!(cin >> n >> k);
}
void solve() {
cout << (n / k + 1) * k << endl;
}
~~~~~
</spoiler>
Complexity: $O(1)$.
### [problem:678B]
The problem was suggested by Arthur Jaworski [user:KingArthur,2016-06-16].
Two calendars are same if and only if they have the same number of days and starts with the same
day of a week. So we should simply iterate over years and maintain the day of a week of January, 1st
(for example). Easy to see that the day of a week increases by...
Tutorial of Educational Codeforces Round 13
81.
[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...
takes $O(\log n)$ time to delete it from the set. In the undo operation, as we
iterate $k$ in
82.
[Tutorial]Using Segment Trees to solve Dynamic Programming problems Both segment trees and dynamic programming are common topics in competitive programming. Sometimes, they even appear together. In this blog, we will mostly use segment trees as a black-box. As such, it is not necessary (though it is highly recommended) to know segment trees to understand this blog. Let's begin.
###Longest Increasing Subsequence(LIS)
_"You are given an array $v$ containing $N$ integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one._
_A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements."_
This problem is most often solved using binary search. There are countless tutorials about this method, so I will not discuss it in detail. However, there exists a more general way to solve it using segment trees.
Since we only care about the order of the elements and not a...
83.
Codeforces Round 1113 (Div. 2) Editorial [problem:2248A]
<spoiler summary="Hint1">
Alice deletes a `0`, Bob deletes a `1`. Which occurrence should each of them choose?
</spoiler>
<spoiler summary="Hint2">
Deleting a `0` makes the string lexicographically larger. Does the position of that `0` matter?
</spoiler>
<spoiler summary="Hint3">
After Alice's move, Bob sees one string and deletes a `1`. What is his best move?
</spoiler>
<spoiler summary="Solution">
Deleting a `0` at an earlier position is always better for Alice. Indeed, compare deleting the `0`s at positions $i < j$: the two results agree before position $i$, and at position $i$ the first result has `1` while the second still has `0`. So Alice deletes the **first** `0`.
After that, Bob wants to minimize the string. By the symmetric argument he deletes the **first** `1` of the remaining string, which is the first `1` of the original string, since deleting a `0` never changes the order of the `1`s.
Hence the answer is the original string with it...
Tutorial of Codeforces Round 1113 (Div. 2)
84.
Codeforces Global Round 4 Editorial [tutorial:1178A]
<spoiler summary="Code">
```
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N; cin >> N;
vector<int> A(N); for (int&a:A) cin >> a;
vector<int> P{1};
int rest = 0, cur = A[0];
for (int i = 1; i < N; ++i) {
if (A[i] <= A[0]/2) {
cur += A[i];
P.push_back(i+1);
} else {
rest += A[i];
}
}
if (cur > rest) {
cout << P.size() << endl;
for (int i = 0; i < P.size(); ++i) cout << P[i] << " \n"[i==P.size()-1];
} else {
cout << 0 << endl;
}
}
```
</spoiler>
[tutorial:1178B]
<spoiler summary="Code">
```
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
int main() {
string S; cin >> S;
ll a = 0, b = 0, c = 0;
for (int i = 0; i < S.size(); ++i) {
if (S[i] == 'o') {
b += a;
} else if (i > 0 && S[i-1] == 'v')...
--; } //~Upper() { delete []V; } void clear() { i = s = 0; t = 0; }
85.
Editorial for Round 850 #### [A. Monsters (easy version)](https://codeforces.me/contest/1785/problem/A)
Notice that this is equivalent to maximizing the damage done by the operation of type $2$. Let us consider the case when there are 2 monsters with health $h$, and $h+k$, and no monsters with health in $(h, h+k)$. Then reducing the monster with health $h + k$ to $h + 1$ cannot make the final outcome worse. You can prove it by noticing that the operation of type $2$ can only happen $h$ times if the health of the monster is above $h + 1$. Now we get monsters with health in such a way, that there exists $H$, where there is monster with health from $1$ to $H$. Then one move of operation $2$ can kill the remaining monsters. So you only need to simulate the above process, and find out how many moves of type $1$ were required to do it.
#### [B. Letter Exchange](https://codeforces.me/contest/1785/problem/B)
Let us consider a graph with $3$ nodes $w, i, n$. For a word of type $wii$ add an edge from $i$ to...
here is less than $n$. Therefore at each point we can only delete the largest
element less than $n, we do a median operation, they delete the current element, and move outwards.
This also implies the, We claim, you can delete any subset of these numbers, as long as the length of
every deleted
86.
Codeforces Round 1073 (Div. 1, Div. 2) Editorial Special thanks to [user:reirugan,2026-01-17], [user:weirdflexbutok,2026-01-17] and [user:intellegent,2026-01-17] for helping with editorials.
[problem:2191A]
- Idea: [user:nifeshe,2026-01-17]
- Solution: [user:nifeshe,2026-01-17]
- Editorial: [user:reirugan,2026-01-17]
<spoiler summary="Hints">
<spoiler summary="Hint 1">
Without the "after sorting condition", there are only two ways to color the cards.
</spoiler>
</spoiler>
<spoiler summary="Solution">
Without the "after sorting condition", there are only two ways to color the cards. We must have that $a$ is alternating in color.
Without loss of generality, color the odd indices red and the even indices blue. This uniquely colors every card. Now, let's sort the array $a$, while also keeping track of the colors; one way to do this is by sorting it as a vector of pairs. Then we simply have to verify that no two adjacent cards are the same color.
Alternatively, you can use the fact that $a$ is a permutation, ...
$n - 2 \times (j - i)$ as long as there are sufficient $)$ to delete after $j$., Greedily delete characters. You will always end up with an RBS if, Why isn't $P(v)$ always $n - 1$? Specifically, when can we delete, index after the position. Since we only delete $($ after $)$, all the indices'
balances must be, // Delete (v, p) // Add (v, prev) sign *= -1; if(v > par) sign *= -1, Root the tree at $n + 1$ again, we delete the $i$-th edge $v \rightarrow p_v$,
and replace it with, We can show that if we can have $j - i$ $($ brackets after position $j$ and we
delete them, we will, Why isn't $P(v)$ always $n - 1$? Specifically, when can we delete vertex $n -
1$?
Tutorial of Codeforces Round 1073 (Div. 1)
Tutorial of Codeforces Round 1073 (Div. 2)
87.
Sad story about rescheduling on the Round 383 Good afternoon.
Sorry. Unfortunately, today (on Friday) we can't run the round 383 :-(
In short, this is because of technical reasons. For those interested in a more detailed description option.
On Thursday night I got sms. It was written that on server for DB backups free HDD space is less than 10%. This server stores three copies of the database over the last three days. It has 2TB drive and Codeforces database over 600GB now.
Since the next day I had planned to spend on the train on the way to NEERC, I decided to delete some redundant data from the DB. I estimate it will give several tens of gigabytes of free space.
I run query to remove redundant data and it was a mistake. I seems because of huge table to update (tens millions of rows) estimated time for the query to compete was at least several hours. As a result, I have killed this query, making KILL QUERY. But the database has continued to lag, I decided to restart it. Operation to shutdown the DB hanged for ~2 ho...
Since the next day I had planned to spend on the train on the way to NEERC, I
decided todelete
88.
Codeforces Round #225 — Editorial [problem:384A]
==================
Usually, when you don’t have any idea how to approach a problem, a good try is to take some small examples.
So let’s see how it looks for N = 1, 2, 3, 4 and 5. With C I noted the coder and with * I noted an empty cell.
By now you should note that answer is N ^ 2 / 2 when N is even and (N ^ 2 + 1) / 2 when N is odd. Good. Generally, after you find a possible solution by taking examples, you need to prove it, then you can code it.
In order to proof it, one needs to do following steps:
1/ prove you can always build a solution having N ^ 2 / 2 (or (N ^ 2 + 1) / 2) pieces.
2/ prove that N ^ 2 / 2 (or (N ^ 2 + 1) / 2) is maximal number – no other bigger solution can be obtained.
For proof 1/ imagine you do coloring like in a chess table.
The key observation is that by placing all coders on black squares of tab...
Tutorial of Codeforces Round 225 (Div. 2)
89.
Polynomial Round 2022 (Div. 1 + Div. 2) Editorial Thanks for your participation! I am so sorry for my careless review. We were preparing for this round for many months and made some problems which writers and testers are all like. We do want to give everyone a good time to enjoy the contest. But carelessness is deadly. In problem B, some test cases should have been made, but we missed them in not only the pretests but also the final tests. In fact, we had not noticed it until some suspicious hacks appeared. I and all co-authors sincerely regret our mistake and hope you can forgive us.
Besides, few people are cyberbullying authors, please do not do so. If you have a bad experience, you can downvote me because of our fault.
[problem:1774A]
Idea: [user:cirno_9baka,2022-12-17]
<spoiler summary="Solution">
The answer is the number of $1$s modulo $2$.
We can get that by adding '-' before the $\text{2nd}, \text{4th}, \cdots, 2k\text{-th}$ $1$, and '+' before the $\text{3rd}, \text{5th}, \cdots, 2k+1\text{-th}$ $1$.
</spoiler...
ways will be $0$. So we can delete $(l_1, r_1)$. , $ or not will be the same except for the sign. So $3$ is useless. So we can
delete such useless
90.
Инструкция к CHelper <div><div><b>1. Установка</b></div><div>Надо скачать <a href="http://code.google.com/p/idea-chelper/downloads/detail?name=chelper2.4.jar">файл плагина</a> и <a href="http://code.google.com/p/idea-chelper/downloads/detail?name=chelper.properties">файл конфигурации</a>. Файл плагина надо положить в %home_dir%\\.IntelliJIdea10\\config\\plugins (если папки plugins нету --- создать ее), а так же добавить в качестве библиотеки к модулям своего проекта (делается через Project Structure -> Dependencies -> Add Single Entry Module Library...). Затем поправить конфигурацию согласно своим нуждам, положить ее в корень проекта --- и все, можно использовать. Для работы с TopCoder необходим плагин moj для арены, инструкции и ссылка --- <a href="http://apps.topcoder.com/forums/;jsessionid=84612D3FBAD554FF37DD381DD857BC20?module=Thread&threadID=597911&start=0&mc=60">здесь</a>, инструкция на русском --- <a href="http://habrahabr.ru/blogs/sport_programming/120942/">здесь</a></div><div><i...
, arial , sans-serif;font-size: 12.0px;line-height: 20.0px;background-color:
rgb(255,255,255);">Delete, , Delete Task, Create Codeforces Tasks., Delete Task - удаляет задание и все его файлы
91.
Codeforces Round 1084 (Div. 3) Editorial Thanks to everyone who participated in this round! I hope you enjoyed the contest.
<spoiler summary="Rate the contest!">
-
Horrible contest
-
Bad contest
-
Average contest
-
Good contest
-
Peak contest
</spoiler>
<spoiler summary="Rate the difficulty!">
-
Extreme contest
-
Hard contest
-
Normal contest
-
Easy contest
-
Trivial contest
</spoiler>
#### [problem:2200A]
<spoiler summary="Rate the problem!">
-
Horrible problem
-
Bad problem
-
Average problem
-
Good problem
-
Peak problem
-
Did not solve
</spoiler>
<spoiler summary="Tutorial">
[tutorial:2200A]
</spoiler>
<spoiler summary="Code (C++)">
~~~
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto &i: a) cin >> i;
...
What if you delete characters instead of replacing them with
Tutorial of Codeforces Round 1084 (Div. 3)
92.
[Tutorial] Graph Potentials, Johnson's Algorithm, and Min Cost Max Flow In this tutorial I'll introduce potentials as it applies to directed graphs and discuss a few of its applications. I haven't seen many resources about this topic, so I decided to write one.
Prerequisites:
- Shortest path algorithms ([Dijkstra](https://cp-algorithms.com/graph/dijkstra.html) and [Bellman-Ford](https://cp-algorithms.com/graph/bellman_ford.html))
- For the Min Cost Max Flow section, you should be familiar with [Ford-Fulkerson](https://cp-algorithms.com/graph/edmonds_karp.html). But you can benefit from this blog with just the Johnson's Algorithm section if you're not familiar with flows.
Introduction
------------------
For notation, let's say there is a weighted, directed graph $G=(V,E)$. Let $n=|V|$ and $m=|E|$. For simplicity, let's assume there are no loops or multiple edges between the same pair of nodes in the same direction. For an edge $u\to v$, we will use $w(u\to v)$ to denote its weight.
Let's motivate the idea of a potential, so the definition d...
$, and it will be correct. Note that the property of a potential is still valid
if wedelete some
93.
Codeforces Round #233 Editorial Please write here if you had written some comments about any suggestions or questions on the announcement. There are a bunch of notification emails but I couldn't read most of them :(
Here are the final top 100 : [Div1](https://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCsQIDAA&url=http%3A%2F%2Fwebcache.googleusercontent.com%2Fsearch%3Fq%3Dcache%3A1RF3QO-_JXoJ%3Acodeforces.com%2Fcontest%2F398%2Fstandings%2B%26cd%3D1%26hl%3Dko%26ct%3Dclnk%26gl%3Dkr&ei=u6YUU9-HGYXEkgWNqIHICA&usg=AFQjCNFkij08MpvPcSG2HI4LDa_FK0COLA&sig2=RI29yARCrh2DimTBQSmfGw&bvm=bv.61965928,d.dGI), [Div2](https://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CC0QIDAA&url=http%3A%2F%2Fwebcache.googleusercontent.com%2Fsearch%3Fq%3Dcache%3ARm3K-hziD8QJ%3Acodeforces.com%2Fcontest%2F399%2Fstandings%2B%26cd%3D1%26hl%3Dko%26ct%3Dclnk%26gl%3Dkr&ei=sKYUU6-KFMbQlAXtzIHABQ&usg=AFQjCNHwmP4LqOrHIo0ELTh9cXnhmY0jWw&sig2=5lJH4564SjPuel1PElvTdQ&bvm=bv.61965928,d.dGI). Congrats to th...
$v$ to set $S_{u}$. * Delete: delete $u$ from set $S_{v}$, $v$ from set
$S_{u}$. * Count: calculate
Tutorial of Codeforces Round 233 (Div. 1)
Tutorial of Codeforces Round 233 (Div. 2)
94.
Codeforces Round 1028 (Div.1, Div.2) Editorial You could tell people didn't seem to like the match very much. I'm sorry I screwed up again ¯\\_(ツ)_/¯
If you're interested, I'd like to share some thoughts I have about this contest.
<spoiler summary="sad story">
This time I've been trying my best to make the problems use more varied algorithms instead of just dp problems, but sadly [problem:2115C] was much harder than expected.
But it seems like people are complaining more about the narrow time limit, centered on [problem:2116C] and [problem:2115C].
No one realized this before the contest, because none of the tester's code is get TLE except the wrong time complexity.
I actually don't see a problem with the Time Limit of [problem:2116C]. Some of you may be puzzled, but let me try to explain this:
- The intended solution is $O(\sum n \max(a) + \max(a)^2)$ and does not contain $\log \max(a)$. Computing $\gcd(x, y)$ is not $O(1)$, if you don't preprocess, then it's not unusual to actually get a TLE.
- I believe the v...
not part of the latest tree version, then $S_x$ will always be empty, and we
can safelydelete $x, root of the relevant subtree with a "reverse" flag. 3. Type 3 (Delete): Since
each element $x
Tutorial of Codeforces Round 1028 (Div. 1)
Tutorial of Codeforces Round 1028 (Div. 2)
95.
Codeforces Round 1020 (Div. 3) Editorial Thanks for the participation. I hope you enjoyed the problems, or at the very least learned something new.
<spoiler summary="Rate Contest Quality">
-
Amazing
-
Good
-
Average
-
Bad
</spoiler>
<spoiler summary="Rate Contest Difficulty">
-
Very Hard
-
Hard
-
Average
-
Easy
-
Very Easy
</spoiler>
<spoiler summary="Favorite Problem">
-
A
-
B
-
C
-
D
-
E
-
F
-
G1
-
G2
</spoiler>
<spoiler summary="Worst Problem">
-
A
-
B
-
C
-
D
-
E
-
F
-
G1
-
G2
</spoiler>
<s>The codes will be posted after the hacking...
. Then, we delete all nodes that could not possibly be the root, and query for
the new centroid., Now, we can delete $b_j$ if $p_{j-1} < s_{j+1}$ (to delete $b_1$, it must be
that $s_{2} > 0$ and
Tutorial of Codeforces Round 1020 (Div. 3)
96.
CSES Range Queries section editorial **UPD:** some video editorials on range query data structures: [youtubePlaylist](https://www.youtube.com/playlist?list=PLb3g_Z8nEv1isaHPaXL1j-pSo60812JtY)
Hello Codeforces, In this blog I will try to write a well detailed editorial for the CSES Range Queries section. The motivation for this editorial comes from https://codeforces.me/blog/entry/70018.
Quoting [user:icecuber,2020-05-09] "I think [CSES](https://cses.fi/problemset/) is a nice collection of important CP problems, and would like it to have editorials. Without editorials users will get stuck on problems, and give up without learning the solution. I think this slows down learning significantly compared to solving problems with editorials. Therefore, I encourage others who want to contribute, to write editorials for other sections of CSES."
So here I am writing an editorial for the range queries section.
If you find any error or maybe have a better solution to some problem please do share.
Range Sum Queries I
=...
try to optimize. So whenever we are asked to delete some xth element of the
list we need to, Now let us say we have the query : delete the xth element of the list, then
this means we
97.
Valentine's Day Contest 2020 Editorial I hope you enjoyed the contest!
Expected problem difficulty is F < A < (G ~ D) < (C ~ E) < B (though it might be different for different people).
I will mainly focus on explaining the full solution to the problems but I will briefly mention how to pass certain subtasks.
### Problem A — Leakage
<spoiler summary="Solution">
This is unfortunately the most standard problem of the set. Obviously, we can model the friends as vertices and friendships as edges in an undirected graph. The problem basically asks us to answer queries of the form: "For a pair of vertices $u, v$, find the number of vertices $w \neq u, v$ such that removing $w$ from the graph disconnects $u$ and $v$".
Removing vertices and disconnecting graphs should remind one of articulation points. The data structure to solve this problem is [block-cut tree](https://en.wikipedia.org/wiki/Biconnected_component#Block-cut_tree). Each biconnected component is considered as a block. An articulation point might be...
Subtask 1 can be solved by brute forcing which vertices to delete and Subtask 2
can be solved with
Tutorial of Valentines Day Contest 2020
98.
Editorial of Codeforces Round 963 (Div. 2) [problem:1993A]
<spoiler summary="Hint">
What is the pattern of Tim's answer sheet that can give him maximum score?
</spoiler>
<spoiler summary="Solution">
Let's say there are $n$ problems take $A$ as the answer, therefore he can only get $n$ points with the answer $A$.
The same is correct for $B$, $C$ and $D$.
Therefore, the maximum score can be achieved is $min(n, A) + min(n, B) + min(n, C) + min(n, D)$.
Time complexity: $O(4n)$
</spoiler>
<spoiler summary="Code (python)">
~~~~~
t = int(input())
for _ in range(t):
n = int(input())
s = input()
print(sum(min(n, s.count(c)) for c in "ABCD"))
~~~~~
</spoiler>
[problem:1993B]
<spoiler summary="Hint 1">
Find a way to make all the elements even. Then odd.
</spoiler>
<spoiler summary="Hint 2">
In the worst case, the number of operations required is the number of even elements + 1. Why?
</spoiler>
<spoiler summary="Solution">
First, if all elements already have the same parity, we don'...
Suppose we want to delete the segment $[i, i+k-1]$ from $a$. This, of $x$, find a way to delete segments of $a$ so that the array $b$ has largest
sum, check if that, Note that each time we delete a segment, the size of $a$ is reduced by $k$. We
do that until $|a
Tutorial of Codeforces Round 963 (Div. 2)
99.
[Tutorial] Dynamic Suffix Arrays Hello, Codeforces!
In this blog I will describe yet another <s>useless</s> unconventional data structure. This time, I will show how to maintain an extended suffix array (suffix array, inverse of suffix array, and $lcp$ array) while being able to add or remove some character at the <b>beginning</b> of the string in $\mathcal{O}(\log n)$ amortized time.
It can be used to <s>overkill</s> solve problem M from [2020-2021 ACM-ICPC Latin American Regionals](https://codeforces.me/gym/103185), which my team couldn't solve during the contest. I learned it from [here](https://oi-wiki.org/string/suffix-bst/) (Chinese), but it is not shown how to maintain the $lcp$ array.
Here is the whole code of the data structure. To read this blog, I recommend you ignore this code for now, but use it if you have questions about helper functions, constructors, etc, since I will pass over some implementation details in the explanations.
<spoiler summary="Full code">
~~~~~
struct dyn_sa {
struct ...
); delete x; } }, ->l; } fix_path(p); delete tmp; } void pop_front() { if (!s.size()) return, {size}(x.right)) \leq \alpha \cdot \text{size}(x)$. It turns out that if we
insert anddelete using
100.
Codeforces Round #564 Editorial [problem:1173A]
Idea: [user:ouuan,2019-06-07]
<spoiler summary="Tutorial">
Consider the two edge cases: all the $z$ persons upvote / all the $z$ persons downvote. If the results are the same in these two cases, it is the answer. Otherwise, the result is uncertain.
</spoiler>
<spoiler summary="Solution">
```cpp
#include <iostream>
using namespace std;
const char result[4] = {'+', '-', '0', '?'};
int solve(int x, int y)
{
return x == y ? 2 : x < y;
}
int main()
{
int x, y, z;
cin >> x >> y >> z;
cout << result[solve(x + z, y) == solve(x, y + z) ? solve(x, y) : 3];
return 0;
}
```
</spoiler>
[problem:1173B]
Idea: [user:Sooke,2019-06-07]
<spoiler summary="Tutorial">
- $m\ge\left\lfloor\frac n 2\right\rfloor+1$
Consider the chess pieces $1$ and $n$.
$\because\begin{cases}|r_1-r_n|+|c_1-c_n|\ge n-1\\\\|r_1-r_n|\le m-1\\\\|c_1-c_n|\le m-1\end{cases}$
$\therefore m-1+m-1\ge n-1$
$\therefore m\ge\frac{n+1}2$
$\because m\...
For each color, we delete all nodes that belong to such color, thus splitting
the tree into some
Tutorial of Codeforces Round 564 (Div. 1)
Tutorial of Codeforces Round 564 (Div. 2)
101.
Codeforces Round #647 Editorial [problem:1362A]
Author: [user:Anadi, 2020-06-04]
<spoiler summary="Tutorial">
[tutorial:1362A]
</spoiler>
<spoiler summary="Solution">
```
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL getR(LL a){
while(a % 2 == 0)
a /= 2;
return a;
}
void solve(){
LL a, b;
scanf("%lld %lld", &a, &b);
if(a > b) swap(a, b);
LL r = getR(a);
if(getR(b) != r){
puts("-1");
return;
}
int ans = 0;
b /= a;
while(b >= 8)
b /= 8, ++ans;
if(b > 1) ++ans;
printf("%d\n", ans);
}
int main(){
int quest;
scanf("%d", &quest);
while(quest--)
solve();
return 0;
}
```
</spoiler>
[problem:1362B]
Authors: [user:Anadi, 2020-06-04] and [user:Okrut, 2020-06-04]
<spoiler summary="Tutorial">
[tutorial:1362B]
</spoiler>
<spoiler summary="Solution">
```
//O(n * maxA) solution
#include <bits/stdc++.h>
using namespace std;
const int N = 1025;
int n;
int in[N];
bool is[N];
bool ch...
//add/delete contribution from fiven node to result void add_result(node *cur,
int mt = 1){ if
102.
Editorial of Codeforces Round 967 (Div. 2) Except hints/solutions, I try to add a "general idea" section discuss about some general strategy and standard ideas used to solve the problem, hope you would like it :)
[problem:2001A]
idea & solution: [user:Misuki,2024-08-20]
<spoiler summary="Hint 1">
What's the most obvious lower bound of the answer?
</spoiler>
<spoiler summary="Hint 2">
Is the lower bound achievable?
</spoiler>
<spoiler summary="General idea">
One standard way to solve optimization problem is to make observation on lower(upper) bound of the answer and prove such bound is achievable, it's useful in lot of problems.
</spoiler>
<spoiler summary="Solution">
Let $x$ be one of the most frequent elements in $a$, then the answer must be at least $(n - \text{frequency of } x)$, and this lower bound is always achievable by keep erasing a non-$x$ element from $a$, and we can prove it's always possible to do so.
proof:
If all elements of $a$ are $x$, we are done. Otherwise, let $y$ denote ...
, z)$ didn't bring extra relation so we can delete it, after that, we would have
Tutorial of Codeforces Round 967 (Div. 2)
103.
Codeforces round #525 (Div. 2) Hi!
I'm back with a new contest, a new color, <strike>and a new batch of xor problems</strike>.
Codeforces round #525, rated for the second division, is taking place on [contest_time:1088]. As usual, first division participants can take part out of competition.
I'm the problemsetter of the round. I'd like to thank [user:300iq,2018-12-02] for the great effort coordinating the round, [user:isaf27,2018-12-04], [user:cdkrot,2018-12-04], [user:BudAlNik,2018-12-04], and [user:gritukan,2018-12-04] for testing the round, [user:scanhex,2018-12-04] for translating the statements to Russian, [user:mahmoudbadawy,2018-12-02] for giving his opinions about the problems, and [user:MikeMirzayanov,2018-12-02] for the great codeforces and polygon platforms.
Like my previous [round](https://codeforces.me/contest/959), you'll be given 6 problems and 2 hours to solve them.
After the contest, I'll be on the [community Discord server](https://codeforces.me/blog/entry/52778) to discuss the pro...
104.
Codeforces Round 969 (Div. 1, Div. 2) Editorial [problem:2007A]
<spoiler summary="Hint 1">
How many odd integers are there in a pair $(a, b, c)$?
<spoiler summary="Answer">
At least 2.
</spoiler>
</spoiler>
<spoiler summary="Hint 2">
It's always better to put **exactly $2$** odd integers and **exactly $1$** even integer in one pair of $(a, b, c)$. Is there a way to always choose optimal $(a, b, c)$?
</spoiler>
<spoiler summary="Hint 3">
Try consecutive integers.
</spoiler>
<spoiler summary="Tutorial">
[tutorial:2007A]
</spoiler>
<spoiler summary="Implementation">
```py
T = int(input())
for _ in range(T) :
l, r = map(int, input().split())
print(((r + 1) // 2 - l // 2) // 2)
```
</spoiler>
[problem:2007B]
<spoiler summary="Hint">
Consider the position of the maximum value in one array. If there's multiple maximum values, choose any. What can you observe?
<spoiler summary="Answer">
The position of the maximum value never changes. That is, if one element is the maximum value...
Consider a formed string. Let's delete useless part that won't
Tutorial of Codeforces Round 969 (Div. 1)
Tutorial of Codeforces Round 969 (Div. 2)
105.
Fenwick Tree generalization using Centroids Hello, Codeforces community! (Again)
After asking many times, I realized that the central idea of this blog was not being understood, and I’ve finally decided to rewrite it. This time I want to be clearer and provide more details. This is not about the classic centroid decomposition, but I’ll try to keep it self-contained so the concept is understandable within this blog.
---
## What is a Centroid?
In a tree, a centroid is a node that, when removed along with its incident edges, minimizes the size of the largest remaining connected component, see figure 1.
<center>
<img src="/predownloaded/03/3f/033f954d1d44920150b706caa12c0045f41bced4.png" alt="centroid of a tree and remaining components">
<br>
<I>figure 1. Centroid of a tree and remaining components</i>
</center>
**Claim**: Let $W(v)$ be the size of the largest component after removing node $v$, and $n$ be the total number of nodes. If $v$ is a centroid, then:
$$W(v) \le \frac{n}{2}$$
**Proof**: Supp...
106.
The Day the Problem Solving Died [Baekjoon Online Judge will cease its operation in April 28, 16 years after its beginning.](https://www.acmicpc.net/board/view/165799)
<spoiler summary="Translation">
Hello,
BOJ, which began in March 2010, will be shutting down its service as of April 28, 2026.
We sincerely thank all of our users who have been with us over the past 16 years.
We made many efforts to continue operating the service, but due to various changes in circumstances, we have unfortunately decided to close it.
Personally, it pains me deeply to shut down a site that has been with me through most of my 20s and 30s. Over these 16 years of running it alone, I have also built many fond memories.
Some users joined as elementary school students and continued using the site all the way into their careers. It was a small dream of mine to one day see them using this site together with their own children. Sadly, the time has now come to let go of that dream.
Rather than disappearing completely, I am con...
107.
[Tutorial] Reachability Tree / DSU-tree This is not to be confused with [DSU on Tree (Sack)](https://codeforces.me/blog/entry/44351).
### What can a Reachability Tree do?
Suppose you are given a weighted (connected) undirected graph of $N$ vertices and $M$ edges. Let's define an ordering of the edges, for example, the edges are ordered in the ascending/descending order of their weights. The reachability tree can help you with:
- Find the minimal/maximal weight of the edges when traversing from vertex $u$ to vertex $v$.
- Find the set of vertices that are reachable from a given vertex using the first $x$ edges, for some arbitrary $x$. You can store some information in this set of reachable vertices, such as the maximum value or the sum of values of all the reachable vertices.
### Constructing a Reachability Tree
The reachability tree is a rooted tree that consists of $N + M$ nodes. The tree will have $N$ leaves which represent the original vertices of the graph, and the rest of $M$ internal nodes represent th...
largest value, output it, then replace its value with $0$. 2. Delete a given
edge $e$.
108.
How to read problem statements But [user:Um_nik,2018-10-26], we all know how to read, we have our whooping 2 month of experience! Oh, my sweet summer child, my experiments show that many people with kinda cool achievements like medals on ROI don't know how to read statements. But don't worry, I'll teach you. Well, probably you won't understand anything, because you didn't try to understand anything in your life, you expect all hard work to be done for you by someone else. Let's start!
Basic rules
==================
- The result of reading the statement is usually pure math model. If story helps to build correct understanding, you can keep it, but still try to discard as many unnecessary details as possible.
- Imagine you want to tell the problem to someone else. What parts you want to tell? (According to my PM, this rule won't help you).
- Shorter = better.
- Simpler = better.
- Limitations are part of problem statement. Especially small limitations, because for small data you can try all the possib...
109.
[Tutorial] Monotonic Stack Optimization for "Last-Segment" DP I recently encountered several problems that looked like standard $O(N^2)$ Dynamic Programming but required a faster solution. I noticed a recurring theme: using **Monotonic Stack** to optimize transitions dependent on range statistics (like min/max/GCD). Sometimes these problems can also be solved using the convex hull trick, but the stack-based approach is often much simpler.
However, not all "Monotone Stack DPs" are the same. Sometimes we use the stack to optimize the **transition loop**, and other times we use it to optimize the **input array itself**.
In this post, I will explain the intuition behind these two distinct patterns.
-----
## Pattern 1: Optimizing the Transition
**Target:** Problems where the cost function behaves like a "Step Function."
### The Problem
We are dealing with a 1D DP recurrence of the form:
$$dp[i] = \min_{0 \le j < i} \{ dp[j] + \text{cost}(j+1 \dots i) \}$$
Where $\text{cost}(j+1 \dots i)$ depends on a range statistic (e.g., ...
Therefore, if $i$ dominates $j$, we can delete $j$ from the array entirely.
110.
CodeChef: Falsely Flagged for Plagiarism in START184 – Here's What They Do to Your Appeals [Update] May 09 — I've received an apology email from CodeChef and my rating has been restored. Hope they improve their procedures for handling such cases in the future.
---
I participated Codechef Starters 184 last Wednesday. Did pretty well, solved 5 problems with Python, and ranked 17. The live rating graph showing my new rating to be 2018, which is +72 from the contest.
Five days after the contest, I received an email: CodeChef — You have been caught for plagiarism in START184. The email said, "Let us know within 1 day if you think you are being wrongly penalized," or my rating would be dropped by 275 points as a penalty.
Of course I didn't cheat in the contest. The email didn't mention which problem or which submission got marked as plagiarism, so I just carefully read ***CodeChef Code Of Conduct*** and ***Plagiarism FAQs*** attached in it, making sure I didn't break any rules.
Ho...
111.
TheForces Round #43 (DIV2-Forces) Editorial Reminder: We welcome you to participate in the official DIV1/DIV2 round scheduled on the 31st!
[A](https://codeforces.me/gym/106014/problem/A)
Idea:[user:tamzid1,2025-07-25]
<spoiler summary="solution">
We can see if $x$ is a perfect square, $x^x$, $x^{(x^x)}$, $\ldots$ are also perfect square.
Proof: assume $x=y^2$, $x^z=(y^z) \cdot (y^z)$.
So the answer is the number of perfect squares not greater than $n$.
There are exactly $\lfloor \sqrt{n} \rfloor$ integers $x$ (with $1 \leq x \leq n$) such that $x$ is a mystic number.
</spoiler>
<spoiler summary="code(C++)">
```cpp
#include <iostream>
#include <cmath>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << static_cast<int>(sqrt(n)) << '\n';
}
return 0;
}
```
</spoiler>
<spoiler summary="Rate the Problem">
Amazing problem:
Goo...
1) Simply delete all leaf vertices, but remember how many children were leafs
for every non-leaf
Tutorial of TheForces Round #43 (DIV2-Forces)
112.
Very detailed (text+video) editorial for Codeforces Round 1107 The video editorial for [contest:2241] is available [here](https://youtu.be/8UUSVssL9QI).
Do check out the [CF Video Editorial Finder](https://codeforces.me/blog/entry/154724) browser extension — it adds links to my video editorials directly from the contest/problems page.
---
[problem:2241A]
<spoiler summary="Hint 1">
Starting from $x$, what values can you reach?
</spoiler>
<spoiler summary="Hint 2">
Each operation replaces $x$ with $x / z$ where $z$ divides $x$.<br>
So in a single step you can jump directly to any divisor of the current $x$.
</spoiler>
<spoiler summary="Hint 3">
Over multiple steps you can still only ever reach divisors of the original $x$.<br>
<br>
To reach any divisor $d$ of $x$, just pick $z = x / d$ in one step — done.
</spoiler>
<spoiler summary="Hint 4">
Answer: YES if and only if $y$ divides $x$.
</spoiler>
<spoiler summary="Video Editorial">
<iframe src="https://www.youtube.com/embed/8UUSVssL9QI?start=540" width="560" heig...
example. Delete the rightmost '1' from it, making the string end with '0'. Now
first and last are, number of inversion pairs, Alice can delete all characters except $i$., E.g., "0101": choose "101" (palindrome) → delete the last '1' → "010" → starts
and ends with '0
113.
Google Code Jam 2017 finals feedback A few weeks ago, I participated in Google Code Jam and Distributed Code Jam finals. Later, the finalists were asked to provide some feedback. I think that my feedback may be interesting for other people as well, so I post it here (I also posted it on Google Code Jam group).
[cut]
<hr style="border-color: gray">
Okay Google,
Thank you for organizing such a great event! Everything went quite well. Mostly. Hopefully it will be even better next year! Here are some things that weren't very good, in my opinion:
Firstly, I think that, when Google is going to organize some event in a country other than United States, the people responsible for that event should study some of that country's laws and regulations, especially those related to visas. This year, finalists were sent visa invitation letters in electronic form, while the rules require visa applicants to submit original documents. Only later, when told about the problem, they finally sent original invitation letters. Fort...
114.
DP on Trees Tutorial A certain question on Quora and some junior asking about DP on Trees is what inspired this post. Its been a long time since I wrote any tutorial, so, its a welcome break from monotonicity of events.
Pre-requisites:
- Will to read this post thoroughly. :)
- Also, you should know basic dynamic programming, the optimal substructure property and memoisation.
- Trees(basic DFS, subtree definition, children etc.)
Dynamic Programming(DP) is a technique to solve problems by breaking them down into overlapping sub-problems which follow the optimal substructure. We all know of various problems using DP like subset sum, knapsack, coin change etc. We can also use DP on trees to solve some specific problems.
We define functions for nodes of the trees, which we calculate recursively based on children of a nodes. One of the states in our DP usually is a node $i$, denoting that we are solving for the subtree of node $i$.
As we do examples, things will get clear for you.
...
, along with a number $K$. The aim is to delete enough nodes from the tree so
that the tree is left
115.
Valentine Algorithm cUp 2015 Are you in love with algorithms? If you are don't miss this round and be algorithm's valentine ;)
On the night before valentine's day ([exact time](http://www.timeanddate.com/worldclock/fixedtime.html?day=13&month=2&year=2015&hour=18&min=30&sec=0&p1=166)), Valentine Algorithm cUp 2015 is going to take place.
There will be 6 problems and 3 hours to solve them. All of them are written by me([user:PrinceOfPersia,2015-02-05]).
This competition is like surprise languages but too different. 3 days before the contest, I will publish tutorial of 5 new algorithm languages(not programming languages) with their compiler codes. Each language is going to be really simple to learn and have at most 6 or 7 commands (they're not like programming languages).
Your program should print the code written in the language the problem says and checker will run it (pay attention that inputs are encoded, don't try to read form input, j...
Announcement of Valentine Algorithm Cup 2015
116.
Set algorithm(rev.2) # Set algorithm Part I
Sometimes we may meet with some functions $S\rightarrow V$(S is a set,V is a value),and we need to handle some transformations on it.
The article is for beginners whick is much easy, and I may continously update the article.
There are some features.
First the problem always give small $n$,such as $n\leq 15,n\leq20$.
Second,the time complexity is always $O(n2^n),O(3^n),O(n^22^n)$.
Let's do some assumption:
The values form a ring and they contain ring operations like addition,substraction,multification or division in constant time.
## FWT/FMT
The most classical one is FWT/FMT.
### Problem
Define $a(S),b(S)(S\subseteq U)$ on a set.
Get all $c(S)=\sum\limits_{i \oplus j=S}a_ib_j\qquad \oplus \text{is} \ \textrm{and,or,xor}$
The general idea:
Let $a, b, c$ be maps (functions) from a set $S$ to a value domain $V=(N/Q/C\cdots)$. We define a transformation $\text{FWT}$ (Fast Walsh Transform) as a map from the space of such functi...
It's not good to delete the root dimension.
117.
Codeforces Round 960 (Div. 2) Editorial Thank you for participation and we hope you enjoy this round :)
Additionally, we sincerely invite you to join the unofficial round of TheForces Community tomorrow. Compete alongside many high-rated participants and earn your own rating in a our own rating system([TheForces Rating System](https://theforces.netlify.app/ratings))!
For more details, pls read https://codeforces.me/blog/entry/131733.
#### [A — Submission Bait](https://codeforces.me/contest/1990/problem/A)
<spoiler summary="hint1">
For Alice, what if choosing the maximum value doesn't work?
</spoiler>
<spoiler summary="hint2">
Consider parity.
</spoiler>
<spoiler summary="solution 1">
Case $1$: When all values appear an even number of times, Alice will lose. This is because no matter which number Alice chooses, Bob can mimic Alice's move.
Case $2$: When at least one value appears an odd number of times, Alice will win. Alice only needs to choose the maximum value that appears an odd number ...
= [&] (const auto &self, int node, int x) -> void { // Delete all intervals
covering point x, 1. if the jury returns $0$, we can delete the entire subtree;, Consider querying a subtree. If the jury returns $0$, we can delete the entire
subtree., Query any leaf $70$ times, then delete all nodes $x$ such that
$maxdep_v-dep_v+1<=70$. Then the
Tutorial of Codeforces Round 960 (Div. 2)
118.
Editorial of Codeforces Round #769 You can also find video editorials for problems B-D on [user:ak2006,2022-01-30]'s [Youtube channel](https://www.youtube.com/channel/UCnZ5rC2_JY0EuYMGMiAbISg)!
####[1632A — ABC](https://codeforces.me/contest/1632/problem/A)
<spoiler summary="Hint 1">Only a few strings have the answer "YES".</spoiler>
<spoiler summary="Hint 2">
For $n \ge 3$, the answer is "NO".
</spoiler>
<spoiler summary="Solution">
Let $n \ge 3$ and the resulting string be $a$. For there to be no palindromes of length greater than $1$, at least all of these inequalities must be true: $a_1 \neq a_2$, $a_2 \neq a_3$, and $a_1 \neq a_3$. Since our string is binary, this is impossible, so the answer is "NO".
For $n \le 2$, there are 4 strings that have the answer "YES": $0$, $1$, $01$, and $10$; as well as 2 strings that have the answer "NO": $00$ and $11$.
Time complexity: $O(n)$
</spoiler>
<spoiler summary="Solution codes">
- [C++ code](https://codeforces.me/problemset/submission/1632...
smallest $r$, delete all segments that have $r$ in them, and repeat. In our
case, this is easy to do
Tutorial of Codeforces Round 769 (Div. 2)
119.
Codeforces Round #781 (Div. 2) Editorial Again, I hope that you liked all the problems. Share your ideas and solutions in the comments, because there are always different ones! So, the editorial:
<spoiler summary="A: GCD vs LCM">
[problem:1665A]
<spoiler summary="Editorial">
In this problem it is enough to print $n - 3$, $1$, $1$, $1$. It is easy to see that this answer is correct for any $n \ge 4$.
</spoiler>
<spoiler summary="Implementation (C++, shishyando)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T --> 0) {
int n;
cin >> n;
cout << n - 3 << ' ' << 1 << ' ' << 1 << ' ' << 1 << '\n';
}
return 0;
}
~~~~~
</spoiler>
</spoiler>
<spoiler summary="B: Array Cloning Technique">
[problem:1665B]
<spoiler summary="Editorial">
We will use a greedy technique. Let's find the most common element in the array. Let it be $x$ and let it occur $k$ times in the array. Then let's make a copy where all elements...
((memorypos+n+MX_ALIGN-1)&-MX_ALIGN); return (void*)ret; } void operator delete
(void *){} void operator
Tutorial of Codeforces Round 781 (Div. 2)
120.
Codeforces Round #198 — Editorial [problem:340A]
------------------
You are given a range $[A, B]$. You're asked to compute fast how many numbers in the range are divisible by both $x$ and $y$. I'll present here an $O(log(max(x, y))$ solution. We made tests low so other not optimal solutions to pass as well. The solution refers to the original problem, where $x, y \le 10^9$.
Firstly, we can simplify the problem. Suppose we can calculate how many numbers are divisible in range $[1, X]$ by both $x$ and $y$. Can this solve our task? The answer is yes. All numbers in range $[1, B]$ divisible by both numbers should be counted, except the numbers lower than $A$ (1, 2, ..., A — 1). But, as you can see, numbers lower than A divisible by both numbers are actually numbers from range [1, A — 1]. So the answer of our task is f(B) — f(A — 1), where f(X) is how many numbers from 1, 2, ..., X are divisible by both x and y.
For calculate in $O(log(max(x, y))$ the f(X) we need some math. If you don't ...
121.
Codeforces Round 1010 (Div. 1, Div. 2, based on Zhili Cup 2025) Editorial Sorry for the late editorial. Our problem setters were so exhausted with the offline competition yesterday that they really need some good rest.
Despite the unexpected and unpleasant incidents that occurred, we are truly surprised and grateful that so many of you still participated in this competition! We sincerely hope you enjoyed it!
(Gratitude for all you guys from [user:Ecrade_,2025-03-16]: I felt so heartbroken when I heard about the unexpected issues, but seeing so many people in the comments comforting us, sharing thoughtful and positive messages that showed genuine empathy, and continuing to fully support our competition even after the wasted time, I was deeply moved. Thank you all! Codeforces truly embodies such a positive and uplifting community spirit!)
[problem:2082A]
<br>
Idea: [user:Ecrade_,2025-03-16]
<spoiler summary="Hint">
Do we really have to consider the problem on the whole matrix?
</spoiler>
<spoiler summary="Solution">
Let $r$ be the num...
For those $d$ satisfy condition (i), let's begin with $f_0$, delete the prime
numbers from small to
Tutorial of Codeforces Round 1010 (Div. 1, Unrated)
Tutorial of Codeforces Round 1010 (Div. 2, Unrated)
122.
CSES DP section editorial Edit: More dp tasks have been added to CSES since this blog was created. For solutions to those problems, check out [user:UnexpectedValue,2023-02-14]'s blog [here](https://codeforces.me/blog/entry/111675).
I'm using bottom-up implementations and pull dp when possible. Pull dp is when we calculate each dp entry as a function of previously calculated dp entries. This is the way used in recursion / memoization. The other alternative would be push dp, where we update future dp entries using the current dp entry.
I think [CSES](https://cses.fi/problemset/list/) is a nice collection of important CP problems, and would like it to have editorials. Without editorials users will get stuck on problems, and give up without learning the solution. I think this slows down learning significantly compared to solving problems with editorials. Therefore, I encourage others who want to contribute, to write editorials for other sections of CSES.
Feel free to point out mistakes.
## Dice Combin...
123.
[Tutorial] Path sum queries on a tree using a Fenwick tree ## Introduction
I've come across several problems that require you to be able to efficiently find the sum of some values on a path from $A$ to $B$ in a tree. One can solve these problems using tree decomposition techniques like heavy-light decomposition or centroid decomposition, but that's a bit of an overkill and not very elegant in my opinion.
In this blog post, I will describe a way to solve these types of problems using just a DFS, a Fenwick tree, and LCA (as well as a way to solve JOIOC 2013 Synchronization this way).
**Note: Whenever I talk about edge $(u, v)$ in this post, I assume that $u$ is the parent of $v$.**
## Prerequisites
- DFS
- Preorder traversal (DFS order)
- Fenwick tree
- Binary lifting and LCA
## The idea
Say you have the following problem:
> Given a tree with $N$ nodes, each node $i$ has a value $a_i$ that is initially 0. Support the following 2 types of operations in $O(\log N)$ time:
>
> 1. Increase the value of $a_i$ by $X$
> 2....
1. Delete the edge $(u, v)$ from the path. 2. Determine whether there is a path
from $u$ to $v$., Let the value of each edge in the tree initially be 0. When we "delete" an
edge, we just update its
124.
Catalan Numbers and Generating Uniform Balanced Bracket Sequences Hi everyone! Today [user:nor,2022-05-27] sir and I would like to talk about generating uniform bracket sequences. Over the past few years when preparing test cases, I have had to generate a uniform bracket sequence a few times. Unfortunately I could not figure out how, so I would like to write a blog about this now. Hopefully this blog would be useful to future problem setters :) Scroll down to the end of the blog to copy our generators.
First, let's define some things. A bracket sequence is a string with $n$ $\texttt{(}$ s and $n$ $\texttt{)}$ s. A **balanced** brackets sequence is a bracket sequence with the additional constraint that it becomes a valid arithmetic expression when we add some $\texttt{1}$ s and $\texttt{+}$ s. Let $p$ be the prefix sum array of a bracket sequence (we assign $1$ to $\texttt{(}$ and $-1$ to $\texttt{)}$ and take the prefix sum). For example, if our bracket sequence is $\texttt{())()((())}$, then $p=[1,0,-1,0,-1,0,1,2,1,0]$.
An alternate way to thi...
-p_{k-1})]$. That is, we append $0$ to the beginning of $p$, delete the last
element of $p$, then add
125.
Codeforces Round #957 (Div. 3) Hello, Codeforces! We are pleased to invite you to [contest:1992], which will be held on [contest_time:1992].
The round will be hosted by rules of educational rounds (extended ICPC). You will be offered 7 problems, which I with [user:Noobish_Monk,2024-07-09], [user:ErnKor,2024-07-09], [user:Kmes,2024-07-09] and
[user:ArSarapkin,2024-07-09] have prepared for you.
The rules of the third division are:
- The **penalty** for a wrong submission is **10 minutes**.
- 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
- after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated.
[Reminding you](https://codeforces.me/blog/entry/59228), that _only trusted participants of the third division_ will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a _trusted participant of the third division_, you mus...
Announcement of Codeforces Round 957 (Div. 3)
126.
[Tutorial] Euler Tour Trees (maintaining dynamic trees through their euler tour) Good morning Codeforces!
Today's post regards a well-known, but surprisingly hard to learn topic, Euler Tour Trees.
Prerequisites:
------------------
- Basic tree knowledge, e.g. general vocabulary
- Balanced Binary Search Tree Knowledge (e.g Treaps/Splay trees). In my opinion, learning treaps is the easiest, and [user:SecondThread,2022-02-03] has a great video/problemset on treaps, so go check it out [here](https://codeforces.me/blog/entry/84017)! The BBST must store parent pointers, so make sure your implementation supports it.
#### Disclaimer
This idea will definitely not show up in easy problems, and is pretty uncommon. Nevertheless, it's a cool concept and it can be used to “cheese” somewhat difficult problems, and I haven't found any resources that describe it well.
Brief Description of Operations
------------------
A Euler Tour Tree is a representation of a dynamic forest of trees. This means that, as long as the graph never contains any cycles, you can su...
delete edge operations.
127.
Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2) Editorial Thank you for participation and we hope you enjoy this round ヽ(^ o ^)/.
During the contest, there was a small issue in problem D. For those affected, we have skipped your duplicate submissions (if your duplicate submissions were not skipped, please let us know). We apologize again for any inconvenience caused.
In addition, we are honored to invite you to our unofficial round tomorrow (*╹▽╹*) [Invitation to TheForces Round #22 (Interesting-Forces)](https://mirror.codeforces.com/blog/entry/119771)
### [1864A-Increasing and Decreasing](https://mirror.codeforces.com/contest/1864/problem/A)
Idea : [user:wuhudsm,2023-08-27]
<spoiler summary="Tutorial">
We use the following greedy construction:
For all $i$ ($1<i<n$), set $a_i=a_{i+1}-(n-i)$. If $a_2-a_1 \geq n-1$, we've found a solution, otherwise there is no solution.
Proof. Assume there's a solution which includes an index $i$ ($1<i<n$) such that $a_{i+1}-a_i>n-i$. We can make $a_j:=a_j+\Delta$ for all $j$ ($2 \le j ...
128.
I started solving Project Euler [user:Radewoosh,2024-01-12] inspired me by [completing](https://codeforces.me/blog/entry/122793) Project Euler, and I recently [started](https://projecteuler.net/progress=ivanovmp), slow but steady, solving its problems. I don't mind anybody adding me as a friend on Project Euler, my friendship key is `2127163_HmDkRoxUDZa38znoBSPq2n4Prg996WEX`, please enter it on [this page](https://projecteuler.net/friends) if you're registered and you'd like to see me in your friend list. (Similarly, you'll appear in my friend list.)
I also record the process and upload on Youtube because, according to the [rules](https://projecteuler.net/about), problems 1–100 are allowed for public analysis (although I'm afraid there won't be any serious or interesting problems in the first hundred). As for now, uploaded are:
* [problems 1–3](https://youtu.be/k2rRnfDxDME);
* [problems 4–12](https://youtu.be/oQ0AXSwlVog);
* [problems 13–24](https://youtu.be/aOBgin-XGkQ);
* [problems 25–36](https://youtu.be...
129.
Editorial for Codeforces Round #798 (Div. 2) # [problem:1689A]
Author: [user:wxhtzdy,2022-06-02]
<spoiler summary="Hint">
Greedily take the smallest character in both strings. What's the exception to this?
</spoiler>
<spoiler summary="Solution">
We can't take the smallest character in both strings when we've already took $k$ elements from the string we chose. Denote $A$ as the number of characters we've took from string $a$ in the last few consecutive moves and denote $B$ the same for $b$. If $A=k$, then we have to take the smallest character in string $b$ instead of possibly $a$. If $B=k$, then we have to take the smallest character in string $a$ instead of possibly $b$.
Remember to reset $A$ to $0$ when you take a character from $b$. Similarly, reset $B$ to $0$ when you take a character from $a$.
</spoiler>
<spoiler summary="C++ Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t; cin>>t;
whil...
We always delete a vertex directly connected to an infected one, . Hence, we may assume we always delete a vertex directly connected to an
infected one.
Tutorial of Codeforces Round 798 (Div. 2)
130.
VK Cup 2015: online mirror and final thanks **The registrations before 00:00 have been deleted, because the form didn't support teams. Please, register again if your registration has been affected.**
VK Cup 2015 Final Round has ended two days ago. It's very likely that you've seen our previous posts. The last event to happen is online mirror of the final round. It will be held on [Thursday, July 30th, at 19:00 Moscow time](http://www.timeanddate.com/worldclock/fixedtime.html?day=30&month=7&year=2015&hour=19&min=0&sec=0&p1=166). Individual contestants as well as teams consisting of two people may participate in this round. Round duration is three hours, problems will be shuffled in comparison with to the original order. Both division participants may take part, but we want to warn 2nd division contestants that problemset may be hard for them. This round is a rated Codeforces round.
Finally, we want to thank all people that made this Championship. Following VK developers, Codeforces team members and the other people suggeste...
Announcement of Codeforces Round 313 (Div. 1)
Announcement of Codeforces Round 313 (Div. 2)
Announcement of VK Cup 2015 - Finals
Announcement of VK Cup 2015 - Finals, online mirror
131.
More and More Suspicious Participants in AtCoder Beginner Contests! Hello, CodeForces.
As I can't find any discussion thread in AtCoder, and the announcements of AtCoder contests are also posted here, I decided to post this blog in CodeForces.
Last time (ABC355), I [reported](https://codeforces.me/blog/entry/129765?#comment-1151921) a suspicious participant [toyuzuko](https://atcoder.jp/users/toyuzuko) who solved problem ABCD in 51 seconds. They also did the similar thing in ABC354.
This time (ABC356), there are much more suspicious participants.
The average first-AC time (in seconds) of ABC347~ABC353 is in the following table:
|Contest|A|B|C|D|E|F|G|
|:-|:-|:-|:-|:-|:-|:-|:-|
|ABC347|21|45|93|244|177|300|824|
|ABC348|15|37|72|302|236|495|430|
|ABC349|23|67|54|116|598|139|634|
|ABC350|26|47|102|74|240|489|335|
|ABC351|22|23|106|352|199|122|902|
|ABC352|27|43|49|90|196|989|188|
|ABC353|24|79|172|88|206|1161|313|
|(minimum)|15|23|49|74|177|122|188|
|(prefix sum)|15|38|87|161|338|460|648|
Note that to get first-AC in a problem...
not just delete ABCD and add some new problems to make an AtCoder Regular
Contest?
132.
Codeforces #253 editorial [cut]
As my english is not very good, please if you see any mistake write me a private message about it.
[problem:443A]
In this task you are to count the number of different letters in the set. In my opinion the easiest way to do this looks like this. You just iterate over all small latin letters and check if the string contains it (with built-in functions).
[problem:443B]
Let's add $k$ question marks to the string. Than we can check all possible starting and ending positions of tandem repeat in a new string. We can check each of them in time $O(n + k)$. We only need to check that some symbols are equal (in our task question mark is equal to every symbol).
[problem:442A]
It's obvious that the order of hints doesn't metter. There are 10 types of hints, so we can try all $2^10$ vartiants of what other players should do. Now we need to check if Boris can describe all of his cards. He can do it iff he can distinguish all pairs of different cards. He can do it if somebo...
possible move (but not on first one). We can prove that we can delete it
earlier. If move which is
Tutorial of Codeforces Round 253 (Div. 1)
Tutorial of Codeforces Round 253 (Div. 2)
133.
Editorial of Educational Codeforces Round 16 ### [problem:710A]
Easy to see that there are only three cases in this problem. If the king is in the corner
of the board the answer is $3$. If the king is on the border of the board but not in a
corner then the answer is $5$. Otherwise the answer is $8$.
<spoiler summary="С++ solution">
~~~~~
char c, d;
bool read() {
return !!(cin >> c >> d);
}
void solve() {
int cnt = 0;
if (c == 'a' || c == 'h') cnt++;
if (d == '1' || d == '8') cnt++;
if (cnt == 0) puts("8");
else if (cnt == 1) puts("5");
else if (cnt == 2) puts("3");
else throw;
}
~~~~~
</spoiler>
Complexity: $O(1)$.
### [problem:710B]
The function of the total distance is monotonic between any pair of adjacent points from the input,
so the answer is always in some of the given points. We can use that observation to solve the problem
by calculating the total distance for each point from the input and finding the optimal point.
The other solution uses the observation that the answer ...
Tutorial of Educational Codeforces Round 16
134.
[Tutorial] Square root decomposition and applications A brief introduction into the applications of square root decomposition
==================
Square root decomposition is the process of separating a structure of size $O(N)$ into $O(\sqrt{N})$ "blocks" of size $O(\sqrt{N})$ each, in a way that aids manipulation of the entire structure. Square root decomposition is extremely versatile. Some of its most well-known use cases are:
- answering queries on a static array, with methods such as Mo's algorithm or block precomputation
- "lazy" brute force modifications, where it is easy to query an entire block, but tag pushing isn't obvious
- separating objects based on a threshold, when there exists both an $O(x)$ algorithm and an $O(n/x)$ algorithm
In this tutorial we will walk through multiple types of square root decomposition.
Answering queries on a static array, offline (Mo's algorithm)
---
Consider a problem where we are asked to find the answer for certain intervals $[l,r]$. We can't quickly compute the answer for an ar...
$ and $nxt$ arrays, it seems impossible to delete values and "roll back" the
$\min$ value. Hence we
135.
[Tutorial] Commutative Segment Trees # Commutative Segment Trees
## Preface
This blog is about an alternative way to implement segment trees.
Knowing segment tree already should not be necessary to understand this
blog, but it is mostly targeted towards people who already know segment trees
but don't know how to for example create a merge sort tree that supports updates.
<span style="color:green">Pros:</span>
- You don't need a fast merge function (which allows you to for example extend to 2D)
- Very easy to implement
- Fast
<span style="color:red">Cons:</span>
- Merging has to be commutative
- Can't easily be turned lazy (meaning only update or query can be on a range, not both)
Disclaimer: This way of implementing segment tree may be what you think of as "a standard segment tree". But the reason I made this blog is that I talked to people who were very familiar with segment trees but did not know how to make a 2D segment tree
(which is a trivial modification of this way to implement segment t...
is fine amortized if we just delete the edges after using them., So after relaxing edges we are allowed to delete them., delete it the next time it is iterated over in a query.
136.
Editoral Codeforces Round #122 Please, report me about every grammar mistake, you see. Thank you.
**Problem <<Exams>>**
Let's notice that $2n \le k \le 5n$. If $k < 3n$ author has to get $2$ on some exams. There are $3n-k$ such exams and that's the answer). If $3n \le k$ author will pass all exams (answer is $0$).
**Problem <<Square>>**
Let the pencil move by the line and put crosses through every $(n+1)$ point. Lets associate every point on the line with point on square perimeter. Namely, point $x$ on the line will be associated with point on square perimeter that we will reach if we move pencil around square to $x$ clockwise. Then lower left corner will be associated with all points $4np$ for every non-negative integer $p$. Crosses will be associated with points $k(n+1)$ for some non-negative $k$. Nearest point of overlap of two families of points will be in point LCM($n+1$, $4n$). Then we will put $\frac{LCM(n+1,4n)}{n+1} + 1$ crosses.
**Problem "Cutting Figure"**
Translation by [user:moskupo...
The algorithm: Check answer 1. We can simply brute-force the square to delete,
and for each
Tutorial of Codeforces Round 122 (Div. 1)
Tutorial of Codeforces Round 122 (Div. 2)
137.
Offline Dynamic MST [Tutorial] Inspired by [an old Adamant blog](https://codeforces.me/blog/entry/15296), I reinvented a variation of the technique for calculating the cost of the minimum spanning tree offline, when edge weight updates are allowed. This technique is not new and already appeared in [work of David Eppstein](https://www.ics.uci.edu/~eppstein/pubs/Epp-TR-92-04.pdf). This was also in Adamant's blog, but I missed it completely :).
So the problem statement is: You're given a undirected, connected, weighted graph with $n$ nodes and $m$ edges. There are $q$ updates of the form: Set the weight of $k'th$ edge in the input to $x$. After each update you should report the total weight of a minimum spanning tree. Notice that this is strong enough to simulate edge deletions and insertions, by just giving the edge a weight of infinity when it is "deleted".
This is difficult to do if you were forced to do all updates online. But offline, we can use divide and conquer on time to achieve a decent time complexity...
138.
[Tutorial] Nearest Neighbor Search: Locality-Sensitive Hashing, K-Dimensional Tree, Vantage-Point Tree Hello everyone,
So I recently prepared a lecture for a Bulgarian camp on the topic since I find it quite wide and interesting. I have never seen an article discussing different approaches for the problem so today I am going to share my knowledge. Don't forget to give me your feedback, please!
Let's start with first defining the problem we are going to solve. We are given a set of $N$ $d$-dimensional points. $Q$ queries follow, each containing a $d$-dimensional point. We should answer each query with the distance (we will use Euclidean distance) to the point from the set which is closest to the queried one. This will be our main focus but we are still going to consider inserting/deleting points from the set when possible. It's important to say that for $d>1$ we will consider only average-case complexity and we will assume that the points are distributed uniformly. Unfortunately, even the average-case complexity is exponential in the number of dimensions.
##### One-Dimensional N...
139.
I built a simple Grid Visualizer because I hate wasting paper Hello Codeforces!
Like many of you, I struggle to visualize grid/coordinate geometry problems when I don't have a pen and paper handy. Debugging DFS/BFS paths or complex geometry on a blank screen is painful.
I couldn't find a simple, lightweight tool that did exactly what I wanted, so I built CP Grid Visualizer.
It's a single-file, browser-based tool to instantly plot points and lines on an infinite grid.
Link: https://himalaya-pahar.github.io/cp-grid-visualization/
github repo: https://github.com/himalaya-pahar/cp-grid-visualization
Features:
- Infinite Grid: Handles negative coordinates and large ranges easily.
- Fast I/O: Left-click to add points. Click any two points to draw a line.
- Interactive: Click points to connect them with lines.
- Precision Control: Switch between Snap-to-Grid (Integers) and Decimal Mode (Floats) instantly.
- Safe Mode: Toggle "Allow Adding Points" OFF to lock the board and prevent accidental clicks.
- Fast Edit: Right-...
- Delete: Right-Click any point to remove it instantly., - Fast Edit: Right-Click any point to delete it instantly.
140.
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...
value. Let $v \leftarrow p_{i, s_i}$, then delete cell $(i, s_i)$ from both
tableaus.
141.
Nebius Round 2 and Codeforces Round 1088 Editorial <spoiler summary="Rating Predictions">
| Predictor | A | B | C | D | E | F | G | H |
|----------------------------------|-----|-----|-----|------|------|------|------|------|
| [user:Proof_by_QED,2026-03-27] | 800 | 1300 | (1400-2000) | 1700 | 2100 | 2400 | 2600 | 3500|
| [user:nifeshe,2026-03-27] | 800 | 1400 | (1400-1900) | 1800 | 2200 | 2600 | 3000 | 3500|
| [user:dinohaur,2026-03-27] | 800 | 1200 | (1400-1700) | 2100 | 2300 | 2600 | 2900 | 3300 |
| [user:_istil,2026-03-27] | 800 | 1200 | (1300-1800) | 1900 | 2300 | 2500 | 2800 | 3300 |
| [user:Dragos,2026-03-27] | 800 | 1400 | (1400-1900) | 1800 | 2100 | 2400 | 2800 | 3500 |
| [user:Argentum47,2026-03-27] | 800 | 1300 | (1400-2000) | 1900 | 2200 | 2500 | ? | ? |
| [user:simplelife,2026-03-27] | 800 | 1200 | (1200-1800) | 1600 | 2000 | 2500 | 6700 | 6700 |
| [user:AksLolCoding,2026-03-27] | 800 | 1000 | (1100-1800) | 1600 | 1900 | 2400 | ? | ? |
| [user:nik_exists,2026-03-27]...
You are allowed to delete two elements in any valid subarray, but you, , we can delete the largest element. Otherwise, we can delete the smallest
element., delete each bit at most once, so the final solution is $O(n \log A)$.
142.
Niche technique with centroids Hello Codeforces!
I was solving [this](https://codeforces.me/gym/102331/problem/J) problem, and the model approach involves HLD solution, however I came up with some interesting approach with centroids. In short, I wrote $dp_{v, cnt, mask}$ where $v$ is vertex in tree in which centroid subtree I am choosing edges, $cnt$ is number of edges that was taken to the matching and $mask$ is mask of vertices which were already taken to some of matching edges, but we only consider those vertexes which have edges to vertices outside of $v$'s centroid subtree.
So this solution works in $O(C \log n)$ where $C$ is number of different $dp$ states, which is equal to $\displaystyle\sum_{v=1}^{n} siz_v \cdot 2^{edges}$ where $siz_v$ is size of $v$'s centroid subtree, and $edges$ is number of different edges from tree going outside from $v$'s centroid subtree.
Here is the proof that number of different states is $O(n \log^2 n)$. Let me know if you notice any mistakes. Thanks to [user:zwezdinv...
+ 1)$. If we delete these path, there will be components of depth $0, 1, \dots
k-1$, so $S(k) \geq 2, Let's consider centroid tree which is built recursively like this: we delete
the centroid from the
143.
Educational Codeforces Round 51 Editorial [problem:1051A]
<spoiler summary="Tutorial">
[tutorial:1051A]
</spoiler>
<spoiler summary="Solution (Ajosteen)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
string s;
bool ok(string t){
int msk = 0;
for(int i = 0; i < int(t.size()); ++i){
if(isupper(t[i])) msk |= 1;
if(islower(t[i])) msk |= 2;
if(isdigit(t[i])) msk |= 4;
}
return msk == 7;
}
int main() {
//freopen("input.txt", "r", stdin);
int t;
cin >> t;
for(int i = 0; i < t; ++i){
cin >> s;
if(ok(s)){
cout << s << endl;
continue;
}
bool fnd = false;
for(int i = 0; i < int(s.size()); ++i){
string t = s;
t[i] = '1';
if(ok(t)){
cout << t << endl;
fnd = true;
break;
}
t[i] = 'a';
if(ok(t)){
cout << t << endl;
fnd = true;
break;
...
, b.beg); a.fill_treap(b.t); delete b.t; a.upd(); return a; }
144.
Codeforces Round #519 Editorial #### [1043A — Elections](http://codeforces.me/contest/1043/problem/A)
<spoiler summary="Tutorial">
We can observe that result cannot exceed $201$ — Awruk gets at least $101$ votes from one person and Elodreip cannot get more than $100$ votes from one person. So we can iterate over every possible integer from $1$ to $201$ and check if Awruk wins with $k$ set to this integer. We have to remember that $k$ — $a_i$ is always at least $0$, so we have to check this condition too. Complexity $O(n * M)$, where $M$ denotes maximum possible value of $a_i$. Try to solve it in $O(n)$.
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int n;
int mx = 0, sum = 0;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
int a; scanf("%d", &a);
mx = max(mx, a);
sum += a;
}
sum *= 2;
sum += n;
sum /= n;
printf("%d", max(sum, mx));
return 0;
}
~~~~~
</spoiler>
Author: [user:FCB1234,201...
Tutorial of Codeforces Round 519 by Botan Investments
145.
Codeforces Round #350 (Div.2) Editorial ### [problem:670A]
There are many ways to solve this problem. Let's talk about one of them. At first we need to write a function, which takes the start day of the year and calculate the number of days off in such year. To make it let's iterate on the days of the year and will check every day — is it day off or no. It is easy to show that if the first day of the year equals to the first day of the week (i.e. this day is Monday) in this year will be minimum possible number of the days off. If the first day of the year equals to the first day off of the week (i.e. this day is Saturday) in this year will be maximum possible number of the days off.
### [problem:670B]
To solve this problem we need to brute how many identifiers will called robots in the order from left to right. Let's solve this problem in one indexing. Let the current robot will call $i$ identifiers. If $k - i > 0$ let's make $k = k - i$ and go to the next robot. Else we need to print $a[k]$, where $a$ is the arr...
ends of the substring which we need to delete now. If $right[rg] == -1$ we
need to move $p$ to the, To print the answer we need to find the position of the first bracket which we
did notdelete and
Tutorial of Codeforces Round 350 (Div. 2)
146.
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...
147.
Codeforces Round 1107 (Div. 3) Editorial Thanks for participating. I apologize for the unexpectedly hard B. Apart from that, I hope you liked the problems and enjoyed the round!
I would like to thank [user:Proof_by_QED,2026-06-24], [user:Forge,2026-06-30], and [user:awesomeguy856,2026-06-24] for pointing out an elegant $\mathcal{O}(n)$ solution for problem G.
I would also like to thank [user:temporary1,2026-06-25] for helping me write the editorial for problem F and [user:Forge,2026-06-30] and [user:reirugan,2026-06-30] for proofreading the editorial.
<div style="height:32px"></div>
<spoiler summary = "Rating predictions">
<table border="1" cellspacing="0" cellpadding="10" style="border-collapse: collapse; text-align: center; margin: auto;">
<thead>
<tr style="background-color: #f0f0f0;">
<th style="text-align: center;">Predictor</th>
<th style="text-align: center;">A</th>
<th style="text-align: center;">B</th>
<th style="text-align: center;">C</th>
<th style="text-align...
a binary string consisting entirely of `0`s or entirely of `1`s. Since a
player maydelete **any, )$ is also odd, so Bob can simply delete the entire remaining string on his
turn and win immediately., Suppose Alice wants to delete all `1`s. Then the chosen subsequence must have
an odd number of, delete characters until only one remains.
Tutorial of Codeforces Round 1107 (Div. 3)
148.
AtCoder Beginner Contest 139 English Solutions #A — Tenki
This is a fairly simple task--just iterate over all positions in the strings and count the ones where S[i] = T[i].
Runtime: $O(|S|)$. [Click here for my submission.](https://atcoder.jp/contests/abc139/submissions/7247680)
---
#B — Power Socket
Note that we already have one socket, so we need to fill $B-1$ more sockets. Additionally, each new outlet we add will take up one socket and add $A$ sockets, resulting in a net addition of $A-1$ sockets. We thus need to create at least $B-1$ sockets where each outlet gives us $A-1$ sockets, making our answer $\lceil \frac{B-1}{A-1} \rceil$. Since most programming languages use floor division, we can also express this as $\lfloor \frac{A+B-3}{A-1} \rfloor$.
Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc139/submissions/7249379)
---
#C — Lower
We essentially use two pointers. Maintain the starting position at zero. Then, while the next position isn't hi...
current engine is added to them. Then, we can prune this data to delete any
redundant nodes as
149.
Codeforces Round #250 Editorial ### [problem:437A]
We enumerate each choice $i$, and then enumerate another choice $j$ $(j \neq i)$, let $cnt = 0$ at first, if choice $j$ is twice longer than $i$ let $cnt = cnt + 1$, if choice $j$ is twice shorter than $i$ let $cnt = cnt - 1$. So $i$ is great if and only if $cnt = 3$ or $cnt = -3$.
If there is exactly one great choice, output it, otherwise output C.
### [problem:437B]
We could deal with this by digits.
Because $lowbit(x)$ is taking out the lowest $1$ of the number $x$, we can enumerate the number of the lowest zero.
Then, if we enumerate $x$ as the number of zero, we enumerate $a$ as well, which $a \times 2^x$ is no more than $limit$ and $a$ is odd. We can find out that $lowbit(a \times 2^x) = 2^x$.
In this order, we would find out that the $lowbit()$ we are considering is monotonically decresing.
Because for every two number $x, y$, $lowbit(x)$ is a divisor of $lowbit(y)$ or $lowbit(y)$ is a divisor of $lowbit(x)$.
We can solve it by greed...
If we delete the vertices in decreasing order, then it will contribute only
$\min(v_x, v_y)$, so, The best way to delete all n nodes is deleting them in decreasing order of
their value.
Tutorial of Codeforces Round 250 (Div. 2)
150.
Codeforces Round 1019 (Div. 2) — Editorial [problem:2103A]
Author: [user:NemanjaSo2005,2025-04-21]
<spoiler summary="Hint 0">
We need to solve the same problem $t$ times. We will make use of [loops](https://www.geeksforgeeks.org/loops-programming/) to do so. From now we will focus on solving a problem for one test case, but remember that all of the following will be in a loop. </spoiler>
<spoiler summary="Hint 1"> So the array $x$ is beautiful if there exists an array of distinct elements $y$ such that $x_i \cdot y_i$ is the same for all $1 \le i \le n$. We will try to make the condition into something more understandable. Suppose that the common product is some constant $C$. How can you express each $y_i$ in terms of $C$ and $x_i$? </spoiler>
<spoiler summary="Hint 2"> It can be expressed as $y_i = \frac{C}{x_i}$. If all $y_i = \frac{C}{x_i}$ must be all different, what does that force upon the array $x$ for it to be beautiful? </spoiler>
<spoiler summary="Hint 3">
Let $i$ and $j$ be indices of two arbitrar...
Tutorial of Codeforces Round 1019 (Div. 2)
151.
CodeForces Round 872(Div. 1&2) Editorial ## A. LuoTianyi and the Palindrome String
Consider the substring of $s$ from the second character to the last, or $s_2s_3\cdots s_n$. If it's not palindrome, then the answer must be $n-1$. What if it's palindrome? This implies that $s_2=s_n$, $s_3=s_{n-1}$, and so on. Meanwhile, the fact that $s$ is palindrome implies $s_1=s_n$, $s_2=s_{n-1}$, etc. So we get $s_1=s_n=s_2=s_{n-1}=\cdots$ or that all characters in $s$ is the same. In this situation, every subsequence of $s$ is palindrome of course, so the answer should be $-1$.
<spoiler summary="Code">
```cpp
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#define ll int
#define ft first
#define sd second
//#define endl '\n'
#define pb push_back
#define ll long long
#define pll pair<ll,ll>
#define no cout<<"NO"<<'\n'
#define no_ cout<<"No"<<'\n'
#def...
. Delete these edges from $E_0$ and we get the edge set $E$. Formally, an edge
$e$ is in $E$ if and only, When we delete the edges in $E$ from the original tree, we get some connected
components. Shrink
Tutorial of Codeforces Round 872 (Div. 1)
Tutorial of Codeforces Round 872 (Div. 2)
152.
A note on a nowcoder problem -- Centroid decomposition (点分治) Nowcoder problem (Chinese) [link](https://ac.nowcoder.com/acm/contest/51721/E). The submission is private because I don't want to publish my Nowcoder account, but you can copy the code at the end of this blog and paste it to the answer sheet, it will get AC.
[English version](https://codeforces.me/blog/entry/114434)
First I would like to thank [user:ShaoNianTongXue5307,2023-03-28] for his idea!
This is a learning note, most for myself. Most of this blog is not original.
**Part 1: Problem Statement:**
A tree $T=(V, E)$ has $n$ vertices and $n-1$ edges, the weight of each vertex $i$ is $a_i$.
For each edge $e$, you can determine its direction, i.e., for two vertices $u, v$, there are two states: $u \rightarrow v$ and $v \rightarrow u$. There are $2^{n-1}$ states in total.
For each state $S$, we define $f(S)$ as
$f(S) := \sum\limits_{(u, v) \in V \times V, v\,\text{is reachable from}\,u} |a_u - a_v|$.
Compute the sum of $f(S)$ over all $2^{n-1}$ states $S$, mo...
~cdt(){ delete[] mxsz; delete[] sz; delete[] p; delete[] g
153.
Setup for remote team competitions Hi. Remote team competitions/trainings became something we have to deal with nowadays and I think having a setup you feel comfortable with is something really valuable and nontrivial to achieve that you definitely should not neglect, effort put into this will quickly pay off. In our Polish Mafia team we already participated in many remote competitions
and struggled with various technical problems and through trial and error we converged to
a setup which I believe is close to ideal. Many of these pieces of advice are applicable to all kinds of remote collaboration, e.g. working on some university projects or research problems, however I felt the biggest need for it during these competitions since they are periods when I really need to be focused hard.
1) Communication <br>
The most important part in remote collaboration is communication. I definitely recommend PUSH TO TALK
(that is — an option where you talk if and only if you hold a specified key).
Background noises of o...
154.
How to solve DP problems: Regular Approach Hello! In the previous post I've introduced two kinds of dynamic programming: _Regular_ and _Process Simulation_. In it I've told how to solve DP problems using Process Simulation, please read it if you missed in order to understand the difference. Now I want to talk about tricks that help me solve DP problems with Regular approach.
While with the Process Simulation approach we had to invent some process that would build us the desired objects, **in the Regular approach we're going to deal with the objects directly**. Each state of the DP _(i.e., a set of values for each parameter)_ will correspond to some class of the desired objects, and the corresponding value in the DP table will contain some information about that class, _which is in fact equivalent to the Subtask formulation I've introduced in the previous post_.
In this post I'll focus on how to come up with transitions for the Regular DP, if you are already decided on the parameters. The general plan is:
1. Determine, ...
[problem:607B] _There is a sequence of numbers, you can delete a consecutive
segment of this
155.
Разбор VK Cup Round 2 [problem:532A]
--------------
We can add $n-k$ miners with height $0$ and it won't affect answer. So we can assume that numbers of miners and caves are the same.
For every cave let's define $t_i$ as maximal possible height of miner working in cave $i$ if we wouldn't change any cave. We can calculate it from root to leaves with line $t_i = min(t_{father}, h_i)$.
Let's say we don't change anything. We will try to assign all workers if it's possible or to do the best possible assignment otherwise — the one where there are few free (not occupied) caves and they are high (value $t_i$ is big). I will say later why we want them to be high. Formal definition (you don't have to read the next paragraph):
For every assignment let's sort free caves by $t_i$. In the best assignment number of free caves is minimal possible. And for every position in such a list free cave in the best assignment has value $t_i$ not lower than in any other assignment. It can be proven that best possi...
Tutorial of VK Cup 2015 - Round 2
156.
How to find alts Yesterday some guy posted a blog about accidentally submitting a solution to a problem in the most recent round meaning to do it after the contest ends. He entered a competition, lost 233 rating and then requested to make the contest unrated to him. As it is already clear to probably everyone, he participated from an alt and meant to submit from it, but for some reason logged in from his main.
<spoiler summary="Screenshot">
</spoiler>
I quickly found his alt and made a comment. Shortly after that he deleted the blog.
Here is a guide on how to find alts!
### Look at the submissions
This method works very frequently. What do people oftenly do after participating in a contest from an alt? They resubmit all the problems from their main. This is how it looks like in the example above:
5 problems were submitted in 1 minute. It means that the guy was either ...
157.
Codeforces Round #947 Editorial [problem:1975A]
Idea: [user:Bazoka13,2024-05-25] Solution: [user:Bazoka13,2024-05-25] Prepared by: [user:Bazoka13,2024-05-25]
<spoiler summary="Hint 1">
We can't do any insertions by the operation.
</spoiler>
<spoiler summary="Hint 2">
If the answer is yes, we can make $a$ become non-decreasing in no more than one operation.
</spoiler>
<spoiler summary="Solution">
Read the hints.
If $a$ is non-decreasing initially, the answer is yes.
If $a$ isn't non-decreasing initially, we can find the smallest $i$ such that $a_i> a_{i+1}$. Then we choose $x=[a_1,a_2,...,a_i]$ and $y=[a_{i+1},a_{i+2},...,a_n]$. If the array $y+x$ is non-decreasing, the answer is yes. Otherwise, the answer is no.
</spoiler>
<spoiler summary="Code">
~~~~~
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
...
$*$, otherwise $s, t$ can be exchanged. We still delete the beginning and the
end first. It is not difficult to, - If one of the first characters of $s$ and $t$ is $*$ or the first characters
can match,delete
Tutorial of Codeforces Round 947 (Div. 1 + Div. 2)
158.
NUS CS3233 Final Team Contest 2023 Editorial The contest announcement and invitation link is [here](https://codeforces.me/blog/entry/114880). The contest link is [here](https://codeforces.me/gym/104296).
## [A. Artistic Masterpiece](https://codeforces.me/gym/104296/problem/A)
<spoiler summary="Tutorial">
Since $(x,y)$ is covered by the brush iff $(x - x_c)^2 + (y - y_c)^4 \leq r$, that means we can decompose the area of the brush into $O(\sqrt[4]{r})$ independent 1-dimensional intervals (a contiguous block with the same $y$-coordinate).
For each center $(x_c,y_c)$ traversed by the brush, add the 1-dimensional intervals for $y \in [y_c - \sqrt[4]{r}, y_c + \sqrt[4]{r}]$. After adding these intervals, the problem is now reduced to computing the area union of 1-dimensional intervals for each separate $y$-coordinate.
</spoiler>
## [B. Broken Calculator](https://codeforces.me/gym/104296/problem/B)
<spoiler summary="Tutorial">
First, we consider the minimum cost to get from an integer $X$ to another integer $Y$ us...
159.
Atto Round 1 (Codeforces Round 1041, Div. 1 + Div. 2) Editorial ### ✨ **Hope you enjoyed the problems!** ✨
<span style="font-size: 20px;">[problem:2127A]</span><br>
**Idea:** [user:Bahamin,2025-08-04]<br>
**Preparation:** [user:Hamed_Ghaffari,2025-08-04]
<spoiler summary="Hints">
<spoiler summary="Hint 1">
What happens if $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) = 0$?
</spoiler>
<spoiler summary="Hint 2">
Now what happens if $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) \neq 0$?
</spoiler>
</spoiler>
<spoiler summary="Solution">
Let's see when does $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}])$ equal $\max([a_i, a_{i+1}, a_{i+2}]) - \min([a_i, a_{i+1}, a_{i+2}])$.
**Case 1:** $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) = 0$
This implies that all numbers are equal and non-zero, since otherwise $\min$ would be less than $\max$ and the difference wouldn't be $0$.
**Case 2:** $\operatorname{mex}([a_i, a_{i+1}, a_{i+2}]) \neq 0$
In this case $\min([a_i, a_{i+1}, a_{i+2}])$ should be $0$ because $0$ is in the seque...
160.
Codeforces Round #290 Editorial **Update 1** : here are the reference solutions for this contest:
1. Div2-A: [http://ideone.com/JP1Ksj](http://ideone.com/JP1Ksj)
1. DIv2-B: [http://ideone.com/udz3bN](http://ideone.com/udz3bN)
1. Div2-C / Div1-A: [http://ideone.com/KVobNb](http://ideone.com/KVobNb)
1. Div2-D / Div1-B: [http://ideone.com/7MQqOm](http://ideone.com/7MQqOm)
1. Div2-E / Div1-C: [http://ideone.com/z3FsU2](http://ideone.com/z3FsU2)
1. Div1-D: [http://ideone.com/Y7j21a](http://ideone.com/Y7j21a)
1. Div1-E: [http://ideone.com/Orbacp](http://ideone.com/Orbacp)
Note that for Div2-E / Div1-C, it is for the harder version: we need to handle '1' in the cycle.
[problem:510A]
There are 2 different ways to solve this kind of task:
First one is to simulate the movement of the snake head, and you draw '#'s on the board. The code will look like:
~~~~~
head = (1, 1)
repeat:
repeat m-1 times: head move to right
repeat 2 times: head move down
repeat 2 times: head move down
repeat m-1 ti...
method: each time we pick one node that have at most 1 neighborhood and delete
it. Repeat this process
Tutorial of Codeforces Round 290 (Div. 2)
161.
Deleting comments Hi Codeforces!
There recently was a post announcing some public event held on AllCups. I just knew that I could not pass by this topic because my experience with AllCups was terrible. That's why I warned the community and posted this comment:
Yesterday I checked and it had +9 upvotes, which means that the majority accepted this comment. But today I see that it was deleted!
As a CM, I have a right to complain about others' comments. I can report about violation of a specific set of rules. I don't see if my comment breaks any of these rules.
But the thing is: if you delete my comment because of some rule violation, then maybe you should let me know, like, "You know, that's not how you write comments on Codeforces, please don't do that again", and it would be at least understandable. I haven't received any notification that my comment was deleted and knew it by accident! As of now from my point of view it looks like AllCups just quietly de...
the thing is: if you delete my comment because of some rule violation, then
maybe you should let me, But the thing is: if you delete my comment because of some rule violation, then
maybe you should
162.
Codeforces Round 962 (Div. 3) Editorial [problem:1996A]
Problem Credits: [user:cry,2024-07-19] <br>
Analysis: [user:cry,2024-07-19]
<spoiler summary="Solution ">
If $n$ is a multiple of $4$, then you can have $\frac{n}{4}$ cows. Otherwise, you must have at least one chicken, so you can have $\frac{n-2}{4}$ cows and $1$ chicken.
</spoiler>
<spoiler summary="Code (C++)">
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc;
cin >> tc;
while (tc--){
int n;
cin >> n;
cout << (n + 2) / 4 << "\n";
}
}
```
</spoiler>
[problem:1996B]
Problem Credits: [user:sum,2024-07-19] <br>
Analysis: [user:cry,2024-07-19]
<spoiler summary="Solution ">
Let's define every $k$ by $k$ block of cells by its value in the top left corner, since all cells in the block must have the same value. So, we can just print out the value of the cell in every $k$'th row and every $k$'th column.
</spoiler>
<spoil...
Tutorial of Codeforces Round 962 (Div. 3)
163.
Codeforces Round 983 (Div. 2) Editorial <spoiler summary="README: Notice about solutions">
All editorial codes contain solutions wrapped in classes. I'll only paste the important part (`namespace solution` in C++, `class Solution` in Python 3) as plaintext in the solution code section (along with the corresponding AC submission link). You might want to see the code template here.
<spoiler summary="C++ template">
```cpp
#include <bits/stdc++.h>
using namespace std;
namespace solution {
bool hasMultipleTests = true;
void preprocess() {
// something
}
void input(int testcase) {
// something
}
void solve(int testcase) {
// something
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solution::preprocess();
int t = 1;
if (solution::hasMultipleTests) cin >> t;
for (int testcase=1; testcase<=t; testcase++) {
solution::input(testcase);
solution::solve(testcase);
}
return 0...
# "Delete" node and move pointer to next def erase(self): if
self.prev[self.pointer, // "Delete" node and move pointer to next void erase() { if (prev[pointer
Tutorial of Codeforces Round 983 (Div. 2)
164.
Unofficial Editorial for AtCoder Beginner Contest #185 [A — ABC Preparation](https://atcoder.jp/contests/abc185/tasks/abc185_a)
==============================================================
<spoiler summary="Solution">
Since we need exactly one of each of $A_1$, $A_2$, $A_3$ and $A_4$, we are limited by the minimum number we have of one of these. Therefore, we need to print the minimum element of these four.
[My solution](https://atcoder.jp/contests/abc185/submissions/18767215)
</spoiler>
[B — Smartphone Addiction](https://atcoder.jp/contests/abc185/tasks/abc185_b)
==============================================================
<spoiler summary="Solution">
If Takahashi's phone is to run out of battery during his walks between two of the locations, it will be at an even lesser battery at the end of that walk. So, we simply need to check that upon entering one of the $M$ cafes, or returning to his house, that his phone's battery is greater than 0, and increase his battery by $y_i-x_i$ for each of the cafes, whi...
165.
Bitwise range AND/OR with no updates in O(n) preprocessing and O(1) time per query There was a blog on this topic that I was about to comment on, but it seems that it got deleted :(
It was asking for a solution in $\mathcal{O}(n)$ preprocessing and $\mathcal{O}(1)$ query time. There are no updates. We make the standard assumptions that input integers have $\mathcal{O}(\log n)$ bits and operations on $\mathcal{O}(\log n)$-bit integers take $\mathcal{O}(1)$ time.
The obvious solutions to range AND and range OR are to
- Count the number of times every bit appears in every prefix ($\mathcal{O}(n \log n)$ preprocessing and $\mathcal{O}(\log n)$ query time)
- Use a interval AND / OR segment tree ($\mathcal{O}(n)$ preprocessing and $\mathcal{O}(\log n)$ query time)
- Use a sparse table ($\mathcal{O}(n \log n)$ preprocessing and $\mathcal{O}(1)$ query time).
Four Russians is a standard trick to achieve $\mathcal{O}(n)$ preprocessing and $\mathcal{O}(1)$ query time. However, I don't see how it can be used here to achieve that: while we can solve all queries of l...
166.
[Shitpost] How to Teach Kids Basic Data Structures Using the Methods of a Mathematics Textbook ## Conventions
This article is based on ordinary set theory. Natural numbers, integers, finite sequences, maps, Cartesian products, total orders, trees, induction, and the finite recursion theorem are assumed to be established. Write $\mathbf N=\{0,1,\ldots\}$ and $\mathbf N_{>0}=\mathbf N\setminus\{0\}$. All trees are finite trees; all intervals not otherwise qualified are integer intervals.
For $l,r\in\mathbf Z$, put
$$
[l,r]=\{i\in\mathbf Z:l\le i\le r\},\qquad [n]=[1,n].
$$
When $l>r$, $[l,r]=\varnothing$. For a nonempty finite set $E$, $|E|$ denotes its cardinality. The symbol $\sqcup$ denotes disjoint union. Composition of maps follows the convention $(f\circ g)(x)=f(g(x))$.
For $n\ge1$, put
$$
\lambda(n)=1+\lfloor\log_2 n\rfloor.
$$
All asymptotic estimates are taken as $n\to\infty$; bounds written in terms of $\lambda(n)$ also apply to $n=1$.
**Computational conventions.** Unless otherwise stated, we use the random-access machine model with word leng...
1. Let $z=0$. 2. While the stack is nonempty and $q_{s_t}>q_i$, set $z=s_t$ and
delete the last
167.
Incredible bug found in __gnu_cxx::rope Today when I took part in the Round #740 solving problem [D. Top-Notch Insertions](https://codeforces.me/contest/1558/problem/D), [my submission](https://codeforces.me/contest/1558/submission/126903561) failed on test 2 without knowing why. After asserting I found that rope contains unwanted contents and I didn't fix the problem during the contest.
However, when I replace all `__gnu_cxx::rope.erase(x)` into `__gnu_cxx::rope.erase(x, 1)`, my code works fine (idk if it will pass system test or not; at least, it passes asserting that all elements are rolled back to the initial state).
Then! I found it unbelievable to see the following code from [here](http://www.aoc.nrao.edu/php/tjuerges/ALMA/STL/html-4.1.2/rope-source.html#l02310):
Look at the line 2318, comments: `Erase, single character`.
However, it calls `erase(__p, __p + 1);`, who will erase `__p + 1` characters starting from the position `__p...
> We should just delete this class, so I don't have to keep fixing bugs in code
that nobody uses or
168.
Ten Years of Competitive Programming 5 Hey, Codeforces!
I’m AmirReza PourAkhavan, the former Codeforces Contest Coordinator. I let the story become complete, and I’m sharing it now.
The story is about a 16-year-old competitive programmer who left his family and migrated to another city alone to follow competitive programming. After seven years, he advanced to the International Collegiate Programming Contest World Finals twice.
Read the previous parts: [1](https://codeforces.me/blog/entry/107465), [2](https://codeforces.me/blog/entry/108838), [3](https://codeforces.me/blog/entry/114356), [4](https://codeforces.me/blog/entry/122483).
**Read the Persian version** [**here**](https://docs.google.com/document/d/1TN8pnS_8te7MLDYzMjlDxFrElNVjE4ZWjo1Ak-JJdmc/edit?tab=t.isfroku1gx3e).
This part covers from December 2016 to November 2017.
## The Codeforces Contest
Our contest was held on Codeforces, and it broke several records.
- The record for the highest number of upvotes on an editorial.
- The record f...
169.
Codeforces Global Round 23 Editorial Hi Codeforces,
I've tried my best to make a different editorial, I wish you enjoy it ...
[problem:1746A]
problem author: [user:MohammadParsaElahimanesh,2022-10-15], [user:AmirrzwM,2022-10-15]
<spoiler summary="step by step solution">
step 1:
It's obvious that the answer is "NO" if $a_{i} = 0$ for all $1 \le i \le n$.
step 2:
Lets prove that the answer is "YES" if $a_{i} = 1$ for at least one $1 \le i \le n$.
step 3:
If size of $a$ is equal to $k$, just use second type operation once and we are done.
step 4:
Otherwise (if $|a| > k$), there will be three cases: (assume that $a_{j} = 1$)
- if $j > 2$, you can use first type operation on first and second element and decrease size of $a$ by 1.
- else if $j < |a|-1$, you can use first type operation on last and second to last element and decrease size of $a$ by 1.
- else, it can be shown easily that $|a| = 3$ and $k = 2$ so you can use second type operation twice and turn $a$ into a single $1$.
In ...
Tutorial of Codeforces Global Round 23
170.
How I vibe coded a programming contests platform Hello old friends!
I recently decided to run an experiment: **could I build an entire programming challenges platform using nothing but an AI assistant**?
This post covers how that went, what I ended up with, and a few “you can’t make this up” moments along the way.
You can check it out [here](https://coding-platform-ochre.vercel.app/) (and solve problems in the ongoing contest) — feedback is welcome.
## Final architecture
* Next.js frontend + backend on Vercel
* Supabase Postgres for Users, Contests, Problems (including input/output files), and Submissions
* Private GitHub repo for problem development, plus a script to upsert them into the DB
* Redis cluster on Redis-Cloud for leaderboards and caching
## Development anecdotes
#### Day 1: instant success → instant disaster
July 28. I open Cursor IDE, set it to claude-4-sonnet, and say: “Make me a programming contest site with multiple ...
“optimization” was: whenever someone submits, delete all leaderboard data,
rescore every submission, ~~~ fetch(`${SUPABASE_URL}/rest/v1/submissions?id=neq.fake`, { method: 'DELETE
', headers
171.
Codeforces::Gym <p> We've made it! Or in any case, we are at least very close to it. </p> <p> On January 19, 2012 at 12:00 we open a sub-project called "Gym". In short, its goal is to enable the Codeforces coders not only to participate in competitions and discuss them, but also to train and coach easily. </p> <p> In fact, despite the wide diversity of online judges in the world, a well thought-out training service system does not exist. So, the expectations from this system are: </p> <ol> <li>Collection of online contests, composed mainly of the past official contests. </li><li> Opportunity to integrate the final standings of past contests in the online contests to be able to train "against" the official participants. </li><li> Opportunity to participate in the training at any time whatsoever, without fear that something breaks down and the server will fall. In short, reliability. </li><li> Opportunity to write virtual contests and to solve the problems in a practice mode. </li...
correction you can edit the results of auto-detecting file types, you can add
ordelete files and do other
172.
[Explanation] dsu on trees (small to large) Original post : [[Tutorial] Sack (dsu on tree)](https://codeforces.me/blog/entry/44351)
In this post, I am trying to explain every line of dsu on tree code.
The reason is the same as blog [51139](https://codeforces.me/blog/entry/51139) when I first learn it.
How many vertices in the subtree of vertex v has some property in $O(n \ log \ n)$ time (for all of the queries)?
**For example:**
Given a tree, every vertex has a color. The query is how many vertices in the subtree of vertex v are colored with color c?
First, calculate the size of the subtree of every vertex, it can be done with a single dfs $(sz[v] = v + all(sz[child \ of \ v]))$
~~~~~
void dfs_size(int v, int p) {
sz[v] = 1;
for (auto u : adj[v]) {
if (u != p) {
dfs_size(u, v);
sz[v] += sz[u];
}
}
}
~~~~~
**Code:**
~~~~~
void dfs(int v, int p, bool keep) {
int Max = -1, bigchild = -1;
for (auto u : adj[v]) {
if (u != p && Max < sz[u]) {
Max = sz[u];
bigchild = ...
go down to small child, we have to delete its information about color count so
that, which is the same as when we add it (now delete instead of add) so the
complexity is $O(n \ log \ n)$
173.
Codeforces Round #146 Tutorial ### [problem:236A]
It is a very simple problem, just count how many distinct chars in the input and output the correct answer.
### [problem:236B]
First of all, we can make a table of size a*b*c to store every number's d value. Then we can just brute force through every tripe to calculate the answer.
### [problem:235A]
It is a simple problem, but many competitors used some wrong guesses and failed. First of all, we should check if n is at most 3 and then we can simply output 1,2,6.
Now there are two cases: When n is odd, the answer is obviously n(n-1)(n-2). When n is even, we can still get at least (n-1)(n-2)(n-3), so these three numbers in the optimal answer would not be very small compared to n. So we can just iterate every 3 number triple in [n-50,n] and update the answer.
### [problem:235B]
Let us take a deep look at how this score is calculated. For an $n$ long 'O' block, it contributes $n^2$ to the answer.
Let us reformat this problem a bit and consider ...
Tutorial of Codeforces Round 146 (Div. 1)
Tutorial of Codeforces Round 146 (Div. 2)
174.
Codeforces Round 962 Video Editorial (with Hints) [problem:1996A]
<spoiler summary="Hint">
Greedily take Cow as long as you can.
</spoiler>
<spoiler summary="Video editorial">
<iframe width="853" height="480" src="https://www.youtube.com/embed/VIxp7EkV1d8?start=77" title="Codeforces Round 962 Solution Discussion | ABCDEFG | All Problems" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen width="700" height="500"></iframe>
</spoiler>
[problem:1996B]
<spoiler summary="Idea">
Just print all index $A[i*K][j*K]$
</spoiler>
<spoiler summary="Video editorial">
<iframe width="853" height="480" src="https://www.youtube.com/embed/VIxp7EkV1d8?start=390" title="Codeforces Round 962 Solution Discussion | ABCDEFG | All Problems" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cros...
Delete one road, now path between any pair of friends is unique. Try
Tutorial of Codeforces Round 962 (Div. 3)
175.
Polygon: updates (January — April 2017) Hello, Codeforces!
It is time to tell about the improvements in [Polygon](https://polygon.codeforces.com/). It is a system for the preparation of programming problems. All Codeforces rounds and many other olympiads prepared in Polygon. Everyone at any time can use this system.
#### Common
A special fields with examples now displayed on a page with a list of files which used in problem and on checker, interactor and validator pages. It will be very useful for the new users and will help them faster understand the system.
[cut] <br/>
Some new mail notifications on change in problems ans contests have been added. Now letters are sent when you add, change or remove access to problem/contest. Besides that the option of add a special emails has been added. Letters are sent on a special mails on any changes in problem or contest. You can add the special emails for the contest on Prop...
176.
Codeforces Round #837 (Div. 2) Editorial We apologize for the delay in editorial of the tasks.
[A. Hossam and Combinatorics](https://codeforces.me/contest/1771/problem/A)
Idea: [user:_HossamYehia_,2022-12-14]
<spoiler summary="Tutorial">
[tutorial:1771A]
</spoiler>
<spoiler summary="Solution(_HossamYehia_)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
#endif
int t;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i = 0 ; i < n ; ++i)
scanf("%d", a + i);
sort(a, a + n);
if(a[0] == a[n - 1]){
printf("%lld\n", (1LL * n * (n - 1LL)));
continue;
}
int mn = 0, mx = n - 1;
while(a[0] == a[mn])
++mn;
while(a[n - 1] == a[mx])
--mx;
long long l = mn;
long long r = n - mx - 1;
...
void operator delete(void *){}
Tutorial of Codeforces Round 837 (Div. 2)
177.
Codeforces Round 967 Video Editorial (with Hints) [Full video](https://youtu.be/aEJg_fFxYmU)
[problem:2001A]
<spoiler summary="Hint 1">
Let v be the element that remains when all the elements are equal.
What is the minimum no of operations required?
</spoiler>
<spoiler summary="Hint 2">
Let the number of times v be present in the array is fv.
Because we will have to delete all the elements not equal to v, the minimum no of operations required will be n — fv.
</spoiler>
<spoiler summary="Hint 3">
It turns out that this minimum is the answer ie we should never delete any element equal to v from the array.
</spoiler>
<spoiler summary="Hint 4">
Since we want the minimum number of operations required, we should choose the element with the maximum value of fv.
</spoiler>
My submission — [submission:277424035]
<spoiler summary="Video Editorial">
<iframe width="853" height="480" src="http...
It turns out that this minimum is the answer ie we should never delete, . Because we will have to delete all the elements not equal to v, the minimum
no of
Tutorial of Codeforces Round 967 (Div. 2)
178.
Codeforces Round #857 Editorial [problem:1802A]
------------------
Idea: [user:Aleks5d,2023-03-13], Preparation: [user:vaaven,2023-03-13]
<spoiler summary="Solution">
Let's show a construction that maximizes the number of likes. We need to first leave all the likes that we can put, and only then delete them.
To minimize the number of likes, we need to delete the like (if we can) immediately after we post it.
The code below implements these constructs.
</spoiler>
<spoiler summary="Code">
~~~~~
#include "bits/stdc++.h"
using namespace std;
void solve() {
int n;
cin >> n;
int likes = 0, dislikes = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > 0) likes++;
else dislikes++;
}
for (int i = 1; i <= n; ++i) {
if (i <= likes) cout << i << ' ';
else cout << likes * 2 - i << ' ';
}
cout << '\n';
for (int i = 1; i <= n; ++i) {
if (i <= dislikes * 2) cout << i % 2 << ' ';
el...
to first leave all the likes that we can put, and only then delete them., To minimize the number of likes, we need to delete the like (if we can)
immediately after we post
Tutorial of Codeforces Round 857 (Div. 1)
179.
IOI 2023 Robot Contest in Z* = 5 [IOI 2023 Robot Contest](https://ioi2023.hu/tasks/#:~:text=robot%20%E2%80%93%20Robot%20Contest) is a great task that reminds me of Turing machines and cellular automata.
<spoiler summary="If the task statement is too intimidating...">
Your goal is to program the robot _Pulibot_ to label a shortest path
between the northwest and southeast corners of a 2D grid with obstacles,
which are guaranteed to be reachable from each other.
However, Pulibot is short-sighted and has no memory.
Knowing only the colors of the cell it is at and the 4 adjacent cells
(including special "colors" for out-of-bounds cells and obstacles),
it has to decide what to recolor its current cell
and which direction to move in (including not moving, as well as terminating).
Pulibot cannot move out-of-bounds or into obstacles.
Initially, all empty cells are colored "blank", and Pulibot starts at the northwest corner.
After Pulibot terminates, the cells colored "path" must form a shortest path,
while th...
180.
TheForces Round #28 (Epic-Forces) Editorial [A Minimum Black Cells](https://mirror.codeforces.com/gym/105028/problem/A)
Idea:[user:wuhudsm,2024-03-14]
<spoiler summary="code">
```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef ABHISHEK_SRIVASTAVA
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, k, curr = 1, cost = 0;
cin >> n >> k;
bool change = 0;
while (k > 0) {
k--;
cost += curr;
if (change)
curr++;
change = 1 - change;
}
cout << cost << '\n';
}
return 0;
}
```
</spoiler>
<spoiler summary="solution">
- For $k=0$, we don't color any cell;
- For $k=1$, we color cell $(1,1)$;
- For $k=2$, we color cells $(1,1),(n,n)$;
- For $k=3$, we color cells $(1,1),(n...
Then we delete one node for each step. When we want to delete node $x$, we set
$\text{dep}_x = 0
Tutorial of TheForces Round #28 (Epic-Forces)
181.
Codeforces Round #269 Editorial [problem:471A]
------------------
Given six sticks and their lengths we need to decide whether we can make an elephant or a bear using those sticks. The only common requirement for both animals is that four leg-sticks should have same length. This means that the answer "Alien" should be given **only** if we can't find four sticks for the legs. Otherwise we will be able to make some animal. The type of the animal will depend on the relation of the remaining sticks' lengths. If they are equal then it will an elephant, if they are different we will have a bear.
So this algorithm should solve the problem:
1. Find the number which appears at least four times in the input.
2. If no such number exist then the answer is "Alien".
3. Otherwise remove four entries of that number from the input.
4. After removing that number you will have two numbers left, compare them and decide whether it's an elephant or a bear.
One shortcut for this problem might be to sort the in...
a. This line is the only line in the chunks — we simply delete the chunk then.
Tutorial of Codeforces Round 269 (Div. 2)
182.
Codeforces Round 1012 (Div.1, Div. 2, based on THUPC 2025 — Finals) Editorial We apologize for the late editorial.
[problem:2090A]
<br>
Idea: [user:_Lucien,2025-03-26]
<spoiler summary="Solution">
Let's calculate how many operations we need. The number of pairs of operations is $\left\lfloor\frac{a}{x + y}\right\rfloor$. Additionally, we add $+1$ if $(a \bmod (x + y)) \ge x$, because in this case, the first player will be able to make one more move. Note that the first part is always even, which means the answer depends only on whether $(a \bmod (x + y)) \ge x$, and in this case, the answer is YES.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void solve() {
int x, y, a;
cin >> x >> y >> a;
if (a % (x + y) < x) {
cout << "NO\n";
} else {
cout << "YES\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
}
~~~~~
</spoiler>
[problem:2090B]
<br>
Idea: [user...
Firstly, consider a classical dp to calculate $dp_{u,k}$ as the number of delete
$k$ vertices in
Tutorial of Codeforces Round 1012 (Div. 1)
Tutorial of Codeforces Round 1012 (Div. 2)
183.
Solution to problem M. Algoland and Berland of 2018-2019 ICPC, NEERC Today, I solved a beautiful problem from the NEERC Subregional Contest: [Problem M](https://codeforces.me/contest/1070/problem/M).
Since I didn't find an editorial nor a solution in the comments, I decided to write this blog about my solution.
For a visualization of my solution see: [Visualization of the program](https://www.jeroenopdebeek.nl/GeometryVisuals/spanningtree.html)
The problem boils down to constructing a spanning tree of a 2D point set with certain constraints. No three points in the point set are collinear. The points have two colors: red and blue. There is at least one blue and one red point. The constraints on the spanning tree are:
<ul>
<li>Edges of the spanning tree can only intersect at the ends, if they are drawn as line segments.</li>
<li>Edges of the spanning tree can only connect points with different colors.</li>
<li>For each blue point, the degree of the point in the spanning tree should be equal to $r_i$. </li>
</ul>
The constraints on $...
. Let's connect these with an edge. If $r_i$ of the blue point is 1, we delete
this point. Else we
184.
HPI 2026 Editorial Thank you to everyone who attended this year's Harker Programming Invitational (HPI)! If you haven't already, we would really appreciate it if you filled out our [feedback form](https://forms.gle/opwQmMZPBtM7uWCt9) so we can make our contest even better next year. Also, [Novice](https://codeforces.me/gym/106410) and [Advanced](https://codeforces.me/gym/106409) problems have been uploaded to the Gym for upsolving.
*Note:* Only solutions for the Advanced division are presented here, but solutions for Novice-only problems (Yash is Cross-Eyed, Repetition, Skills) can be provided upon request.
## Harker!!
<spoiler summary="Solution">
Pretty straightforward: most languages have a standard library function for finding a given substring in a string, so you can just use that.
</spoiler>
<spoiler summary="Code (Team Aarav)">
```python
def solution(s):
if "harker" in s:
return 1
return 0
T = int(input())
for _ in range(T):
s = input()
prin...
**Proof:** If two palindromes were to overlap, we would have to delete the
second one before
Tutorial of HPI 2026 Advanced
Tutorial of HPI 2026 Novice
185.
[Tutorial] Disjoint Sets Union (DSU) Extensions with Auxiliary Nodes: Move and Erase Hello Codeforces community, this is my first educational blog on a topic, hopefully some will find it useful despite it not being difficult in nature.
Note: This is not meant to be an introduction to Disjoint Sets Union, if needed, please refer to this [tutorial](https://codeforces.me/edu/course/2/lesson/7) before reading the following.
This is a tutorial based on this [article](https://oi-wiki.org/ds/dsu/). Here, I'll include some new ideas and implementation details of mine as well. Thanks [user:DavidTan,2024-06-17] and [user:nickyfoo,2024-06-17] for proof-reading and also [user:kelzzin2,2024-06-17] for exisiting.
DSU Recap
=========
For those who need a quick recap, DSU are meant to support 2 main operations:
- $union(a,b)$: merge the 2 sets that contain $a$ and $b$.
- $find(a)$: return some identifier that represents the set that $a$ is in. Note that $find(a) = find(b)$ iff $a$ and $b$ are in the same set.
How this is done is by representing the sets as forests. ...
$ operation, we can use the same array to represent $delete$, this is done by
setting node $i$ to point to
186.
Manacher's algorithm and code readability Hi everyone again! Recently, solving the problem [1937](http://acm.timus.ru/problem.aspx?space=1&num=1937) from Timus (by the way, I recommend it to you too! It is a great opportunity to improve yourself in string algorithms), I was faced with the necessity of finding all subpalindromes in the string. Experienced programmers already know that one of the best algorithms for this is Manacher's algo that allows you to get all subpalindromes in compressed form without any additional structures. The only problem — the algorithm is kinda hard to implement. That is, its idea is simple and straightforward, but the implementation usually are heaps of code to the widespread consideration of where to write +1, and where -1.
[cut]
<br>
For those who do not know or do not remember, I will describe briefly the Manacher's algorithm. Conciseness in memory is achieved through the fact that we do not store the indices of palindromes, and for each item in the string we store the half of th...
187.
Polygon's New Feature: Resolving Conflicts (finally!) Hello Codeforces!
I and [user:DK318,2021-07-09], as students of ITMO University, joined the Codeforces team in June. Last month we mainly dealt with the development of the Polygon platform and were focused on one significant feature lots of people dreamed of.
Have you ever made some changes to the problem, and at the same time another person changed the same file? I believe most of you did and disliked this situation. If you wanted to resolve the conflict, you needed to download an archive containing all your changes and repeat them all in the newest revision of the problem. This was very confusing and time-consuming, wasn't it? And now we present probably the most anticipated feature of Polygon since its creation: **a web interface for resolving conflicts**.
[cut]<br>
When the conflict occurs, the link 'Resolve Conflicts' will appear on the sidebar accessing the page, where you can merge different versions. If it is impossible to load into the problem, the same button will...
188.
Codeforces Round #114 — Tutorial I am sorry for mistakes in English and I will be glad if you tell me about them.
#### [problem:168A] Аuthor ~kuniavski,2012-03-27.
In this task, it was necessary to write exactly what has been described in statement.
In particular, it was necessary to have
$\left\lceil \frac{N\cdot Y}{100} \right\rceil $ people, who come to the meeting.
For this it was necessary to create
$\max(0,\left\lceil\frac{N \cdot Y}{100} \right\rceil -X) $ clones.
#### [problem:168B] Аuthor ~kuniavski,2012-03-27.
In this problem you had to write exactly what has been described in statment too.
Read lines one by one. Also keep the last block of lines that are not
amplyfying. If the next line is amplyfying (which can be checked
by linear search), we print the last block, if any, and the line itself.
Otherwise, remove all spaces from the string and add to the last block.[cut]
It only remains to distinguish between an empty block and a block of empty lines.
#### [problem:167A] Аuthor ~Alex-G...
Tutorial of Codeforces Round 114 (Div. 1)
Tutorial of Codeforces Round 114 (Div. 2)
189.
Codeforces Round #330 (Div.1 + Div.2) Editorial [595A — Vitaly and Night](http://codeforces.me/problemset/problem/595/A)
It was easy realization problem. Let's increase the variable $i$ from 1 to n, and inside let's increase the variable $j$ from 1 to $2 \cdot m$. On every iteration we will increase the variable $j$ on 2. If on current iteration $a[i][j] = '1'$ or
$a[i][j + 1] = '1'$ let's increase the answer on one.
Asymptotic behavior of this solution — $O(n m)$.
[595B — Pasha and Phone](http://codeforces.me/problemset/problem/595/B)
Let's calculate the answer to every block separately from each other and multiply the answer to the previous blocks
to the answer for current block.
For the block with length equals to $k$ we can calculate the answer in the following way. Let for this block the number must be divided on $x$ and must not starts with digit $y$. Then the answer for this block — the number of numbers containing exactly $k$ digits and which divisible by $x$,
subtract the n...
It can be easily shown that this algorithm delete always some number of the
leftmost, rightmost, Now, let's delete the magnets from the door one by one, gradually the door will
decrease. Obviously
Tutorial of Codeforces Round 330 (Div. 1)
Tutorial of Codeforces Round 330 (Div. 2)
190.
CodeCraft'15 IIIT Hyderabad Editorial [problem:100589A]
------------------
Given a rooted tree(at node 1) of **N** nodes,you have to handle a total of **Q** operations of type:
**1 U L X**: Increase coins by **X** of all nodes at a distance of **L** from root.
**2 X**: Report sum of all coins in subtree rooted at **X**.
**N** <= 10<sup>5</sup>
**Q** <= 10<sup>4</sup>
#### Difficulty:
Medium-Hard
####Explanation:
This approach uses a very specific technique of maintaining a buffer of update queries and updating the whole tree once buffer size exceeds a constant limit(we maintain this limit as sqrt(M)).
~~~~~
buffer=[]
q=input
while q--:
query = input()
if query==update:
buffer.add(query)
else:
//say query is “2 X”
//the answer that has been already calculated for node X
prevans= ans(X)
for i=0 to buffer.size():
//add to prevans the effect of buffer[i]
//let’s say buffer[i]=”1 U L...
191.
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + 2) Editorial <spoiler summary="Rating predictions">
| Predictor | A | B | C | D1 | D2 | E | F1 | F2 | G | H |
|-----------|---|---|---|----|----|---|----|----|---|---|
| Predicted | 486 | 927 | 839 | 1160 | 2236 | 1694 | 2406 | 3639 | 2607 | 3250 |
| [user:nifeshe,2026-10-18] | 800 | 900 | 1100 | 1400 | 2600 | 2000 | 2500 | 3500 | 2900 | 3400 |
| [user:ttamx,2026-10-18] | 800 | 1000 | 1200 | 1400 | 2500 | 1800 | 2100 | 3500 | 2800 | 3100 |
| [user:ItzSleepyXD,2026-10-18] | ? | ? | 1000 | ? | ? | ? | 2100 | 2800 | ? | ? |
| [user:simplelife,2026-10-18] | 800 | 1000 | 1100 | 1500 | ? | 1900 | 2300 | 3500 | ? | 3000 |
| [user:wakanda-forever,2026-10-18] | 900 | 1000 | 1100 | ? | ? | 2000 | 2100 | ? | ? | ? |
| [user:Marszpace,2026-10-18] | 800 | 1000 | 1100 | 1500 | ? | 1900 | ~2200 | ? | ? | ? |
| [user:Argentum47,2026-10-18] | 800 | 1200 | 1200 | 1600 | ? | 1900 | 2300 | ? | ? | 2700 |
| [user:omsincoconut,2026-10-18] | 800 | 1100 | 1300 | ? | ? | ? | 2400 | 3500 | 2600 | 3100 |
| [user:...
192.
Codeforces Round 1046 (Div. 1, Div. 2) Editorial <spoiler summary="Rate the Contest!">
- Amazing round:
- Good round:
- Average round:
- Bad round:
- Horrible round:
</spoiler>
[problem:2136A]
Idea: [user:Alan_dong,2025-08-25]
Preparation: [user:Register,2025-08-25]
<spoiler summary="Hint">
If one team got a score of $x$ in the first half, what is the maximum score the other team could get?
</spoiler>
<spoiler summary="Solution">
We can consider the first half and the second half separately. The dream might come true if and only if the scores in both halves are possible. In the second half, the RiOI team scored $(c - a)$ goals, while the KDOI team scored $(d - b)$ goals.
Suppose the RiOI team scored $x$ goals in some half. Denoting the score of the KDOI team as $y$, one can see that the maximal value of $y$ is $2\cdot x + 2$, under the goal order $\tt{\color{red}K\color{red}K\color{black}RK\color{red}K\color{black}R...RK\color{red}K\color...
Tutorial of Codeforces Round 1046 (Div. 1)
Tutorial of Codeforces Round 1046 (Div. 2)
193.
Centroid Decomposition on a tree(Beginner) ## When Centroid Decomposition comes?
1. Suppose a problem says that how many paths have a length exactly k in a tree.
2. Or, how many paths have xor k.
3. Sum of all xor path in a tree.
4. update a node Black to white or white to black. now query the shortest path from a node to a white node.
etc.
**So, it is clear, when a paths problem comes then we can use Centroid Decomposition.**
**For a single node query or from a specific node, DSU on Tree may do it.**
## Algorithm:
### 1. Find a centroid of current tree T.
`What is Centroid? `
Simply Centroid is a node if we delete it. It makes some subtrees where every subtree size must be less than **sz/2** {
sz is the size of the current tree T.}
`How can we find it?`
=> Take a node random node of current tree T. Now if it's every subtree size less than sz/2. Then it is a centroid.
=> If not, go to the highest size of the subtree.
**Note: In a tree only two Centroid possible F...
### 3. Delete the Centroid node C and find the new centroid of all subtrees.  Editorial [problem:1974A]
Idea: [user:Aksenov239,2024-05-21]
<spoiler summary="Tutorial">
[tutorial:1974A]
</spoiler>
<spoiler summary="Solution">
~~~~~
nt = int(input())
for t in range(nt):
line = input()
x, y = [int(q) for q in line.split()]
mm = (y + 1) // 2
x -= (mm * 5 * 3 - y * 2 * 2)
x = max(x, 0)
mm += (x + 5 * 3 - 1) // (5 * 3)
print(mm)
~~~~~
</spoiler>
[problem:1974B]
Idea: [user:MikeMirzayanov,2024-05-21]
<spoiler summary="Tutorial">
[tutorial:1974B]
</spoiler>
<spoiler summary="Solution">
~~~~~
def solve():
n = int(input())
b = input()
cnt = [0] * 26
for c in b:
cnt[ord(c) - ord('a')] = 1
tmp = ''
for i in range(26):
if cnt[i] > 0:
tmp += chr(ord('a') + i)
a = ''
for c in b:
a += tmp[-1 - tmp.find(c)]
print(a)
for _ in range(int(input())):
solve()
~~~~~
</spoiler>
[problem:1974C]
Idea: [user:MikeMirzayanov,2...
Tutorial of Codeforces Round 946 (Div. 3)
195.
Mo's algorithm and 3D Mo Mo's algorithm
==================
<spoiler summary="Problem 1">
### the number of distinct elements on a segment of an array
Given an array $A$ of length $n$ and $q$ queries.
Queries:
- Find the number of distinct elements on the segment [l; r] of the array $A$.
</spoiler>
<spoiler summary="Problem 2">
### the number of distinct elements on a segment of an array + changing an element
Given an array $A$ of length $n$ and $q$ queries.
Queries:
- Find the number of distinct elements on the segment [l; r] of the array $A$.
- Change an element
</spoiler>
Let's solve the first problem. We can solve it using persistent data structures, but we want to be able to solve problem 2 as well.
### Algorithm 1
Let's solve the task offline. We need to sort the queries using the <$\frac{l}{k}$, r> comparator, where k is a fixed integer. It is quite obvious that we can easily add/delete one integer (we can do that using another array B, $B_{i}$ equals to the number...
We don't know how to delete the elements.
196.
Codeforces Round #323 Editorial **Adiv2**
To solve the problem one could just store two arrays $hused[j]$ and $vused[j]$ sized $n$ and filled with false initially. Then process intersections one by one from $1$ to $n$, and if for $i$-th intersections both $hused[h_i]$ and $vused[v_i]$ are false, add $i$ to answer and set both $hused[h_i]$ and $vused[v_i]$ with true meaning that $h_i$-th horizontal and $v_i$-th vertical roads are now asphalted, and skip asphalting the intersection roads otherwise.
Such solution has $O(n^2)$ complexity.
Jury's solution: [submission:13390628]
**Bdiv2**
It is always optimal to pass all the computers in the row, starting from $1$-st to $n$-th, then from $n$-th to first, then again from first to $n$-th, etc. and collecting the information parts as possible, while not all of them are collected.
Such way gives robot maximal use of every direction change. $O(n^2)$ solution using this approach must have been passed system tests.
Jury's solution: [submission:13390612]
*...
table and delete it from table elements set. We've deleted $gcd(a_n,a_n)$, so
the set now contains
Tutorial of Codeforces Round 323 (Div. 1)
Tutorial of Codeforces Round 323 (Div. 2)
197.
5th place curse in Turkish Team Selection Contest and my goodbye Hello, I want to talk about an ongoing curse in Turkey. I am the most recent victim of that curse at it's 9th year. Let's start with the beginning.
#### 2015-2016
Curse starts with [user:ErdemKirez,2023-05-10] taking 5th place in 2015. After that year, he tried his best and was in the team in 2016. But because of some reasons Turkey team wasn't able to participate IOI 2016. After that, the curse has started. You can look at this [blog](https://codeforces.me/blog/entry/54007) for details.
#### 2017
I don't know who was at 5th place that year. But probably curse was active.
#### 2018-2019
In 2018, [user:TahsinEnesKuru,2023-05-10] got 5th place. 3/4 of that team was at their last year so he had a high chance of being in the team at 2019. But he didn't know, he was already cursed. He missed the team with a difference of 3/700. He also has a [blog](https://codeforces.me/blog/entry/66811) about it.
#### 2020
At that year, [user:ExpertHunter,2023-05-10] got 5th place. He was at hi...
wrong problem. Luckily, for solving the subarray version i just needed to
delete some lines, but while
198.
Codeforces Round #157 — Editorial ###[problem:259A]
Obviously, the only correct rows are rows WBWBWBWB and BWBWBWBW. Only thing you need to do is to check whether each string is one of these. If yes then print YES, else print NO.
###[problem:259B]
Since each number is less than or equal to $10^5$, you can loop all possible $a_{1,1}$ values, the rest of cells can be calculated from this.
###[problem:258A]
It's pretty easy to notice that you need to delete the first (from the left) 0-digit. The only catchy case is 111...111 — here you need to delete any of 1-digits.
###[problem:258B]
First of all, lets think about the problem of finding array $c_i$ — the number of integers from 1 to $m$ such, that the number of lucky digits is equal to $i$. It's pretty standart dynamic programminc problem, which can be solved with state [position][less][count].
It can be solved directly using DP, but to simplify a bit you can use brute force (recursion) to brute all possible assignments of numbers of ...
It's pretty easy to notice that you need to delete the first (from the left)
0-digit. The only
Tutorial of Codeforces Round 157 (Div. 1)
Tutorial of Codeforces Round 157 (Div. 2)
199.
[Gym Contest Editorial] HIAST Collegiate Programming Contest 2016 ## Cards
We notice that the second box includes only even numbers , because all numbers in it are in the form `2X`
- if the number is odd it's obviously in the first box .
- if the number `X` is even then `X` and `X/2` will not be in the same box .
So we can keep dividing the number on 2 until we get an odd number which is obviously in the first box, After that we can easily compute the answer depending on how many times we divided the number until it became odd .
Total Complexity: **O(log(Q))**
Problem by: [user:AHMED_GAFER,2016-08-11]
##RGB plants
Since `n` is very large, we have to find a fast way to calculate the answer.
We can notice that after each day, we can calculate the number of each one of the flowers `New`, based on the number of the flowers on the day before `Old`, like the following:
- The number of red flowers would be equal to `NewRed = OldRed*1 + OldGreen*4 + OldBlue*7`.
- The number of green flowers would be equal to ...
digit which is greater than the digit to the right of it and delete it, or
delete the right most, top of the stack while the top of stack is bigger than the current digit and
we candelete more
200.
[Tutorial] Invariants and Monovariants Hello Codeforces! Some months ago I wrote tutorial about [basics of recurrent sequences](http://codeforces.me/blog/entry/54154). This blog, my second tutorial is about mine another favorite topic — Invariants and Monovariants. These are useful concepts which will help you solving problems, especially, constructive ones. Even if you are not familiar with this topics, I'm sure that you solved problems with use of invariants and monovariants without knowing it, continue reading, you will understand my point :) There will be hard problems which are based on old IMO problems, so I will try my best to explain solutions of examples.
So, what are Invariants and Monovariants? An invariant is a quantity that doesn't change. A monovariant is a quantity that changes monotically (that is, non-decreasing or non-increasing). Seems simple, yes?
Let's start with a few easy examples which you will better understand its point. I suggest you to try solving problems by your own before reading ...
201.
[GYM] Damascus-CPC 2018 — Editorial A. Martadella Strikes Again
==================
if $ R*R > 2*r*r $ print $1$, otherwise print $2$
$R$ and $r$ should be **long long** or **double** to avoid overflow
[C++ Code](https://pastebin.com/1CKZu6yN)
B. Amer and Graphs
==================
Since the edges are undirected ,we can store the edges ${u,v}$ as $(u \le v)$ for every edge $(1 \le i \le n)$.
Let's assign a unique number for every unique edge in the array, then our problem will be reduced to :
Find the number of different segments of the array which have the exact same elements ( same frequencies as well for each element ).
This problem is a classic hashing problem that can be solved this way :
let's choose some random large prime numbers $P$ and $MOD$ ,for example $P=304933 , MOD=10^9+7$.
replace every element ${x_i}$ from the array with $ P^{x_i} \% MOD $.
now the final problem is about finding different segments of the array which have the same sum value $\% MOD$ .
This sol...
Delete any edge from the cycle, let's say it connects nodes $u$ and $v$ with
weight $w$.
202.
Codeforces Round #362 (Editorial) [Here](https://gitlab.com/amirmd76/cf-round-362/tree/master) is git repository to solutions of problems of this contest.
### Div.2 A
You should check two cases for YES:
1. $x\ mod\ s = t\ mod\ s$ and $t \leq x$
2. $x\ mod\ s = (t + 1)\ mod\ s$ and $t+1 < x$
Time Complexity: $\mathcal O(1)$
[Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/2A)
### Div.2 B
Nothing special, right? just find the position of letters `.` and `e` with string searching methods (like `.find`) and do the rest.
Time Complexity: $\mathcal O(n)$
[Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/2B)
### A
Do what problem wants from you. The only thing is to find the path between the two vertices (or LCA) in the tree. You can do this in $\mathcal O(lg(n))$ since the height of the tree is...
delete her.
Tutorial of Codeforces Round 362 (Div. 1)
203.
Codeforces Round 1114 (Div. 3) — Editorial Thank you for participating in the contest! I hope you enjoyed all problems :) Also, thanks to [user:reirugan,2026-08-04] for proofreading the editorial.
<spoiler summary="Rating Predictions">
| Predictor | A | B | C1 C2 | D | E | F | G |
|----------------------------------|-----|-----|------|------|------|------|------|
| [user:yse,2026-08-04] | 800 | 800 | (900 — 1000) | 1200 | 1400 | 1700 | 2000 |
| [user:Wageeh,2026-08-04] | — | 1000 | (1300 — 1300) | 1500 | — | — | 1900 |
| [user:Proof_by_QED,2026-08-04] | 800 | 800 | (1000 — 1100) | 1300 | 1300 | 1900 | 2100 |
| [user:detective...dots,2026-08-04] | 800 | 900 | (1100 — 1100) | 1300 | 1400 | 1800 | 2100 |
| [user:Mr_Bald,2026-08-04] | 800 | 900 | (1100 — 1200) | 1400 | 1500 | 1800 | — |
| [user:Argentum47,2026-08-04] | 800 | 900 | (1000 — 1200) | 1300 | 1400 | 1800 | 2000 |
</spoiler>
<spoiler summary=...
will still exist. The only way we can delete the whole block is if it had a
size of $1$. This allows
Tutorial of Codeforces Round 1114 (Div. 3)
204.
Editorial of Codeforces Round 958 (Div. 2) Thanks for participation!
**Update**: added alternative solutions/proofs for A,B,D,F
[problem:1988A]
<spoiler summary="Hint 1">
The optimal sequence of operations is very simple.
</spoiler>
<spoiler summary="Solution">
The optimal sequence of operations is adding $k-1$ 1-s into the set each time, at the same time decreasing $n$ by $k-1$. This implies that the answer is $\lceil \frac{n-1}{k-1}\rceil$.
<spoiler summary="Why?">
I failed to find a Div2-A level proof. If you have a simpler proof please share it in the comments.
Consider the number of elements that is $\equiv 1\pmod{(k-1)}$ in the set. The number of such elements increase by at most $k-1$ in each operation, and the aforementioned sequence of operation achieves the maximum increment.
---
A simpler proof in the comments: consider the number of elements in the set. It increases by at most $k-1$ each time, and our construction reaches the maximum increment.
</spoiler>
</spoiler>
<spoiler summar...
Consider a vertex $x$. If we delete it, what would happen to the tree? Vertices
that are on the
Tutorial of Codeforces Round 958 (Div. 2)
205.
TheForces Round #19 (Briefest-Forces) Editorial [A](https://codeforces.me/gym/104455/problem/A)
<spoiler summary="code">
```
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
const int MOD=998244353;
void Delta() {
int a,b,c,d;
cin >> a >> b >> c >> d;
cout << (a+b>c+d?"YES":"NO") << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) Delta();
}
```
</spoiler>
<spoiler summary="solution">
The probability of Alice's winning is strictly higher than Bob's iff $l_1+r_1>l_2+r_2$.
<spoiler summary="Why?">
Lemma1:The distribution of scores for two dice rolls is symmetrical, with the axis of symmetry being $l+r$.
For example,for $[2,4]$,the distribution of scores is $4,5,5,6,6,6,7,7,8$.
Lemma2:For two intervals with the same axis of symmetry(i.e. $l1+r1=l2+r2$),Alice's probability of losing is always equal t...
**Submitting this code directly will get ILE, please delete cerr and
Tutorial of TheForces Round #19 (Briefest-Forces)
206.
Codeforces Round 911 (Div. 2) Editorial [problem:1900A]
Author: [user:NemanjaSo2005,2023-11-26]
<spoiler summary="Hint 1">
Assume that cells $i-1$, $i$, and $i+1$ are covered in water. What happens if you remove water from cell $i$?
</spoiler>
<spoiler summary="Hint 2">
The water at position $i$ is replaced as both cells $i-1$ and $i+1$ have water in them.
</spoiler>
<spoiler summary="Solution">
Read the hints.
If there are 3 consecutive empty cells $i-1$, $i$, $i+1$, we can place water in cells $i-1$ and $i+1$ and then move water from cell $i$ to all other cells. If there are no such cells, we have to place water on every empty cell.
So if we find substring ''...'' in the array, the answer is $2$, otherwise the answer is the number of empty cells.
Time and memory complexities are $O(N)$.
</spoiler>
<spoiler summary="Bonus">
Solve the problem if it is required that each cell is filled with water, or next to at least $1$ cell that is filled with water.
</spoiler>
[problem:1900B]
...
Tutorial of Codeforces Round 911 (Div. 2)
207.
An efficient way to strengthen up your segment tree. I'm going to talking about a coding style in segment tree which I used for a long time. Not only is it more systematically, but it also support more kind of segment tree.
1. Old style
------------
Assume that we are making a segment tree support operators assign elements in a range (assign-range L R X) and get max element in a range (max-range L R).
I found a large number of people use the following way to build segment tree:
~~~~~
void lazy_update(int u, int ll, int rr) {
if (Lazy[u]==-1) return; // assume that -1 is unused value
if (ll!=rr) Lazy[u*2]=Lazy[u*2+1]=Lazy[u];
Max[u]=Lazy[u]; Lazy[u]=-1;
}
void assign_range(int u, int ll, int rr, int L, int R, int X) {
lazy_update(u, ll, rr); // call a function to lazy-update node u (which operate segment ll..rr)
if (ll>R || L>rr) return;
if (L<=ll && rr<=R) {
Lazy[u]=X;
lazy_update(u, ll, rr);
return;
}
assign_range(2*u, ll, (ll+rr)/2, L, R, X);
assign_range(2*u+1, (ll+rr)/2+...
- check i j k: Check if S[i..i+k-1] is equal to S[j..j+k-1]. - delete k: Delete
k-th element.
208.
Graph saving methods Hi.
## Introduction.
We have a graph, we want to save it (and maybe run DFS on it for example); simple? Yes, but I want to show different methods for this, you can choose any of them depending on problem.
### Adjacency matrix.
Simple, if graph is not weighted, save in $G[v][u]$ if there is an edge between $v$ and $u$ or not.
If graph is weighted, if there is an edge between $v$ and $u$ save it’s weight in $G[v][u]$, save $-1$ otherwise (if weight can be negative, use $inf$ instead of $-1$).
Memory usage : $\mathcal{O}(n ^ 2)$.<br>Overall time complexity : $\mathcal{O}(n ^ 2)$ (for running dfs).
<spoiler summary="Code here">
~~~~~
// God & me
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 17;
int n, m;
bool G[maxn][maxn], mark[maxn];
void dfs(int v){
if(mark[v]) return ;
mark[v] = 1;
for(int u = 0; u < n; u++)
if(G[v][u])
dfs(u);
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
...
about edges, i.e. change weight, delete edge). Keep index of edges related to
each vertex in its
209.
Meta Hackercup Practice D2 problem #### Problem D2: Line of Delivery (Part 2) [Link](https://www.facebook.com/codingcompetitions/hacker-cup/2024/practice-round/problems/D2)
Hello everyone, I'd like to talk about Problem D2 from the recent Meta Hacker Cup 2024 Practice Round. The solution suggests that we can use a treap data structure to efficiently handle the operations described in the problem.
Operation 1) Insert a stone at $E_i^{th}$ empty position.
Operation 2) Move all stones to the left of the inserted stone by 1 unit in the negative direction.
Yes, treaps can be used to solve this problem, but I’ve come up with a simpler solution using a vector approach. Let's maintain an array called `emptyPlaces` that stores information about all the empty spots. In this array, I track how many balls are located immediately to the right of each empty position. So `emptyPlaces[i]` denoted how many consecutive balls are immediately right towards $i^{th}$ empty ...
210.
Codeforces Round 1066 (Div. 1 + Div. 2) Editorial [problem:2157A]
Author: [user:TheScrasse,2025-11-22]<br>
Preparation: [user:TheScrasse,2025-11-22]
<spoiler summary="Hint 1">
Each value $x$ is independent of the others; only its own frequency matters.
</spoiler>
<spoiler summary="Hint 2">
In a balanced array, value $x$ must appear either $0$ times or **exactly** $x$ times.
</spoiler>
<spoiler summary="Solution">
- Each value $x$ is independent of the others; only its own frequency matters. In particular, for each value, find its frequency $f[x]$.
- In a balanced array, value $x$ must appear either $0$ times or **exactly** $x$ times. Specifically, if it appears $< x$ times at the beginning, you have to delete all its occurrences, otherwise you should keep $x$ occurrences. Specifically, for each $x$, add $f[x]$ to the answer if $f[x] < x$, else add $f[x] - x$.
Complexity: $O(n)$ time. Slower solutions (e.g., $O(n^2)$) are allowed.
</spoiler>
<spoiler summary = "Code">
[submission:350380351]
</spoiler>
[...
delete all its occurrences, otherwise you should keep $x$ occurrences.
Specifically, for each $x$, add
Tutorial of Codeforces Round 1066 (Div. 1 + Div. 2)
211.
[Community Editorial] Codeforces Round #720 (Div.2) Problem D — Nastia Plays with a Tree Hello Codeforces!
Today was Codeforces Round #720 (Div.2), in which I solved problem D — Nastia Plays with a Tree. As I find my solution different from the solutions I heard of after the contest, I will explain it in detail in this blog post. I will note that you still might find value in reading this if you solved the problem, as my proposed solution also maintains at every stage the graph being a forest (i.e I don't create any cycles).
**The Solution**
<spoiler summary="Solution By FiveSixFiveFour">
Note that in this editorial, when I write *simple path*, I mean a simple path between two nodes without having extra edges going from any of the nodes that do not belong to that simple path, or simply a node not connected to anything (this will be clearer once we see drawings).
We should first note that bamboo is simply a tree that looks like a single line of connections (i.e a simple path).
We observe that given the sequence of moves the order we delete/link edge...
We observe that given the sequence of moves the order we delete/link edges in
does not change the
212.
[Tutorial] On Applications of CDQ Divide & Conquer _This tutorial is nominated for the [blog posts competition](https://codeforces.me/blog/entry/149422) from [user:cadmiumky,2026-02-07]. Thanks to him for this initiative!_
_Also thanks to [user:Ghos007,2026-02-08], [user:dima210121012101,2026-02-08], [user:dmitryAdams,2026-02-08] and ChatGPT for proofreading this post and giving useful feedback._
---
CDQ Divide & Conquer is an interesting algorithmic technique that nobody talks about (at least in Russian CP community). However, it is quite powerful, as it often provides unexpectedly clean solutions to seemingly tedious problems. In this tutorial, I will discuss different contexts where this method is useful. I also want to collect what I have seen about this technique on the Internet in one place and add my own insights. Credit to [robert1003's blog](https://robert1003.github.io/2020/01/31/cdq-divide-and-conquer.html) where I first learned this method.
The main idea of this technique is to calculate the **influence/contr...
, $i$ splits one existing interval into two, so we delete the two intervals
that had $i$ as an, delete another point with the same $r$. This is easy to fix by compressing
$r_i$ values and assigning
213.
About ordered set Hi everyone! I think many of you know about such data type as set. It must support such operations like:
* Insert an element into set;
* Check if the set contain some element;
* Delete element from set.
If we talk about ordered set, then elements (what a surprise!) must be kept in some order. As I think, there is also very important next operations:
* Find the k-th element in a set;
* Find the order of element in a set.
Most of all, for the implementation of such functional some may use binary balanced trees (AVL- tree , red-black tree , cartesian tree , etc). However, in this article I would like to talk about some of the features in the implementation of an ordered set with other structures. In particular, I'll show the implementation with the segment tree and with the Binary Indexed Tree (Fenwick tree). But I just want to note that it only allows you to build the set of natural numbers. For all other types of elements such methods will not work :(
The basic id...
* Insert an element into set; * Check if the set contain some element; * Delete
element from
214.
Codeforces Global Round 28 Editorial [problem:2048A]
Author: [user:Little09,2024-12-19]
<spoiler summary="Hint 1">
How much does the number decrease when we remove two consecutive $3$ s?
</spoiler>
<spoiler summary="Tutorial">
### [problem:2048A]
When we transform $\overline{x33y}$ into $\overline{xy}$ (where $x$ and $y$ are decimal numbers), the actual value changes from $10^{p+2} \cdot x + 33 \cdot 10^p + y$ to $10^p \cdot x + y$. The decrease is $99 \cdot 10^p \cdot x + 33 \cdot 10^p$. It is easy to see that $33 \mid (99 \cdot 10^p \cdot x + 33 \cdot 10^p)$. Therefore, we can replace the operation of removing two consecutive $3$ s with a series of $-33$ operations.
Hence, we only need to determine whether $x$ can be reduced to $0$ using a series of $-33$ operations, which is equivalent to checking whether $x \bmod 33$ equals zero.
</spoiler>
[problem:2048B]
Author: [user:wsyear,2024-12-19]
<spoiler summary="Hint 1">
If the permutation is sufficiently long, what is the maximum number of leng...
Tutorial of Codeforces Global Round 28
215.
The Automaton Interpretation for the KMP Algorithm ## Introduction
This article was started by [user:LeoRiether,2025-09-04] and concluded by me. I found his idea incredible and offered to help him finishing the text he started to write [here](https://leoriether.github.io/posts/kmp/) some years ago. I hope everyone finds it interesting! I think it's the most natural way to understand the KMP algorithm.
When following the examples, you should use [user:LeoRiether,2025-09-04]'s [KMP simulator](https://leoriether.github.io/kmp-simulator/) to see for you yourself what is happening.
The definitions presented here will not be so rigorous, but will instead follow a more intuitive approach. We will use examples with strings composed of characters from $a$ to $z$, but you could do the exact same with any other alphabet (like the natural numbers or whatever you want).
## Automaton?
The text will assume you know what is a nondeterministic finite automaton (NFA) and a deterministic finite automaton (DFA), but I believe that an intuitive...
$B$ that have the character $S_i$, we will prepare to create a new thread at
$B$ anddelete the
216.
Hello 2026 Editorial We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated!
<spoiler summary="Rate The Contest!">
-
Great contest
-
Good contest
-
Average contest
-
Bad contest
</spoiler>
## [2183A — Binary Array Game](https://codeforces.me/contest/2183/problem/A)
Idea & Preparation: [user:wangmarui,2025-12-23]
<spoiler summary="Rate The Problem!">
-
Good Problem
-
Okay Problem
-
Bad Problem
-
Didn't Solve
</spoiler>
<spoiler summary="Hint 1">
If the sequence $a$ consists entirely of $1$ s, what will Alice do?
</spoiler>
<spoiler summary="Hint 2">
Consider discussing the values of $a_1$ and $a_n$.
</spoiler>
<spoiler summary="Solution">
First, if the entire sequence consists of $1$ s, Alice wins immediately by operating on the whole sequen...
Tutorial of Hello 2026
217.
CHelper 3.9 I would really appreciate any new ideas of what new features to add
I would also appreciate [donations](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=)
-----
3.99
Kattis support for both Chrome and Contest parsers. You'd need to accept new permissions for Chrome extension. Good luck at ACM ICPC World Finals online contest!
-----
3.98
Codechef fix
-----
3.97
Fixed issue with template selection and Chrome plugin interaction
-----
3.96
Smallish update — you can now select task template per task. You can have several templates for general tasks, one where you need to output with Case #, GCJ where you need to integrate parallelization and similar
-----
3.95
Support for Idea 14.1+
Parsers for RCC and USACO fixed
You can now parse other Codeforces contests when live contest is ongoing
Sorry fo...
Also speed up and for RCC parsing, HackerRank parsing fix and Delete Task pop
up fix, Would you delete this files by mistake they would be recreated next time you
reopen project or when
218.
Counting forests with limited degrees and component sizes Someone posted a modified variant of [ABC 180 F](https://atcoder.jp/contests/abc180/tasks/abc180_f) here before and asked for help solving it. The task went as follows: given $n$ and $\ell$, count the number of labeled graphs on $n$ vertices such that no vertex has a degree exceeding 3, there is no cycle in any connected component (i.e. the graph is a forest) and the largest connected component has exactly $\ell$ vertices.
I wrote a rather long comment explaining how to solve it. I hit "post" and...
the blog was gone.
**To whoever was the author: please don't do this. It's very frustrating to put effort into writing an explanation only to discover that it had been completely in vain.** Even if you already got an answer from elsewhere, other users might enjoy reading the solution. It was not the case here, but especially don't delete/hide your blog if there already are answers in the comments. This way ...
especially don't delete/hide your blog if there already are answers in the
comments. This way you're
219.
mBIT 2025 Editorial Thank you to everyone who competed in mBIT 2025! It was a record breaking year for us with 84 in-person participants and 135 online participants. We hoped you guys enjoyed it as much as we did.
We tried hard to make the problems fun and interesting for as wide of a skill gap as possible. In fact, this year's competition had an in-person team of middle schoolers that was unfamiliar with for loops, and an online team with all three participants in the top 15 in the world in codeforces. We are glad to contribute to all niches of the computer science community: beginner and advanced, local and global. Thank you all for your enthusiasm.
Congratulations to the winners:
**Online Advanced:**
- 1st place — HoMaMaOvo — Masaki Nishimoto, Riku Kawasaki, Yui Hosaka
- 2nd place — mathforcesbox — Brian Xue, Bing-Dong Liu, Alex Chen
- 3rd place — bluepuppygreenturtle — Rain Jiang, Kai Jiang
**Online Intermediate:**
- 1st place — NULP Lega...
220.
Editorial of TheForces Round #13 Hello Codeforces!
Thanks for participating in [the round](https://codeforces.me/contestInvitation/6f589939fd095f0f82a175a52d83611a2ddd49d0), We hope you liked the problems!
Also huge thanks to [user:Endlessdreams,2023-05-07] for preparing the editorial.
<spoiler summary="Round 13">
<spoiler summary="Problem A">
Calculate the units first, and then calculate the value according to the units
<spoiler summary="Code">
~~~
void elysia() {
int n;cin >> n;
if(n<1024ll) cout << n << "B" << endl; else
if(n<1024ll*1024ll) cout << n/1024ll << "KiB" << endl; else
if(n<1024ll*1024ll*1024ll) cout << n/1024ll/1024ll << "MiB" << endl; else
if(n<1024ll*1024ll*1024ll*1024ll) cout << n/1024ll/1024ll/1024ll << "GiB" << endl;
}
~~~
</spoiler>
</spoiler>
<spoiler summary="Problem B">
You can compute this with fast powers, or you can compute whether n is odd or even.
<spoiler summary="Code">
~~~
void elysia() {
int n,m;
cin >> n >> m;
cout << power...
Let $dp_{l,r}$ represent the number of methods to delete the interval $(l,r)$.
We enumerate $x$ to, We must delete everything within $(l+1,x-1)$ before $a_l-a_x$, while $(x+1,r)$
is free todelete.
Tutorial of TheForces Round #13 (Boombastic-Forces)
221.
Maintain subtree information using link/cut trees In the tutorial of [problem:1172E], I didn't write things on how to maintain subtree information, because I thought it was a popular trick. However, through [user:tmwilliamlin168,2019-06-12]'s [comment](/blog/entry/67511?#comment-518361), I realized that this trick may be not so common in other countries, so I decided to write a blog on it.
This blog will tell you how to maintain subtree information using LCT, with solutions on some problems, so you should know LCT before reading this blog.
## Main Idea
The main idea is simple: record the sum of information of "virtual subtrees", where the "virtual subtrees" refers to the subtrees except the one in the Splay.
In the picture, $1$, $2$, $6$, $10$ are in a Splay, while $8$ and $12$ are in another. The "virtual subtrees" of $1$ is $3$ and $4$, the "virtual subtrees" of $4$ is $7$ and $8$, the node $8$ has no "virtual subtree".
You need to update the i...
` delete the $x$-th simple path inserted in $S$ 4. `x y` a query, asking if all
simple paths in $S$ go
222.
Me trying to study Atcoder World Tour Finals 2026 Algorithm : E — Even Rows 
It took days for me to just to barely understand the editorials and from my own opinion, it was so obscure and omitted lot of thing to barely make sense so I had an idea to share my own analysis here for everyone to discuss. Please note this is a wall of text since I want to elaborate on every ambiguous part of editorial and explain my flow of logic as much as possible and for anyone patient enough to read through the end, please share some advice and opinion to optimize and speed up my logic arguments, maybe fixing some typo or request some clarification of my explanation if possible. Thank you for reading.
First about the problem statement, it can be divide into 3 parts :
- Input :
+ A table with size $N\times M$
+ Each cell is either empty or has a piece on it
- Algorithm 1 : Take a table with pieces on it as input
+ Define the way to move a piece in the table
+ The ...
223.
Editorial for Codeforces Round #910 (Div. 2) ## [1898A *-* Milica and String](https://codeforces.me/contest/1898/problem/A)
Author: [user:n0sk1ll,2023-10-01]
<spoiler summary="Hint">
In one move, Milica can replace the whole string with $\texttt{AA} \ldots \texttt{A}$. In her second move, she can replace a prefix of length $k$ with $\texttt{BB} \ldots \texttt{B}$. The process takes no more than $2$ operations. The question remains — when can we do better?
</spoiler>
<spoiler summary="Solution">
In the *hint* section, we showed that the minimum number of operations is $0$, $1$, or $2$. We have $3$ cases:
0. No operations are needed if $s$ already contains $k$ characters $\texttt{B}$.
1. Else, we can use brute force to check if changing some prefix leads to $s$ having $k$ $\texttt{B}$s. If we find such a prefix, we print it as the answer, and use only one operation. There are $O(n)$ possibilities. Implementing them takes $O(n)$ or $O(n^2)$ time.
2. Else, we use the two operations described in the hint se...
\geq i$. To move $s_j$ to position $i$, we need to delete all characters
between $s_i$ and $s_j$ that
Tutorial of Codeforces Round 910 (Div. 2)
224.
Codeforces Round #187 tutorial [problem:315A]
Just check for each bottle, can I open it with another. In this task can pass absolutely any solutions.
[problem:315B]
We will support all of the elements in the array, but also we will supprt additionally variable add: how much to add to all the elements. Then to add some value to every element we simply increase the add. In the derivation we deduce the value of the array element + add. When you update the item we put to a value, value that you need to put minus the current value of add.
[problem:314A]
Note that if we remove some of the participants, we never remove the participants with lower numbers as theirs amount will only increase. So just consider the sequence of all the participants, and if the participant does not fit we delete him.
[problem:314B]
It is clear that we can use greedy algorithm to look for the number of occurrences of the 2nd string in the first string, but it works too slow. To speed up the process, you can look at the ...
participants, and if the participant does not fit we delete him.
Tutorial of Codeforces Round 187 (Div. 1)
Tutorial of Codeforces Round 187 (Div. 2)
225.
Bahnasy Tree [cut]
** بسم الله والحمدلله والصلاة والسلام على رسول الله **
Bahnasy Tree
==================
**GitHub Repository:** [Bahnasy-Tree](https://github.com/Mostafa-Bahnasy/Bahnasy-Tree)
Bahnasy Tree is a dynamic tree that represents a **sequence of length $N$** (positions $1..N$). It is controlled by two parameters:
- $T$ ( **threshold** ): the maximum fanout a node is allowed to have before we consider it "too wide".
- $S$ ( **split factor** ): used when splitting; computed from the node size using the smallest prime factor (SPF). If $S > T$, we fallback to $S = 2$.
The tree supports the usual sequence operations (find by index, insert, delete) and can be extended to support range query / range update by storing aggregates (sum, min, etc.) and optionally using lazy propagation.
---
## 1) Node meaning and the main invariant
Each node represents a contiguous block of the sequence. If a node represents a block of length `sz`, then its children partition this block into...
## 6) Delete complexity, So the worst-case delete is:
226.
Codeforces Round 970 Video Editorial (with Hints) [I'm currently live discussing the problems.](https://youtu.be/pZlCq4e21Cs)
I will add problemwise timestamp after the discussion stream.
You can join in if something in this blog is unclear or there are more questions.
[problem:2008A]
<spoiler summary="Idea">
- No of ones must be even.
- If no of ones is zero, then no of twos must be even.
These are necessary and sufficient conditions.
</spoiler>
My submission — [submission:279068120]
<spoiler summary="Video Editorial">
<iframe width="853" height="480" src="https://www.youtube.com/embed/pZlCq4e21Cs?start=130" title="Codeforces Round 970 Solution Discussion | ABCDEFGH" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
</spoiler>
[problem:2008B]
<spoiler summary="Hint 1">
If it is a square matrix, then N must be a perfect square.
</spoiler>
<spoiler su...
Tutorial of Codeforces Round 970 (Div. 3)
227.
Improvement of the functionality of test scripts in Polygon Good night/dawn/morning/day/dusk/evening/night, Codeforces!
Today I am glad to present you the latest features of the [Polygon](https://polygon.codeforces.com/) — the system for creation and preparation of programming problems and contests. All Codeforces Rounds are made using Polygon.
New features are concentrated around test script.
#### Part one. Test autonumeration
The first new feature allows you to automatically numerate tests.
Instead of this
~~~~~
gen_n 5 10 1 > 57
gen_n 5 10 2 > 58
gen_n 5 10 3 > 59
gen_n 5 10 4 > 60
gen_n 5 10 5 > 61
~~~~~
you can now write this
~~~~~
gen_n 5 10 1 > $
gen_n 5 10 2 > $
gen_n 5 10 3 > $
gen_n 5 10 4 > $
gen_n 5 10 5 > $
~~~~~
Dollar sign, used to mark autonumeration, stands for the first unused test index. So, for example:
~~~~~
gen 1 > $
gen 2 > $
gen 4 > $
gen 5 > $
gen 3 > 3
~~~~~
will be translated to...
- It is impossible to delete, edit or move script test using web-interface. To
do it, you must edit, If you delete any test, all dollar tests will be renumerated instantly and they
will still be
228.
Codeforces Round 1083 (Div. 2) Editorial Thank you for participating and accompanying Simons! We hope you enjoyed the problems.
<spoiler summary="Rate the contest!">
-
Horrible contest
-
Bad contest
-
Average contest
-
Good contest
-
Epic contest
</spoiler>
<spoiler summary="Rate the difficulty!">
-
Impossible contest
-
Hard contest
-
Average contest
-
Simple contest
-
Trivial contest
</spoiler>
<spoiler summary="Rating Predictions">
| | A | B | C | D | E | F | G |
|-----| ----- | -----| -----| -----| -----| -----| -----|
| [user:Leftist_G,2026-02-25] | 800 | 800 | 1400 | 2000 | 2400 | 2600 | 2900 |
| [user:cool_milo,2026-02-25] | 800 | 800 | 1400 | 1800 | 2400 | 2700 | 3300 |
| [user:StayAlone,2026-02-25] | 800 | 900 | 1500 | 1900 | 2300 | 2200 | 2800 |
| [user:liuhangxin,2026-02-25] | 800 | 900 | 1000 | 1300 | | 2500 |...
to a way to keep the maximum number on one side and delete the others.
Tutorial of Codeforces Round 1083 (Div. 2)
229.
Invitation to TOKI Regular Open Contest #24 Hello again Codeforces 👋,
We are excited to invite you to **TOKI Regular Open Contest #24**!
Key details:
- Contest link: [TLX](https://tlx.toki.id/contests/troc-24)
- Time: [18th December 2021, 13:05 UTC](https://www.timeanddate.com/worldclock/fixedtime.html?msg=TOKI+Regular+Open+Contest+%2324&iso=20211218T1305&p1=1440&ah=2&am=30)
- Writers: [user:errorgorn,2021-12-13], [user:maomao90,2021-12-13], [user:oolimry,2021-12-13]
- Duration: 150 minutes
- Problems: 7, but one of the problems will have a subtask
- Scoring distribution: **100 — 200 — 400 — 600 — (600 + 200) — 900 — 1000**
Many thanks to:
- [user:prabowo,2021-12-13] 👨‍❤️‍💋‍👨 for 🕒 coordinating the 👦🌷 contest and translating our 💰🅱 stupid 😕💩 jokes into ➡ Indonesian 🇮🇩.
- [user:icypiggy,2021-12-13] for helping 💻 us DZ...
problems and making us delete a problem 😡🤬 giving useful feedback 🥰
230.
Performance tip : using std::deque as a memory cache If you've been doing competitive programming for a while, you're probably aware by now that dynamically allocating memory (i.e. using `new` or `malloc`) is pretty expensive in terms of computation time (both because of slow allocation and potential cache misses).
What many people do to avoid dynamically allocated memory is implement a "memory cache": a pre-allocated array of elements, from which you can fetch elements at will. In code, this might look like this:
~~~~~
elem elemCache[MAX_NUMBER_OF_ELEMENTS];
int nxtElemCache = 0;
elem *fetchElement() {
return &elemCache[nxtElemCache++];
}
~~~~~
And instead of using the `new` operator, you just use the `fetchElement` function (you can also override the `new` operator itself, but it's slightly less readable for the purposes of this thread, so we'll leave it at that).
The problem arises when you do not know what `MAX_NUMBER_OF_ELEMENTS` is. For example, let's say that you are implementing a data structure (maybe a p...
231.
Aleppo-CPC 2025 Tutorial Thank you for participating in our contest, share your solutions and ideas in the comments.
Problem A: [GCD MEX](https://codeforces.me/gym/106007/problem/A)
Problem Author: [user:Go8,2025-07-18], Tutorial By: [user:Hosen_ba,2025-07-20]
<spoiler summary="Tutorial">
make the first element $a_1 = lcm(1,2,\cdots,n-1)$ and the other $n-1$ elements $(1,2,3,...,n-1)$, then you will have $gcd(a_1,1) = 1$, $gcd(a_1,2) = 2$, $\cdots$ etc.
then the $mex$ is at least $n$
</spoiler>
<spoiler summary="Code">
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
int n;
cin>>n;
if(n==1)
{
cout<<0<<endl;
return;
}
ll x=1;
cout<<n<<endl;
for(ll i=1; i<n; i++)
{
cout<<i<<" ";
x=(x*i)/__gcd(x,i);
}
cout<<x<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--)
{
solve();...
bits of type2 are totally unnecessary you can just ignore them and delete them
from $x$ and from
Tutorial of The 2025 Aleppo Collegiate programming contest
232.
Codeforces Round #804 (Div. 2) Editorial Reupload The [original blog](https://web.archive.org/web/20220705073720/https://codeforces.me/blog/entry/104088) was deleted yesterday by one of the other authors. We are very sorry about this.
[A — The Third Three Number Problem](https://codeforces.me/contest/1699/problem/A)
=====
Authors:
[user:antontrygubO_o,2022-10-31], [user:Gheal,2022-10-31]
<spoiler summary="Hints">
<spoiler summary="Hint 1">
An answer exists only when $n$ is even.
</spoiler>
<spoiler summary="Hint 2">
$a \oplus a = 0$
$a \oplus 0 = a$
</spoiler>
</spoiler>
<spoiler summary="Solution">
First and foremost, it can be proven that $(a \oplus b) + (b \oplus c) + (a \oplus c)$ is always even, for all possible non-negative values of $a$, $b$ and $c$.
<spoiler summary="Proof">
Firstly, $a \oplus b$ and $a+b$ have the same parity, since $a + b = a \oplus b + 2 \cdot (a \text{&} b) $. Therefore, $(a \oplus b) + (b \oplus c) + (a \oplus c)$ has the same parity as $(a+b)+(b+c)+(a+c...
Tutorial of Codeforces Round 804 (Div. 2)
233.
Codeforces Round 1070 (Div.2) Editorial Thank you all for participation! We hope, you enjoyed the problems.
###[problem:2176A]
<spoiler summary="Hints">
<spoiler summary="Hint 1">
Which element of the array cannot be removed using the described operations?
</spoiler>
<spoiler summary="Hint 2">
Under what condition the element $a_j$ **cannot** be removed?
</spoiler>
</spoiler>
<spoiler summary="Solution">
Note that the element $a_1$ cannot be removed using the described operations.
In general, the $j$-th element **cannot** be removed if $a_j$ is not less than all elements $a_1 \ldots a_{j - 1}$.
Otherwise, among the elements $a_1 \ldots a_{j - 1}$, there will always be an element $a_i > a_j$, which means that $a_j$ can be removed.
The constraints are small enough, so for each element, this statement can be checked in $O(n)$ for one check — resulting in a total of $O(n^2)$ for the test.
The idea for solving it in $O(n)$ is as follows:
- We will process the elements starting from $a...
Tutorial of Codeforces Round 1070 (Div. 2)
234.
Keep Problems — Browser Extension | Keep track of coding problems Hello everyone!
I would like to share my new extension [Keep Problems](https://chromewebstore.google.com/detail/keep-problems/bpcgbgiipbblkoajepkmlcdgafnhiamp), which I think can be very useful.
##Description
------------------
Keep Problems is a browser extension that helps to save and keep track of problems from different platforms (Codeforces, CodeChef, AtCoder etc.)
### Features
#### Add Problem
- Save problem with link, name, difficulty, tags, code and notes
- If codeforces problem, then it will fetch name, difficulty and tags
- For other platforms, it will fetch possible information
- Add code and notes in the code and notes section
- Manage problems in different folders by giving appropriate folder name
#### Import/ Export
- Do you share problems with others? If yes, then this feature can be very useful for you
- Add and filter problems you wa...
#### Sort, Search, Filter, Edit, Delete
235.
Problems of CSP(China) Sharing & Discussion Hello codeforces!
CSP-J/S(Certified Software Professional-Junior/Senior) of China ended. CSP-J/S (or you can say NOIp ,but it has been dead) was held by OI rules. In OI rules, every problem has the same score distribution $100$ points. In one problem, there is several testdatas (like $10$ ,$20$ or $25$). Every testdata has the same score distributions. Once you pass a testdata, you can get the score. You can submit your code during the contest, but can't see the result. The organizer will judge all the programs together after contest.
I'd like to share the problems of CSP-S here! Hope you guys enjoy. Don't mind my poor English, I spent a whole afternoon translating.
<spoiler summary="D1T1 code">
$\bf{D1T1\ Gray\ Code\ 1s\ 256MB}$
$\bf{Statement}$
_Gray Code_ is a special permutation of $n$-bit binary strings ,which requires adjacent strings have **exactly one different** bit. Specially, the first string is adjacent to the last string.
One example of $2$-bit _Gray Cod...
** simple path between two vertices. Delete a vertex and all edges that connect
it, and the tree splits
236.
Fast searching silly mistakes in C++: shortly and with examples **To find an error in the code you just need...**
[cut]
$$\text{ }$$
Firsly, you can check overflow of integer types, mistakes like `=` instead `==`, writing a `long long` value in `int` and something else. It can be done in compile time with enabling of all available warnings. You can check your code fast [there](https://godbolt.org/z/SCiLFB). Link have examples and you can read them. Warnings is not an errors, but sometimes can be.
[Description of warnings can be found there](https://codeforces.me/blog/entry/15547).
<spoiler summary="List of used warnings">
```
-Wall -Wextra -pedantic -std=c++17 -O3 -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op -Wshift-overflow=2 -Wduplicated-cond -Wcast-qual -Wcast-align -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC
```
</spoiler>
Secondly, you can test your solution in **custom invocation**. You should go to [Custom invocation](https://codeforces.me/contest/1307/customtest), place your code and test on samples and...
237.
Codeforces Round #366 (Editorial) [Here](https://gitlab.com/amirmd76/cf-round-366) are the solutions to all problems.
### Div.2 A
Just alternatively print "I hate that" and "I love that", and in the last level change "that" to "it".
Time Complexity: $\mathcal O(n)$
### Div.2 B
First of all, instead of cycles, imagine we have bamboos (paths). A valid move in the game is now taking a path and deleting an edge from it (to form two new paths). So, every player in his move can delete an edge in the graph (with components equal to paths). So, no matter how they play, winner is always determined by the parity of number of edges (because it decreases by 1 each time). Second player wins if and only if the number of edges is even. At first it's even (0). In a query that adds a cycle (bamboo) with an odd number of vertices, parity and so winner won't change. When a bamboo with even number of vertices (and so odd number of edges) is added, parity and so the winner will cha...
delete an edge in the graph (with components equal to paths). So, no matter how
they play, winner is
Tutorial of Codeforces Round 366 (Div. 1)
Tutorial of Codeforces Round 366 (Div. 2)
238.
Checklist for OI Problems (WebApp) Hello Everyone,
I guess everyone who is preparing for OI already know about this [Checklist for OI Problems](https://codeforces.me/blog/entry/59422) prepared by [user:ko_osaga,2018-11-01]. I've been using this for quite a long time, and it is really helpful!
But since the checklist gets updated from time to time, I found it hard to migrate from the previous checklist to new checklist. So, I made the following web app for the same purpose! Now you don't need to worry about migrating, I can just add the problems to database and it'll update automatically!
Link: [OI Checklist](https://oichecklist.pythonanywhere.com)
Please find the features and changes to the main checklist bellow:
Features and Changes
------------------
1. First of all, now the checklist contains direct link to each problem, while the main checklist had link to some parent of the link. And clicking on a contest name will lead to the official "Task" page of that contest, which generally contains jud...
want to search your browser history and delete all entries of
oichecklist.herokuapp.com. Happy
239.
Codeforces Round #245 — Editorial [problem:430A]
------------------
The problem asks you to output “-1” if there is no solution. A natural question is now: “when there is no solution”? Try to come up with a test like this!
After some analysis, you’ll see anyhow we draw the points and the lines, there will always be a solution. By manually solving small cases, you might already have found the pattern. But for now, let’s assume anyhow we draw points and lines, there will always be a solution. Let’s have a fixed set of points. Then, anyhow we draw a line, there should still be a solution. So, we need to find a coloring of points, such as for every line, |number of red points which belong to it – number of blue points which belong to it| <= 1.
Suppose anytime you color a point with red you assign it +1 value. Also, anytime you color it with blue you assign it -1 value. Then, for a segment, the drawing is good if S = sum of values assigned to points that belong to segment is between -1 and 1 (in other words |S| ...
Note: in my solution, I don’t actually do deletion. If I have to delete a range
[i, j] I create a
Tutorial of Codeforces Round 245 (Div. 1)
Tutorial of Codeforces Round 245 (Div. 2)
240.
Codeforces Round #259 Editorial Overview
========
There are 3 normal tasks accompanied with 2 challenge tasks in div 1 as we usually do. You can check the [Statistics](http://codeforces.me/blog/entry/13271) by By [user:DmitriyH,2014-08-06] for detail.
Problem B, C is by [user:sevenkplus,2014-08-06], problem D is by [user:xlk,2014-08-06] and problem A, E is by me.
Problem E is rather complicated then hard, it means if you carefully broke down the problem into smaller ones, it became quite straightforward. During the contest, only [user:kcm1700,2014-08-06] managed to solve it successfully.
Problem D, which decided the round boiled down to the following nice Dynamic Programming subproblem: you are given $2^20$ numbers. For each position i between 0 and $2^{20}-1$, and for each distance $j$ between 0 and 20, what is the sum of the numbers with such indexes $k$ that $k$ and $i$ differ in exactly $j$ bits? The fun part is not how to do it $T$ times, it is how to do it even once on $10^6$ numbers.
[user:...
constant insert and delete operations on those balanced tree, thus the overall
complexity is $O(nlogn)$.
Tutorial of Codeforces Round 259 (Div. 1)
Tutorial of Codeforces Round 259 (Div. 2)
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/11/2026 05:51:36 (k3).
Desktop version, switch to mobile version.
Supported by
