[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...

Full text and comments »

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...

Full text and comments »

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...

Full text and comments »

[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...

Full text and comments »

[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 &mdash; 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 &mdash; 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...

Full text and comments »

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...

Full text and comments »

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"...

Full text and comments »

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 &mdash; NO (because otherwise $a_{n}$ is not smaller than sum of the neighbors). We claim, that in all other cases answer is &mdash; 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...

Full text and comments »

Hello 2026 Editorial We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated! <spoiler summary="Rate The Contest!"> - Great contest - Good contest - Average contest - Bad contest </spoiler> ## [2183A &mdash; Binary Array Game](https://codeforces.me/contest/2183/problem/A) Idea & Preparation: [user:wangmarui,2025-12-23] <spoiler summary="Rate The Problem!"> - Good Problem - Okay Problem - Bad Problem - Didn't Solve </spoiler> <spoiler summary="Hint 1"> If the sequence $a$ consists entirely of $1$ s, what will Alice do? </spoiler> <spoiler summary="Hint 2"> Consider discussing the values of $a_1$ and $a_n$. </spoiler> <spoiler summary="Solution"> First, if the entire sequence consists of $1$ s, Alice wins immediately by operating on the whole sequen...

Full text and comments »

Organized C++ Ordered Set and Multiset Hello everyone! After a long break from competitive programming, I’m back with something I wanted to have ready in my template: an ordered set and multiset with a clean member-function interface. One of the main reasons I created this project was to support the competitive programming community at Latakia University (Previously Tishreen University). I wanted contestants to have a reusable ordered-set and multiset template they can keep in their own templates and adapt to their problems. The project is **Organized C++ Ordered Set**. You can write `ordered_set<int>` or `ordered_multiset<int>`, access sorted ranks with `s[i]`, and use normal-looking bounds and erasure functions. It uses GNU PBDS with a strict comparator, including when duplicates are present. [Code, examples, and complete API reference](https://github.com/Tareq-Ali-1998/Organized-CPP-Ordered-Set) [GitLab mirror](https://gitlab.com/tareqali591998/organized-cpp-ordered-set) ## Usage first ```c++ ordere...

Full text and comments »

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...

Full text and comments »

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> ...

Full text and comments »

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 &mdash; Concert Tickets (for those with no CSES account, see [here](https://www.technicalkeeda.in/2020/10/concert-ti...

Full text and comments »

AtCoder Beginner Contest 136 English Solutions #A &mdash; 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 &mdash; 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. ...

Full text and comments »

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; } } ``` </...

Full text and comments »

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 &#128153;. #### [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...

Full text and comments »

Как тренироваться: почему для школьных олимпиад не надо учить сложные темы и решать гробы Всем доброго времени суток! На этот пост меня вдохновил [user:Wind_Eagle,2022-04-05] своим [постом](https://codeforces.me/blog/entry/101549). Этот блог является заключительным в цикле [челлендж::поготовься к респе](https://codeforces.me/blog/entry/99856). Советую перед прочтением сначала прочитать его, а также вышеописанный блог, так как данный наследуется от них. Для начала подведу итоги челленджа. Он оказался скорее неуспешным, чем успешным. Единственное, что я получил от него &mdash; опыт, который будет полезен в будущем. Итак, итоги: - Взять диплом на республике. Не выполнил, остался без диплома. Нарешал очень плохо, наконец понял, что главная проблема не столько даже лежит в программировании, сколько в психологии. Заметил очень нехорошую особенность: пришёл как на первый, так и на второй тур, все 5 часов не мог сосредоточиться, чего-то боялся (сам не знаю, чего). Из-за этого я фактически не думал, а скорее просто выписывал на листочке что-то и пытался просто реализовать...

Full text and comments »

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"> ...

Full text and comments »

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...

Full text and comments »

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...

Full text and comments »

Codeforces Round 1129 (Div. 2) Editorial Thank you for participating in the round! <spoiler summary="Fun facts"> - D1 was originally proposed as B. - This round originally had a problem called "Token Moving", but we removed it during the testing phase. </spoiler> <spoiler summary="Rate this round"> - Amazing: - Good: - OK: - Bad: - Terrible: </spoiler> [problem:2277A] Author: [user:Getaway_Car,2026-10-24] <spoiler summary="Hints"> <spoiler summary="Hint 1"> Check the values $0, 1, 2, \ldots$ in increasing order. What is needed for $i$ to be the maximum of some multiset? </spoiler> <spoiler summary="Hint 2"> A multiset with maximum $i$ needs one element equal to $i$ and $k - 1$ other elements not exceeding $i$. An element that is not used now can still be used for any larger value, so keep track of how many such elements are available. </spoiler> </spoiler> <spoiler summary="Tutorial"> To maximize ...

Full text and comments »

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 ...

Full text and comments »

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`. &mdash; O(log n) - `find_by_order(k)`: Returns the iterator for the `k`th element (use `k = 0` for the first element). &mdash; O(log n)...

Full text and comments »

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 ...

Full text and comments »

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...

Full text and comments »

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 &mdash; [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...

Full text and comments »

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...

Full text and comments »

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...

Full text and comments »

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...

Full text and comments »

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...

Full text and comments »

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 &mdash; $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...

Full text and comments »

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 ...

Full text and comments »

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...

Full text and comments »

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"> ...

Full text and comments »

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...

Full text and comments »

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...

Full text and comments »

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** &mdash; _O(n log^2 n)_ - **Query Complexity** &mdash; _O(log^3 n)_ - **Update Complexity** &mdash; _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 ...

Full text and comments »

Editorial for TheForces Round #40 #### [Problem A &mdash; 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)$ </...

Full text and comments »

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...

Full text and comments »

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...

Full text and comments »

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...

Full text and comments »

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 ...

Full text and comments »

Invitation to CodeRed — 2020 by IIIT Allahabad Hello everyone !! After 3 successful editions, [Aparoksha](https://aparoksha.org/) is back with flagship coding event &mdash; **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 &mdash; [CodeRed 2020 online preliminary round](https://www.codechef.com/CORE2020?itm_campaig...

Full text and comments »

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; ...

Full text and comments »

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...

Full text and comments »

[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...

Full text and comments »

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$. <...

Full text and comments »

Разбор Codeforces Round 990 (Div. 2 + Div. 1) ### Div2A Alyona is happy when there are no unfinished layers &mdash; 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 &mdash; if tied, take the earlier character in the alphabet. Find the character which appears the highe...

Full text and comments »

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` #...

Full text and comments »

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...

Full text and comments »

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;...

Full text and comments »

[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 ...

Full text and comments »

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? ...

Full text and comments »

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: ...

Full text and comments »

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...

Full text and comments »

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...

Full text and comments »