in order. Adding them up, you get an “infinite polynomial” which somewhat
encodes the sequence. The, A partition of $n$ into $k$ parts is a multiset of positive integers of size
$k$ which sum up to $n
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 144 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 136 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
→ Find user
→ Recent actions
You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:
305— search for 305, most probably it will find blogs about the Round 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
[Tutorial] Generating Functions in Competitive Programming (Part 1) Hi everyone! Inspired by the recent [Codeforces Round 641](https://codeforces.me/contest/1349), I decided to write an introductory tutorial on generating functions here. I am by no means an expert in generating functions so I will write about what I currently know about them. [user:MiFaFaOvO,2020-05-15] has written a really interesting [blog](https://codeforces.me/blog/entry/76447) here on Codeforces about more advanced applications of generating functions, but I think there is no English tutorial on the basics of this topic yet (or at least on CP sites). Thus, I would like to share about this topic here.
I plan to split this tutorial into two parts. The first part (this post) will be an introduction to generating functions for those who have never learned about them at all, and some standard examples and showcases of generating functions. The second part will be a collection of several applications of generating functions in CP-style problems. If you are already familiar with ge...
2.
I compiled a list of almost all useful blogs ever published on Codeforces [update: till 09.06.2021] <h3 style="color:red">If there are any blogs that I have missed, please tell in the comment section. Thank you.</h3>
# Mathematics Stuff
- [Number Theory in Competitive Programming [Tutorial]](https://codeforces.me/blog/entry/46620)
- [Number of points on Convex hull with lattice points](https://codeforces.me/blog/entry/62183)
- [FFT, big modulos, precision errors.](https://codeforces.me/blog/entry/48465)
- [Number of ways between two vertices](https://codeforces.me/blog/entry/19078)
- [Mathematics For Competitive Programming](https://codeforces.me/blog/entry/76938)
- [FFT and NTT](https://codeforces.me/blog/entry/19862)
- [Burnside Lemma](https://codeforces.me/blog/entry/51272)
- [Number of positive integral solutions of equation 1/x+1/y=1/n!](https://codeforces.me/blog/entry/76836)
- [On burnside (again)](https://codeforces.me/blog/entry/64860)
- [Simple but often unknown theorems/lemmas/formula? Do you know?](https://codeforces.me/blog/entry/55912)
- [Probabili...
](https://codeforces.me/blog/entry/88494) - [An alternative sorting order for
Mo's algorithm](https
3.
Unofficial Editorial for Educational Round 95 (Div. 2) Here are my approaches to the problems today:
#### [problem:1418A]
Since the second trade is the only way to get coal, we clearly need to perform the second trade $k$ times. So how many times do we need to do the first trade? We can see that in order to end up with enough sticks and coal by the end, we need to obtain $ky + k$ sticks ($ky$ to convert to coal and $k$ to save as sticks). Since the first trade really just gives us $x - 1$ new sticks each time, we'll need to make $\displaystyle \left \lceil \frac{ky + k - 1}{x - 1} \right \rceil$ first trades ([reference to floor and ceiling functions](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) for anyone unfamiliar).
For implementation details, note that for positive integers $a$ and $b$, $\displaystyle \left \lceil \frac{a}{b} \right \rceil = \left \lfloor \frac{a + b - 1}{b} \right \rfloor$. Code: [submission:92851684]
#### [problem:1418B]
We can think about the problem as follows: we want to order the $a_i$ to...
we need to do the first trade? We can see that in order to end up with enough
sticks and coal by the, In order to do this and handle queries, we can store all of the positions in a
set and all of the
4.
[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...
int n,k; multiset > s; //non-decreasing order
5.
[Tutorial] "1354D — Multiset" + A Gentle Introduction to Fenwick Trees (For the tutorial, skip to the second paragraph)
The recently held [Educational Codeforces Round 87](https://codeforces.me/contest/1354) was full of controversies. The delay in its start, the overlap with Google Code Jam and then the many complaints that problems B, C1, C2 and D were all google-able! In particular, problem D was heavily criticised due to its strict memory limit which didn't help non-C++ users. The authors have given their reasons for this — to discourage the use of memory heavy data structures such as policy-based data structures (gnu pbds) and treaps. I personally found the contest to be "educational" indeed and I'm sure the same authors will now deliver even better contests in the future.
Here I discuss the problem [D — Multiset](https://codeforces.me/contest/1354/problem/D) and some of the ways in which it could be solved. This blog is aimed at beginners. I hope to provide you with a gentle introduction to this fast and easy-to-implement data st...
[Tutorial] "1354D — Multiset" + A Gentle Introduction to Fenwick Trees, binary search that doesn't calculate the $k^{th}$ order statistic. It takes
advantage of the fact that, frequency of the element $i$ in our multiset. Adding an integer $k$ to the
multiset is now equivalent, , n]$) into the multiset 2. Find the $k^{th}$ order statistic in the multiset
and remove exactly, 2. Find the $k^{th}$ order statistic in the multiset and remove exactly one
copy of it from the, Now back to the problem we were solving. As we had concluded earlier, the order
statistics can be, multiset) which comes at the $k^{th}$ place in sorted order. As stated earlier,
this is the smallest, ~~~~~ int findByOrder(int k) { // kth order statistic int left = 1, right =
MAX_N
6.
On "PermutationForces" Disclaimer: This blog is entirely my own opinion, please do not get mad at the authors from round 779. If you did not enjoy that round, please do not blame the authors. Personally, I felt that the authors overall did a wonderful job ([user:SPyofgame,2022-04-02]'s div 2F was honestly one of my favourite problems in 2022 so far).
Last week round 779 was held, a common feedback that people seemed to be quite vocal about was that the round was "PermutationForces".
If we look at the actual contest, we do see that problems B, C, D, E all contain the word permutation inside, so it is natural to think that pr...
consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For
example, $[2,3,1,5,4]$ is a, $ in arbitrary order, so there are at most $\frac{n}{k}$ elements which are a
multiple of $k
7.
Editorial of CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!) [A. Beautiful Sequence](https://codeforces.me/contest/1810/problem/A)
<spoiler summary="Hint">
What is the necessary and sufficient condition?
</spoiler>
<spoiler summary="Tutorial">
The necessary and sufficient condition for a beautiful sequence is that there exist one $i$, such that $a_{i} \le i$. Just check the sequence for the condition.
</spoiler>
<spoiler summary="Solution">
~~~~~
#include<bits/stdc++.h>
using namespace std;
int a[100005];
void solve()
{
int n;
scanf("%d",&n);
for(int i =1;i <= n;i++) scanf("%d",&a[i]);
for(int i = 1;i <= n;i++) {
if(a[i] <= i) {
puts("YES");
return;
}
}
puts("NO");
}
int main()
{
int t;scanf("%d",&t);
while(t--) solve();
}
~~~~~
</spoiler>
[B. Candies](https://codeforces.me/contest/1810/problem/B)
<spoiler summary="Hint">
How the binary representation changes after an operation?
</spoiler>
<spoiler summary="Tutorial"...
Still, at the moment just before the $x$-th operation, let us sort the elements
in themultiset in, multiset in non-decreasing order, $S_{0},S_{1} \dots S_{k}$. We will show that
the answer is $S_{0
8.
Editorial of Codeforces Round #572 Codes have been added!
We've added challenges(mostly not hard) to some tasks. Feel free to share solutions and ask any questions in comments!
Keanu Reeves
----------
If the string is good, then answer it's itself. Otherwise, there are at least two strings in answer, and we can print substring without its last symbol and its last symbol separately. Complexity $O(n)$.
[code](https://pastebin.com/Dc0gtG9n)
Number circle
----------
Let's suppose that array is sorted. First of all, if $a_n \ge a_{n - 1} + a_{n - 2}$, than the answer is — NO (because otherwise $a_{n}$ is not smaller than sum of the neighbors). We claim, that in all other cases answer is — YES. One of the possible constructions (if the array is already sorted) is:
$a_{n - 2}, a_{n}, a_{n - 1}, a_{n - 4}, a_{n - 5}, \ldots ,a_1$
It's easy to see, that all numbers except $a_n$ will have at least one neighbor which is not smaller than itself. Complexity $O(nlog(n))$.
[code](https://past...
calculate needed pairs for segments in the order of increasing of their
length: firstly for segments of
Tutorial of Codeforces Round 572 (Div. 1)
Tutorial of Codeforces Round 572 (Div. 2)
9.
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...
refer to the last elements of $a$ and $b$ respectively). We also have an
initially emptymultiset $S, multiset $S$, which represents the reserve. We will perform the following
operations in thisorder
Tutorial of Codeforces Global Round 20
10.
Some short snippets that will shorten your time. Hi there!
==================
In this blog I would like to share some of the code snippets that can shorten your time in future contests. Of course, I'll ignore the "international snippets"
<spoiler summary="like:">
~~~~~
#define SZ(a) (ll)a.size()
#define FOR(i,a,b) for (ll i=(ll)a; i<=(ll)b; i++)
#define f first
#define mp make_pair
#define s second
#define p pair
#define all(C) C.begin(), C.end()
~~~~~
</spoiler>
Sometimes you may find typing the identical thing again and again is boring, this blog is about some method that a few people use to get rid of them (or just only me).
So, let's get started.
#### Scanning/printing the whole vector in a single `std::cin/std::cout`
<spoiler summary="Snippet">
~~~~~
template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};
~~~~~
</spoiler>
...
#### Ordered set and ordered multiset
11.
Ordered Set and Multiset Alternatives for Languages Without Built-In Libraries I have been doing competitive programming for some months now. While attempting problems above 1800 in difficulty, I noticed that some of them required the use of ordered sets/multisets that support lookup, addition and deletion of elements in O(log(n)) time. Their solutions usually involve the use of std::set or std::multiset in C++. However, I code primarily in Python and there are no built-in packages available on Codeforces. Normally outside of Codeforces I just import sortedcontainers.sortedlist which I use like an Order Statistic tree. Here I discuss some strategies which I have used to overcome these issues. I hope that it helps others who are stuck so that they do not give up on their favourite languages. For C++ users, this may not be as useful, but you can still see how alternative data structures may be used to solve problems.
The example I use here is CSES — Concert Tickets (for those with no CSES account, see [here](https://www.technicalkeeda.in/2020/10/concert-ti...
Ordered Set and Multiset Alternatives for Languages Without Built-In Libraries, OrderedList data structure. By the way, the **OrderedList** is my
implementation of theOrder Statistic, in difficulty, I noticed that some of them required the use of ordered
sets/multisets that support, **Method 3: Actually using a self-implemented B-tree or Order Statistic Tree**
------------------------------------------------------------------------------, **Method 3: Using some sort of Order Statistic Tree (PyRival's SortedList)** :
[submission, EDIT: [user:rishabnahar2025,2021-03-31] has a good suggestion for an Order
Statistic Tree template
12.
AtCoder Beginner Contest 136 English Solutions #A — Transfer
First, we compute the resulting amount of water in Cup 1. Observe that this is equal to $min(A, B+C)$. Let this value be $D$. Then, the amount transferred from Cup 2 to Cup 1 is simply $D - A$, so the amount remaining in Cup 2 is $C - D + A$.
Time complexity: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc136/submissions/6682058)
---
#B — Uneven Numbers
There are several efficient ways to approach this problem. One is to simply to count the one-, three-, and five-digit numbers less than or equal to $N$. However, because of the small maximum on $N$, a more naive approach works. Simply iterate over every value from $1$ to $N$, count its digits, and add one to the answer if the count is odd. (We can count a number's digits by repeatedly adding one to the count and dividing the number by ten until it reaches zero.)
Time complexity: $O(N \log N)$. Note that $O(\log N)$ is possible with the more efficient approach. ...
) --- #C — Build Stairs We employ a greedy strategy. Process the elements in
increasingorder, Iterate over the multiset in increasing order. Maintain the number of
subtractions required to
13.
Codeforces Round 1050 (Div. 4) Editorial #### [problem:2148A]
<spoiler summary="Solution (written by cry)">
Notice that if we pair each odd-indexed element with an even-indexed element, it sums to $0$.
Therefore, our strategy is to pair the $2i$'th element with the $(2i+1)$th element until there are no more elements to pair. Note that if $n$ is odd, then there exists an unpaired odd element at the end. In this case, the answer will just be that ending element, which will be $x$. Otherwise, when $n$ is even, we paired every element perfectly and the sum will be $0$.
Time complexity: $\mathcal{O}(1)$ per test case.
</spoiler>
<spoiler summary="Code (C++) (MikeMirzayanov)">
```cpp
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int x, n;
cin >> x >> n;
if (n % 2 == 0)
cout << 0;
else
cout << x;
cout << endl;
}
}
```
</...
$\frac{\texttt{cnt}_i}{k} - c_i$ occurrences inside multiset $1$. We can place
the other elements
Tutorial of Codeforces Round 1050 (Div. 4)
14.
Codeforces Round 1061 (Div. 2) Editorial ### Thank you for participating !
Special Thanks to [user:hxu10,2025-10-24] for giving me the chance to write the editorial and for [user:maomao90,2025-10-24] for enhancing the editorial !.
Editorial of Problems E and F are written by hxu10, and the rest are written by me. I hope they're insightful and concise, please let me hear your opinion about it or any feedback in general 💙.
#### [problem:2156A]
<spoiler summary="Hints">
<spoiler summary="Hint 1">
Since $m_1 \le m_2$, the total number of slices Alice ate is always at least as much as the total number of slices Bob ate.
What's optimal construction ?
</spoiler>
<spoiler summary="Hint 2">
We want to try to minimize the difference between the total number of slices Alice ate and the total number of slices Bob ate.
</spoiler>
<spoiler summary="Hint 3">
The optimal construction is to let both $m_1$ and $m_2$ to be equals to one. The sequence of operations, denoted by $(m_1, m...
the relative order or values of $p_y$ and $p_z$, and the multiset $[p_i,
\ldots, p_n]$ is preserved, - Since the operation does not depend on the relative order or values of $p_y$
and $p_z$, and the
Tutorial of Codeforces Round 1061 (Div. 2)
15.
Как тренироваться: почему для школьных олимпиад не надо учить сложные темы и решать гробы Всем доброго времени суток! На этот пост меня вдохновил [user:Wind_Eagle,2022-04-05] своим [постом](https://codeforces.me/blog/entry/101549).
Этот блог является заключительным в цикле [челлендж::поготовься к респе](https://codeforces.me/blog/entry/99856). Советую перед прочтением сначала прочитать его, а также вышеописанный блог, так как данный наследуется от них.
Для начала подведу итоги челленджа. Он оказался скорее неуспешным, чем успешным. Единственное, что я получил от него — опыт, который будет полезен в будущем. Итак, итоги:
- Взять диплом на республике. Не выполнил, остался без диплома. Нарешал очень плохо, наконец понял, что главная проблема не столько даже лежит в программировании, сколько в психологии. Заметил очень нехорошую особенность: пришёл как на первый, так и на второй тур, все 5 часов не мог сосредоточиться, чего-то боялся (сам не знаю, чего). Из-за этого я фактически не думал, а скорее просто выписывал на листочке что-то и пытался просто реализовать...
в stl структуры данных: map / set / multiset - встроенные в g++ структуры
данных:ordered set, - встроенные в g++ структуры данных: ordered set / ordered multiset, их
особенности и баги
16.
Codeforces Round 1095 (Div. 2) Editorial Thanks for participating. We hope you liked the problems and enjoyed the round.
#### [problem:2226A]
Idea: [user:wakanda-forever,2026-04-21] <br>
Preparation: [user:wakanda-forever,2026-04-21] <br>
Solution: [user:wakanda-forever,2026-04-21] <br>
<spoiler summary = "Solution">
For any two positive integers $x$ and $y$, observe that $x \times y \ge x + y$ when $x > 1$ and $y > 1$. Thus, it is never optimal to choose two elements that are more than $1$ in a single operation. Also, it is optimal to choose as many $1$'s as possible in a single operation.
Hence, we opt to choose subsequences of the form $[1, 1, \ldots, x]$ and delete them. Note that the cost for this operation is equal to $x$. Therefore, the answer is just the sum of elements that are more than $1$. But if the last element is $1$, it cannot be clubbed with any "more than $1$ element", and it adds $1$ to the answer.
Time Complexity: $\mathcal{O(n)}$
</spoiler>
<spoiler summary = "Implementation">
...
handle this, let us process the required values in decreasing order, i.e.,
from $k-1$ to $0$. We maintain, To handle this, let us process the required values in decreasing order, i.e.,
from $k-1$ to $0$. We
Tutorial of Codeforces Round 1095 (Div. 2)
17.
C++ tips and tricks Hello, codeforces.
I would like to tell you about some tricks and constructions I use in C++. They are not hidden or anything, moreover, most of them are from stl or maybe well known among software engineers, but I often see codes where something is done by hand in, say, 5 lines, while in stl there is a function which does the same.
The things below are filtered by my personal sense of non-popularity (so no `__builtin` functions) and usage frequency (so there almost surely are similar things I don't know about) and are not really sorted in any reasonable order. Let's begin. [cut]
<hr>
- ### `all(x)`
This may be an exception to the rule of non-popularity -- this is quite widely used, but some next items will depend on `all(x)`, so I define it here. So, I talk about
```[c++]
#define all(x) (x).begin(), (x).end()
```
Now sorting a vector looks like `sort(all(vec))` instead of `sort(vec.begin(), vec.end())`.
However, it's not all about this define. Imagine you nee...
things I don't know about) and are not really sorted in any reasonable order.
Let's begin. [cut]
18.
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...
two comments may require an account registration with a phone number in order
to be displayed. If
19.
Introduction to New Data Structure: Wavelet Trees Hi CF Community,
http://rachitiitr.blogspot.in/2017/06/wavelet-trees-wavelet-trees-editorial.html
I think it's safe to assume that this is a new data structure for most of us.
Consider the following problems:
1. Number of elements in subarray $A[L...R]$ that are less than or equal to $y$.
(Persistence Segment Tree? Ordered multiset + BIT ?)
2. Number of occurrences of element $x$ in subarray $A[L...R]$.
(Subpart of 1st problem)
3. The $k^{th}$ smallest element in subarray $A[L...R]$.
(Ordered multiset + BIT would work for subarrays beginning from index 1)
I know you might have many other solutions, and you might think what I am trying to prove.
What if I told you, all of the above can be easily done in O(logn) using Wavelet Trees :o. Plus, its very easy to code :D Awesome, isn't it?
Check the implementation [here](http://ideone.com/Tkters).
The post just introduces the basic usage of wavelet trees. There is still more that you can ...
$y$. (Persistence Segment Tree? Ordered multiset + BIT ?) 2. Number of
occurrences of, $. (Persistence Segment Tree? Ordered multiset + BIT ?) 2. Number of
occurrences of element $x
20.
Ordered Set with Custom Sorting Operator in C++ ## Ordered Sets in C++
In C++, ordered sets can be created using special code templates.
~~~~~
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
~~~~~
Two primary structures are introduced:
- `ordered_set` maintains sorted unique elements in ascending order using `less` comparison.
- `ordered_multiset` allows duplicates using a `less_equal` comparison, preserving the sorted order.
### Fucntions
In addition to normal set operations, the ordered set supports:
- `order_of_key(k)`: Gives the count of elements smaller than `k`. — O(log n)
- `find_by_order(k)`: Returns the iterator for the `k`th element (use `k = 0` for the first element). — O(log n)...
Ordered Set with Custom Sorting Operator in C++, descending order for set or multiset., sorted order. ### Fucntions In addition to normal set operations, the ordered
set supports, ### Deletion in Multiset To remove an element in a multiset, you must delete it
using **iterators**:, ordered multiset. It ensures that duplicate elements are retained while
maintaining the desired sorting
21.
Sliding Window: Handling Non-Invertible Operators # Sliding Window
The sliding window technique is a powerful approach for solving problems involving subarrays. It works by maintaining a subarray (window) of elements and moving (sliding) this window across the data to compute results efficiently.
---
## Introduction
When I first learned the sliding-window trick for **sum**, it felt like magic: out went an O(n·K) double loop, in came an O(n) solution. Then I tried to do the same for **minimum** and promptly got stuck. You can’t “subtract” a minimum!
In this tutorial you’ll learn:
1. How **invertible** operators (sum, XOR) let you slide in O(n)
2. Why **non-invertible** operators (min, max, GCD…) break the simple trick
3. A general O(n) approach using **two stacks** and **aggregation**
---
## 1. Invertible Operators: Sum & XOR
If you can **undo** your operation in O(1), the sliding window is trivial.
### 1.1 Fixed-Size Window Sum
```cpp
vector<int> slideSum(const vector<int>& a, int K) {
int ...
) (also requires ordered set / two priority queues or multisets) - [Sliding
Window Cost] (https, ] (https://cses.fi/problemset/task/1076) (also requires ordered set / two
priority queues or multisets
22.
2017 CMUT BeihangU Contest, Editorial This editorial corresponds to [contest:102253] (stage 1), which was held on Jun 25th, 2017.
There are 12 problems in total. You can solve them as a team member or an individual in a 5-hour contest. By the time you join as virtual participants, 770 teams, or even more, will compete with you virtually.
---
Editorial in the English version has been completed, which is a bit different from its Chinese version (mostly because I don't want bad editorials to ruin the contest, lol). However, **for the sake of hiding spoilers**, editorials are locked and will be shown as the following conditions are met:
- Editorials for the easiest 4 problems will be revealed after the replay **(all unlocked)**;
- Each for the hardest 5 will be released if the corresponding problem has been solved by at least 5 users or teams on Codeforces::Gym **(all unlocked)**;
- Each for the others will be published when the relevant problem has been solved by at least 10 users or teams in virtual participati...
**unordered multiset** formed by the corresponding exponents in its prime
factorization. Our next, Finally, we have to replace $n$ by the corresponding multiset $E$, where we had
better choose the
23.
std::multiset vs std::priority_queue vs __gnu_pbds::priority_queue Quite often in programming you need to use a data structure that supports operations like adding an element, accessing a minimum and removing a minimum. There are several solutions for this in C++. The most popular solutions are `std::multiset` and `std::priority_queue`, and less known one is `__gnu_pbds::priority_queue` (Like everything from `__gnu_pbds` it is supported only in GNU C++. To use this structure, you must add `#include <ext/pb_ds/priority_queue.hpp>` to the program).
Let's take a brief look at what these structures are.
`std::multiset` is a data structure that stores elements in sorted order. It is different from `std::set` in its ability to store several occurrences of equal elements. In addition to the capabilities of inserting an element and also accessing and removing a minimum, the structure supports removing any element by value and iterator, searching for the next and previous element, as well as binary search. The time complexity of all the described operati...
std::multiset vs std::priority_queue vs __gnu_pbds::priority_queue, ++. The most popular solutions are `std::multiset` and `std::priority_queue`,
and less known one is, `std::multiset` is a data structure that stores elements in sorted order. It is
different from `std
24.
Invitation to CodeRed- 2018 
Hello Codeforces!
[Aparoksha](https://aparoksha.org/) presents to you an all-new flagship event **CodeRed** in association with ACM.
If you have the appetite for algorithmic problem solving, then don't miss it out!
It will be a 5-hour long **team event** with a maximum size of the team being **3 members**.
The preliminary round will be held on Codechef, and the onsite round will be held during Aparoksha.
The total prize money is worth **INR 50,000**. The **best 40 teams** will make it to the onsite round.
Also, top **2** teams in the **online round** will get **INR 3000 and 2000** respectively, along with Codechef Laddus.
All teams making it to the onsite round will get CodeRed T-shirts.
Contest link is here — [CodeRed 2018](https://www.codechef.com/CODR2018)
The problem set comprises **6 problems** of varying difficulty level.
So be ready to have a nail-biting exper...
Was based on **Mo's on Tree**. In order to get the minimum absolute, will be the answer. Was based on **Mo's on Tree**. In order
25.
Combinatorial species: An intuition behind generating functions Hi everyone!
The usage of generating functions is quite common in competitive programming these days. But it seems to happen so, that they're mostly presented as a way to simplify formal manipulation with polynomial coefficients, rather than something meaningful. But there actually is a meaning to all of this, and today I'm going to shed a light on it.
Alongside the blog post we'll uncover the combinatorial meaning of
- The addition $F(x)+G(x)$,
- The multiplication $F(x)G(x)$,
- The exponent $\exp F(x)$,
- The logarithm $\log F(x)$,
- The sum of the infinite geometric progression $\frac{1}{1-F(x)}=1+F(x)+F^2(x)+\dots$,
- The general composition $F(G(x))$
for the generating functions $F(x)$ and $G(x)$ and the underlying structures they represent.
### Prerequisites
- Basic notion of set theory (cardinality of sets, mappings, bijections, cartesian product, disjoint union, etc);
- Polynomials and formal power series (representation, convolution formula, power seri...
](https://en.wikipedia.org/wiki/Partition_of_a_set) of $A$; - **Linear order
species** $L$ corresponds
26.
Order Capital Round 1 (Codeforces Round 1038, Div. 1 + Div. 2) Editorial #### [problem:2122A]
<spoiler summary="Solution">
[tutorial:2122A]
</spoiler>
<spoiler summary="Bonus">
Solve the problem for when the integers have to be in the range $[1, k]$ for some $k$.
</spoiler>
#### [problem:2122B]
<spoiler summary="Solution">
[tutorial:2122B]
</spoiler>
<spoiler summary="Bonus">
Solve the problem for multisets faster than $\mathcal{O}(n^3)$.
</spoiler>
#### [problem:2122C]
<spoiler summary="Solution">
[tutorial:2122C]
</spoiler>
#### [problem:2122D]
<spoiler summary="Solution">
[tutorial:2122D]
</spoiler>
<spoiler summary="Bonus">
Prove and construct exact bound for the answer.
</spoiler>
#### [problem:2122E]
<spoiler summary="Solution">
[tutorial:2122E]
</spoiler>
<spoiler summary="Bonus">
Solve the problem in $\mathcal{O}(nk)$.
</spoiler>
#### [problem:2122F]
<spoiler summary="Solution">
[tutorial:2122F]
</spoiler>
<spoiler summary="Bonus">
Write a checker for this problem.
</spo...
Order Capital Round 1 (Codeforces Round 1038, Div. 1 + Div. 2) Editorial
27.
Codeforces Round #357 (Div. 2) Editorial [problem:681A]
If for any participant $before_i \ge 2400$ and $after_i > before_i$, then the answer is "YES", otherwise "NO"
[Code](https://ideone.com/kzMYfl)
[problem:681B]
We can simply try every $a$ from $0$ to $n / 1234567$ and $b$ from $0$ до $n / 123456$, and if $n - a * 1234567 - b * 123456$ is non-negative and divided by $1234$,
then the answer is "YES".
If there is no such $a$ and $b$, then the answer is "NO".
[Code](https://ideone.com/zbPSkF)
[problem:681C]
Let's solve this problem with greedy approach.
Let's apply operations from log in given order.
If current operation is $insert$ $x$, then add element $x$ to heap.
If current operation is $removeMin$, then if heap is not empty, then simply remove minimal element, otherwise if heap is empty, add operation $insert$ $x$, where $x$ can be any number, and then apply $removeMin$
If current operation is $getMin$ $x$ then do follows:
1. While heap is not empty and its minimal element is less t...
In order to fit time limit, you need to use data structure, which allows you to
apply given, ] Let's solve this problem with greedy approach. Let's apply operations from
log in givenorder. If
Tutorial of Codeforces Round 357 (Div. 2)
28.
Codeforces Round #193 (Div. 2) — Tutorial Any suggestions, remarks and information about mistakes are welcomed. If you can improve the quality of this tutorial, please write me a private message :)
**[problem:332A]**
Since $n \ge 4$, one Vasya’s turn does not affect his other turns. Consequently, you should find just the number of positions (0-indexed) in the given string, which indexes are multiples of $n$ and before which there are at least three same symbols.
Asymptotics of the solution — $O(|s|)$
[Code](http://pastebin.com/hn4wzXj0)
**[problem:332B]**
Let’s build the array of partial sums, which will permit to find the sum in any segment of the array in $O(1)$. Let's iterate through the number $a$ (the left edge of the leftmost segment) in descending order. Now we need to find among segments of length $k$, starting from position which index is greater than or equal to $a+k$, a segment with the maximum sum. Since we search $a$ in descending order, we can maintain this segment during the transition fr...
affect parameters of an answer). Let’s iterate through $i$ — the position of
the firstorder in the, left edge of the leftmost segment) in descending order. Now we need to find
among segments of length
29.
Slope trick explained _Special thanks to [user:Ari,2020-05-13] for helping me proof-reading this blog :D_
Hi everyone! Some years ago I read [user:zscoder,2020-05-12]'s tutorial on slope trick. Initially, I found the blog a bit difficult to understand, so I came up with a different explanation and system for my personal use. Today, I finally have the courage to share it with you guys. So without further ado, let's get started!
#### Formulation and properties
Slope trick is a way to represent a function. Here, I denote that a function is **slope-trick-able** (sorry for the lack of creativity) if the function satisfies 3 conditions:
1. It is continuous.
2. It can be divided into multiple sections, where each section is a linear function with an integer slope.
3. It is a convex/concave function. In other words, the slope of each section is non-decreasing or non-increasing when scanning the function from left to right.
For example, the function $y = f(x) = |x|$ is a slope-trick-able function ...
represent this function by storing the linear function of the rightmost
section, and themultiset $\text{S
30.
Applying insert/delete/median queries using std::multiset (iterators and insert/erase) Hi Codeforcers!
Recently I was trying to solve a query-type problem and after solving the problem I learned something new about C++ that I would like to share. Here's the problem statement:
We have a set that initially contains only a single `0`. This set can contain multiple elements with the same value. We are given $Q$ queries. There are 3 types of queries:
1. **INSERT x**: Insert number x to the set,
2. **DELETE x**: Remove one occurrence of number x from the set. It is guaranteed that the number exists in the set,
3. **MEDIAN**: Print median of the numbers in the set. Median of a set of numbers is the middle element after sorting the numbers in the set in non-decreasing order. If the size of the set is a multiple of 2, among the two middle elements, print the left one.
Number of queries won't exceed $2 \cdot 10^5$.
I will assume that there is only **INSERT/MEDIAN** queries for convenience. **DELETE** operations are handled similar to **INSERT** in my solut...
Applying insert/delete/median queries using std::multiset (iterators and
insert/erase), -decreasing order. If the size of the set is a multiple of 2, among the two
middle elements, print the left
31.
CSES Sorting and Searching section editorials I just completed CSES Sorting and Searching section problems. And I didn't find any editorials for this. So I am writing my own approach for the problems.Please do correct me if I made any mistakes and do share your approach for the problems.
My solutions are [here](https://github.com/Perdente/CSES/tree/main/Sorting%20and%20Searching)
complete editorial for [CSES](https://cses.fi/problemset/) coding platform of all 27 problems in Sorting and Searching section.
--------------------------------------------------------------------------------------------------------------------------------------
**1.Distinct Numbers**
<spoiler summary="Editorial">
Just use set to store the elements and answer is the size of set.
</spoiler>
<spoiler summary="idea">
~~~~~
int n,x;cin>>n;
set<int>s;
for(int i=0;i<n;++i)
{
cin>>x;
s.insert(x);
}
cout<<s.size()<<endl;
~~~~~
</spoiler>
**2.Apartments**
<spoiler summary="Editorial">
...
constant. To search from the window we have to use ordered multiset as it's
searching is faster
32.
Editorial: SPC '22 Final Contest | Programming Club, IIT Madras If you are unable to view the problems, then [click here](https://codeforces.me/contestInvitation/f75b8b3108b87bce68dcef4fd29d16ecee886585) once to get access to the contest and then access the problems.
<p></p>
#### [A. Har Ghar Tiranga](https://codeforces.me/gym/394792/problem/A)
Problem Author: [user:AdC_AB2,2022-08-16]
<spoiler summary = "Tutorial">
In the year (say $y$) we celebrate $(y-1946)^{th}$ independence day
</spoiler>
<spoiler summary = "Solution">
~~~
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
cout << n-1946 << endl;
}
}
~~~
</spoiler>
#### [B. Mafia in IITM](https://codeforces.me/gym/394792/problem/B)
Problem Author: [user:anmol73,2022-08-16]
<spoiler summary="Tutorial">
Anmol starts at the origin $(0,0)$ initially. Let his position after $k$ $(k < n)$ moves be $(x,y)$ and his final position be $(X,Y)$ . Since hi...
Since we do not have a simple ordered multiset, For computing $x_1$, we can use an ordered multiset. Every day we will insert
the value of the
33.
Falsely accused of plagiarism [Submissions are not at all similar] **In yesterday's [contest:1632], I was falsely accused of plagiarism where as none of the people in question have codes similar to one another.**
I received the following message.
<spoiler summary="Problem C">
<a href='https://www.linkpicture.com/view.php?img=LPic61f7873debc2c1045477817'><img src='https://www.linkpicture.com/q/C_2.png' type='image'></a>
</spoiler>
<spoiler summary="Problem D">
<a href='https://www.linkpicture.com/view.php?img=LPic61f7876063257829672565'><img src='https://www.linkpicture.com/q/D.png' type='image'></a>
</spoiler>
Submissions of all the users for Problem C.
<spoiler summary="codebuster_10">
~~~~~
#include <bits/stdc++.h>
#define int int64_t //be careful about this
using namespace std;
namespace IN{
template<class T> void read(vector<T> &A);
template<class S,class T> void read(pair<S,T> &A);
template<class T,size_t N> void read(array<T,N> &A);
template<class T> void read(T& x){
cin >> x;}
template<cla...
exists (`sum < 0`). // Can be used as an ordered set/multiset on indices in
`[0, tree_n)` by using, ordered set/multiset on indices in `[0, tree_n)` by using the tree as a 0/1 or
frequency array
34.
Point Updates in Merge Sort Trees Hello, I have implemented the version of **merge sort tree** that can handle **point updates** and supports duplicate elements in the tree.
I have done it using [C++ STL: Policy based data structures](https://codeforces.me/blog/entry/11080).
There is no implemented tree multiset in STL. So, I have used pair<T,int> as a key where the second element in pair is the time when item has been added, in order to maintain uniqueness of elements.
The time complexity summaries are as follows :
- **Build Complexity** — _O(n log^2 n)_
- **Query Complexity** — _O(log^3 n)_
- **Update Complexity** — _O(log^2 n)_
The code **queries the kth largest element in a range**, similar to [MKTHNUM](https://www.spoj.com/problems/MKTHNUM/) in spoj but with an **update** part.
~~~~~
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define lc ((n)<<1)
#define ...
structures](https://codeforces.me/blog/entry/11080). There is no implemented
treemultiset in STL. So, There is no implemented tree multiset in STL. So, I have used pair as a key
where the second
35.
Editorial for TheForces Round #40 #### [Problem A — Submission Bait II](https://codeforces.me/gym/105767/problem/A)
Author: [user:wuhudsm,2025-03-07]
Preparer: [user:Banis,2025-03-07]
<spoiler summary="Hint">
Think about what it means for one number to divide another. If $x$ and $y$ are two distinct integers and $x$ divides $y$ then $x$ can't be too big with respect to $y$, more specifically $x \leq \frac{y}{2}$. How can we use this in our problem?
</spoiler>
<spoiler summary="Solution">
Read the hint first. $\newline$
While constructing the array $a$ of size $n$, the goal is to pick numbers from $1$ to $2n$ such that no number divides another. The hint gives us a nudge: $x | y \implies x \leq y/2$, so what if we construct the array in a way that $\text{min}(a)$ (the smallest element of the array) is greater than $\frac{\text{max}(a)}{2}$ (half of the maximum element). We can construct the array $[n + 1 \ldots 2n]$ which satisfies our required condition. $\newline$
Time Complexity : $O(n)$
</...
array is the collection of its values; that is, the positions are not
important, only themultiset of, the collection of its values; that is, the positions are not important, only
themultiset of numbers
Announcement of TheForces Round #40 (Maths-Forces)
36.
A blog on the Sprague-Grundy Theorem So, I ended up making a talk on Sprague-Grundy as part of a club at my school, and thought that the denizens of codeforces would appreciate it. As follows is roughly what was on the handout, which goes over Sprague-Grundy along with the application of its theory to Nim. As this is my first blog post on Codeforces, please do let me know if there are any mistakes in formatting.
I hope you find this interesting, as writing and explaining this helped me understand how to apply it to problems. This handout was written as more math-oriented, so it may be a bit heavy. The exercises are left unsolved, as they are intended to be worked through by the reader.
If you just want to get to what the Sprague-Grundy is defined as, search for "The Sprague-Grundy function of a game" after reading how games were defined.
Way too much theory
=============================
A necessary definition of games
-------------------------------
For this talk, a game will be a two-player sequential game o...
is defined as a multiset of heaps of a given size. Combining previous
statements, a game of Nim is, , order matters If there are two stacks, then the number of positions gets more
complicated. From
37.
Why counting with multiset is a bad idea? Because $\text{\footnotesize \texttt{multiset::count}}$ works in $O(n)$ time.
Quite recently I needed to solve this kind of problem:
$\text{{\bfseries Abridged statement.} Given an array } A,\ |A| = n,\ \forall i \in [1..n]\ a_i \in [-10^9..10^9] \text{ and } a_i \in \mathbb{Z} \text{ compute the value of the most frequent element in } A.$
I decided to use $\text{\footnotesize \texttt{multiset}}$, since it had some __useful__ method called $\text{\footnotesize \texttt{count}}$. And since I needed to _count_ the elements I coded something like this:
~~~
int main() {
int n;
vector<int> a(n);
multiset<int> cnt;
/* Read array */
// Insert elements in multiset
for (auto i : a)
cnt.insert(i);
// Choose among all elements of a the most frequent
int ans = 0;
for (auto &i : cnt)
ans = max(ans, cnt.count(i));
cout << ans << endl;
return 0;
}
~~~
Now. The problem was that this code was jud...
Why counting with multiset is a bad idea?, tree, we know that if we commit _DFS_ through the tree and write out the nodes
in theorder of, Because $\text{\footnotesize \texttt{multiset::count}}$ works in $O(n)$ time.
Quite recently I
38.
Interesting Problem (maybe) Hello,
Recently my friend encountered the following problem during a coding interview:
You are given a string $S$ and a set $T$ of $n$ strings. You need to choose a multiset from $T$ (you can choose the same string any number of times) and then concatenate the strings from the multiset in any order to obtain the string $S$. What is the maximum possible size of such a multiset?
There is a simple $O(|S|^2)$ solution using DP + trie. First add all strings from $T$ to a trie. Let $DP[i]$ be the answer for $S_{i...|S|-1}$. To calculate $DP[i]$, we traverse the trie according to the substring $S_{i...|S|-1}$, and try to update $DP[i]$ for each string we encounter in the trie.
Assuming the sum of the lengths of strings from the set $T$ is $X$, there is also a solution with complexity $O(|S| * sqrt(X))$:
<spoiler>
This is an optimization to the previous DP solution.
Divide the strings into light strings (with length $\le sqrt(X)$) and heavy strings (with length $> sqrt...
in any order to obtain the string $S$. What is the maximum possible size of
such amultiset?, order to obtain the string $S$. What is the maximum possible size of such a
multiset? There is a
39.
Handy C++ Class for Order Statistics: SortedArray (PBDS Wrapper) Hey everyone!
I recently built a neat wrapper around GNU PBDS's ordered multiset to simplify operations like:
- Counting how many elements are <, <=, >, or >= a value
- Range frequency queries like [l, r], (l, r], etc.
- Accessing the k-th smallest element (0-based) with [] operator
It's named **SortedArray**, and it makes these operations intuitive using operator overloading.
Use the code below and make sure you have ordered_set included from PBDS,
~~~~~
class SortedArray {
ordered_multiset arr;
public:
long long size() { return arr.size(); }
void operator += (long long x) { arr.insert(x); }
long long operator < (long long x) { return arr.order_of_key(x); }
long long operator <= (long long x) { return arr.order_of_key(x+1); }
long long operator > (long long x) { return arr.size() - arr.order_of_key(x+1); }
long long operator >= (long long x) { return arr.size() - arr.order_of_key(x); }
long long LR(long long l, long long ...
Handy C++ Class for Order Statistics: SortedArray (PBDS Wrapper), Hey everyone! I recently built a neat wrapper around GNU PBDS's ordered multiset
to simplify, I recently built a neat wrapper around GNU PBDS's ordered multiset to simplify
operations like:
40.
Invitation to CodeRed — 2020 by IIIT Allahabad Hello everyone !!
After 3 successful editions, [Aparoksha](https://aparoksha.org/) is back with flagship coding event — **CodeRed**.
**CodeRed 2020** consists of 2 rounds, **Online preliminary round** and **Onsite final round**.
The online preliminary round will be a **3-hour** long team event with a maximum size of the team being 3 members. The participants need not be from the same college/institution/organization. Problem set has 6/7 problems of varying difficulty. [CodeRed 2020](https://www.codechef.com/CORE2020?itm_campaign=contest_listing) is scheduled at [March 11, 2020 at 22:00 IST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=CodeRed+2020&iso=20200311T1630&ah=3)
Last year [CodeRed 2019](https://www.codechef.com/CORD2019?itm_campaign=contest_listing) had 1271 teams registered, we are expecting higher participation this year. You can register your team here — [CodeRed 2020 online preliminary round](https://www.codechef.com/CORE2020?itm_campaig...
change the order of levels. Then, for each level keep the maximum value of the
node, building segment, ; } }; struct LineContainer : multiset> { // (for doubles, use inf = 1/.0,
div(a,b) = a/b
41.
Codeforces Round #638 (Div. 2) Editorial [problem:1348A]
<spoiler summary="Tutorial">
[tutorial:1348A]
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void solve(){
int N;
cin>>N;
//note: 1<<X means 2^X
//we put largest coin in first pile
int sum1=(1<<N), sum2=0;
//we put n/2-1 smallest coins in first pile
for (int i=1;i<N/2;i++)
sum1+=(1<<i);
//we put remaining n/2 coins in second pile
for (int i=N/2;i<N;i++)
sum2+=(1<<i);
cout<<sum1-sum2<<endl;
}
int main(){
int t; cin>>t;
while (t--)
solve();
}
~~~~~
</spoiler>
[problem:1348B]
<spoiler summary="Tutorial">
[tutorial:1348B]
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void solve(){
int N,K;
cin>>N>>K;
set<int>s;
for (int i=0;i<N;i++){
int a;
cin>>a;
s.insert(a);
}
//if more than K distinct numbers, print -1
if (s.size()>K){
cout<<-1<<endl;
return;
...
<=N;i++) v.push_back({{a[i],b[i]},i}); sort(v.begin(),v.end()); multiset
Tutorial of Codeforces Round 638 (Div. 2)
42.
Practice Problems on Set, Multiset, Map ### CSES 1084 – Apartments
We match applicants with apartments. Each applicant can take an apartment within `±k` of his desired size.
```cpp
// https://cses.fi/problemset/task/1084/
int n, m, k;
cin >> n >> m >> k;
vector<int> s(n);
for (int i = 0; i < n; i++) cin >> s[i];
sort(s.begin(), s.end());
multiset<int> ms;
while (m--) {
int x; cin >> x;
ms.insert(x);
}
int ans = 0;
for (int i = 0; i < n; i++) {
int l = s[i] - k, r = s[i] + k;
auto it = ms.lower_bound(l); // first apt >= l
if (it != ms.end() && *it <= r) {
ans++;
ms.erase(it);
}
}
cout << ans << "\n";
```
---
### CSES 1091 – Concert Tickets
Each customer wants a ticket with price ≤ `x`.
```cpp
// https://cses.fi/problemset/task/1091/
int n, m;
cin >> n >> m;
multiset<int> ms;
for (int i = 0; i < n; i++) {
int x; cin >> x;
ms.insert(x);
}
for (int i = 0; i < m; i++) {
int a; cin >> a;
auto it = ms.upper_boun...
Practice Problems on Set, Multiset, Map, ### Codeforces 637B – Chat Order, (s.begin(), s.end()); multiset ms; while (m--) { int x; cin >> x; ms.insert(x, We need to print the chat names in the order of their last appearance.
43.
[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...
%93Watson_algorithm). If we insert the points in a random order, we can
significantly reduce the
44.
IZhO 2020 editorial(not all problems yet) A month ago [IZhO 2020](https://izho.kz/izho-2019-2/about/) was held in Almaty, Kazakhstan. Thanks to [user:Tima,2020-01-28] we can submit our solutions [here](/group/Uo1lq8ZyWf/contests). Here is editorial for problems day1 A, day1 B, day2 C. Please write solutions for other problems in comments.
[user:Benq,2020-01-28] has published his codes for all problems [here](/blog/entry/72687?#comment-576121).
**[Day1 A](/group/Uo1lq8ZyWf/contest/265564/problem/A)**
<spoiler summary="Observation">
$a1$ $a2$ $a3$ $x$ $a5$ $a6$ $a7$
$b1$ $b2$ $b3$ $y$ $b5$ $b6$ $b7$
Lets assume numbers in position $i = 4$` $x$ and $y$ are swaped. $y$ may go to positions ${4, 5, 6, 7}$. $y$ can't go to positions ${1, 2, 3}$ cause $y > x >= a3 >= a2 >= a1$. Similarly $x$ may go to positions ${1, 2, 3, 4}$ but can't go to positions ${5, 6, 7}$. Its easy to see that still $a_1 <= b_1, a_2 <= b_2, a_3 <= b_3$, furthermore $a_4 <= b_4$ $=>$ Next swap will occurr in $j$, where $j > i$.
<...
minimum$ operations. In C++ we have $std::multiset$. We'll maintain two of
them` $A$ and $B$. Lets, $ and $get minimum$ operations. In C++ we have $std::multiset$. We'll maintain
two of them` $A
45.
Denied Judgement for Haunted House 904 Div 2 Can anybody tell what is the issue in this, did pass a lot of cases but crashed for a case
The problem
https://codeforces.me/contest/1884/problem/B
// This is going to be the template for competitive programming
#include <iostream> // cin, cout, basic I/O
#include <algorithm> // sort, max, min, lower_bound, upper_bound
#include <cmath> // sqrt, pow, abs, log, sin, cos, etc.
#include <cstring> // memset, memcpy, strcmp (C-style strings)
#include <vector> // vector
#include <set> // set, multiset, ordered sets
#include <map> // map, multimap
#include <unordered_map> // hash map (average O(1))
#include <unordered_set> // hash set (average O(1))
#include <queue> // queue, priority_queue
#include <stack> // stack
#include <deque> // deque (double-ended queue)
#include <bitset> // bitset (fixed-size bit manipulation)
#include <numeric> // accumulate, gcd, lcm, iota`
#...
// set, multiset, ordered sets #include // map, multimap #include, ) #include // vector #include // set, multiset, ordered sets #include
46.
Разбор Codeforces Round 990 (Div. 2 + Div. 1) ### Div2A
Alyona is happy when there are no unfinished layers — that is, in front of her is a perfect square with odd side length. Since the order of pieces is fixed, it is enough to keep track of the total current size $s$ of the puzzle, and after each day check, if the $s$ is a perfect square of an odd number. The easiest way to do that is to create an additional array containing $1^2, 3^2, 5^3, ..., 99^2$, and check after each day, whether $s$ is in this array.
<spoiler summary="Code">
~~~~~
NT = int(input())
sqs = set()
k = 1
while k * k <= 100 * 1000:
sqs.add(k * k)
k += 2
for T in range(NT):
n = int(input())
a = list(map(int, input().split()))
answer = 0
cursum = 0
for t in a:
cursum += t
if cursum in sqs:
answer += 1
print(answer)
~~~~~
</spoiler>
### Div2B
Find the character which appears the lowest number of times — if tied, take the earlier character in the alphabet. Find the character which appears the highe...
a perfect square with odd side length. Since the order of pieces is fixed, it
is enough to keep, ; multiset back; for (int i = n - 1; i >= 0; i--) { if (frontfront >= frontback
|| a[i, ; } } vector> tasks; int unused = 0; vector order(n); iota
Tutorial of Codeforces Round 990 (Div. 1)
Tutorial of Codeforces Round 990 (Div. 2)
47.
CSES — Sliding Window Editorial Some of the most powerful techniques are also the simplest yet identifying when and how to apply them effectively can be challenging. Sliding window is one such method. Sliding window helps solve problems involving sequences, subarrays, or continuous segments by efficiently tracking changes as the window moves forward.
While tackling the CSES Sliding window problems, I noticed that many seemingly complex tasks like tracking the sum of elements in a dynamic segment, finding a subarray's minimum or maximum, or counting distinct elements can be simplified and optimized with this technique. Initially, one might consider brute-force methods iterating over every possible subarray or recomputing values from scratch. However, the core idea behind sliding window is smartly updating the state of the window rather than recalculating everything each time.
In my experience, the primary challenge while solving these problems came down to accurately managing the data structures supporting the w...
time. For that, we use a deque where we maintain the elements in increasing
order of value. When a, , which behaves like a balanced BST with support for order statistics. This
structure allows us to
48.
STL Basics – lower_bound, upper_bound, BST, Set, Multiset, Map, Priority Queue # Advanced STL Structures — A Complete Guide
Hi everyone! In this lecture we'll go deeper into STL structures that are **must-know** for competitive programming.
---
## 1. Iterators & Vectors
Iterators are like pointers that let you navigate through containers.
```cpp
vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin(); // points to first element
auto end = v.end(); // points AFTER last element
sort(v.begin(), v.end()); // sort entire vector
v.end() - v.begin(); // size of vector
```
### Key Facts
* `v.begin()` → iterator to first element
* `v.end()` → iterator AFTER last element (not the last element itself!)
* `v.size()` = `v.end() - v.begin()`
### Important Trick
Count numbers in range `[l, r]` = `r - l + 1`.
This formula appears constantly in:
- Binary search problems
- Range queries
- Coordinate compression
**Example:**
```cpp
// How many integers from 5 to 10 inclusive?
int count = 10 - 5 + 1;...
STL Basics – lower_bound, upper_bound, BST, Set, Multiset, Map, Priority Queue, . `multiset` Same as `set`, but **allows duplicates**. ```cpp multiset ms = {1,
2, 3, 4, 4, /largest element * **Event simulation** → process events in time order
49.
[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 ...
------------------ We want a data structure that we can think of a set/multiset
of **non-negative integers**, or
50.
What to do for query problems? Howdy Codeforces!
Recently, while solving previous Codefoces problems, I have seen many query problems. What I mean by query problems are: you are given q queries, like updating and printing something.
This is what I have gathered from query problems:
- Arrays can be used for simple query problems.
- Prefix sums can sometimes be used for query problems (No Updates Ranged Query)
- Sets/Multisets are often used for query problems that need O(logn) operations.
- Ordered set is used for some query problems (Point Update Range Query)
- Segment tree (with lazy propagation on ranged updates) can be used often for Point Update Range Query, Range Update Point Query, Range Update Range Query.
Of course, although segment tree is a solution for many query problems, it isn't easy to code, especially for specialists like me.
Me personally, I have started to direct myself to thinking set/multiset first, because it seems to often work.
Did I miss any ways to solve query problems?
...
are often used for query problems that need O(logn) operations. - Ordered set
is used for some, /Multisets are often used for query problems that need O(logn) operations. -
Ordered set is used for
51.
Codeforces Round #760 (Div. 3) Editorial [problem:1618A]
Idea: [user:Brovko,2021-12-14], preparation: [user:Brovko,2021-12-14]
<spoiler summary="Tutorial">
[tutorial:1618A]
</spoiler>
<spoiler summary="Solution (Brovko)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
vector <int> b(7);
for(int i = 0; i < 7; i++)
cin >> b[i];
cout << b[0] << ' ' << b[1] << ' ' << b[6] - b[0] - b[1] << endl;
}
}
~~~~~
</spoiler>
[problem:1618B]
Idea: [user:BledDest,2021-12-14], preparation: [user:awoo,2021-12-14]
<spoiler summary="Tutorial">
[tutorial:1618B]
</spoiler>
<spoiler summary="Solution (awoo)">
~~~~~
for _ in range(int(input())):
n = int(input())
s = input().split()
for i in range(n - 3):
if s[i][1] != s[i + 1][0]:
s.insert(i + 1, s[i][1] + s[i + 1][0])
break
else:
...
]; int q[N]; int p[N]; multiset wst[N], bst[N]; long long sum; int getp(int a){
return a, ]; multiset wst[N], bst[N]; long long sum; int getp(int a){ return a == p[a] ?
a : p[a] = getp(p[a
Tutorial of Codeforces Round 760 (Div. 3)
52.
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...
increasing order of $k$ and also the array $a$ in increasing order (compute
the permutation $p_1, p_2
53.
ACM Marathon 2024 Tutorial [Smartass (Easy Version)](https://codeforces.me/group/ppRciMeJFg/contest/477806/problem/B)
<spoiler summary="Tutorial">
We realize that $n$ isn't too large in this version of the problem. First thing that comes to mind is using brute force. We'll simply check the sum of every single subarray and check if it's equal to $0$. An $O(n ^ 3)$ solution won't suffice so instead we'll have to write an $O(n ^ 2)$ one. We'll also have to make sure that the variable keeping track of our sum is of type `long long` since the values of $a_{i}$ reach up to $10^9$, meaning `int` would overflow.
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
#define IAMSPEED ios_base::sync_with_stdio(0); cin.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define getrand(l, r) uniform_int_distribution<int>(l, r)(rng)
const int mod = 1000000007;
const int oo = 1000000010;
const int N = 1010;
int n, arr[N];
void solve...
current sliding window using a `multiset` in order to both check if the
condition has been satisfied, window using a `multiset` in order to both check if the condition has been
satisfied yet and for
54.
Gale-Ryser Theorem _This blog is a submission for the [Third Codeforces Month of Blog Posts](https://codeforces.me/blog/entry/149422), thanks to [user:cadmiumky,2026-02-10] for the initiative!_
_Thanks to [user:TeaTime,2026-02-10] and [user:k1r1t0,2026-02-10] for giving feedback on the post._
---
Hi everyone!
I want to talk about Gale-Ryser Theorem and some of its applications. I've provided proofs for each fact in the blog, they're hidden under the spoilers.
---
Gale-Ryser Theorem
==================
We have an array of $n$ non-negative integers $a_1, a_2, \ldots, a_n$ and an array of $m$ positive integers $b_1, b_2, \ldots, b_m$, $b_i \le n$. The array $b$ describes a sequence of operations, in the $i$-th operation we need to decrease the values at $b_i$ positions by $1$, formally pick $b_i$ unique indices $j_1, j_2, \ldots, j_{b_i}$ and decrease $a_{j_p}$ by $1$ for $1 \le p \le b_i$. We want to know if it's possible to have all $a_i \ge 0$ after the operations.
Without loss o...
for $2 \le k \le m$. Assume $a$ is sorted in non-increasing order, then after
we do the first
55.
Codeforces Round #115 — editorial F #### Problem [problem:175F]
Construct the graph with vertices corresponding to castles and edges to roads. Note, that a degree of each graph vertex does not exceed _4_, so the amount of edges does not exceed _E_ <= _2_ * _N_.
In order to solve the problem let's find out how we can handle each query with time _O_(_log_(_N_)). Consider the query to find amount of gnomes destroyed by the Mission of Death. Assume that the edge weight is the amount of gnomes on the appropriate road. We must find the shortest path between two vertices and among them the path with the smallest amount of edges. So, the way is described by two numbers --- _G_ and _R_ --- amount of gnomes and edges (for now we do not consider lexicographical minimality). One edge between vertex _u_ and _v_ is described by (_C_(_u_,_v_), _1_), where _C_(_u_,_v_) --- amount of gnomes on the edge (_u_,_v_). Consider two vertices _s_ and _t_. We want to find the path between them. The shortest path between them can be one of ...
along the Evil Shortcut or the path between two vertices of the Good Path. In
order to find gnomes on, not exceed _E_ <= _2_ * _N_. In order to solve the problem let's find out how
we can handle each
Tutorial of Codeforces Round 115
56.
[SOLVED] Finding counter example (misunderstanding) Hello , My name is Mohammad , I am new to competitive programming. I need some help finding a counter example to my code or to find out why it's wrong. It's a classic CSES sorting and searching problem : [Collecting numbers](https://cses.fi/problemset/task/2216/)
Please read the logic of the code before reading the actual code.
Here is my code :
~~~~~
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int INF = 1e10;
const int N = 1e5 + 1;
signed main(){
int n;
cin >> n;
vector <int> v(n);
for (int i = 0; i < n; i++){
cin >> v[i];
}
set < int > s;
s.insert(v.front());
for (int i = 1; i < n; i++){
int x = v[i];
auto put = s.upper_bound(x);
if (put == s.begin()){
s.insert(x);
}
else {
put--;
s.erase(put);
...
numbers in an increasing order and not necessary in the order of $1 , 2 ...
n$. But the problem want the, the second element into $s$ in one of the vectors in the set in an increasing
order. The set
57.
I need Help to optimize a Dp Code !! Today, I learned Digit DP for the first time, so I tried to solve different kinds of Digit DP problems. While doing that, I came upon [This](https://codeforces.me/problemset/problem/2039/C1) question. I know this is not a Digit Dp question, and there is a much better approach to this question. However, I wrote a solution using the concepts I learned and got **TLE on Test Case 5**. Can Someone help me optimize this further?
Here is the code :
~~~~~
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree< T , null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update >;
// *st.find_by_order(i) --> element at ith position
// st.order_of_key(x) --> no. of ele less than x
//For multiset change less to less_equal and for reverse order change less to greater
#define int long long
#define endl '\n'
#define all(x) (x).begin(), (x)....
// st.order_of_key(x) --> no. of ele less than x //For multiset change less to
less_equal and for reverse, >; // *st.find_by_order(i) --> element at ith position // st.order_of_key(x)
--> no. of ele less than x //Formultiset
58.
Help with Policy based Data Structure — ordered_set Hi all,
I hope you are having a great day.
I was solving [this](https://codeforces.me/problemset/problem/61/E) problem, which is quite simple with the policy based Data Structure [Ordered Set](https://codeforces.me/blog/entry/11080).
However, I wanted to create a Ordered Multiset, but I couldn't get it to work, as I could not erase from the resulting data structure.
Can someone please help me by giving me the code for the ordered_multiset which supports insertion,deletion, order_by_key, and size?
Thanks,
-BC
Edit 2: It finally worked! :) Yay, I solved the problem, but more importantly, I found out some important things when using an `ordered_multiset`.
You must include the following in your code, apart from everything else to use the `ordered_multiset`.
~~~~~
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
~~~~~
Let's call our `ordered_multiset` `om` since its suuuuper annoying ...
However, I wanted to create a Ordered Multiset, but I couldn't get it to work,
as I could not erase, ](https://codeforces.me/blog/entry/11080). However, I wanted to create a
Ordered Multiset, but I
59.
AtCoder Beginner Contest 140 English Solutions #A — Password
We have $N$ choices for each of the three characters in our password. This gives us a total of $N \cdot N \cdot N = N^3$ possible passwords. We can thus print $N \cdot N \cdot N$ as our answer.
Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc140/submissions/7380201)
---
#B — Buffet
We can solve this with a brute-force simulation, simply implementing the procedure given in the problem. Iterate over the dishes in the order specified by array $A$, and when we eat dish $i$, add $B[i]$ to our answer, plus $C[i-1]$ if we just ate dish $i-1$.
Note that since we'll eat every dish once, we could also just add the sum of array $B$ to our answer as we read it in, iterating over $A$ only to add values from $C$ where necessary. My solution implements this approach.
Runtime: $O(N)$. [Click here for my submission.](https://atcoder.jp/contests/abc140/submissions/7383059)
---
#C — Maximal Value
We're giv...
order specified by array $A$, and when we eat dish $i$, add $B[i]$ to our
answer, plus $C[i-1]$ if we
60.
Codeforces Round #491 (Div.2), Editorial [problem:991A]
<spoiler summary="Editorial">
There are 4 groups of students — those who visited only the first restaurant, who visited only the second, who visited both places and who stayed at home. One of the easiest ways to detect all the incorrect situations is to calculate number of students in each group. For the first group it is $A-C$, for the second: $B-C$, for the third: $C$ and for the fourth: $N-A-B+C$. Now we must just to check that there are non-negative numbers in the first three groups and the positive number for the last group. If such conditions are met the answer is the number of students in the fourth group.
~~~~~
int n1 = a - c;
int n2 = b - c;
int n3 = c;
int n4 = n - n1 - n2 - n3;
if (n1 >= 0 && n2 >= 0 && n3 >= 0 && n4 > 0)
cout << n4;
else
cout << -1;
~~~~~
In general you are recommended to view [inclusion–exclusion principle](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle).
Moreover the limitatio...
redo the lowest grades firstly. So we have to sort the values in the ascending
order and begin to
61.
CodeCraft-21 and Codeforces Round #711 (Div. 2) Editorial [problem:1498A]
==================
#### [**Video Editorial**](https://www.youtube.com/watch?v=lV5cb8wh3sE)
**Author and Problemsetting:** [user:ninja_28,2021-03-29]
**Editorialist:** [user:sigma_g,2021-03-29]
<spoiler summary="Hint">
Can you think of the simplest properties that relate a number and its sum of digits?
</spoiler>
<spoiler summary="Hint 2">
Note that if $X$ is a multiple of 3, then **both** $X$ as well as the sum of digits of $X$ are a multiple of 3! Can you put this property to use here?
</spoiler>
<spoiler summary="Hint 3">
If $X$ is a multiple of 3, then $\texttt{gcd-sum}(X) \ge 3$. Therefore, we are guaranteed that at least every third number will satisfy the constraints required by our problem $(\texttt{gcd-sum}(X) > 1)$.
</spoiler>
<spoiler summary="Solution">
Therefore, for the input $n$, we can simply check which one of $n$, $n+1$, and $n+2$ has its gcd-sum $> 1$, and print the lowest of them.
</spoiler>
<spoi...
="Another implementation"> It is also possible to implement the solution with a
`multiset` and
Tutorial of CodeCraft-21 and Codeforces Round 711 (Div. 2)
62.
CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) Editorial We apologize for the technical difficulties in Task B. We hope you enjoyed the rest of the contest. We will add hints soon.
[problem:1870A]
<spoiler summary="Tutorial">
Note that if $min(n, x+1) < k$, then the answer is $-1$.
Otherwise, there are two cases:
- If $k=x$, then the suitable array looks like $[0, 1, 2, \dots, k-1, \dots, k-1]$.
- If $k \ne x$, then the suitable array looks like $[0, 1, 2, \dots, k-1, x, \dots, x]$.
In both cases, we can construct the array and calculate its sum in linear time. The overall complexity is $O(n \cdot t)$.
</spoiler>
[problem:1870B]
<spoiler summary="Tutorial">
Note that after performing the operation on $b_j$, which has some bit set to 1, this bit will become 1 for all numbers in $a$ (and will remain so, as a bit cannot change from 1 to 0 in the result of an OR operation). If $n$ is even, then in the final XOR, this bit will become 0, as it will be equal to the XOR of an even number of ones. If $n$ is odd, then ...
breadth-first search (BFS). In both traversals, we go to the children of a
node in ascendingorder of the
63.
A notorious coincidence (1854E) So one thing led to another and now I'm here to share my results.
[Codeforces Round 889 (Div. 1)](https://codeforces.me/contest/1854)
------------------
As of writting this blog that's the most recent codeforces round and there was some controversy about some problems in it. I'm here to talk about a funny thing that happened involving its div1E.
This story starts during the contest.
<spoiler summary="You can skip this, it's just me talking about what happened to me before reaching E">
I was taking the contest and thinking about going to sleep after 1 hour without mindsolving anything but A1 but then I ended up solving CBA1. Without being able to notice that my solution to A1 was actually the intended solution to A2 and not having the faith in the gods of AC to just take the minimum of both constructions, I turned into E as I'm notoriously bad at interactive problems.
</spoiler>
Revisiting E after solving the other problems, I thought "maybe using a bunch of ones and hi...
solution: For each multiset of values 1 and 2 with sum less than 60, greedily
build the number of ways
64.
Editorial for A2SV Education Phase I — Contest #6 [A. Zoro’s Bounty Dilemma
](https://codeforces.me/gym/594356/problem/A)
<spoiler summary="Solution">
There is four possible outcomes to this problem, if there has been both a '>' and '<' in your string , then you cant determine the winner so you return '?'. with that case out of the way you just need to keep track of if theres been a '<' or '>' since we know both couldnt have been there, so which ever one you find, you print, if its neither , you can return '='.
</spoiler>
<spoiler summary="Code">
```python
for _ in range(int(input())):
s = input()
if '<' in s and '>' in s:
print('?')
elif '<' in s:
print('<')
elif '>' in s:
print('>')
else:
print('=')
```
</spoiler>
[B. Thousand Sunny's Network Setup](https://codeforces.me/gym/594356/problem/B)
<spoiler summary="Solution">
The problem requires selecting k computers with the highest possible equal internet speed, given that we can only decrease speeds but not increase them. A simple a...
The problem involves rearranging an array b to match the order of, and efficient approach is to sort the array in descending order and directly
pick the k-th largest
65.
Codeforces Global Round 16 Editorial We hope that you enjoyed the contest. Let's get right into the editorial:
<spoiler summary="A: Median Maximization">
[problem:1566A]
<spoiler summary="First solution">
<spoiler summary="Hint 1">
Which numbers smaller than the median should be taken?
</spoiler>
<spoiler summary="Hint 2">
Which numbers bigger than the median should be taken?
</spoiler>
<spoiler summary="Hint 3">
Greedy algorithm.
</spoiler>
<spoiler summary="Editorial">
Let's consider the array of $n$ elements in non-decreasing order. We can make numbers before the median equal to zero, after that we have $m = \lfloor {\frac{n}{2}} \rfloor + 1$ numbers, which sum should be $n$ and the minimal of them (i.e. median value) should be maximized.
To do so, it is enough to make all these numbers equal $\lfloor {\frac{s}{m}} \rfloor$, and then add what's left to the last number ($s \bmod m$). It's easy to see that such array matches all the conditions and it is impossible to make median greater.
</s...
$ elements in non-decreasing order. We can make numbers before the median equal
to zero, after that we
Tutorial of Codeforces Global Round 16
66.
Codeforces Round 965 (Div. 2) Editorial #### [problem:1998A]
Problem Credits: [user:sum,2024-07-03] <br>
Analysis: [user:cry,2024-07-03]
<spoiler summary="Solution ">
We can construct a solution by fixing all $x_i$ as $x_c$ or all $y_i$ as $y_c$. For example, if we fix all $y_i$ as $y_c$, then we can output pairs $(x_c-1, y_c), (x_c+1, y_c), (x_c-2, y_c), (x_c+2, y_c), ... , (x_c- \lfloor \frac{k}{2} \rfloor, y_c), (x_c + \lfloor \frac{k}{2} \rfloor, y_c)$. If the $k$ is odd, we need one more pair, so just output $(x_c, y_c)$.
</spoiler>
<spoiler summary="Code (C++)">
```cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--){
int x, y, k; cin >> x >> y >> k;
for(int i = 0; i < k - k % 2; i++){
cout << x - (i & 1 ? 1 : -1) * (i / 2 + 1) << " " << y << "\n";
}
if(k & 1){
cout << x << " " << y << "\n";
}
}
}
```
</spoiler>
#### [problem:1998B]
Problem Credits: [user:satyam343,2024-08-07] <br>
Analysis: [user:cry,2024-07-03]
<spoiler summ...
out how to find an array's score. Assume the array $a$ is sorted in increasing
order as the order
Tutorial of Codeforces Round 965 (Div. 2)
67.
Please help, want to know error in my code. Hi there, apologies for a newbie post. I wanted to know error (possibly corner case) in my code. It would be really heplful.
Actually I want to get back in to competitive programming. Most of the time, I was able to find the corner cases to my error prone code, but since I lost the habit of doing competitive, I am having trouble with this simple thing.
Here is the problem: https://codeforces.me/contest/1935/problem/C
And here is my code: https://codeforces.me/contest/1935/submission/251937077
What I tried to do is simple. Sort in terms of b, and then finding the appropriate a's between two indexes and brute forcing it across the array to get the maximum.
In order to find a efficiently, I used multiset.
- first optimizing as per the lowest possible a's and removing the largest
- and then adding whatever we can
It would be really helpful. Thanks!
between two indexes and brute forcing it across the array to get the maximum.
Inorder to find a, In order to find a efficiently, I used multiset.
68.
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...
the rest of cells with cyclic order(i.e. color $j$-th cell of the first
segment, of second the
69.
Codeforces Round 971 (Div. 4) Editorial Thanks for participating! Despite the round being unrated, we hope you've enjoyed the problemset. We put a lot of effort into this round :prayge:
I want to give huge thanks to [user:Dominater069,2024-08-28] and [user:satyam343,2024-08-28] for their heavy contributions to the subtasks of G. If you're participating out of competition, we hope you enjoyed attempting these bonus subtasks. Otherwise, we hope you will enjoy upsolving them!
[problem:2009A]
Problem Credits: [user:cry,2024-08-28] <br>
Analysis: [user:cry,2024-08-28]
<spoiler summary="Solution ">
We choose $c$ between $a$ and $b$ $(a \leq c \leq b)$. The distance is $(c - a) + (b - c) = b - a$. Note that the distance does not depend on the the position $c$ at all.
</spoiler>
<spoiler summary="Code (Python) (ntarsis30) ">
```py
for _ in range(int(input())):
a,b = map(int,input().split())
print(b-a)
```
</spoiler>
[problem:2009B]
Problem Credits: [user:cry,2024-08-28] <br>
Analysis: [user:cry...
$b_i=a_i-i$ for all $i$. Now, if $b_i=b_j$, then $i$ and $j$ are in correct
relativeorder. Now, to
Tutorial of Codeforces Round 971 (Div. 4)
70.
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;
...
read() { cin >> n; } inline void solve() { multiset was; for (int i = 1; i <=
n; i, void read() { cin >> n; } inline void solve() { multiset was; for (int i = 1; i
71.
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=...
shadows. So if you sort the distinct values of $b$, they correspond in order
to the distinct values of $a
Tutorial of Codeforces Round 1114 (Div. 3)
72.
Editorial for Hello 2023 ## [problem:1779A]
Author: [user:n0sk1ll,2022-12-27]
<spoiler summary="Hint">
What happens when $\texttt{L}$ appears after some $\texttt{R}$ in the string?
</spoiler>
<spoiler summary="Solution">
Suppose that there exists an index $i$ such that $s_i = \texttt{R}$ and $s_{i+1} = \texttt{L}$. Lamp $i$ illuminates trophies $i+1,i+2,\ldots n$ and lamp $i+1$ illuminates $1,2,\ldots i$. We can conclude that all trophies are illuminated if $\texttt{L}$ appears right after some $\texttt{R}$. So, strings $\texttt{LLRRLL}, \texttt{LRLRLR}, \texttt{RRRLLL}, \ldots$ do not require any operations to be performed on them, since they represent configurations of lamps in which all trophies are already illuminated.
Now, we consider the case when such $i$ does not exist and think about how we can use the operation **once**. Notice that if $\texttt{R}$ appears right after some $\texttt{L}$, an operation can be used to transform $\texttt{LR}$ into $\texttt{RL}$, and we have concluded before...
tournament graph, in the topological order ($S_1$ is the "highest" component,
while $S_k$ is the "lowest
Tutorial of Hello 2023
73.
[Tutorial] Knapsack, Subset Sum and the (max,+) Convolution **Edit**: I have realized that this blog has been sent quite a lot on discord servers, so I am adding a content page at the start to help organize this blog better.
## Prerequisites
Let us first define the classical knapsack, unbounded knapsack and subset sum problems.
#### Subset Sum
There are $N$ items. The $i$-th item has weight $w_i$. Find a set $S$ such that $\sum\limits_{i \in S} w_i = C$.
#### Knapsack
There are $N$ items. The $i$-th item has weight $w_i$ and value $v_i$. Find a set $S$ such that $\sum\limits_{i \in S} w_i \leq C$ and $\sum\limits_{i \in S} v_i$ is maximized.
#### Unbounded Knapsack
There are $N$ items. The $i$-th item has weight $w_i$ and value $v_i$. Find a **multiset** $S$ such that $\sum\limits_{i \in S} w_i \leq C$ and $\sum\limits_{i \in S} v_i$ is maximized.
You should know how to do both versions of knapsack in $O(NC)$ and subset sum in $O(\frac{NC}{32})$ before reading this blog.
In this blog post, I will just show some res...
value $v_i$. Find a **multiset** $S$ such that $\sum\limits_{i \in S} w_i \leq
C$ and $\sum\limits_{i
74.
Editorial of Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) [problem:1654A]
Author: [user:TheScrasse,2022-02-24]<br>
Preparation: [user:TheScrasse,2022-02-19]
<spoiler summary="Hint 1">
Suppose you want to choose pieces of cake $i$, $j$. Can you make them adjacent in $1$ move?
</spoiler>
<spoiler summary="Solution">
The answer is the sum of the $2$ maximum weights.
You can always pick the $2$ maximum weights: if they are $a_i$ and $a_j$ ($i < j$), you can flip the subsegment $[i, j-1]$ to make them adjacent.
The result can't be larger, because the sum of the weights of any $2$ pieces of cake is never greater than the sum of the $2$ maximum weights.
Iterating over all pairs of pieces of cake is enough to get AC, but you can solve the problem in $O(n \log n)$ by sorting the weights and printing the sum of the last $2$ values, or even in $O(n)$ if you calculate the maximum and the second maximum in linear time.
Complexity: $O(t \cdot n^2)$, $O(t \cdot n \log n)$ or $O(t \cdot n)$
</spoiler>
Official solution: [submissi...
., multiset or priority queue), the following algorithm works. While either $a$
or $b$ is not empty
75.
Code Gladiator Solution Access solutions of **_"Code Gladiators"_** Contest organized on _HackerRank_ and held by **TSoC** in IIITNR.
WEEK-1
------
#### [Rank Realization](https://www.hackerrank.com/contests/code-gladiatorspractice/challenges/rank-realization)
<spoiler summary="Explanation">
- **Problem**:
Determine the count of participants with ratings strictly higher than Divyansh's rating.
- **Input**:
- Divyansh's rating (r).
- Number of participants (n).
- Array arr containing ratings of other participants.
- **Approach**:
- Read r, n, and arr.
- **Counting Higher Ratings**:
— Initialize a counter variable counter to 0.
— Iterate through each rating in arr.
— If the rating is strictly higher than r, increment counter.
- **Output**:
- Print the value of counter, representing the number of participants with ratings strictly higher than Divyansh.
</spoiler>
<spoiler summary="Code">
Python
```python
r = int(input())
n = int(in...
**: - Sort the total costs of using move 2 for each machine in non-decreasing
order. - **Counting Goodies, class Solution { multiset l, r; public: long long minimumCost(vector
76.
Help with a Leetcode problem [Problem](http://https://leetcode.com/problems/maximum-number-of-tasks-you-can-assign/description/)
You have n tasks and m workers. Each task has a strength requirement stored in a 0-indexed integer array tasks, with the ith task requiring tasks[i] strength to complete. The strength of each worker is stored in a 0-indexed integer array workers, with the jth worker having workers[j] strength. Each worker can only be assigned to a single task and must have a strength greater than or equal to the task's strength requirement (i.e., workers[j] >= tasks[i]).
Additionally, you have pills magical pills that will increase a worker's strength by strength. You can decide which workers receive the magical pills, however, you may only give each worker at most one magical pill.
Given the 0-indexed integer arrays tasks and workers and the integers pills and strength, return the maximum number of tasks that can be completed.
below is the code that i tried with a complexity of N(logN)(logN). N=...
(); // Sorting the tasks and workers in increasing order sort(tasks.begin
77.
Accepted or TLE? The upper_bound Trap Every Programmer Should Know [problem:https://codeforces.me/contest/2254/problem/E
#### std::upper_bound vs set::upper_bound: The Hidden TLE Trap in C++
Many competitive programmers know that `std::upper_bound` runs in **O(log n)**.
Many also know that `std::set::upper_bound()` runs in **O(log n)**.
So naturally, this code should also be **O(log n)**, right?
```cpp
set<int> s = {1,2,3,4,5};
auto it = upper_bound(s.begin(), s.end(), 3);
```
Unfortunately...
**Wrong.**
This can easily turn an accepted solution into a **TLE**.
---
## The Catch
The free algorithm
```cpp
std::upper_bound(first, last, x)
```
works on **Forward Iterators**.
A `std::set` provides **bidirectional iterators**, not random-access iterators.
Binary search requires jumping to the middle quickly.
For vectors, this is easy:
```cpp
mid = first + (last - first) / 2;
```
Both `+` and `-` are O(1).
For a set, however, there is no indexing.
To reach the middle, the algorithm repeat...
ordered associative containers: * `set` * `multiset` * `map` * `multimap`
**Always use the
78.
Interesting implementation of Persistent Sets *Do you really hate tree rotations? This blog post is for you!*
Recently, I've been solving [problem:768G] and I came up with a solution which is so ridiculously overengineered that I think it deserves its own blog post!
I don't want to go over all the details of the solution. Instead, I want to demonstrate a nice way to implement and apply Persistent Set and Persistent Array data structures and share a few ideas some may find interesting.
Basically, what I wanted to do is compute for each node $x$ of the rooted tree a set, which would contain the sizes of all subtrees of $x$. In other words, if we denote $sz(y)$ — the size of the subtree rooted at $y$, I want to compute the set $S(x) = \{sz(y) | y \in subtree(x)\}$ for all $x$. We also want this set to have some `lower_bound` and `upper_bound` functionality.
Obviously, just storing these sets in a normal way would require $O(n^2)$ memory, so we need another approach. Let's use the same idea that we use when building ...
->right->total; return tmp; } ~~~~~ `this_t` is the alias for `paorder>`, the
data type of
79.
Codeforces Round #932 (Div. 2) Editorial [problem:1935A]
Idea: [user:i_love_penguins,2024-02-24] <br> Preparation: [user:i_love_penguins,2024-02-24] <br> Editorial: [user:i_love_penguins,2024-02-24]
<spoiler summary="Hints">
<spoiler summary="Hint 1">
The answer will always have either the prefix $s$, or the reversed string $s$.
</spoiler>
<spoiler summary="Hint 2">
Adding the string to the end is required no more than once.
</spoiler>
</spoiler>
<spoiler summary="Solution">
Let $t$ be the reversed string $s$. Notice that it is advantageous for us to use operation 1 (adding the reversed string at the end) no more than once. Indeed, having obtained some string, we will simply spend the remaining operations on flipping the string. Thus, we will get the original string or the reversed one, depending on the parity of the number of remaining operations.
It is easy to see that the answer will always have either the prefix $s$, or $t$. Then, we find two lexicographically minimal strings with the prefix $s...
. How can changing the order of the messages reduce time?
Tutorial of Codeforces Round 932 (Div. 2)
80.
[EDITORIAL] Syrian Private Universities Collegiate Programming Contest 2023 [A — G Game](https://codeforces.me/gym/104426/problem/A)
Author: [user:Blade-Master,2023-07-10]
<spoiler summary="Tutorial">
</spoiler>
<spoiler summary="Solution">
</spoiler>
[B — Permutation Tree](https://codeforces.me/gym/104426/problem/B)
Author: [user:Space-Time-,2023-07-10]
<spoiler summary="Tutorial">
This problem is solved greedily. Let $v$ be the minimum unassigned node in the tree.
We have to assign it the minimum possible value. This can be done by assigning each unassigned value on the simple path from the root $x$ to $v$ the minimum possible value. This can be done in $O(n)$.
</spoiler>
<spoiler summary="Solution">
~~~~~
#include<bits/stdc++.h>
using namespace std;
int n , x , p [200005] , k , pr [200005];
vector < int > gr [200005];
void dfs ( int x , int pt )
{
pr [x] = pt;
for ( auto u : gr [x] )
{
if ( u == pt ) continue;
dfs ( u , x );
}
}
int up ( int x )
{
if ( p...
) \times ((n-i)! - (\text{the order of the suffix after } i))$. (Because $p$
and $c$ have the same prefix
81.
Fast Access in Multiset I have a multiset . Using a loop I am inserting elements. In each loop , I am asked to access n th element of the multiset . where n is increasing in ascending order,1,2,3,4
I used iterator and pointed it to the begin. But for every loop , I have to iterate . This gives me TLE.
Is there any process for fast accessing in multiset ??
Fast Access in Multiset, element of the multiset . where n is increasing in ascending order,1,2,3,4
82.
Codeforces Round 1025 (Div. 2) Editorial Thank you for your participation! We hope you enjoyed the problems! We would love to hear your feedback! Please share your thoughts in the comments.
<br>
<spoiler summary="How did you find the contest?">
- Great:
- Good:
- Average:
- Bad:
- Trash:
</spoiler>
<spoiler summary="Which problem was your favorite?">
- A:
- B:
- C1:
- C2:
- C3:
- D:
- E:
- F:
</spoiler>
<spoiler summary="Which problem did you find the least enjoyable?">
- A:
- B:
- C1:
- C2:
- C3:
- D:
- E:
- F:
</spoiler>
<br>
[problem:2109A]
Idea by [user:MOUFLESS,2025-05-17], prepared by [user:MO...
="Hint 1"> What changes if the turn order is reversed — starting with Fouad's
move before
Tutorial of Codeforces Round 1025 (Div. 2)
83.
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 ...
] Forget about minimize lexicographical order. What's the size of longest $b
Tutorial of Codeforces Round 967 (Div. 2)
84.
[Tutorial] Zeta, Mobius Transform to AND, OR, GCD Convolution ## Introduction
[Original Post(Korean)](https://blog.naver.com/jinhan814/223175490201)
For those who have studied the Inclusion-Exclusion Principle or the Mobius Inversion formula, you may have wondered about the definition of $μ(n)$ and the process of offsetting unnecessary values by multiplying $(-1)^{|s|}$. Although it is possible to show the validity of these formulas through expansion, such proofs lack intuitive clarity.
In this article, I will define Zeta and Mobius Transform on a Poset and explore examples from various Posets. Understanding these concepts will provide insights into the Inclusion-Exclusion Principle and the Mobius Inversion formula. Additionally, Zeta and Mobius Transform are essential concepts connected to SOS DP and AND, OR, GCD, LCM Convolution. In the final part of the article, we will examine interesting connections to various convolutions from Zeta and Mobius Transform.
## Table of Contents
1. What is Poset?
2. Zeta, Mobius Transform on Pose...
relationship between $b$ and $c$. For this reason, ($S$, $≤$) is referred to
as a PartiallyOrdered Set
85.
Venice Technique Motivation & Problem
---
Recently saw [this](http://codeforces.me/problemset/problem/923/B) problem. For some this problem might seem like a segment tree problem and it is indeed one. However this problem and others where segment tree does not apply can be solved using another approach. I will rephrase the problem in a simpler way. We want a data structure capable of doing three main update-operations and some sort of query. The three modify operations are:
**add**: Add an element to the set.
**remove**: Remove an element from the set.
**updateAll**: This one normally changes in this case subtract X from **ALL** the elements. For this technique it is completely required that the update is done to **ALL** the values in the set equally.
And also for this problem in particular we may need one query:
**getMin**: Give me the smallest number in the set.
Observing this operations we want to handle, **SegmentTree** seems legit except for the remove, but we can wave it arou...
** then we can just use a **MULTISET**. And in fact if the remove is only to
the minimum element then we
86.
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>
...
,2025-11-17] For a multiset $S$, we will find a check to
Tutorial of Codeforces Round 1064 (Div. 1)
Tutorial of Codeforces Round 1064 (Div. 2)
87.
STLs STL (Standard Template Library):
** Vector **
- Definition: A dynamic array that can change in size.
- Syntax: `vector <data_type> name(size);`
- By default, all elements are initialized to zero if no value is specified.
- Available functions:
- Add an element to the end: `name.push_back(value);`
- Copy elements from another vector: `vector<data_type> v2(v);`
- Swap elements between two vectors: `v1.swap(v2);`
** Deque (Double Ended Queue) **
- Definition: Allows insertion and deletion of elements from both ends.
- Syntax: `deque<data_type> name;`
- Available functions:
- Add an element to the back: `push_back();`
- Add an element to the front: `push_front();`
- Remove an element from the back: `pop_back();`
- Remove an element from the front: `pop_front();`
- Remove an element at a specific INDXition: `erase(name.begin() + n);`
** List **
- Defin...
]` ** Multiset ** - Definition: Similar to a set, but allows storing duplicate
values
88.
Editorial of ICPC de Tryst 2026 I hope you enjoyed the contest!
[Contest link](https://codeforces.me/contestInvitation/f8ab858a73f3627f85787c828e7ba84d12495ce9)
<spoiler summary="Rating Predictions and Tags for the Problem">
| Problem | Expected Rating | Tags|
| :---: | :---: | :---: |
| [A. Game is Game](https://codeforces.me/gym/675631/problem/A) | 1500 | games, math |
| [B. Hakurei Shrine's Purification Ritual](https://codeforces.me/gym/675631/problem/B)| 1600 |number theory, binary search|
| [C. Permutation Game](https://codeforces.me/gym/675631/problem/C) | 2600 | dp, greedy, implementation,brute force |
| [D. Path Blow-up?](https://codeforces.me/gym/675631/problem/D) | 2400|bitmasks, trees, dp, combinatorics, implementation|
| [E. Coffee Date of MEX](https://codeforces.me/gym/675631/problem/E)|2100|constructive algorithms, brute force|
| [F. Wordleforces](https://codeforces.me/gym/675631/problem/F) |1800 |math, combinatorics|
| [G. Adaptive Guessing](https://codeforces.me/gym/675631/probl...
draft from the pool of $f_x = 1$ elements in strictly descending order.
Because Alice always takes the
89.
Unlabeling combinatorial species (cycle index series) Hi everyone!
In my [previous blog](https://codeforces.me/blog/entry/103979), I wrote about how generating functions can be used to enumerated labeled species. In this blog, I want to continue the topic by writing about how one can account for different kinds of symmetries when counting different combinatorial structures. Ultimately, we will end up deriving and hopefully understanding the analogue of [Pólya enumeration theorem](https://en.wikipedia.org/wiki/Pólya_enumeration_theorem) in species.
Difficulty: ★★★★☆
Prerequisites:
- Familiarity with combinatorial species (see my [prev. blog](https://codeforces.me/blog/entry/103979)), OR
- Very good intuition with enumerative combinatorics, genfuncs and recap below.
I will try to use plain language rather than formulas as much as possible, as it seems to be the preferred format for readers.
## Recap
Below is a very brief recap of the most important things from the previous article. I tried to keep it as informal as p...
ordered trees on $n \in \{1,2,3,4\}$ vertices. An **unlabeled structure** is
what we
90.
Codeforces Round #940 and CodeCraft-23 (Div. 2) Editorial [problem:1957A]
==================
**Idea:** [user:keyurchd_11,2024-04-21]
**Problem Setting:** [user:shakr,2024-04-21] [user:lezirtin,2024-04-21]
**Editorial**: [user:shakr,2024-04-21] [user:TheRaja,2024-04-21]
There were a few solutions which passes pre-tests with the assumption that $a_i \leq n$. We apologize for the pre-tests on A not including this case.
<spoiler summary="Hint 1">
To create the most polygons, you should use as few sticks as possible per polygon. What polygon has the least number of sides?
</spoiler>
<spoiler summary="Solution">
[tutorial:1957A]
</spoiler>
<spoiler summary="Rate this problem">
-
Great Problem
-
Ok Problem
-
Bad Problem
-
Didn't solve
</spoiler>
<spoiler summary="C++ Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int> a(101, 0);...
, switch around the loop order. The number of distinct ways
Tutorial of Codeforces Round 940 (Div. 2) and CodeCraft-23
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;
...
="Hint 1.3"> Process $k$ in decreasing order.
Tutorial of Codeforces Round 1084 (Div. 3)
92.
Manthan, Codefest'19 Editorial ### [1208A — XORinacci](https://codeforces.me/contest/1208/problem/A)
The sequence is $a$, $b$, $a\oplus b$, $a$, $b$, $a\oplus b$ $\cdots$
Since, the sequence has a period of $3$, $f[i] = f[i \mod 3]$.
<br>
<spoiler summary="Code">
```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int test,a,b,n;
cin>>test;
while(test--){
cin>>a>>b>>n;
switch (n%3){
case 0:
cout<<a<<endl;
break;
case 1:
cout<<b<<endl;
break;
default:
cout<<(a^b)<<endl;
}
}
return 0;
}
```
</spoiler>
### [1208B — Uniqueness](https://codeforces.me/contest/1208/problem/B)
After removing a sub-segment, a prefix and a suffix remain, possibly of length $0$.
Let us fix the prefix which does not contain any duplicate elements and find the maximum suffix we can get without repeating the elements. We can use map/set ...
) ##### **Approach 1** Let us fill the array with numbers from $1$ to $N$ in
increasingorder. $1$ will
93.
Doubt regarding policy based data structure I am implementing an ordered multiset but I am not able to erase elements from it .
https://ideone.com/pnx4R3
From above code, after erasing the number of elements shown are same as without erasing .
I am implementing an ordered multiset but I am not able to erase elements from
it . https
94.
random-oi-facts Dear fellow Codefeorcers,
In hope of educating the vast public, I have written the following notes which hopefully can help readers to have skyrocketed ratings soon. Enjoy!
the following is a poggers string function:
string s, t;
getline(cin, s);
stringstream ss(s);
while (ss >> t) cout << t << '\n';
As a side note, some coders like to use "goto die;" when they are frustrated enough with a task
Global variables are initialized as 0, so you don't need to initialize them (unless you want to initialize to something else)
remember to write an init function for multisets
Today's fact: MATH
one of the laws of log
Log (a’)=,loga -> this can help prevent use of binary exponentiation to prevent an extra log factor in time complexity
If you want to determine whether the i-th bit (from right, 0-based) is set (equal to 1 in binary representation) in integer x, write:
if(x & (1LL << i))
(1LL << i) means "2 to the power of i"
For example
if(x & (1LL << 3)) {
cout << "orz\n";
}...
Priority queue automatically sorts the elements in the queue according to some
specificorder. The
95.
Tips and Tricks ---
https://codeforces.me/contest/2175/problem/A
## Tip: Counting Distinct Elements in All Prefixes
When a problem asks for the number of **distinct elements before or up to each index**, use **prefix traversal + frequency tracking**.
### Idea
* Traverse the array from left to right.
* Maintain a frequency map (or array).
* When an element appears **for the first time**, increase the distinct count.
* Store this count for each prefix.
### Implementation
```cpp
map<int, int> freq;
vector<int> distinct(n);
int cnt = 0;
for (int i = 0; i < n; i++) {
if (++freq[x[i]] == 1)
cnt++; // new distinct element
distinct[i] = cnt; // distinct elements in prefix [0..i]
}
```
### Sum of Distinct Counts Over All Prefixes
```cpp
long long ans = 0;
for (int i = 0; i < n; i++) {
ans += distinct[i];
}
```
### Why This Works
Each element contributes to the distinct count **exactly once**, at its **first occurrence...
**. --- Custom Comparator for Pairs: Sort by Sum Tip: Sort pairs in descending
order based on sum of elements
96.
Help in a Div3 question Hello,
I was trying to solve [this question](https://codeforces.me/contest/978/problem/F).
I am getting TLE on test 8. What I did is first, I stored the pairs which quarrel in an adjacency list like we store in the graph. Then I sorted the programmers based on their skills in increasing order. Then I iterated one by one from the smallest skill person to the highest skilled programmer and kept storing their skills in multiset. So to find the answer for each, I subtracted the adj[x].size() and the same skilled programmers that have occurred before.
I can't understand why I am getting TLE. Can someone please explain the reason? Also, what should I incorporate into my code to solve this problem? I find my approach similar to the tutorial.
[My submission](https://codeforces.me/contest/978/submission/73551928).
I also try to use unordered multiset instead but that too is giving TLE. [Link](https://codeforces.me/contest/978/submission/73552464)
like we store in the graph. Then I sorted the programmers based on their
skills in increasingorder
97.
Codeforces Round 1029 (Div. 3) Editorial <spoiler summary="Rating Predictions">
| Predictor | A | B | C | D | E | F | G | H |
|----------------------------------|-----|-----|------|------|------|------|------|------|
| [user:AksLolCoding,2025-06-06] | 800 | 800 | 900 | 1300 | 1500 | 1800 | 1900 | 2300 |
| [user:SpyrosAliv,2025-06-06] | 800 | 800 | 1100 | 1200 | — | 1600 | 1900 | 2200 |
| [user:wuhudsm,2025-06-06] | 600 | 800 | 1300 | 1500 | 2100 | 1900 | 2100 | 2200 |
| [user:Dominater069,2025-06-06] | 800 | 800 | 1000 | 1200 | 1900 | 1800 | 1800 | 2000 |
| [user:Proof_by_QED,2025-06-06] | 800 | 800 | 1100 | 1300 | 1500 | 1700 | 1900 | 2400 |
| [user:reirugan,2025-06-06] | 800 | 800 | 1300 | 1400 | 1600 | 1800 | 2100 | 2400 |
| [user:-firefly-,2025-06-06] | 800 | 800 | 1200 | 1300 | — | 1700 | 1800 | 2300 |
| [user:Edeeva,2025-06-06] | 800 | 800 | 1200 | 1400 | 1500 | 1800 | 2000 | — |
| [user:Intellegen...
perform after pairing the operations. Since we need to have an arithmetic
sequence inorder to explode
Tutorial of Codeforces Round 1029 (Div. 3)
98.
STL Containers Every Competitive Programmer Should Know The C++ Standard Template Library (STL) is essential for competitive programming (CP) on platforms like Codeforces. It provides powerful, optimized data structures and algorithms that save time and prevent you from reinventing the wheel during contests.The primary STL containers every competitive programmer must know are grouped below by their functionality, use cases, and time complexities:1. Sequence Containersstd::vector (Dynamic Array)What it is: A dynamic array that can resize itself automatically when an element is inserted or deleted.Why it's essential: It is the default container for storing sequential data. Unlike standard static arrays, vectors can be passed to functions seamlessly, resized on the fly, and integrated directly with STL algorithms like std::sort.Key Operations: * Access: v[i] $\rightarrow \mathcal{O}(1)$Insert/Delete at end: v.push_back(), v.pop_back() $\rightarrow \mathcal{O}(1)$ amortizedInsert/Delete in middle: $\rightarrow \mathcal{O}(N)$std::deque (Double-...
elements (multiset) in a strictly sorted order using a Balanced Binary Search
Tree (Red-Black Tree).Why
99.
Teamscode Spring 2023 Editorial This is the editorial for a recent contest [Teamscode](https://www.teamscode.org/). The problems are open for upsolving on [this gym](https://codeforces.me/gym/104287). Problems were prepared by [user:oursaco,2023-04-06], [user:dutin,2023-04-06], [user:thehunterjames,2023-04-06], [user:Bossologist,2023-04-06], [user:Esomer,2023-04-06], and me.
### [A. What do you do when the contest starts? Are you busy? Will you solve Bingo?](https://codeforces.me/gym/104287/problem/A)
<spoiler summary = "Editorial">
<spoiler summary = "Are you busy?">
1. WorldEnd/SukaSuka
2. Bocchi the Rock
</spoiler>
<spoiler summary = "No Sweep">
1. Thomas
</spoiler>
<spoiler summary = "Multiplication Table">
1. Lycoris Recoil
</spoiler>
<spoiler summary = "Greatest Common Multiple">
1. Bokuben
</spoiler>
<spoiler summary = "A Certain Scientific Tree Problem">
1. A Certain Scientific Railgun
</spoiler>
<spoiler summary = "Two and Three">
1. Quintessential Quintluplets...
order of the fog altitude, we can maintain a BIT such that all points below the
fog have a value of 1
Tutorial of Teamscode Spring 2023 Contest
100.
Codeforces Round 1122 (Div. 3) Editorial Thanks for participating in [contest:2266]!
<spoiler summary="Rate the contest!">
<spoiler summary="Quality">
-
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:2266A]
<spoiler summary="Hint">
How many participants can possibly have solved all three problems?
</spoiler>
<spoiler summary="Solution">
At most $\min(a_1,a_2,a_3)$ participants could have solved all three problems. This is achievable by making the same $\min(a_1,a_2,a_3)$ participants solve every problem, then distributing the remaining solves arbitrarily.
Thus, the answer is $n-\min(a_1,a_2,a_3)$.
...
order from left to right and repeatedly moving the required section into the
next position. Suppose
Tutorial of Codeforces Round 1122 (Div. 3)
101.
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...
$a$ and $b$ are ordered in $t$, **exactly $1$** inversion will be contributed
to $\Sigma$. Therefore
Tutorial of HPI 2026 Advanced
Tutorial of HPI 2026 Novice
102.
[AtCoder] Unofficial HHKB Programming Contest 2020 Editorial ### [A – Keyboard](https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_a)
<spoiler>
Basically, just do what it says in the problem statement. The function to turn a character uppercase is `std::toupper(t)` in C++, `Character.toUpperCase(t)` in Java, `t.toUpperCase()` in Kotlin, or `t.upper()` in Python.
</spoiler>
### [B – Futon](https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_b)
<spoiler>
Iterate through every row and column. If the current square is `.`, look at the neighbor to the right, if it's also `.`, increment the answer. Likewise the neighbor downward. There is no need to look leftward or upward as those positions would already have been counted.
</spoiler>
### [C – Neq Min](https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_c)
<spoiler>
Initiate an array of booleans indexed over $[0, 1 + \max p]$. Maintain a pointer $j$ starting at index $0$.
Iterate through $p$. In each iteration, mark the corresponding index as "true", then use ...
intervals in non-increasing (descending) order of $R_i$ (henceforth we assume
$R_i \geq R_{i+1}$ for
103.
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...
bottom in order, starting from zero. The $i$th block will have the form $4i +
0$ $4i + 1$ $4i
Tutorial of Codeforces Round 857 (Div. 1)
104.
Teamscode Summer 2023 Editorial This is the editorial for the recent Teamscode Summer 2023 contest, and the problems are open for upsolving on this [gym](https://codeforces.me/gym/104520). Problems were prepared by [user:oursaco,2023-08-22], [user:dutin,2023-08-22], [user:thehunterjames,2023-08-22], [user:Bossologist,2023-08-22], [user:Esomer,2023-08-22], [user:danx,2023-08-22], [user:codicon,2023-08-22], [user:willy108,2023-08-22], and [user:hyforces,2023-08-22]. The problems were tested by [user:omeganot,2023-08-22], [user:codicon,2023-08-22], [user:cry,2023-08-22], [user:skye_,2023-08-22], [user:Litusiano_,2023-08-22], and [user:apple_method,2023-08-22].
### [A. Who is cooking?](https://codeforces.me/gym/104520/problem/A)
<spoiler summary="Solution">
danx
</spoiler>
<spoiler summary="Code">
~~~~~
print("Esomer")
~~~~~
</spoiler>
### [B. Restaurant Sorting](https://codeforces.me/gym/104520/problem/B)
<spoiler summary="Solution">
The answer is $n - $ the longest prefix of the array where a...
substring lexicographically greater than the string described above. Then, in
order to preserve the
Tutorial of Teamscode Summer 2023 Contest
105.
HELP please ... Problems with STL::Multiset I'm trying to solve a problem using Union Find, for storing Connected Components of a graph, and a Multiset for ordering the Components' Weights ... but i'm getting "SIGSECV ( Abort Called ) "... here is my code [Link](http://pastebin.com/DKX3vYe4)
HELP please ... Problems with STL::Multiset, Multiset for ordering the Components' Weights ... but i'm getting "SIGSECV (
Abort Called
106.
Distinct GCDs (Hard) - Proof that the construction is optimal Why the construction is optimal
==================
Welcome to my first blogpost :)
This problem https://codeforces.me/contest/2158/problem/F2 was one of the hardest problems I've tried to understand. The official editorial gives a very nice construction but, coming from an analysis/pure math background, for the sake of intuition I sought a proof of (a) a lower bound on the number of distinct values we may use, and (b) why the $10 \times 10$ construction is in fact optimal for all $n \le 5000$.
As such, this post is the same solution as the editorial written in a more "theorem" style. To summarize, I derive the extremal function $g(k)$ = maximum number of distinct adjacent gcds you can get if you use only $k$ distinct values, show that the construction exactly matches that bound, then prove the gcd-uniqueness of the $10 \times 10$ grid in a bit more detail.
First glance
==============================================
At first sight, the problem feels impossible for thre...
^{18}$. In order to understand this problem and solve it we may (you guessed
it) decompose into two
107.
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...
$. That is, if we consider $[5, 6, 7, 8]$ modulo $2$, we obtain the multiset
$\{1, 0, 1, 0
Tutorial of Good Bye 2022: 2023 is NEAR
108.
Codeforces Round 973 (Div. 2) Editorial [2013A — Zhan's Blender](https://codeforces.me/contest/2013/problem/A)
First to solve: [user:rob00,2024-09-21]
<spoiler summary="Solution">
Let's consider two cases:
- If $ x \geq y $. In this case, the blender will mix $ \min(y, c) $ fruits every second (where $ c $ is the number of unmixed fruits). Therefore, the answer will be $ \lceil \frac{n}{y} \rceil $.
- If $ x < y $. Here, the blender will mix $ \min(x, c) $ fruits every second. In this case, the answer will be $ \lceil \frac{n}{x} \rceil $, similarly.
Thus, the final answer is $ \lceil \frac{n}{\min(x, y)} \rceil $.
</spoiler>
<spoiler summary="Code">
```
#include <iostream>
using namespace std;
int main(){
int t = 1;
cin >> t;
while(t--){
int n, x, y;
cin >> n >> x >> y;
x = min(x, y);
cout << (n + x - 1) / x << endl;
}
}
```
</spoiler>
[2013B — Battle For Survive](https://codeforces.me/contest/2013/problem/B)
First to ...
order. Let $ A $ be the minimum possible GCD for the current prefix of
Tutorial of Codeforces Round 973 (Div. 2)
109.
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...
assumed that the interval endpoints are distinct for simplicity. If they are
not, we canorder the
Tutorial of Codeforces Round 979 (Div. 2)
110.
CodePlus Long 2024 Editorial [contest:540279]
==================
[problem: 540279A]
<spoiler summary="Tutorial">
The problem boils down to finding the number of coordinates between $A_i$ and $A_{i+1}$ which are divisible by $k$ .Where $i$ is even considering $0$ based indexing.
</spoiler>
<spoiler summary="Code">
```c++
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll floor(ll x, ll m) {
ll r = (x % m + m) % m;
return (x - r) / m;
}
int main() {
int t;
cin >> t;
while (t--)
{
ll n, k, ans = 0;
cin >> n >> k;
vector<ll>a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < n; i += 2)
{
ans += floor(a[i + 1] - 1, k) - floor(a[i] - 1, k);
}
cout << ans << endl;
}
}
```
</spoiler>
[problem:540279B]
<spoiler summary="Hint ">
This is a modified version of a popular problem $Dungeon$ $Game$.Try to solve...
void _print(multiset v); template void _print(pair p) { cerr
111.
CodePlus Long 2025 Editorial Welcome to the Editorial of CodelPlus Long 2025.
CodePlus Long Contest is a 2-day coding competition featuring a mix of educational and challenging problems. It allows participants to learn, practice, and compete to enhance their problem-solving skills.
You can attempt the contest [here](https://codeforces.me/contestInvitation/940e1bd9749a95d26fbca52cd74512d1b505f65e).
(Many Original and Challenging problems, you can give it a try :) )
The problems were authored and prepared by [user:pranavsingh0111,2025-10-14],[user:Sarvesh0955,2025-10-16],[user:Ragnar21,2025-10-16],[user:rndascode,2025-10-16],[user:ankitgarg2105,2025-5-14],[user:utk_09,2025-8-14].
We would also like to thank, [user:Rishabh_king,2025-10-16] for testing.
Author : [user:Sarvesh0955,2025-10-14]
<spoiler summary="Problem A">
This problem can be solved in several ways; one approach is as follows:
---
### Graph Construction
Construct a new graph ( **nodes n+1 to 2n** ) where all edge weights ar...
, class V> void _print(map v); template void _print(multiset v); template
112.
Codeforces Round 908 (Div. 1, Div, 2) Editorial I'm very very sorry to all Div2 participants for unclearness in statement of A, and not including notes in the statement of B, hope it didnt ruined a contest for you. Thank you all for participating, I hope you enjoyed non-empty subset of the problems! You can rate the problems of the round in the corresponding spoilers.
[problem:1894A]<br>
<div class="spoiler"> <b class="spoiler-title">Hint 1</b> <div class="spoiler-content" style="display: none;">
You can always bruteforce $X$ and $Y$, and check every pair of $(X, Y)$ separately, but there is a tRiCkY solution that involves zero implementation.
</div></div>
<div class="spoiler"> <b class="spoiler-title">Hint 2</b> <div class="spoiler-content" style="display: none;">
Have you ever watched a game of tennis, a game of volleyball, e.t.c?
</div></div>
<div class="spoiler"> <b class="spoiler-title">Tutorial</b> <div class="spoiler-content" style="display: none;">
[tutorial:1894A]</div></div>
<spoiler summary="Solution">...
answer: $LIS(a)+1$, you can insert $b$'s in decreasing order anywhere. When
you can't achieve $LIS
Tutorial of Codeforces Round 908 (Div. 1)
Tutorial of Codeforces Round 908 (Div. 2)
113.
A2SV Contest #26 Editorial [Here](https://codeforces.me/contestInvitation/aa6037d6b47fcf6618fbb56b120dca0f7bc735b8) is the link to the contest. All problems are from Codeforces' problem set
[A.Maxim vs. Yogurt: The Great Discount Battle](https://codeforces.me/gym/629689/problem/A)
<spoiler summary="Solution">
We want the **minimum cost** to buy exactly $n$ yogurts when:
- A single yogurt costs $a$ burles.
- A promotion lets you buy **two yogurts for $b$** burles.
You may mix buying single yogurts and buying pairs. Let's reason through the options, compare costs, and derive a compact formula.
---
#### **_Key Observations_**
1. **Always-available baseline:**
- You can always buy all yogurts one-by-one. That gives the cost.
- `Cost = n.a`
2. **When is the promotion useful?**
- Buying two yogurts with the promotion costs $b$. Compare this to buying those two separately:$2a$.
- If $b \geq 2a$, the promotion **is not beneficial** (or is equal). Then buying every ...
desired multiset equality. --- #### **Summary of Approach** 1. Precompute
**prefix sums** for
114.
A2SV G4 — Contest #10 #### [A) XOR MIXUP](https://codeforces.me/gym/436344/problem/A)
<spoiler summary="Approach">
Any element of the array works. Why?
Given an array a, b, c, d, we need to find a number in the array such that the xor of the rest of the elements equals this number. The array's overall xor is zero. So, any element from the array can be selected as the answer since the xor of a number with itself is zero. Therefore, a, b, c, or d can be chosen as the answer.
</spoiler>
<spoiler summary="Code">
~~~~~
def solve():
length = int(input())
nums = list(map(int, input().split()))
return nums[0]
def main():
num_tests = int(input())
for _ in range(num_tests):
print(solve())
main()
~~~~~
</spoiler>
#### [B) Raising Bacteria](https://codeforces.me/gym/436344/problem/B)
<spoiler summary="Approach">
To determine the minimum number of bacteria needed to achieve exactly x bacteria in the box at some point, we ...
://codeforces.com/gym/436344/problem/D) In order for the given
115.
MemSQL start[c]up Round 2 -- Editorial This is the Editorial for [contest:326] and [contest:335]. Congratulations [user:RAD,2013-08-05] for online round winner and [user:Petr,2013-08-05] for onsite and overall score winner!
This editorial is written jointly by the contest's coordinators (i.e., MemSQL engineers).
[problem:335A] -- [user:SkidanovAlex,2013-08-05]
Reference solution: [user:nwin,2013-08-05]'s [submission:4222182]
Instead of calculating the smallest possible number of sheets given a fixed $n$, let us instead try to compute the smallest possible value of $n$ given a fixed number of sheets. Let $k$ denote the number of sheets. If a particular letter appears $p$ times in $s$, then it must appear at least $ceil(p/k)$ times in the sheet. Thus we can compute the smallest possible value of $n$ by summing $ceil(p/k)$ over all letters. Now the original problem can be solved using binary search on $k$ (or brute force, since the constraints were small enough).
[problem:335B] -- [user:SkidanovAlex,2013-08-...
element in sorted order in constant time. Skiplist is different from any tree
structures because it has a
Tutorial of MemSQL start[c]up Round 2
Tutorial of MemSQL start[c]up Round 2 - online version
116.
[Editorial] 0xPPL AlgoBee II By Scaler School Of Technology <spoiler summary="Problem A - Number Theory">
We can utilize the formula for the sum of a geometric progression to compute the sum of divisors raised to the power 69 efficiently.
$$
\left(1 + p_1^{69} + p_1^{69*2} + \ldots + p_1^{69*e_1}\right) \times \left(1 + p_2^{69} + p_2^{69*2} + \ldots + p_2^{69*e_2}\right) \times \ldots \times \left(1 + p_n^{69} + p_n^{69*2} + \ldots + p_n^{69*e_n}\right)
$$
When computing the sum of divisors of a number, each divisor contributes to the total sum according to its power. For a prime factor $x$ raised to the power $y$, the divisors are of the form $x^0, x^1, x^2, \ldots, x^y$. Notice that these are in a geometric progression.
The formula for the sum of a geometric progression is:
$$S = \frac{a \cdot (r^n - 1)}{r - 1}$$
<ul>
<li><b>S</b>: The sum of the geometric progression.</li>
<li><b>a</b>: The first term of the progression (in this case, 1).</li>
<li><b>r</b>: The common ratio, which is $x^{69}$.</li>
<li>...
#define si set #define msi multiset #define maxn 1000005
117.
Topics Problems Good Day to you!
While a lot of us, when he begins to start competitive programming he found difficult to found problems on some topics in the beginning to practice of it, and same thing for a lot of ICPC Communites that they have started.
These are some topic not advanced and videos, problems and articles on them.
<br>
<spoiler summary="Prefix Sum & Frequency Array">
[Wonderful Coloring](https://codeforces.me/contest/1551/problem/B1)
[Do Not Be Distracted](https://codeforces.me/contest/1520/problem/A)
[Letter](https://codeforces.me/problemset/problem/43/B)
[Pangram](https://codeforces.me/problemset/problem/520/A)
[Andryusha and Socks](https://codeforces.me/contest/782/problem/A)
[Count Numbers](https://codeforces.me/group/c3FDl9EUi9/contest/262795/problem/A)
[Count Characters](https://codeforces.me/group/c3FDl9EUi9/contest/262795/problem/B)
[Range Sum Query](https://codeforces.me/group/c3FDl9EUi9/contest/262795/problem/E)
[Count a's](https...
=ApnaCollege) (Multiset) [Adel
Nassim](https://www.youtube.com/watch?v=PPFhtX23oXc&list
118.
AlgoUtsav 2024 | Editorial 
We'd like to thank you all for participating in the contest and hope you enjoyed it. Hope to see you again next year!
The tutorial for problem B will be added soon.
---
<h2>[problem:509001A]</h2>
Idea: [user:ninjamayank,2024-03-19]
<spoiler summary="Solution">
The solution to this problem required **binary search on answer with 2D prefix sum**. First we binary search on the threshold. For a chosen threshold we create a new grid with values greater than or equal to $k$, set to $1$, and others to $0$. Next, we make a 2D prefix grid of size $n$ x $n$ for the new matrix containing values $0$ and $1$. Now we iterate over all possible $k$ x $k$ grids and get the sum using the prefix matrix. If the sum equals $k^2$ the chosen threshold is valid. We can continue the search for the maximum threshold further according to the validity of the chosen one.
The overall time-complexity is $O(n^2...
points and print them in sorted order. The second part asks for the minimum
difference between
119.
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]...
the multiset of $b$, we need to "lose" the element $a_l$ and "gain" the
element $a_r$. At first
120.
How to maintain elements in sorted order like multiset in python efficiently Please share any resources for the title. I’m writing this because I couldn’t solve yesterday’s Problem C as SortedList wasn’t available in the Python compilers.
How to maintain elements in sorted order like multiset in python efficiently
121.
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...
the number of permutations where $x_a, x_{a-1}, …, x_{0}$ appear from left to
right in thisorder
Tutorial of Valentines Day Contest 2020
122.
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...
) //Partition function (raw) http://www.spoj.com/problems/GOODB/ (2) //Easy
(NICE): Choose [order
123.
Minimum value for all continuous ranges of fixed size in linear complexity <spoiler summary="For not c++ users">
In this blog I refer to names of some data-structures in c++,
So here is the list of names that seem not clear to me
Set — Red-black tree
https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
Priority queue — Binary heap
https://en.wikipedia.org/wiki/Binary_heap
Deque — Double-ended queue
https://en.wikipedia.org/wiki/Double-ended_queue
</spoiler>
###Initial problem
Statement:
Let $A$ be an array $A_0,A_1,\ldots,A_{n-1}$ of the size $n$.
Find the maximum sum of continuous subarray(window) of the size $k$ with possibility to ignore one of the elements.
#####Naive $O(n\cdot k)$ solution:
Let's denote
$sums[i]=A_{i-k+1}+A_{i-k+2}+\ldots+A_i$
$minimum[i]=min(A_{i-k+1},A_{i-k+2},\ldots,A_i , 0)$
(if minimum is positive, we will use 0 instead)
For $i < k - 1, minimum[i]=sums[i]=0$
Key idea: The answer is maximum of $sums[i] - minimum[i]$, for every $k-1 \leq i < N$
<spoiler summar...
($set$) (in our case multiset)! Although hidden constants of sets are way
bigger than priority queue
124.
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...
element in the subtree of $x$ (excluding $x$ itself). Since $n$ can never be
removed, inorder for $x
125.
[Replay] BUBT Intra University Programming Contest Summer 2021 Hello Programmers,
A **replay of BUBT Intra University Programming Contest Summer 2021** will be held tomorrow. You are all invited to attend this contest. The problem sets are prepared for beginners and intermediates. We hope you’ll like the problems. Do participate in the replay contest and boost your problem solving skills. Our online judge platform is codeto.win.
**This contest is open for all.**
Contest Link: https://codeto.win/contest/2016
Contest Date: **19 November 2021**
Contest Time: **3 PM**
Contest Duration: **5 Hours**
Editorial:
-------------------
### [MINIMUM DIFFERENCE](https://codeto.win/contest/2016/problem/E)
**Problem Setter:** ALL MOON TASIR
**Tester :** Jahin, Rifatul Islam & Khairul Anam Mubin
**Problem Type:** Combinatorics + STL
**Hints:** Learn stl function next_permutation.
**Approach:** Let's try all possible ways to rearrange digits in the numbers and check the difference between maximum and minimum number.
**Au...
finding maximum numbers in an array takes some bad time complexity so we can
usemultiset / map to store
126.
ICPC de Tryst 2025 Editorial I hope you liked the contest. We apologize for the inconvenience caused due to the problem $I$.
### [problem:595453A]
---
**Author:** [user:Proelectro444,2025-03-13]
<spoiler summary="Solution">
#### Inspiration
[https://codeforces.me/problemset/problem/1748/b](https://codeforces.me/problemset/problem/1748/b)
**Why the Classic Two-Pointer Technique Fails:**
The classic two-pointer technique relies on a monotonicity property; that is, if an array is diverse then every subarray of it should also be diverse, or if an array is not diverse then none of its subarrays are diverse. However, the diverse property does not behave monotonically, so a straightforward application of the two-pointer method does not work.
Instead, we modify the approach and compute the count in $\max(a)$ steps. In the $m^\text{th}$ iteration, we compute the number of diverse subarrays that have exactly $m$ distinct elements. Notice that if a subarray has exactly $m$ distinct elements, then ...
in order to be diverse every element in the subarray must appear at most $m$
times
127.
Codeforces Round 921 (Div. 1, Div. 2) Editorial I hope you enjoyed the round. Here is the editorial. Do provide your feedback on each problem so that we can improve upon them the next time.
#### [2A. We Got Everything Covered!](https://codeforces.me/contest/1925/problem/A)
Author: [user:JaySharma1048576,2024-01-27]
<spoiler summary="Hint 1">
The smallest length for such a string is $n\cdot k$.
</spoiler>
<spoiler summary="Tutorial">
The smallest length possible for such a string is $n\cdot k$.
<spoiler summary="Why?">
To have the string $\texttt{aaa}\ldots\texttt{a}$ as a subsequence, you need to have at least $n$ characters in the string as $\texttt{a}$. Similarly for all $k$ different characters. So, that gives a total length of at least $n\cdot k$.
</spoiler>
In fact, it is always possible to construct a string of length $n\cdot k$ that satisfies this property. One such string is $(a_1a_2a_3\ldots a_k)(a_1a_2a_3\ldots a_k)(a_1a_2a_3\ldots a_k)\ldots n$ times where $a_i$ is the $i^{th}$ letter of English alph...
(x) set #define US(x) unordered_set #define OMS(x) multiset #define UMS(x
Tutorial of Codeforces Round 921 (Div. 1)
Tutorial of Codeforces Round 921 (Div. 2)
128.
Code League — National Competitive Programming Contest — Round 2 — Editorial Here is the link to the contest: [Link](https://codeforces.me/contestInvitation/f528fcc29732183e36f82a0adfdc6dbac0743f3f)
### [A. Free Coupon](https://codeforces.me/gym/690685/problem/A)
<spoiler summary="Rate the Problem">
- **How good is this problem?**
- Very Good
- Good
- Bad
- Very Bad
- **How hard is this problem?**
- Very Easy
- Easy
- Hard
- Very Hard
</spoiler>
<spoiler summary="Hint">
Which items should be taken using coupons?
<spoiler summary="Answer">
Since a coupon can be used on any item regardless of its price, it is always best to use coupons on the most expensive items. This allows us to spend our coins only on cheaper items.
</spoiler>
</spoiler>
<spoiler summary="Solution">
The problem asks us to find the maximum number of items Abenezer can obtain given $k$ coins, with the offer that every $b$ items bought with coins yiel...
free. Therefore, our strategy is simple: 1. Sort the items by price in
ascendingorder. 2
129.
Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022 Editorial We'd like to thank you all for participating in the contest, and hope you enjoyed it. Hope to see you again next year!
<s>The editorial for problem F will be added soon.</s> It is now added.
---
<h2>[problem:1726A]</h2>
Idea: [user:anubhavdhar,2022-09-06] <br>
Editorial: [user:anubhavdhar,2022-09-06]
<spoiler summary="Hint 1">
Which subsegments are relevant?
</spoiler>
<spoiler summary="Hint 2">
$a_n$ and $a_1$ can be taken up only by _some_ combination of elements, not all.
</spoiler>
<spoiler summary="Solution">
[tutorial:1726A]
</spoiler>
<spoiler summary="Implementation">
<spoiler summary="C++">
~~~~~
#include<bits/stdc++.h>
using namespace std;
inline void test_case(){
int N;
cin >> N;
int A[N];
int ans = -1000000007;
for(int i = 0; i < N; ++i){
cin >> A[i];
}
for(int i = 0; i < N; ++i){
ans = max(ans, A[(i - 1 + N) % N] - A[i]);
}
for(int i = 1; i < N; ++i){
ans = max(ans, A[i] - A[0]);
}
...
light to turn green. We can achieve this with a multiset storing all currently
visible endpoints, and
130.
Invitation to Insomnia Qualifier 2022 Hello Codeforces!
Computer Club, MNNIT Allahabad, India is glad to invite you to the annual programming competition of MNNIT, INSOMNIA, which is an ACM-ICPC style team programming contest of 2.5 hours duration held on Codeforces during its annual technical fest Avishkar. The team can consist up to 3 members.
<b>Contest Details: </b>
<ol>
<li> Qualifiers: </li>
<ul>
<li> Start Time: Wednesday, November 9, 21:00 IST</li>
<li> Duration: 2.5 hours</li>
</ul>
<li> Finals: </li>
<ul>
<li> Start Time: Sunday, November 13, 12:00 IST</li>
<li> Duration: 2.5 hours</li>
</ul>
</ol>
**Top 25** global teams, and **Top 25** teams from MNNIT (based on the result of Qualifiers) will qualify to the Finals. The prize distribution for global teams is mentioned below: <br>
Teams consisting of MNNIT students only will be eligible for a seperate prize pool.
Register your team for the qualifiers here: https://forms.gle/BKsbKfoGzSxC394R8 <br>...
. But keeping $left[i]$ and $right[i]$ for each node would be too much memory,
because there areorder
131.
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...
} \frac 1 {2^i}$. And this method can be proven to be optimal, if we find
anothermultiset $T
Tutorial of Codeforces Round 901 (Div. 1)
Tutorial of Codeforces Round 901 (Div. 2)
132.
Editorial For CodeRed 2024 Greetings everyone! We hope you enjoyed the problems. Here is the editorial of the [contest](https://codeforces.me/contests/514183). Sorry for delay!.
###[A — Construct a subsequence](https://codeforces.me/gym/514183/problem/A)
<spoiler summary="Hint">
Check if $i$-th bit of the cost can be $0$?
</spoiler>
<spoiler summary="Tutorial">
Let's say the cost $2^{30} - 1$, we will try to set the $i$-th bit of the cost to $0$ while iterating $i$ from $29$ to $0$.
<spoiler summary="Why iterating in reverse? ">
We are iterating in reverse because if we can construct a subsequence with cost that has $i$-th bit $0$, then even if all bits $j$, $j < i$ are $1$ it would still have less cost.
</spoiler>
You can pick an index $i$ in your subsequence if $a_i$ is a sub-mask of the cost you are currently constructing.
Now greedily club indices that have distance $\leq k$ between them. Note that if you can make a subsequence we length $l'$, $(l' \gt l)$, you also ma...
,multiset>>>m2; void query1(int value){ if(m2.count(value)==0
133.
Teamscode Spring 2024 Contest Official Editorial Sorry for the long wait. These problems were brought to you by [user:esomer,2024-04-05], [user:danx,2024-04-05], [user:dutin,2024-04-05], [user:jay_jayjay,2024-04-05], [user:oursaco,2024-04-05], [user:superhelen,2024-04-05], [user:thehunterjames,2024-04-05], [user:willy108,2024-04-05], and [user:yash_9a3b,2024-04-05]. Also, massive thanks to [user:omeganot,2024-04-05] for his [unofficial editorial](https://codeforces.me/blog/omeganot) (which was posted a lot sooner than ours).
[Novice A/](https://codeforces.me/gym/105066/problem/A)[Advanced A: It's Time to Submit](https://codeforces.me/gym/105067/problem/A)
==================
<spoiler summary="Solution">
Both "YES" and "NO" are consistent answer (as long as exactly one of them is the answer).
If you print "YES" and get AC, you are getting AC by printing the sample output.
If you print "NO" and get AC, you are getting AC by not printing the sample output.
Never assume just because the carrot is big ... the sample out...
apply the swaps in reverse order. This is because if we apply the swaps (in
the correctorder) from
Tutorial of Teamscode Spring 2024 (Novice Division)
Announcement of Teamscode Spring 2024 (Advanced Division)
134.
Codeforces Round 1082 (Div. 2)A,B,C1,C2,D,E,F,G1,G2 personal solution # A. Parkour Design
**Category:** Mathematics
## Logic
By plotting the points on scratch paper, we can observe a very clear pattern: all reachable points lie on specific line segments with a slope of $-1$ . These line segments belong to lines that can be expressed as:
$$ y = -x + k , \text{ where } k \pmod{3} = 0 , k \in \mathbb{Z} $$
To restrict the lines to segments, we also need to apply constraints on $x$ :
$$ x \in [ 2k , 4k ] $$
We can directly check these conditions.
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
void solve() {
int x, y;cin >> x >> y;
if ((x + y) % 3 != 0)cout << "NO\n";
else {
int k = (x + y) / 3;
if (x >= 2 * k && x <= 4 * k)cout << "YES\n";
else cout << "NO\n";
}
...
update the segments and the contribution $ans_{k}$ . We also use a `multiset
len` to track the
135.
Daily Diary (Competitive Coding in Summers) I realised that there is only one way improve one's skill, and that is through practice. So I decided to practice more topics and more problems on codeforces and different judges. This is simply a daily record for what I did through my vacation.
I also want to tell you about **stopstalk.com** . It is a good site to make and keep you daily coding record.
##**16 MAY 2017**
##### **Problems Solved** -
###### 1. http://codeforces.me/problemset/problem/535/D
This was a simple problem and it used Z function for prefix length calculation
###### **solution link** — http://codeforces.me/contest/535/submission/27152004
###### 2. http://codeforces.me/problemset/problem/551/B
Although the problem was simple, I had some trouble in understanding the language of the problem. It took time more than required.
###### **solution link** — http://codeforces.me/contest/551/submission/27160921
<br>
##### **Participated Contest** -
I participated in a v...
insertion in beginning, I used level order traversal to insure that the parent
are inserted before the
136.
Codeforces Round 1033 (Div. 2) and CodeNite 2025 Editorial Thanks for participating in our CodeNite 2025.
####[2120A — Square of Rectangles](https://codeforces.me/contest/2120/problem/A)
Idea: [user:aryansanghi,2025-06-11] Solution: [user:aryansanghi,2025-06-11] Prepared by: [user:aryansanghi,2025-06-11]
<spoiler summary="Hint">
There are only two possible ways to arrange rectangles into a square if possible.
</spoiler>
<spoiler summary="Solution">
The only cases possible to arrange rectangles into a square are:
1. All three rectangles are put side by side, i.e. $l_1=l_2=l_3=b_1+b_2+b_3$ or $b_1=b_2=b_3=l_1+l_2+l_3$.
2. Rectangles $2$ and $3$ are side by side with rectangle $1$ above it, i.e. $l_1+l_2=l_1+l_3=b_1=b_2+b_3$ or $b_1+b_2=b_1+b_3=l_1=l_2+l_3$.
Check both these cases, and if either is true, output YES, otherwise NO. Complexity is $O(1)$ per test.
</spoiler>
<spoiler summary="Code - aryansanghi">
~~~~
//Written By Aryan Sanghi
#include<bits/stdc++.h>
using namespace std;
#define ll long...
multiset of $n$ non-negative integers that sum to $p$. $\text{Greedy:}$ Loop
$j$ from $n - 1$ to $0
Tutorial of Codeforces Round 1033 (Div. 2) and CodeNite 2025
137.
DesCode 4.0 ## Details
**Date:** 29th January 2022
**Time:** 03:00 pm to 06:00 pm
**Platform:** codeforces
**By:** The Society of Coders, IIIT Naya Raipur
**For:** BTech Students
**Contest Link:** [DesCode 4.0](https://codeforces.me/contestInvitation/8bab3f0bf9445dcdd6c5eaa5618bc7380e5ed685)
We would like to express our great gratitude to:
- [user:monkedluffy,2022-01-29], [user:sonicBoom,2022-01-29], [user:shinigami_09,2022-01-29] and [user:momotaroUWU,2022-01-29] for the coordination of the round and preparing problems.
- [user:Yoks1729-,2022-01-29] and [user:sandesh_04_06,2022-01-29] for testing the round and providing useful feedback.
- [user:MikeMirzayanov,2022-01-29] for cool platforms Codeforces and Polygon.
This contest had 3 hours to solve 8 problems.
## Editorial
Thanks for participating, hope you enjoyed the problems!
Please do not hesitate to provide feedback, so we can improve in setting problems next time.
#### Problem — A : [Majnu Ki M...
(map v); template void _print(multiset v); template void
138.
Editorial [GYM] 2018 BACS Contest replay [problem:101864A]
Setter: [user:ISwearItIsMyLastContest,2018-08-10]
Alternate Writer: [user:prophet_ov_darkness,2018-08-10], [user:s_h_shahin,2018-08-10]
<spoiler summary="Editorial">
This problem actually reflect the [josephus problem](https://en.wikipedia.org/wiki/Josephus_problem).
The main part of this problem is to find Number of possible Y such that **josephus(Y,2) = X** .
After finding this rest part is obvious calculation.
Let’s see first few values of josephus(i,2): 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15
We can see that there is a nice pattern here. **josephus(n,2)** is an increasing odd sequence that restarts with **josephus(n,2) = 1** whenever the index **n** is a power of 2.
First we will find minimum value of p such that **josephus(p,2) = X**. we can do this in **O(log n)** , because for every **q>0** **josephus(2^q-1,2) = 2q^-1** and **josephus(2^q,2) = 1**. So we can run loop through q >= 0 and find highest value of **q** such that **josephus(2...
[MAXN],subSize[MAXN] , height[MAXN]; multiset < int > sums; void Clear(){
sums.clear
Tutorial of 2018 BACS Contest Replay
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/26/2026 11:18:49 (g2).
Desktop version, switch to mobile version.
Supported by
