[Tutorial] Non-trivial DP Tricks and Techniques Hi everyone! Today I want to share some DP tricks and techniques that I have seen from some problems. I think this will be helpful for those who just started doing DP. Sometimes the tutorials are very brief and assumes the reader already understand the technique so it will be hard for people who are new to the technique to understand it. Note : You should know how to do basic DP before reading the post DP + Bitmasks ------------------ This is actually a very well-known technique and most people should already know this. This trick is usually used when one of the variables have very small constraints that can allow exponential solutions. The classic example is applying it to solve the Travelling Salesman Problem in $O(n^{2} \cdot 2^{n})$ time. We let $dp[i][j]$ be the minimum time needed to visit the vertices in the set denoted by $i$ and ending at vertex $j$. Note that $i$ will iterate through all possible subsets of the vertices and thus the number of states is $O(2^{n} \cdo...

Полный текст и комментарии »

EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2) Editorial [2002A &mdash; Distanced Coloring](https://mirror.codeforces.com/contest/2002/problem/A) idea & solution: [user:xcyle,2024-08-12] <spoiler summary="Hint 1"> Consider the case with $n=m=k$. </spoiler> <spoiler summary="Hint 2"> Generalize the solution for all $n,m,k$. </spoiler> <spoiler summary="Tutorial"> It can be shown that for any $k\times k$ subgrid, the colors we use must be pairwise distinct. Thus, we have an lower bound of $\min(n,k)\cdot\min(m,k)$. We can show that this lower bound is indeed achievable by coloring the upper-left $\min(n,k)\cdot\min(m,k)$ subgrid with distinct colors, and copy-pasting it to fill the rest of the grid. Time complexity: $O(1)$. </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int t, n, m, k; int main() { scanf("%d", &t); while (t--) { scanf("%d%d%d", &n, &m, &k); printf("%d\n", min(n, k)*min(m, k)); } return 0; } ~~~~~ </spoiler> [2...

Полный текст и комментарии »

MacMahon's master theorem Hi everyone! Mandatory orz to ~Elegia,2023-12-04 whose [blog](https://blog.csdn.net/EI_Captain/article/details/108900963) introduced me to MMT as an elegant approach to prove Dixon's identity. Today, I would like to write about MacMahon's master theorem (MMT). It is a nice result on the intersection of combinatorics and linear algebra that provides an easy proof to some particularly obscure combinatorial identities, such as the **Dixon's identity**: $$ \sum\limits_k (-1)^k \binom{a+b}{a+k} \binom{b+c}{b+k} \binom{c+a}{c+k} = \binom{a+b+c}{a,b,c}. $$ Besides that, MMT has large implications in Quantum Physics, which we will hopefully discuss. For now, let's formulate MMT. <hr> **MMT**. Let $\mathbf A = [a_{ij}]_{n\times n}$, $\mathbf X = \operatorname{diag}(x_1,\dots,x_n)$, $\mathbf t = (t_1,\dots,t_n)$, $\mathbf x = (x_1,\dots,x_n)$ and $\mathbf k = (k_1,\dots,k_n) \geq 0$. Then, $$ \boxed{[\mathbf t^\mathbf k] \prod\limits_{i=1}^n \left(\sum\limits_{j=1}^n a_{ij} t_j...

Полный текст и комментарии »

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 | &mdash; | 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 | &mdash; | 1700 | 1800 | 2300 | | [user:Edeeva,2025-06-06] | 800 | 800 | 1200 | 1400 | 1500 | 1800 | 2000 | &mdash; | | [user:Intellegen...

Полный текст и комментарии »

[Tutorial] Inclusion-Exclusion Principle Hello, Codeforces! The reason why I am writing this blog is that my ACM/ICPC teammate [user:calabash_boy_love_15,2019-01-18] is learning this technique recently(he is a master in string algorithms,btw), and he wanted me to provide some useful resources on this topic. I found that although many claim that they do know this topic well, problems concerning inclusion-exclusion principle are sometimes quite tricky and not that easy to deal with. Also, after some few investigations, the so-called "Inclusion-Exclusion principle" some people claim that they know wasn't the generalized one, and has little use when solving problems. So, what I am going to pose here, is somewhat the "Generalized Inclusion-Exclusion Principle". Most of the describing text are from the graduate text book _Graduate Text in Mathematics 238, A Course in Enumeration_, and the problems are those that I encountered in real problem set, so if possible, I'll add a link to the real problem so that you can solve it by yours...

Полный текст и комментарии »

Unlabeling combinatorial species (cycle index series) Hi everyone! In my [previous blog](https://mirror.codeforces.com/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://mirror.codeforces.com/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...

Полный текст и комментарии »

Arrow product: How to enumerate directed graphs Hi everyone! In this blog, I would like to present a somewhat novel concept in competitive programming, which is, while being relatively simple, allows us to enumerate directed graphs with specific type of strongly connected components. This allows us to easily and uniformly compute generating functions e.g. for acyclic digraphs or strongly connected digraphs. The formalism introduced here is also very intuitive at that. I initially wanted to make a problem based on the content of this blog to appear in today's round, but after some discussions we decided to exclude it, as the contest already had a sufficient amount of difficult problems. You may try the original problem **[problem:441297A]** via the [invitation link](https://mirror.codeforces.com/contestInvitation/4d42a205a747b194397bbabd35ab2e81f9793447). #### Prerequisites You are expected to be familiar with exponential generating functions, and the [exponential formula](https://en.wikipedia.org/wiki/Exponential_formula) for c...

Полный текст и комментарии »

Distinct GCDs (Hard) - Proof that the construction is optimal Why the construction is optimal ================== Welcome to my first blogpost :) This problem https://mirror.codeforces.com/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...

Полный текст и комментарии »

Codeforces Round #333 — editorial ### Hints: [div2A](#div2A): Try conversions between bases. [div2B](#div2B): Solve a simpler version of the problem where $A_{i+1} \neq A_i$ for all $i$. [div1A](#div1A): What are the shortest paths of the vehicles? what's the shorter of those paths? [div1B](#div1B): Forget about the ceiling function. Draw points $(i,A[i])$ and lines between them &mdash; what's the Lipschitz constant geometrically? [div1C](#div1C): Some dynamic programming. Definitely not for the exp. score of one person &mdash; look at fixed scores instead. [div1D](#div1D): Compute $dif(v)$ in $O(N)$ (without hashing) and then solve the problem in $O(N^2)$. You need some smart merges. [div1E](#div1E): Can you solve the problem without events of type 1 or 2? Also, how about solving it offline &mdash; as queries on subsets.  ### <a name="div2A"></a>Div. 2 A: Two Bases ------------------------------------ It's easy to compare two numbers if the same bas...

Полный текст и комментарии »

Solutions for Сodeforces Beta Round #41 <b>А. Guilty — to the kitchen!<br></b>Let us reformulate the statement: we need to find the maximum possible value of x (mentioned in the statement) so that the amount of each ingredient will be enough. Clearly, such x equals min(b_i / a_i). Now it suffices to take minimum of the two values: soup volume we gained and the volume of the pan.<br><b><br>В. Game of chess unfinished.</b><br>In this problem you are to check exactly what the statement says: if the king's position and all the positions reachable by him in one turn are "beaten", — that's a mate. Thus, we have to determine "beaten" positions correctly. Let us remove the black king from the chessboard, leave the positions of&nbsp; the rooks "unbeaten" (not to forget about possible taking of the rook by the black king), mark positions reachable by rooks "beaten" and then mark positions reachable by white king as "beaten".<br><br><b>С. Safe cracking.</b><br>The answer in this problem is always affirmative, which means it is always p...

Полный текст и комментарии »

Fourier transform on groups. Part 1: Irreducible representations Hi everyone! Consider the following problem. You're given two arrays $a_1, a_2, \dots, a_{n!}$ and $b_1, b_2, \dots, b_{n!}$. You need to compute the array $c_1, c_2, \dots, c_{n!}$, such that $$ c_k = \sum\limits_{i \circ j = k} a_i b_j, $$ where $i \circ j$ denotes the composition of the $i$-th and the $j$-th lexicographically smallest permutations of $n$ elements. Generally, typical approach to such things would be to escape into space in which the convolution corresponds to the component-wise product of two vectors, and then to transform back into initial space. For example, with the summation rule being $i + j \equiv k \pmod n$, it is well known that the corresponding transform is exactly the discrete Fourier transform of vectors $a_i$ and $b_j$. But with more generic groups, things may be much more complicated, and I will write a series of blog posts explaining it. * **Fourier transform on groups. Part 1: Irreducible representations** * **[Fourier transfor...

Полный текст и комментарии »

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

Полный текст и комментарии »

[Tutorial] Network simplex Hello! If you've learned the simplex algorithm and a minimum cost flow algorithm, perhaps you've also heard about this fancy thing called [network simplex](https://en.wikipedia.org/wiki/Network_simplex_algorithm) which is supposed to be a specialization/optimization of the simplex algorithm for computing a [minimum cost circulation](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem). If your google search didn't turn up any interesting results or your interest faded, you might have moved on to other subjects. Well I didn't! So this is a tutorial on network simplex (NS) for the **minimum cost circulation** problem. I'll describe and formulate the problem, show how it relates to the usual minimum cost flow problem, explain the theory behind the algorithm in-depth, and then derive the implementation details. ## Introduction The algorithm commonly used in competitive programming for this sort of task is a minimum cost flow algorithm based on finding augmenting paths in a *f...

Полный текст и комментарии »

Codeforces Global Round 26 Editorial Thank you for participating! We put a lot of effort into this contest. Special thanks to [user:TheScrasse,2024-06-08] for contributing to these problems. <spoiler summary="Rating Predictions"> | Person | A | B | C1 | C2 | D | E | F | G | H | |--------------------------------------------|------|------|------|------|------|------|------|------|------| | [user:null_awe,2024-06-08] | 800 | 1000 | 1200 | 1700 | 2200 | 2400 | 2500 | 2900 | 3400 | | [user:buffering,2024-06-08] | 800 | 1000 | 1300 | 1800 | 2300 | 2400 | 2600 | 3100 | 3500 | | [user:redpanda,2024-06-08] | 800 | 1100 | 1200 | 1800 | | | | | | | [user:thescrasse,2024-06-08] | 800 | 1000 | 1200 | 1600 | 2200 | 2500 | 2500 | 3100 | 3400 | | [user:bronze_coder,2024-06-08] | 800 | 1000 | 1600 | 1800 | 2400 | | | 2700 | 3500 | | [user:awesomeguy856,20...

Полный текст и комментарии »

Invariant List | Share Your Invariant Here! [Invariant](https://brilliant.org/wiki/invariant-principle-definition) is a property that remains unchanged after operations/transformation, we see this a lot in competitive programming, especially with operations involved. <spoiler summary="Simple Example"> Given an array $a$ of $n$ integers with $n \geq 2$, in one operation you can choose two different indices $i$ and $j$ $(1 \leq i, j \leq n)$ and increment $a_i$ with $1$ and decrement $a_j$ with $1$. Given another array $b$ of $n$ integers, is it possible to change $a$ to $b$ with some operations? It is easy to see that the invariant for this problem is that: The sum of all the integers in $a$ will remain unchanged. With that information, we can further prove that it is possible to change $a$ to $b$ if the sum of integers in $a$ is equal to the sum of integers in $b$. </spoiler> I wanted to make an "Invariant List" here so the community could benefit from it, if you have some invariants in mind share with us ...

Полный текст и комментарии »

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

Полный текст и комментарии »

Codeforces Trainings Season 1 Episode 4: Editorial ### A. Arrangement of RGB Balls (difficulty: easy) If, among 3 consecutive balls, there are no two of the same color, then there's exactly one ball of every color among them. Thereforce, the sequence is determined by the order of the first 3 balls. Imagine these are RGB; then, the sequence continues as RGBRGBRGB... There are only $3!=6$ possible initial triples, so we can try all the sequences defined by them, and for every one of them, check if it can be constructed. [cut] When is it possible to construct such a sequence? Take the initial triple to be "GRB", for example (the idea for other triples is analogous). It's clear that the sequence is "GRB" repeated some $K$ times, and after that, there are the first 0, 1 or 2 balls from that triple (for example, "GRBGRBGR" or just "G"). It's clear that $K=min(R,G,B)$. So it's possible to construct iff $1\ge G-K \ge R-K \ge B-K$. Testing the existence of any sequence can be done in $O(1)$ time like this. There are $O(1)$ possib...

Полный текст и комментарии »

Codeforces Round #785 (Div. 2) Editorial I am sorry for the weak tests in B, for C being a little standardish and for misjudging the relative difficulties of E and F. Nevertheless, I hope you enjoyed the round. Here is the editorial. Do provide your feedback on each problem so that I can improve upon them the next time. #### [A. Subtle Substring Subtraction](https://mirror.codeforces.com/contest/1673/problem/A) <spoiler summary="Hint 1"> Greedy </spoiler> <spoiler summary="Hint 2"> The answer depends on whether the length of $s$ is even or odd and on the first and last characters of $s$ if the length is odd. </spoiler> <spoiler summary="Tutorial"> The problem can be solved greedily. Let $n$ be the length of the given string. - If the $n$ is even, it is always optimal for Alice to remove the whole string. - If the $n$ is odd, it is always optimal for Alice to remove either $s_1s_2\ldots s_{n-1}$ or $s_2s_3\ldots s_n$ based on which gives the higher score and then Bob can remove the remaining character ($s_n$ or ...

Полный текст и комментарии »

Codeforces Round #315 Editorial [problem:569A] Suppose we have downloaded $S$ seconds of the song and press the 'play' button. Let's find how many seconds will be downloaded when we will be forced to play the song once more. $\frac{x}{q} = \frac{x-S}{q-1}$. Hence $x=qS$. Solution: let's multiply $S$ by $q$ while $S<T$. The answer is the amount of operations. Complexity &mdash; $O(\log T)$ [problem:569B] Let's look at the problem from another side: how many numbers can we leave unchanged to get permutation? It is obvious: these numbers must be from $1$ to $n$ and they are must be pairwise distinct. This condition is necessary and sufficient. This problem can be solved with greedy algorithm. If me meet the number we have never met before and this number is between $1$ and $n$, we will leave this number unchanged. To implement this we can use array where we will mark used numbers. After that we will look over the array again and allocate numbers that weren't used. Complexity &mdash; $O(n)$. ...

Полный текст и комментарии »

Codeforces Round #269 Editorial [problem:471A] ------------------ Given six sticks and their lengths we need to decide whether we can make an elephant or a bear using those sticks. The only common requirement for both animals is that four leg-sticks should have same length. This means that the answer "Alien" should be given **only** if we can't find four sticks for the legs. Otherwise we will be able to make some animal. The type of the animal will depend on the relation of the remaining sticks' lengths. If they are equal then it will an elephant, if they are different we will have a bear. So this algorithm should solve the problem: 1. Find the number which appears at least four times in the input. 2. If no such number exist then the answer is "Alien". 3. Otherwise remove four entries of that number from the input. 4. After removing that number you will have two numbers left, compare them and decide whether it's an elephant or a bear. One shortcut for this problem might be to sort the in...

Полный текст и комментарии »

Analysis of polynomial hashing Unfortunately, most derivations of the chance of polynomial hashing collision are invalid, wrong, or misleading, and finding reliable public sources with proofs is incredibly difficult. This article is a formal analysis of the method. The goal of this article is to complement well-known empirical facts with theory, provide boundaries on the probability of collision, justify common choices, and advise against certain popular parameters. There is no code in this article, and it's mostly theoretical. It's more of a summa of everything we know about polynomial hashing in integers rather than a guide for beginners. You'll probably find something of interest still. I do, however, describe some methods of cracking hashes, which I can provide code and additional explanation for if someone asks in the comments and some general guidelines in the last section of the present article. ## Table of contents - The concept of polynomial hashing - Classical justification of the coprimality r...

Полный текст и комментарии »

My learning note on AGC061C based on Little09's (Simplified) Chinese Blog I admit that [AGC061C](https://atcoder.jp/contests/agc061/tasks/agc061_c) is too hard for me, and I don't even understand its [official editorial](https://atcoder.jp/contests/agc061/editorial/5695). Today I see a [Luogu blog](https://www.luogu.com.cn/blog/LJA001111/agc061c-first-come-first-serve) with a very genius and clear idea on this problem. I learned a lot from it, and I would like to share it to you now. The writer of this blog is possibly [user:little09,2023-02-15], but I am not quite sure. **Part1: Problem Statement and Constraints** There are $N$ customers named $1$, ..., $N$ visiting a shop. Customer $i$ arrives at time $A_i$ and leaves at time $B_i$ The queue order is first in first out, so $A_i$ and $B_i$ are both increasing. Additionally, all $A_i$ and $B_i$ are pairwise distinct. At the entrance, there's a list of visitors to put their names in. Each customer will write down their name next in the list exactly once, either when they arrive or when they leave. ...

Полный текст и комментарии »

Invitation To CodeChef AlgoManiac 2021 (Rated for Div 3, Open to All) Hello, Codeforces! We are glad to invite you to the awesome (we've tried our best to make it such) [CodeChef AlgoManiac 2021: Code For Future](https://www.codechef.com/CDMN2021), brought to you by Chandigarh University and CodeChef, that will start on [Thursday, September 02, 2021, at 20:00 IST (UTC + 5.5)](https://www.timeanddate.com/worldclock/fixedtime.html?msg=AlgoManiac+2021%3A+Code+For+Future&iso=20210903T1430&p1=1440).  Joining me on the problem setting panel are: - **Contest Admin:** [user:nishant403,2021-09-02] - **Setters:** [user:hitch_hiker42,2021-08-19], [user:prasanna2425,2021-08-19], [user:ars9,2021-08-19], [user:ShivY08,2021-08-19] - **Testers:** [user:_runtimeTerror_,2021-09-02], [user:nishant403,2021-09-02], [user:vichitr,2021-09-02], [user:infinitepro,2021-09-02], [user:hitch_hiker42,2021-08-19], [user:prasanna2425,2021-08-19], [user:ars9,2021-08-19], [user:ShivY08,2021-08-19]...

Полный текст и комментарии »

AlgoThugs 2026 — Editorial ### Contest announcement blog: [Link](https://mirror.codeforces.com/blog/entry/152857) ### [problem:669000A] Author: [user:Krishnadev44,2026-04-15] <spoiler summary="Hint 1"> We claim that the answer is always `YES`. </spoiler> <spoiler summary="Hint 2"> Let the direct path from vertex $u$ to vertex $v$ consist of $d$ edges. Since $u$ and $v$ are distinct, $d \ge 1$. Let the sequence of costs along these edges be $C = (c_1, c_2, \dots, c_d)$. We claim that there always exists a contiguous subarray of $C$ whose sum is perfectly divisible by $d$. </spoiler> <spoiler summary="Solution"> Let $S$ denote the prefix sum array of $C$, where the $k$-th prefix sum is defined as: $$S_k = \sum_{i=1}^{k} c_i \quad \text{for } 1 \le k \le d$$ Consider the values of these prefix sums modulo $d$. There are two cases: * Case $1$: There exists an index $k$ such that $S_k \equiv 0 \pmod d$. In this case, the sum of the prefix subarray $(c_1, c_2, \dots, c_k)$ is directly divisi...

Полный текст и комментарии »

Problems that I authored so far Hi everyone, after [contest:1854], maybe it's time to collect all my problems here. For now, I've mainly invented easy-ish problems. I wish to invent a very hard problem sooner or later :) <spoiler summary="Update after Pinely Round 3"> Done :D </spoiler> I'm putting the story of each problem under spoiler, because it may contain parts of the solution. I invented many problems by just trying random setups until I came up with something solvable, but some problems (especially the harder ones, for example [problem:1854D]) may have more interesting stories. Fun facts: - I struggled a lot to find a suitable div2A for [contest:1654]. I proposed a lot of problems that turned out to be unsuitable (for example, because they were too hard), then I used them somewhere else. - While I was writing this blog, I realized that [problem:1849E] is identical to my problem [preoii_allenamento \- Allenamento su ChinaForces](https://training.olinfo.it/#/task/preoii_allenamento/statement),...

Полный текст и комментарии »

NextTuring 2026 Joint Prelims — Official Editorial CodeForces Group Link: [https://mirror.codeforces.com/group/0jQZ3oBvJG](https://mirror.codeforces.com/group/0jQZ3oBvJG) [Problem A](https://mirror.codeforces.com/group/0jQZ3oBvJG/contest/686493/problem/A) ================== Problem Author: ~jothin,2026-04-19 <spoiler summary="Solution"> "lesser the age gap between two people, higher the interaction between them" so we need to find the first neighbour pair with the lowest age gap </spoiler> <spoiler summary="Code (python)"> ~~~~~ n=int(input()) A=[int(x) for x in input().split()] from itertools import pairwise req=min(abs(x-y) for x,y in pairwise(A)) for i in range(n-1): if abs(A[i]-A[i+1])==req: print(i+1) break ~~~~~ </spoiler> [Problem B](https://mirror.codeforces.com/group/0jQZ3oBvJG/contest/686493/problem/B) ================== Problem Author: ~jothin,2026-04-19 <spoiler summary="Solution"> he gets the verdict "Wrong answer on test k" So, he knows the correct answer for the first k-1 test ca...

Полный текст и комментарии »

[Tutorial] Abstract Proofs of DP Algorithms ## Introduction Most of DP algorithms I studied online, there are some subtleties that I didn't find any proof of. May be they are found somewhere already, but not to my knowledge. I think most people find the things that I'm going to prove here intuitive and need no proof, but for if you're really picky about being uncertain of something if you didn't see a proof (like me), it can bother you. Also, knowing the proofs can sometimes better help the thinking process. The purpose of this blog is to provide examples of proofs of famous DP algorithms to, first show them, and second serve as a general pattern of techniques on how would one prove a DP algorithm. Now, most DP problem involve a set of states $V$, and a set of transitions $E$ such that $(V, E)$ constitutes a directed acyclic graph or DAG (sometimes weighted). Thus, we will continue discussing DP calculations on a DAG. ### Conventions - A graph $G = (V, E)$ is a pair of sets $V$ and $E$ where $E \subseteq ...

Полный текст и комментарии »

Codeforces Round 1090 (Div. 4) Editorial I hope you all enjoyed the contest! Special thanks to: - [user:damamila,2026-04-05], for creating problem G - [user:chromate00,2026-04-05], [user:AG-88301,2026-04-05], [user:simplelife,2026-04-05], [user:SpyrosAliv,2026-04-05], [user:reirugan,2026-04-05] and [user:damamila,2026-04-05] for editorials for B-G respectively. - [user:cry,2026-04-05], for helping answer clarifications. <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> #### [A &mdash; The 67th Integer Problem](https://mirror.codeforces.com/contest/2218/problem/A) ...

Полный текст и комментарии »

Exponential Length Substrings in Pattern Matching Hi all, I would like to share with you a part of my undergraduate thesis on a Multi-String Pattern Matcher data structure. In my opinion, it's easy to understand and hard to implement correctly and efficiently. It's (relatively) competitive against other MSPM data structures (Aho-Corasick, suffix array/automaton/tree to name a few) when the dictionary size is specifically (uncommonly) large. I would also like to sign up this entry to [user:bashkort,2024-10-04]'s [Month of Blog Posts](https://mirror.codeforces.com/blog/entry/133806):-) Many thanks to him and peltorator for supporting this initiative. #### Abstract This work describes a hash-based mass-searching algorithm, finding (count, location of first match) entries from a dictionary against a string $s$ of length $n$. The presented implementation makes use of all substrings of $s$ whose lengths are powers of $2$ to construct an offline algorithm that can, in some cases, reach a complexity of $O(n \log^2n)$ even if there are $O...

Полный текст и комментарии »

An Interesting Problem given a set of $n \le 10^5$ range $[x_i, 2 \times x_i]$ and $\sum x_i \le 10^5$ determine the number of arrays $a$ such that $x_i \le a_i \le 2 \times x_i$ and all the elements in $a$ are pairwise distinct

Полный текст и комментарии »

Codeforces Round #127 — editorial #### Problem A(div 2) --- LLPS It's assumed that this problem can be solved just looking at the samples and without reading the statement itself :) Let's find the letter in the given string which comes last in the alphabet, denote this letter by $z$. If this letter occurs $p$ times in the given string, then the answer is string $a$ consisting of letter $z$ repeated $p$ times. Why is it so? Using the definition of lexicographical comparison and the fact that $z$ is the largest letter in the string it's easy to understand that if some other subsequence $b$ of the given string is lexicographically larger than $a$, then string $b$ should be longer than $a$ and, moreover, $a$ should be a prefix of $b$ (that is, $b$ should start with $a$). But string $b$ must be a palindrome, therefore its last letter must be $z$. In this case string $b$ must contain more occurrences of letter $z$ than the original string $s$ does, which is impossible as $b$ is a subsequence of $s$. Beside...

Полный текст и комментарии »

National Competitive Programming Challenge — Editorial Here is the link to the contest: [Link](https://mirror.codeforces.com/contestInvitation/6071a436743e70518e953453aadcf924bca069aa) ### [A. The Blacksmith](https://mirror.codeforces.com/gym/656191/problem/A) <spoiler summary="Credits"> - **Problem Idea**: [user:eulmelk,2025-12-12] - **Problem Setter**: [user:eulmelk,2025-12-12] </spoiler> <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> #### Approach 1 <spoiler summary="Tutorial"> **Step 1**<br> $n \le 500$, so the total number of pairs is at most $\frac{n(n-1)}{2} = \frac{500 \cdot 499}{2} = 124750$. This is easily manageable within time limits. **Step 2**<br> By checking every possible pair, we never miss any valid combination. Therefore, keeping the maximum among all va...

Полный текст и комментарии »

About 2031C (Penchick and BBQ Buns, problem C of CF Round 987), and extra challenges Author of the problem [problem:2031C] here, hope you enjoyed the contest yesterday (Almost exactly 24 hours ago...)! Looking at the votes on [the editorial](https://mirror.codeforces.com/blog/entry/136260), it's obvious that it's a very polarizing problem: an hour or so after the contest, the problem had roughly equal numbers of "likes" and "dislikes", and now (as of writing) there are around 320 likes to 200 dislikes. Of course, this is completely predictable: the opinions on this problem were quite polarized for a few reasons: 1. Troll and WA trap: it's **very** easy to fall into the trap of thinking that there is no solution for all odd $n$; thus, **over 12,900** (!) WA on pretest 2 solutions were received, as compared to only 4,700ish Accepted solutions. This ratio seems a bit extreme for a problem C; in the previous Div.2's problem C ([problem:2028C]), there were 3,500ish Rejected solutions to 2,500ish Accepted ones. 2. The construction: hard-coding the case $n=27$ seems weird an...

Полный текст и комментарии »

Codeforces Round 984 (Div. 3) Editorial [problem:2036A] Idea: [user:m3tr0,2024-11-03] <spoiler summary="Tutorial"> If for all $i$ $(1 \leq i \leq n - 1)$ is true $|a_i - a_{i+1}| = 5$ or $|a_i - a_{i+1}| = 7$, the answer to the problem is “YES”, otherwise it is “NO”. Complexity: $O(n)$ </spoiler> <spoiler summary="Solution (myav)"> ~~~~~ #include <bits/stdc++.h> using namespace std; bool solve(){ int n; cin >> n; vector<int>a(n); for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 1; i < n; i++) { if(abs(a[i] - a[i - 1]) != 5 && abs(a[i] - a[i - 1]) != 7) return false; } return true; } int main() { int t; cin >> t; while(t--){ cout << (solve() ? "YES" : "NO") << "\n"; } } ~~~~~ </spoiler> [problem:2036B] Idea: [user:Seny,2024-11-03] <spoiler summary="Tutorial"> Let's create an array `brand_cost` of length $k$ and fill it so that `brand_cost[i]` stores the cost of all bottles of brand $i+1$. Then sort the array...

Полный текст и комментарии »

[Tutorial] A New Perspective on Numbers and Operators: Introducing Group Theory We often start our mathematical journey with counting, primes, and basic arithmetic. Then we encounter modular arithmetic, with its intriguing properties and theorems like Euclid's algorithm and the Chinese Remainder Theorem. But what if there's a deeper, more abstract framework that ties all these concepts together? You might have encountered hints that group theory is behind some clever algorithms and data structures ([like this comment suggests](https://mirror.codeforces.com/blog/entry/103174?#comment-915676)). But if you've tried to learn about it, you might have found resources that felt either too abstract and disconnected from your existing knowledge ([for instance](https://zhtluo.com/cp/from-burnside-to-polya-a-short-introduction-to-group-theory.html)), or too intimidating and complex ([like this one](https://mirror.codeforces.com/blog/entry/91731)). This blog aims to bridge that gap. We'll start with familiar ground in discrete math and modular arithmetic, and then progressively in...

Полный текст и комментарии »

Codeforces Beta Round #66 editorial: Problems D, E, F <p class="MsoNormal"><b><span lang="EN-US">Problem D</span>.</b></p> <p class="MsoNormal"></p><p class="MsoNormal"><p class="MsoNormal"><span class="apple-style-span"><span lang="EN-US" style="font-size:12.0pt;line-height:115%;font-family:&quot;Times New Roman&quot;,&quot;serif&quot;; mso-ansi-language:EN-US">First, let’s divide graph to connected components (provinces). Next, we consider only new graph on these components – for each province we assign a vertex of the <span style="color:black">graph.</span></span></span><span class="apple-converted-space"><span lang="EN-US" style="font-size:12.0pt; line-height:115%;font-family:&quot;Times New Roman&quot;,&quot;serif&quot;;color:black;mso-ansi-language: EN-US">&nbsp;</span></span><span class="apple-style-span"><span lang="EN-US" style="font-size:12.0pt;line-height:115%;font-family:&quot;Times New Roman&quot;,&quot;serif&quot;; color:black;mso-ansi-language:EN-US">Let the total number of provinces is <i style="mso-bidi-font-styl...

Полный текст и комментарии »