You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:

  • 305 — search for 305, most probably it will find blogs about the Round 305
  • andrew stankevich contests — search for words "andrew", "stankevich" and "contests" at the same time
  • user:mikemirzayanov title:testlib — search containing "testlib" in title by MikeMirzayanov
  • "vk cup" — use quotes to find phrase as is
  • title:educational — search in title

Results

1.
[Tutorial] Matroid intersection in simple words
By ATSTNG, history, 7 years ago, In English
[Tutorial] Matroid intersection in simple words **[This article is also available in [Russian](https://codeforces.me/blog/entry/69287?locale=ru)]** Hello, CodeForces. I think that matroids are beautiful and powerful concept, however, not really well known in competitive programming. I’ve discovered matroids at 2019 Petrozavodsk Winter Training Camp. There was a problem that clearly cannot be solved using usual techniques I knew, editorial for this problem was just these three words “just matroid intersection”. Back then it took me more than 2 days of upsolving to find all the information and details I need and implement solution that gets Accepted on this. And it took way longer to actually understand why does it work and exactly how does it work. (I still hesitate in some details.) Of course, it is not hard to google up all the definitions and some related articles, but in my opinion they all are focused more on mathematical part of theory, strict proofs in some not really obvious but short ways, and observing only ke...
on edges of some undirected graph. Set of edges is independent if it does not contain a cycle. This, on two connected graphs. We can unite their graphs together resulting in graph with two connected

Full text and comments »

  • Vote: I like it
  • +904
  • Vote: I do not like it

2.
Arrow product: How to enumerate directed graphs
By adamant, history, 4 years ago, In English
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://codeforces.me/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...
Arrow product: How to enumerate directed graphs, based on the number of the source vertices of the graph: $$ \boxed{a_n = \sum\limits_{i=1}^n (-1, that the product, the above interpretations is called the **arrow product** of the structures $A$ and $B$. This, "> $D(x,u+1)$ represented as an arrow product Illustration from the paper , "> $G(x,u+1)$ represented as the arrow product of $e^{A(x) u}$ and $G(x)$ , "> Element of the arrow product of digraphs (first interpretation) , #### Arrow product, -exclusion principle based on the number of the source vertices of the graph:, /labeled), while edges indistinguishable from each other. Proper way to define an arrowproduct in, As a notational convenience, we will use the symbol $\curvearrowright$ for such product, so that, Then, we can represent the class of objects enumerated by $D(x, u+1)$ as the arrowproduct of a set, ]**, much harder version of the problem above, where cactus is a graph where "each edge belongs to at most

Full text and comments »

  • Vote: I like it
  • +245
  • Vote: I do not like it

3.
Codeforces round #628 editorial
By mohammedehab2002, history, 7 years ago, In English
Codeforces round #628 editorial ### [problem:1325A] $a=1$ and $b=x-1$ always work. Code link: https://pastebin.com/ddHKD09B First AC: [user:Sevlll,2020-03-14] **Bonus task:** can you count the valid pairs? ### [problem:1325B] Let the number of distinct elements in $a$ be called $d$. Clearly, the answer is limited by $d$. Now, you can construct your subsequence as follows: take the smallest element from the first copy, the second smallest element from the second copy, and so on. Since there are enough copies to take every element, the answer is $d$. Code link: https://pastebin.com/hjcxUDmY First AC: [user:socho,2020-03-14] ### [problem:1325C] Notice that there will be a path that passes through the edge labeled $0$ and the edge labeled $1$ no matter how you label the edges, so there's always a path with $MEX$ $2$ or more. If any node has degree 3 or more, you can distribute the labels $0$, $1$, and $2$ to edges incident to this node and distribute the rest of the labels arbitrarily. Other...
$q$. Let's create a graph where the vertices are the prime numbers (and $1$,) and the edges are the, because their product would be greater than $maxAi$. So that means ANY walk in thisgraph has a node, shortest subsequence whose product is a perfect square is just the shortest cycle in thisgraph!

Full text and comments »

  • Vote: I like it
  • +288
  • Vote: I do not like it

4.
Codeforces Round #268 Editorial
By EvenImage, 12 years ago, In English
Codeforces Round #268 Editorial I'll upload my example solutions and will post links to them as soon as it becomes possible. All the problems in Div 1 don't have the unique solution. I list several solutions to each problems. There are also some interesting bonus problems. I can't solve some of them yet :( If you have interesting ideas, feel free to share and discuss your ideas in the comments. :) My English is poor, so if there are some mistakes or something you can't understand, you can also discuss it in the comments. [problem:469A] [I Wanna Be the Guy](http://kayin.moe/iwbtg/downloads.php) is an interesting game. I strongly recommend it to you. The problem itself is easy. Just check if all the levels could be passed by Little X or Little Y. [submission:7894174] [problem:469B] This problem is not hard. Just iterator over all possible $t$, and check if the schedule of Little X and Little Z will overlap. [submission:7894252] **Bonus:** 1. $p,q\leq 50, l,r\leq 10^9$ 2. $p,q,l,r\leq 1...
$. The degree of every node is at most $2$. So this graph consists of a lot of chains and cycles, and, Construct a undirected graph $G$ with $2n$ vertices $v_1, v_2, \dots, v_{2n}$, where the edge

Full text and comments »

  • Vote: I like it
  • +124
  • Vote: I do not like it

5.
Codeforces Round 969 (Div. 1, Div. 2) Editorial
By LMydd0225, history, 2 years ago, In English
Codeforces Round 969 (Div. 1, Div. 2) Editorial [problem:2007A] <spoiler summary="Hint 1"> How many odd integers are there in a pair $(a, b, c)$? <spoiler summary="Answer"> At least 2. </spoiler> </spoiler> <spoiler summary="Hint 2"> It's always better to put **exactly $2$** odd integers and **exactly $1$** even integer in one pair of $(a, b, c)$. Is there a way to always choose optimal $(a, b, c)$? </spoiler> <spoiler summary="Hint 3"> Try consecutive integers. </spoiler> <spoiler summary="Tutorial"> [tutorial:2007A] </spoiler> <spoiler summary="Implementation"> ```py T = int(input()) for _ in range(T) : l, r = map(int, input().split()) print(((r + 1) // 2 - l // 2) // 2) ``` </spoiler> [problem:2007B] <spoiler summary="Hint"> Consider the position of the maximum value in one array. If there's multiple maximum values, choose any. What can you observe? <spoiler summary="Answer"> The position of the maximum value never changes. That is, if one element is the maximum value...
sort splits the graph into several layers. The beauty is the product of factorials of number of, . Otherwise, the topo sort splits the graph into several layers. The beauty is theproduct of factorials of

Full text and comments »

  • Vote: I like it
  • +138
  • Vote: I do not like it

6.
Codeforces Round 1048 (Div. 1, Div. 2) Editorial
By installb, history, 14 months ago, In English
Codeforces Round 1048 (Div. 1, Div. 2) Editorial [2139A &mdash; Maple and Multiplication](https://codeforces.me/contest/2139/problem/A) Idea: [user:installb,2025-09-08] Preparation: [user:installb,2025-09-08],[user:2014CAIS01,2025-09-08] <spoiler summary="Solution"> If $a=b$ we need $0$ steps. If $a$ can be divided by $b$, we only need $1$ step, which is to multiply $b$ by $\frac{a}{b}$. Same for the case when $b$ can be divided by $a$. Otherwise, we need at most $2$ steps. As both $a$ and $b$ are positive integers, we can first multiply $a$ by $b$ and then multiply $b$ by the original value of $a$. Both number will be equal to $a\times b$. </spoiler> <spoiler summary="Code (C++)"> ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; int solve(){ int a,b; cin >> a >> b; if(a == b) return 0; if(a % b == 0 || b % a == 0) return 1; return 2; } int main(){ ios::sync_with_stdio(false); int TC; cin >> TC; while(TC --){ cout <<...
construction of a matrix into the construction of a directed graph, as the determinant and, directed graph determined by the adjacency matrix $M$. We can also interpret $m_{i,j}=0$ as "the edge from

Full text and comments »

  • Vote: I like it
  • +235
  • Vote: I do not like it

7.
Matrix Exponentiation tutorial + training contest
By Errichto, 6 years ago, In English
Matrix Exponentiation tutorial + training contest tl;dr &mdash; video tutorial https://www.youtube.com/watch?v=eMXNWcbw75E and codeforces GYM training https://codeforces.me/gym/102644 (register by finding this contest in GYM instead of using the link directly) video editorial: [part 1 (ABCDEF)](https://www.youtube.com/watch?v=kQuCOFzWoa0) and [part 2 (GHI)](https://www.youtube.com/watch?v=RA_SpxP2t54) codes to all 9 problems: https://github.com/Errichto/youtube/tree/master/matrix-exponentiation Prerequisites: binary exponentiation and iterative dp (you don't need to know matrices) The youtube tutorial ([link](https://www.youtube.com/watch?v=eMXNWcbw75E)) focuses on intuition and graph-like visualization . Or, if you prefer, below is a shorter (less detailed) text tutorial instead. You can practice by solving a set of 9 educational problems in GYM https://codeforces.me/gym/102644. ABCD are easy, EF medium, GHI are hard. If you are stuck, see hints below or watch the full solution analysis &mdash; [part 1 (ABCDEF)](https:...
://www.youtube.com/watch?v=eMXNWcbw75E)) focuses on intuition and graph-like visualization . Or, if you prefer

Full text and comments »

  • Vote: I like it
  • +606
  • Vote: I do not like it

8.
An intuition and simpler proof for Kirchoff's tree theorem
By Everule, history, 4 years ago, In English
An intuition and simpler proof for Kirchoff's tree theorem Kirchoff's tree theorem was recently used in https://atcoder.jp/contests/abc253/tasks/abc253_h, and it on first glance, almost feels like black magic, but I will show that it is not the case. So prerequisites... Advanced contestants may skip these <spoiler summary="Prerequisites"> #### Permutation Cycles Given a permutation $P = [P_1, P_2, P_3 \ldots P_n]$. Define a Digraph on $n$ vertices with the edges $(i, P_i)$. These form a set of directed cycles, and they are called the cycles of the permutation. $\text{sgn}(P) = (-1)^{C+n}$, where $C$ is the number of cycles in $P$. #### What is a Determinant The determinant of a matrix $M$ is $$\sum\limits_{P \in S_n} \text{sgn}(P) \prod_{i = 1}^{n} M_{i, P_i}$$ ####What is an Arborescence An arborescence rooted at $r$ is a directed graph with $n-1$ edges such that every node is reachable from $r$. ####What is a functional graph A functional Graph induced by $f$ on $V$ is a graph $G = (V, E)$ where $E$ contains $(x, f(x))$ for eve...
determinant. We let $M_{i, i} = -|G_i| = -deg_i$, so that the permutation is weighted by theproduct, graph with $n-1$ edges such that every node is reachable from $r$. ####What is a functionalgraph A

Full text and comments »

  • Vote: I like it
  • +251
  • Vote: I do not like it

9.
A problem collection of ODE and differential technique
By EvenImage, history, 7 years ago, In English
A problem collection of ODE and differential technique ##A problem collection of ODE and differential technique *This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them.* For those who are interested in well-known problems in China. Thank [user:Elegia,2020-04-23] and [user:djq_cpp,2020-04-23] for developing this technique. Thank [user:tEMMIE.w.,2020-04-23] for reviewing this article. ####[Chain Reaction](http://uoj.ac/problem/50) in UOJ Round 3 By [user:vfleaking,2020-04-23] **Statement** ​ You are given a set $A$, you need to compute $g_{i} = \frac{1}{2} \sum_{j,k}{i-1 \choose j}{i-1-j \choose k} g_jg_k$ where $i-1-j-k \in A$. **Solution** ​ Let the EGF of $g$ be $x(t)$ and EGF of $A$ be $a(t)$. Thus $x'(t)=\frac{1}{2} a(t) x^2(t)+1$. We can solve this equation by D&C and FFT in $O(n\log^2 n)$. But there is a <s>slower</s> solution in $O(n\log n)$. ​ For a polynomial equation $f(x(t))=0$, we can use the Newton's method to solve it. If we find ...
Hadamard product here. - If $u \in \mathcal{D}$, $v$ is algebraic and $v(0)=0$, then $w=u(v(x)) \in

Full text and comments »

  • Vote: I like it
  • +1044
  • Vote: I do not like it

10.
Nimbers and Sprague-Grundy theorem
By adamant, history, 4 years ago, In English
Nimbers and Sprague-Grundy theorem Hi everyone! Today I'd like to write about the so-called Grundy numbers, or nimbers. I will start by providing a formal recap on the Sprague-Grundy theorem and then will advance to the topic that is rarely covered in competitive programming resources, that is I will write about nimber product and its meaning to the game theory. _I was asked to add the following to the blog: THANK SIR MASTER [user:ADAM_GS,2022-06-12] FOR GREAT AND VALUABLE REVIEW SIR_ ## Prerequisites Familiarity with the following concepts: - Basic [set theory](https://en.wikipedia.org/wiki/Set_theory) notion: [union](https://en.wikipedia.org/wiki/Union_%28set_theory%29), [cartesian product](https://en.wikipedia.org/wiki/Cartesian_product) and [symmetric difference](https://en.wikipedia.org/wiki/Symmetric_difference) of sets, [set of all subsets](https://en.wikipedia.org/wiki/Power_set) denoted as $2^A$, etc; - [Groups](https://en.wikipedia.org/wiki/Group_%28mathematics%29) and [fields](https://en.wiki...
is rarely covered in competitive programming resources, that is I will write about nimberproduct

Full text and comments »

  • Vote: I like it
  • +204
  • Vote: I do not like it

11.
Educational Round 102 A-E Editorial and Thoughts
By nika-skybytska, 6 years ago, In English
Educational Round 102 A-E Editorial and Thoughts [My solutions on GitHub](https://github.com/Sky-Nik/Codeforces/tree/main/edu-102) ### A. Replacing Elements The minimum value that an element can get is the sum of the two smallest elements of the initial array. Constraints allowed to find such pair in $O(n^2)$ by brute force. One can also sort the array in $O(n \log n)$ and take `a[0] + a[1]`. However, the optimal method to select $k$ min elements is, of course, a heap with a size limit of $k$ elements which performs this job in $O(n \log k)$. We then change every element to this value if such a change reduces it, and compare against the limit. ### B. String LCM We have to print the lcm anyways, so we can just generate it by looping over two string simultaneously with a pair of indices. If lcm exists then its length is the lcm of lengths of the two strings, hence it is relatively short. If we encounter a pair of different symbols while iterating then lcm does not exist and we print -1. ### C. No More Inversions If yo...
one edge as its max-edge (a total of four options, according to the product rule). It follows that we, -edge and at most one edge as its max-edge (a total of four options, according to theproduct rule

Full text and comments »

  • Vote: I like it
  • +137
  • Vote: I do not like it

12.
Problems that I authored so far
By EvenImage, 4 years ago, In English
Problems that I authored so far Since competitive programming is dying, and I'm almost retired, so it's time to review the problems I authored. Hi everyone! I wanted to write such a blog for a long time, motivated by similar blogs, [by](https://codeforces.me/blog/entry/113093) [user:antontrygubO_o,2023-02-25], [by](https://codeforces.me/blog/entry/108940) [user:adamant,2023-02-25] and [by](https://codeforces.me/blog/entry/108595) [user:tibinyte,2023-02-25]. This is not a super-comprehensive list. I set many shit problems that I don't want to share for some local contests. It can be long, and I'm not sure if I have finished half of them yet. The number of asterisks after the label indicates the recommendation levels. One asterisk means this problem is worth reading. Two asterisks mean this problem is one of my favorite problems, Three asterisks mean this problem is one of my best problems. | # | Date | Problem | Contest | Comment | | ---- | ----------- | --------------------------------------------...
a complete bipartite graph with $k(k \leq 20)$ edges removed. Every edge has a weight. Find the, bipartite graph with $k(k \leq 20)$ edges removed. Every edge has a weight. Find the number of perfect

Full text and comments »

  • Vote: I like it
  • +311
  • Vote: I do not like it

13.
Everyday Apps You Use That Are Secretly Running Graph Algorithms
By saanTH, history, 4 months ago, In English
Everyday Apps You Use That Are Secretly Running Graph Algorithms Open your phone right now. Maps, Instagram, Spotify, LinkedIn, Uber — whatever you tap on, there's a good chance a graph is quietly doing the heavy lifting behind the scenes. In competitive programming, graphs are just nodes and edges you traverse with BFS, DFS, or Dijkstra. In the real world, those same nodes and edges represent people, places, songs, and rides — and the algorithms running on them are worth billions of dollars. **Here are 5 apps you probably used today that are secretly graph problems in disguise.** **** **** **1. Google Maps / Waze — Shortest Path Algorithms** **** The graph: Every intersection is a node. Every road segment is an edge, weighted by distance, speed limit, and live traffic. The algorithm: A modified version of Dijkstra's algorithm or A* search — the same algorithm you'd use to solve a "shortest path" problem on a competitive programming judge. The twist is that edge weights change in real time based on traffic data from millions of phones, so...
Everyday Apps You Use That Are Secretly Running Graph Algorithms, a good chance a graph is quietly doing the heavy lifting behind the scenes. In competitive, The graph: Users and items (movies, songs, products) form a bipartite graph — users connect to the

Full text and comments »

  • Vote: I like it
  • -11
  • Vote: I do not like it

14.
Editorial for Codeforces Round #346 (Div. 2)
By IlyaLos, history, 11 years ago, translation, In English
Editorial for Codeforces Round #346 (Div. 2) [659A &mdash; Round House](http://codeforces.me/contest/659/problem/A) The answer for the problem is calculated with a formula $((a - 1 + b)$ $\mod$ $n$ + $n$) $\mod$ $n$ + $1$. Such solution has complexity $O(1)$. There is also a solution with iterations, modelling every of $|b|$'s Vasya's moves by one entrance one by one in desired direction, allowed to pass all the tests. This solution's complexity is $O(|b|)$. [659B &mdash; Qualifying Contest](http://codeforces.me/contest/659/problem/B) Let's consider the participants from every region separately. So for every region we just need to sort all of its participants by their score in non-increasing order. The answer for a region is inconsistent if and only if the score of the second and the third participant in this order are equal, otherwise the answer is the first and the second participant in this order. The solution complexity is $O(n \log{n})$. [659C &mdash; Tanya and Toys](http://codeforces.me/contest/65...
/contest/659/problem/E) One should notice, that for every connected component of thegraph the problem, In this task one should find a connected area, in which the product of the minimum value of the

Full text and comments »

  • Vote: I like it
  • +85
  • Vote: I do not like it

15.
Randomized general matching with Tutte matrix
By adamant, history, 5 years ago, In English
Randomized general matching with Tutte matrix Hi everyone! Some time ago [user:1-gon,2021-07-01] wrote an [article](https://codeforces.me/blog/entry/92339) about Edmonds blossom algorithm to find the maximum matching in an arbitrary graph. Since the problem has a very nice algebraic approach, I wanted to share it as well. I'll start with something very short and elaborate later on. **[Library Checker &mdash; Matching on General Graph](https://judge.yosupo.jp/problem/general_matching)**. Given a simple undirected graph on $N \leq 500$ vertices, find the maximum matching. <hr> **tl;dr**. The Tutte matrix of the graph $G=(V, E)$ is \begin{equation} T(x_{12}, \dots, x_{(n-1)n}) = \begin{pmatrix} 0 & x_{12} e_{12} & x_{13} e_{13} & \dots & x_{1n} e_{1n} \newline -x_{12} e_{12} & 0 & x_{23} e_{23} & \dots & x_{2n} e_{2n} \newline -x_{13} e_{13} & -x_{23} e_{23} & 0 & \dots & x_{3n} e_{3n} \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline -x_{1n} e_{1n} & -x_{2n} e_{2n} & -x_{3n} e_{3n} & \dots & 0 \end{...
/blog/entry/92339) about Edmonds blossom algorithm to find the maximum matching in an arbitrarygraph

Full text and comments »

  • Vote: I like it
  • +223
  • Vote: I do not like it

16.
Problems that I authored so far
By antontrygubO_o, 4 years ago, In English
Problems that I authored so far **UPD 1 [May 17 2025]:** I added my problems from Ukrainian Olympiad in Informatics (among others). They are available here: [contest:105820] Hi everyone! I wanted to write such a blog for a long time, motivated by similar blogs [by](https://codeforces.me/blog/entry/108940) [user:adamant,2023-02-20] and [by](https://codeforces.me/blog/entry/108595) [user:tibinyte,2023-02-20]; I finally decided to do it after my Universal Cup contest. This is not a super-comprehensive list, I also set some problems for some local contests, but that's most of it. I want to encourage other setters to write such blogs. For me, it's very interesting to read about the backstories of some problems and also to see all the problems by some author gathered in one place (as most authors give problems to several platforms). One important point. As you will see from the comments, many of my problems were improved by other people, and I myself improved some problems by other people. I think that it's cruc...
| June 2019 | [Vus the Cossack and a Graph ](https://codeforces.me/contest/1186/problem/F

Full text and comments »

  • Vote: I like it
  • +460
  • Vote: I do not like it

17.
Combinatorial species: An intuition behind generating functions
By adamant, history, 4 years ago, In English
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...
- Basic notion of set theory (cardinality of sets, mappings, bijections, cartesianproduct, disjoint

Full text and comments »

  • Vote: I like it
  • +380
  • Vote: I do not like it

18.
Distinct GCDs (Hard) - Proof that the construction is optimal
By Immanence, 11 months ago, In English
Distinct GCDs (Hard) - Proof that the construction is optimal Why the construction is optimal ================== Welcome to my first blogpost :) This problem https://codeforces.me/contest/2158/problem/F2 was one of the hardest problems I've tried to understand. The official editorial gives a very nice construction but, coming from an analysis/pure math background, for the sake of intuition I sought a proof of (a) a lower bound on the number of distinct values we may use, and (b) why the $10 \times 10$ construction is in fact optimal for all $n \le 5000$. As such, this post is the same solution as the editorial written in a more "theorem" style. To summarize, I derive the extremal function $g(k)$ = maximum number of distinct adjacent gcds you can get if you use only $k$ distinct values, show that the construction exactly matches that bound, then prove the gcd-uniqueness of the $10 \times 10$ grid in a bit more detail. First glance ============================================== At first sight, the problem feels impossible for thre...
big graph with a distinct prime $p_e$, and let each vertex be the product of primes on its incident, construction i.e. label every edge of a big graph with a distinct prime $p_e$, and let each vertex

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

19.
Beyond Basic BFS: Solving Multi-Agent and Complex Path Problems with State-Space BFS
By MrStark2244, history, 16 months ago, In English
Beyond Basic BFS: Solving Multi-Agent and Complex Path Problems with State-Space BFS Hello Codeforces community! We all know and love Breadth-First Search (BFS). It's our go-to for finding the shortest path in unweighted graphs. But what happens when the problem isn't just about moving a single entity from point A to point B? What if there are two entities moving simultaneously, or if the "state" of our problem involves more than just a single vertex? This is where the powerful technique of **BFS on a State-Space Graph (often implicitly a Product Graph)** comes into play. It's not a new algorithm, but rather a fundamental *application pattern* of BFS that allows us to tackle a much wider range of problems. --- ### The Core Concept: State-Space BFS Imagine your problem isn't just about a single node in a graph. Instead, the "situation" or "configuration" of your problem is more complex. * **What is a "State"?** In State-Space BFS, a "state" is a tuple that encapsulates *all the necessary information* to describe the current configuration of your p...
powerful technique of **BFS on a State-Space Graph (often implicitly a Product Graph)** comes into play, This is where the powerful technique of **BFS on a State-Space Graph (often implicitly aProduct

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

20.
Grakn Forces 2020
By graknlabs, 6 years ago, In English
Grakn Forces 2020 “Codeforces… assemble!” <center> <img alt="grakn" src="https://grakn.ai/assets/svg/logo.svg" style="float:right; height: 50px; margin: 10px; max-width:10%;"/> </center> We are thrilled to announce **Grakn Forces 2020**; hosted by Codeforces and sponsored by [Grakn Labs](https://vaticle.com/). Thank you to Codeforces for providing a world-class competition structure to partner with. We can’t wait to see what you all are capable of. This international competition consists of 1 round, lasting 2.5 hours. The contest will comprise 7-9 problems and will be in accordance with classic Codeforces rules. **Prizes:** - 1st place = 500 euros - 2nd place = 250 euros - 3rd place = 100 euros **Additional Prizes:** Top 50 receive: _Grakn Labs swag pack:_ - Stickers - Grakn Labs t-shirt Random 50 from 51-250 receive: _Grakn Labs swag pack:_ - Stickers - Grakn Labs t-shirt **About Grakn Labs** [Grakn Labs](https://github.com/graknlabs) is a team...
](https://github.com/graknlabs/grakn) knowledge graph and the [Graql](https://github.com/graknlabs

Full text and comments »

Announcement of Grakn Forces 2020
  • Vote: I like it
  • +464
  • Vote: I do not like it

21.
CodeTON Round 5 Editorial
By platelet, 3 years ago, In English
CodeTON Round 5 Editorial ### [problem:1842A] <spoiler summary="Tutorial"> Let's view it as when monsters $x$ and $y$ fight, their health changes into $\max(x-y,0)$ and $\max(y-x,0)$ respectively. So any monster with $0$ health is considered dead. Therefore, a player loses when the health of his monsters are all $0$. Notice that $\max(x-y,0)=x-\min(x,y)$ and $\max(y-x,0)=y-\min(x,y)$. Therefore, after each step, the sum of the health of monsters decrease by the same amount for both players. Therefore, we only need to know $\sum a_i$ and $\sum b_i$ to determine who wins. If $\sum a_i > \sum b_i$, Tsondu wins. Else if $\sum a_i < \sum b_i$, Tenzing wins. Else, it is a draw. </spoiler> <spoiler summary="Code"> ~~~~~ #include <iostream> using namespace std; int main() { ios::sync_with_stdio(false), cin.tie(nullptr); int T; cin >> T; while (T--) { int n, m, a[50], b[50]; long long sumA = 0, sumB = 0; cin >> n >> m; for (int i = 0; i < n;...
graph with $n$ left nodes representing the points in the original problem and $k$ right nodes

Full text and comments »

  • Vote: I like it
  • +573
  • Vote: I do not like it

22.
Yandex.Algorithm Online Round 1 Analysis
By Michael, 13 years ago, In English
Yandex.Algorithm Online Round 1 Analysis In the first online round of Yandex.Algorithm competition 609 participants submitted at least one solution and 396 submitted at least one correct solution. Problems _Non-Squares_ and _Kingdom Division_ were fairly easy, both resulted in approximately 300 correct submissions. Problem _Stacks of Coins_ was moderately easy and was solved by 145 participants. The three other problems proved to be more difficult. _Stickers_ could be a very challenging string problem, but small input size allowed for dynamic programming solution, which 22 contestants got right. _Assistants_ was solved by 13 participants; it required binary search, greedy, and some basic data structures to get it under time limit.During the contest, nobody was able to solve _State Roads_, which was a neat graph-theoretical problem with a simple to code, but a quite tricky solution. Congratulations to [user:Kenny_HORROR,2013-07-15] who was the only one to solve five problems, and to [user:Petr,2013-07-15], [user:tourist,20...
limit.During the contest, nobody was able to solve _State Roads_, which was a neatgraph-theoretical, . For each edge that is added to the graph we pick at random an integer weight. For each node $v \in

Full text and comments »

  • Vote: I like it
  • +81
  • Vote: I do not like it

23.
Simple DP optimizations
By rembocoder, 4 years ago, translation, In English
Simple DP optimizations No, I don't mean Convex Hull Trick and Knuth optimization. I mean simpler and more common methods. _This is a continuation of my series of posts on DP, to understand the terminology read the [prologue](https://codeforces.me/blog/entry/102542)._ ### Transitions from a segment Very often after building the DP graph one can discover that the transitions into a state go not from a random set of vertices, but from some segment of values for one of the parameters. _For example, from states `dp[i][j]` with some constant `i` and `j` lying in a segment `[a, b]`._ **In such cases one may not implement each transition separately, but to implement them all at once.** If by implementing a transition we mean adding from `dp[A]` to `dp[B]`, then we can use prefix sums. In case if we need to find the _best_ transition into `dp[B]`, then we can use Segment Tree. #### An Example [AtCoder DP Contest: Problem M](https://atcoder.jp/contests/dp/tasks/dp_m) _Find the number of integer seq...
after building the DP graph one can discover that the transitions into a state go not from a random

Full text and comments »

  • Vote: I like it
  • +188
  • Vote: I do not like it

24.
[Tutorial] Generating Functions in Competitive Programming (Part 2)
By zscoder, history, 6 years ago, In English
[Tutorial] Generating Functions in Competitive Programming (Part 2) Welcome to Part 2 of my tutorial on generating functions. The [first part](https://codeforces.me/blog/entry/77468) focused on introducing generating functions to those without any background in generating functions. In this post, I will demonstrate a few applications of generating functions in CP problems. Let us start with some relatively straightforward examples. Note: Unless stated otherwise, all computations are done modulo a convenient prime (usually $998244353$). Also, $[n]$ denotes the set $\\{1,2,...,n\\}$. ### Blatant Applications in Counting Problems **Problem.** [AGC 005 Problem F](https://atcoder.jp/contests/agc005/tasks/agc005_f) You have a tree $T$ with $n$ vertices. For a subset $S$ of vertices, let $f(S)$ denote the minimum number of vertices in a subtree of $T$ which contains all vertices in $S$. For all $1 \le k \le n$, find the sum of $f(S)$ over all subsets $S$ with $|S| = k$. Constraints: $n \le 2 \cdot 10^{5}$. <spoiler summary="Solution"> First, ...
}}$ (the product of the number of sequences of switch flips such that switch $i$ is flipped exactly $a_{i

Full text and comments »

  • Vote: I like it
  • +518
  • Vote: I do not like it

25.
Editorial of Codeforces Global Round 21
By feecIe6418, 4 years ago, In English
Editorial of Codeforces Global Round 21 Thanks for participation! If your solution to D involves any data structures and is not $O(n)$ -- please read the "solution 1". I believe it is very interesting, but to make the difficulty suitable for D we allowed not $O(n)$ solutions. [problem:1696A] <spoiler summary="Hint 1"> How many operations will we perform? <spoiler summary="Answer"> At most one. Why? </spoiler> </spoiler> <spoiler summary="Solution"> Suppose we can only perform exactly one operation. In this case the answer is $S=\max_{1\le i\le n}(a_i\mathrm{\ or\ }z)$. In fact, we can prove that this is the answer. Define $a_i'$ as the value of $a_i$ after some operations. It suffices to prove the answer will never exceed $S$. Note that $z$ will always become a submask of itself after any number of operations, so $a_i$ will always be a submask of $(a_i\mathrm{\ or\ }z)$ after any number of operations. This leads to the conclusion that $a_i'\le (a_i\mathrm{\ or\ }z)$ for all $i$. Thus $\max_{1\le i...
hints first to understand the solution better. Construct a graph with $\binom n2$ vertices $(1,2

Full text and comments »

  • Vote: I like it
  • +332
  • Vote: I do not like it

26.
Codeforces Beta Round #26 tutorial
By slycelote, 16 years ago, In English
Codeforces Beta Round #26 tutorial <h3>A. <a href="../../../contest/26/problem/A">Almost Prime </a></h3>This is a straightforward implementation problem: factor every number from 1 to n into product of primes and count the number of distinct prime divisors.<br><br><h3>B. <a href="../../../contest/26/problem/B">Regular Bracket Sequence </a></h3>Read the string from left to right and calculate the balance of brackets at each step (i.e., the difference between the number of "(" and ")" characters written out). We need to keep this balance non-negative. Hence, every time when the balance equals 0 and we read the ")" character, we must omit it and not write it out. The answer to the problem is twice the number of ")" characters that we wrote out.<br><br><h3>C. <a href="../../../contest/26/problem/C">Parquet </a></h3>We'll derive several necessary conditions for the parquet to be possible. If some of them is not fulfilled, the answer is "IMPOSSIBLE".<br><b>1.</b> m*n must be even, because it equals the to...
straightforward implementation problem: factor every number from 1 to n into product of primes and count the

Full text and comments »

  • Vote: I like it
  • +24
  • Vote: I do not like it

27.
Editorial of Virtual Farewell IIT (ISM) Dhanbad
By cjchirag7, 6 years ago, In English
Editorial of Virtual Farewell IIT (ISM) Dhanbad Here, we present you the Editorial for the [Virtual Farewell IIT (ISM)](https://codeforces.me/contestInvitation/a52c365430f69a8f04d28eafb2cad804d392072c). I hope you enjoyed the contest !! [A. Farewell or Best Wishes](https://codeforces.me/gym/102625/problem/A) ----------------- **Author :** [user:chefpr7,2020-06-21] <spoiler summary="Tutorial"> Firstly, if the office is located anywhere in the path of the auto, then their plan will always fail, i.e if $X=1$ or $Y=M$ then best wishes are on the way. Otherwise, the auto can meet the agents only in the cells ($1$, $Y$) or ($X$, $M$). The time needed to reach these cells can be obtained in $O$($1$). Agent A initially headed North reaches the cell ($1$, $Y$) at time $t$ = $Y$-$1$ and after that it comes back at intervals of $2*(N-1)$. So all we need to do is check whether the time taken by the auto to reach any of the two cells is a term in the arithmetic progression of time taken by an agent to reach that cell. If we ch...
edge may not be in one of the connected components of the graph constructed so far. Thus for this, , our graph is a tree, so the shortest paths are unique between any two nodes. We have to find for

Full text and comments »

  • Vote: I like it
  • +48
  • Vote: I do not like it

28.
Nice trick involving sparse matrix exponentiation (kind-of)
By bicsi, history, 6 years ago, In English
Nice trick involving sparse matrix exponentiation (kind-of) Recently, I’ve figured out a way to improve matrix exponentiation-like algorithms for sparse matrices. I’m pretty sure that some of you might find this being _elementary linear algebra_, but I’m pretty proud of my discovery, so I’m going to write a blog post about it. I've marked some TODOs and ideas in square brackets, in case you want to help me enhance this. ### Prerequisites Cayley-Hamilton theorem, Berlekamp-Massey algorithm, fast linear recurrence solvers. ### Terminology - $M$ is an $n \times n$ “sparse” matrix, with $m$ entries different than $0$. - $k$ is the exponent. Complexities will be written in terms of $n, m, k$. ### Cayley-Hamilton theorem One of the most astonishing theorems in my opinion, what the theorem says is that for any $n \times n$ matrix, there exists some coefficients $c_i$ such that. $M^n = \sum_{i = 1}^n c_i M^{n - i}$ $c$ is often called the **characteristic polynomial** of $M$. This theorem essentially says that the powers...
that a matrix-vector product $Mv$ can be computed in complexity $O(m)$). Summing up, we can do the

Full text and comments »

  • Vote: I like it
  • +178
  • Vote: I do not like it

29.
Everything About Dynamic Programming
By Karan2116, history, 11 years ago, In English
Everything About Dynamic Programming **I decided to gather some good material on the web related to DP and found some good explanation by svg on topcoder forums..Hence wrote this blog.Will format it when i get time.** ![ ](http://codeforces.me/predownloaded/2c/af/2caf058ab9cf6db0f875c573fb0d6e73de572122.png) **Problem:** About 25% of all SRM problems have the "Dynamic Programming" category tag. The DP problems are popular among problemsetters because each DP problem is original in some sense and you have to think hard to invent the solution for it. Since dynamic programming is so popular, it is perhaps the most important method to master in algorithm competitions. The easiest way to learn the DP principle is by examples. The current recipe contains a few DP examples, but unexperienced reader is advised to refer to other DP tutorials to make the understanding easier. You can find a lot of DP examples and explanations in an excellent tutorial Dynamic Programming: From novice to advanced by Dumitru. The purpose ...
mappings of the tree on the graph. First of all, we choose root of the tree because it is easier to, result is not zero — prune impossible states for (int q = 0; qgraph[p, — full image of current domain for (int q = 0; qgraph[p][q

Full text and comments »

  • Vote: I like it
  • +90
  • Vote: I do not like it

30.
DP Tutorial and Problem List
By Ahnaf.Shahriar.Asif, history, 7 years ago, In English
DP Tutorial and Problem List Today I've listed some DP tutorials and problems. Actually, I made it for my personal practice. But I think It may Help others too. Update: I write stuff [Here](https://duoblogger.github.io) in Bengali. I probably have one or two basic DP tutorials too. If you understand Bengali, it may help. **Note: If you have some other tutorial links and nice problems, mention them. I'll add them here. It'll help me too.** ## Dynamic programming: * [Topcoder Tutorial](https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/) * [Dynamic Programming,from novice to advanced](https://www.cnblogs.com/drizzlecrj/archive/2007/10/26/939159.html) * [Learn DP and other tricks](https://www.codechef.com/certification/data-structures-and-algorithms/prepare#foundation) * [Non-trivial DP tricks](https://codeforces.me/blog/entry/47764) * [Everything about Dynamic Programming](https://codeforces.me/blog/entry/43256) * [Digit DP 1](https://...
solutions of digit dp problems](https://codeforces.me/blog/entry/7221) * [digit Dp forproduct digits, /blog/entry/7221) * [digit Dp for product digits](https://codeforces.me/blog/entry/53286) * [Digit

Full text and comments »

  • Vote: I like it
  • +301
  • Vote: I do not like it

31.
Codeforces Beta #27 - Tutorial
By Fefer_Ivan, 16 years ago, translation, In English
Codeforces Beta #27 - Tutorial <p> <size =="" 18=""><strong>A. <a href="http://codeforces.me/contest/27/problem/A">Next Test</a></strong></size><br> We will create an array of boolean used[1..3001] ans fill it with "false" values. For each of n given number, we will assign corresponding used value to "true". After that, the index of first element of used with "false" value is the answer to the problem.<br><br> <size =="" 18=""><strong>B. <a href="http://codeforces.me/contest/27/problem/B">Tournament</a></strong></size><br> To solve this problem first of all we should find such numbers A and B that occur in the input data not (n - 1) times, but (n - 2). We can notice, that winner-loser relation in this problem is transitive. This means that if X wins against Y and Y wins against Z, than X wins against Z. So to find out who is harsher A or B, let's look for such C, that the results of the match A with C and B with C are distinct. If such C exists, than the one, who wins against C should be printed first. I...
> Let's build the graph. Vertexes will correspond to segments/roads and edge between vertexes i and j

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it

32.
The Competitive Programmer's Guide to Graph Theory
By albeXL, history, 2 years ago, In English
The Competitive Programmer's Guide to Graph Theory Hello there, As some might know, I am a double ICPC World Finalist and Computer Scientist. I compiled a collection of graph theory problems to help you become more proficient in Bipartite Graphs, Functional Graphs, and Eulerian Paths. This is a comprehensive list of 15 problems of medium to hard difficulty, with all the reasoning and formal proofs needed to solve them. It goes deeper than the usual experience of solving problems in competitive programming, where the formal aspect is usually overlooked. The problems are taken from: - Codeforces - AtCoder - Andrew Stankevich Contests - ICPC World Finals This book is for you if you are up for a challenge and willing to allocate time to solving these 15 problems. The ideas exposed here are not only challenging but also some of the most beautiful ones I was exposed to during my competitive programming years. This book is also for you if you are a complete beginner in graph theory. It contains an introductory secti...
The Competitive Programmer's Guide to Graph Theory, compiled a collection of graph theory problems to help you become more proficient in Bipartite Graphs, - It takes time and effort to create a product with this depth., By purchasing this product, you will gain access to the current draft and receive all future

Full text and comments »

  • Vote: I like it
  • -17
  • Vote: I do not like it

33.
Codeforces Round #295 Editorial (now with bonuses!)
By Endagorion, 12 years ago, In English
Codeforces Round #295 Editorial (now with bonuses!) We would like to thank the testers of this round's and Winter Computer Camp olympiad's problems: [user:alger95,2015-03-02], [user:thefacetakt,2015-03-02], [user:adamant,2015-03-02], [user:dragonic,2015-03-02], [user:Who179,2015-03-02], [user:ASverdlov,2015-03-02]. Make sure to comment if you find any mistakes. **UPD**: I've just remembered to put up the usual challenges for the problems. So, here they go. [problem:520A] Idea: [user:Endagorion,2015-03-02] Preparation: [user:Endagorion,2015-03-02] To check that every letter is present in the string we can just make a boolean array of size 26 and for every letter set the corresponding variable to TRUE. In the end check that there are 26 TRUEs. That is an $O(n)$ solution. Also don't forget to change all letters to lowercase (or all to uppercase). To make all the letters lowercase, one could use standard functions, like `tolower` in Python. Also, it is known that the letters from `a` to `z` have consecutive ASCII numbe...
-02] The simplest solution is simply doing a breadth-first search. Construct a graph with numbers

Full text and comments »

  • Vote: I like it
  • +151
  • Vote: I do not like it

34.
Beyond the Contest: How Competitive Programming Powers Real Life and Sports
By saanTH, history, 4 months ago, In English
Beyond the Contest: How Competitive Programming Powers Real Life and Sports If you've ever done competitive programming (CP), you know the drill — segment trees at 2 AM, dynamic programming (DP) transitions that make your head spin, graphs that refuse to be traversed efficiently. It's easy to dismiss this as "just contest stuff." But the truth is, almost every algorithm you grind on Codeforces or LeetCode has a real job somewhere in the world — and one of the most fun places to see this is sports. This post covers two things: Everyday, real-life uses of classic CP concepts. A deep dive into how algorithms — especially DP — quietly run the show in cricket, tennis, basketball, football, chess, and more. **Part 1: CP Concepts You Already Know, Working in the Real World** **** **Sorting & Searching** **** Every time you sort products by price on Amazon or search for a contact on your phone, you're using variants of merge sort, quicksort, or binary search. Databases use B-trees (a generalization of binary search trees) to fetch records in logari...
logarithmic time instead of scanning millions of rows. **** **Graph Algorithms** **Google Maps, . **** **Graph Algorithms**

Full text and comments »

  • Vote: I like it
  • -22
  • Vote: I do not like it

35.
[Tutorial] Voronoi Diagram and Delaunay Triangulation in O(n log n) with Fortune's Algorithm
By Monogon, history, 6 years ago, In English
[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...
graph of boundaries between regions. A vertex in this graph is where three or more segments meet

Full text and comments »

  • Vote: I like it
  • +499
  • Vote: I do not like it

36.
More on D-Finite Functions II: Problems
By Elegia, history, 22 months ago, In English
More on D-Finite Functions II: Problems After finishing this part, I found out some of them are not that related to D-Finite functions (especially for the last section), but in these problems, we still need some insight to deal with differential operators. So I'll keep them here. ## Sums involving powers Let's consider the following problem of summation $$ \sum_{0\leq n \leq M} f(n) \cdot n^k, $$ where $M$ can be finite or infinite. We want to separate a large class of $f$ such that such summation can be solved in $O(k)$. You may already know some examples: - For the constant function $f(n) = 1$, known as [662F](https://codeforces.me/problemset/problem/622/F), can be solved in linear time through Lagrange interpolation on consecutive sampling points. - For the geometric series $f(n) = r^n$, you can find the [finite case](https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomial) and [infinite case](https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomial_limit) (assume $|r| < 1$) in Libra...
](https://atcoder.jp/contests/agc069/tasks/agc069_e). ## Graph Enumeration Problems **PA 2019

Full text and comments »

  • Vote: I like it
  • +113
  • Vote: I do not like it

37.
Codeforces round #716 editorial
By mohammedehab2002, 6 years ago, In English
Codeforces round #716 editorial ### [problem:1514A] If any element is not a perfect square, the answer is yes. Otherwise, the answer is no, because $a^2*b^2*...=(a*b*...)^2$. Code link: https://pastebin.com/s83sFt3G ### [problem:1514B] Let's start with an array where every single bit in every single element is $1$. It clearly doesn't have bitwise-and equal to $0$, so for each bit, we need to turn it off (make it $0$) in at least one of the elements. However, we can't turn it off in more than one element, since the sum would then decrease for no reason. So for every bit, we should choose exactly one element and turn it off there. Since there are $k$ bits and $n$ elements, the answer is just $n^k$. Code link: https://pastebin.com/0D8yL5WW ### [problem:1514C] So first observe that the subsequence can't contain any element that **isn't** coprime with $n$. Why? Because then its product won't be coprime with $n$, so when you take it modulo $n$, it can't be $1$. In mathier words, $gcd(prod \space mod \s...
contain any element that **isn't** coprime with $n$. Why? Because then its product won't be coprime

Full text and comments »

  • Vote: I like it
  • +135
  • Vote: I do not like it

38.
Codeforces Round #296 Editorial
By Zlobober, 12 years ago, translation, In English
Codeforces Round #296 Editorial [problem:527A] ============== It’s easy to see that described process is equivalent to the following loop: ~~~~~ while a > 0 and b > 0: if a ⩾ b: a = a - b else: b = b - a ans = ans + 1 ~~~~~ But such naive approach will obviously lead to verdict TLE, since it makes ~$10,2015-03-19^{12}$ operations even on the third sample test. The key idea is to replace repeating subtraction operations with integer division operations. This leads to the logarithmic-time solution that looks similar to the Euclid algorithm: ~~~~~ while a > 0 and b > 0: if a ⩾ b: ans = ans + a div b a = a mod b else: ans = ans + b div a b = b mod a ~~~~~ [problem:527B] ============== The first observation is that the new Hamming distance may not be less than the old one minus two, since we change only two characters. So the task is to actually determine, if we can attain decrease by two, one or can’t attain decrease ...
is the one that is product of the largest horizontal segment by the largest vertical segment. One of

Full text and comments »

  • Vote: I like it
  • +55
  • Vote: I do not like it

39.
Codeforces Round #140 Editorial
By Malinovsky239, 14 years ago, translation, In English
Codeforces Round #140 Editorial ### [A div2. Where do I Turn?](http://codeforces.me/contest/227/problem/A) Let's consider cross product of vectors $\overrightarrow{AB}$ and $\overrightarrow{BC}$, which is equal to $\overrightarrow{AB_x} \cdot \overrightarrow{BC_y} - \overrightarrow{AB_y} \cdot \overrightarrow{BC_x}$. Sign of cross product defines sign of a sine of oriented angle between vectors (because cross product is also equal to $|\overrightarrow{AB}| \cdot |\overrightarrow{BC}| \cdot sin(\overrightarrow{AB}, \overrightarrow{BC})$), and that sign leads us to the correct answer. If cross product is equal to zero, then $A, B$ and $C$ lay on the same straight line. So the answer is <<TOWARDS>>. If cross product is more than zero, then answer is <<LEFT>>. And, at last, if it's less than zero, the answer is <<RIGHT>>. Also you should notice that the value of cross product doesn't fit 32-bit type, so you have to use 64-bit type in order to avoid integer overflow. [Implementation](http://pastebin.co...
Consider the following interpretation of the problem: stone piles are graph vertices. Operation, product of vectors $\overrightarrow{AB}$ and $\overrightarrow{BC}$, which is equal to

Full text and comments »

  • Vote: I like it
  • +57
  • Vote: I do not like it

40.
Codeforces Trainings Season 2 Episode 8: Editorial
By Xellos, 12 years ago, In English
Codeforces Trainings Season 2 Episode 8: Editorial [Complete problemset + tests + original presentation of solutions.](http://www.bapc.eu/problemset.zip) [Official scoreboard](http://bapc.eu/scoreboards/bapc/), [public contest scoreboard](http://www.bapc.eu/scoreboards/public/), [used for training elsewhere](http://www.cs.ubc.ca/~acm-web/practice/2014-10-25/scores.php). Short hints first, more detailed solutions afterwards. ### A. Avoiding the Apocalypse (difficulty: medium-hard, [code](http://ideone.com/JQOMyq)) Maxflow in a suitably selected graph. Ford-Fulkerson is sufficient. <hr> The vertices of our graph need to correspond to states that one person can be in when traversing the original road network; the number of people moving in a group is then represented by flow along edges. Therefore, the most natural choice is to use vertices corresponding to states (location, time). The rules from the problem statement say that at most $c$ people can move along an edge $e=(u->v)$ in the original at any time. That me...
suitably selected graph. Ford-Fulkerson is sufficient. The vertices of our graph need to

Full text and comments »

  • Vote: I like it
  • +116
  • Vote: I do not like it

41.
Codeforces Round #309 Editorial
By Lewin, 11 years ago, In English
Codeforces Round #309 Editorial [Div2A: Kyoya and Photobooks](http://codeforces.me/contest/554/problem/A) ----------------------- Solving this problem just requires us to simulate adding every character at every position at the string, and removing any duplicates. For instance, we can use a HashSet of Strings in Java to do this (a set in C++ or Python works as well). Bonus: Prove that the number of ways is always (length of string + 1) * 25 + 1. Example code: http://codeforces.me/contest/554/submission/11767578 [Div2B: Ohana Cleans Up](http://codeforces.me/contest/554/problem/B) ----------------------- For each row, there is only one set of columns we can sweep so it becomes completely clean. So, there are only $n$ configurations of sweeping columns to look at. Checking a configuration takes $O(n^2)$ time to count the number of rows that are completely clean. There are $n$ configurations in all, so this takes $O(n^3)$ time total. Alternatively, another way of solving this problem is finding the m...
coefficients then evaluate the product. Example code: http://codeforces.me/contest/553/submission/11767584

Full text and comments »

  • Vote: I like it
  • +115
  • Vote: I do not like it

42.
Duality in linear programming. Part 2 — in competitive programming
By adamant, history, 4 years ago, In English
Duality in linear programming. Part 2 — in competitive programming Hi everyone! Previously, I wrote a [general introduction](https://codeforces.me/blog/entry/105049) to linear programming duality. In this blog, I would like to write about several problems that could be solved with this technique. Familiarity with the first blog, or general knowledge of dual problems and how to construct them is generally expected to navigate in this one. Thanks to [user:brunovsky,2022-08-09] and [user:Golovanov399,2022-08-09] for problem suggestions! And particularly special thanks to [user:WeakestTopology,2022-08-09] for problem suggestions and all insightful discussions on the topic! [cut]<br> ### Dual construction mnemonics To simplify the construction of dual problems, let's recall the correspondence between constraints/variables in primal and dual problems. <spoiler summary="LP duality mnemonics"> Standard definition of LP dual problem looks like this: $$\begin{gather} \max\limits_x & c^\top x & \color{red}{\text{(maximization)}} & \ove...
/problemsets/acmsguru/problem/99999/206)**. Given a weighted graph and its spanning tree $T$, you need

Full text and comments »

  • Vote: I like it
  • +169
  • Vote: I do not like it

43.
Essentials of Elementary Number Theory
By Everule, history, 5 years ago, In English
Essentials of Elementary Number Theory This is a blog starting from the very basics of number theory, in a way that flows fluidly from one concept to another and is based in developing an intuitive feeling for the basics of elementary number theory. This is not a blog to simply gloss over. I consider more of a guided exploration into the world of discovering things in the world of number theory, and I don't expect anyone to immediately understand all the insights in this blog. But if you put an honest effort into discovering how I find these insights you will find much use for my blog. If you do not know some notation or some elementary theorem I use you should refer to this. <spoiler summary="Elementary definitions"> We start with the basic definition that is at the heart of number theory. Let $a \mid b$ (read a divide(s) b) for some $a,b \in \mathbb{Z}$ for some if there exists $k \in \mathbb{Z}$ such that $b = ak$. Similarly $a \not\mid b$ if there does not exist such $k$. If $g \mid a$, then $g \mid ab$. ...
graph with $V = RRS$ and $E = (a,ax)\ \forall\ a \in V$. Let us now analyse this graph. As we have

Full text and comments »

  • Vote: I like it
  • +308
  • Vote: I do not like it

44.
AtCoder Regular Contest #111 Livesolve [A-D]
By nika-skybytska, 6 years ago, In English
AtCoder Regular Contest #111 Livesolve [A-D] CF seems to be the most reasonable place to post about AtCoder, as there are no blogs on AtCoder itself, so here we go. [Problems](https://atcoder.jp/contests/arc111), [my solutions](https://github.com/Sky-Nik/AtCoder/tree/main/arc111), [YT video](https://www.youtube.com/watch?v=ckAmjtXRpaA&feature=youtu.be&ab_channel=NikitaSkybytskyi). Short text editorial: A. If $10^N = A \cdot M^2 + B \cdot M + C$ then answer is $B$, and it remains to compute $10^N \pmod{M^2}$ with binary exponentiation. B. Cards form a graph. Connected components can be optimized independently. We can take all vertices from a component iff it is not the tree. Otherwise, we can take all vertices but one. C. Every permutation is a product of cycles. Process people in the increasing order of weight. Every cycle (and hence the entire permutation) will be resolved optimally unless you ran into smth that makes overall permutation impossible. D. If `c[u] > c[v]` then we must have `u -> v` as all vertices...
exponentiation. B. Cards form a graph. Connected components can be optimized independently. We can take all

Full text and comments »

  • Vote: I like it
  • +43
  • Vote: I do not like it

45.
Topcoder SRM #661 Anti-insomnia Member Editorial
By Endagorion, history, 11 years ago, In Russian
Topcoder SRM #661 Anti-insomnia Member Editorial There's always a problem to fall asleep after a late night (early morning) match, also drinking coffee during competition doesn't exactly help with that. So, here comes a rough write-up of div1 problems. #### 250 &mdash; MissingLCM As one can verify easily using prime factorization theorem, the LCM of a set of numbers is $\prod_{p\text{ is prime}} p^{\alpha_p}$, where $\alpha_p$ is the maximal power of $p$ which divides some element of the set. Let us find largest $p^t \leq n$ for every prime $p \leq n$; there should be a number in $[n + 1; m]$ that divides $p^t$ as well. Thus, $m \geq p^t (\lfloor \frac{n}{p^t} \rfloor + 1)$; there is a case when the new number divides some greater power of $p$, but we're fine with that. Find the greatest lower constraint for all $p \leq n$. Use the Eratosphene's sieve to find all the primes. An $O(n)$ solution is possible. #### 450 &mdash; ColorfulLineGraphs Consider vertices from left to right. How many ways there are to place a new vert...
, possibly with an edge. The answer is simply the product $k \cdot (k + (k - 1)) \cdot (k + 2(k - 1

Full text and comments »

  • Vote: I like it
  • +48
  • Vote: I do not like it

46.
General ideas
By adamant, 10 years ago, translation, In English
General ideas **// Finally translated!** Hi everyone! Do you like ad hoc problems? I do hate them! That's why I decided to make a list of ideas and tricks which can be useful in mane cases. Enjoy and add more if I missed something. :) [cut]<br> **1. Merging many sets in $O(n\log{n})$ amortized.** If you have some sets and you often need to merge some of theme, you can do it in naive way but in such manner that you always move elements from the smaller one to the larger. Thus every element will be moved only $O(\log{n})$ times since its new set always will be at least twice as large as the old one. Some versions of DSU are based on this trick. Also you can use this trick when you merge sets of vertices in subtrees while having dfs. **2. Tricks in statements, part 1.** As you may know, authors can try to hide some special properties of input to make problem less obvious. Once I saw constraints like $\relax 1 \leq a \leq b \leq 10^5, \dots, ab \leq 10^5$. Ha-ha, nice joke. It is actually...
). ([user:amd,2016-11-16]'s problem from Hunger Games) **6. Cycles in graph as linear space.** Assume every

Full text and comments »

  • Vote: I like it
  • +296
  • Vote: I do not like it

47.
Everything on Mo's Algorithm
By saurabhyadavz, 6 years ago, In English
Everything on Mo's Algorithm > Possibly, someone called "MO" once used the trick in a local contest, and the name stuck and later got popular. I have never encountered the name "Mo's algorithm" outside of competitive programming. > The technique, or the term "Mo's Algorithm" ("莫隊算法" in Chinese) was originally thought of and popularized by 莫涛 (Mo Tao) and his teammates. >It was first used to tackle a problem from 2009 China IOI Camp: 小Z的袜子(hose) — authored by 莫涛 himself. The problem was: given a sequence of integers, for any given interval, calculate the probability of choosing any 2 numbers and the 2 numbers are equal. _Now let's start. I have here compiled the tutorial, some articles written by me, and problems on Mo's algorithm._ ### Tutorials: - [**Sqrt Decomposition**](https://cp-algorithms.com/data_structures/sqrt_decomposition.html) - [**Introduction to Mo's algorithm**](https://blog.anudeep2011.com/mos-algorithm/) &mdash; By [user:anudeep2011,2020-08-20] - [**Introduction to Mo's algorithm**(...
-values-within-the-range-a-to-b-using-mos-algorithm/) - [Queries for Count of divisors of theproduct

Full text and comments »

  • Vote: I like it
  • +243
  • Vote: I do not like it

48.
Codeforces Round #143 (Div. 2) Editorial
By Igor_Kudryashov, 14 years ago, translation, In English
Codeforces Round #143 (Div. 2) Editorial [problem:231A] It is needed just to implement actions described in statement. You had to read data and to calculate number of members of team, which were sure about the solution, for every task. If this number is greater than one, the answer must be increased by one. [problem:231B] Let's see, what will be the last number of array after $i$ iterations. After the first iteration it will be $a_{n-1} – a_n$ (and total number of elements will be decreased by one). After the second iteration the last number will be $a_{n-2} – a_{n-1} + a_n$. It is not hard to see, that after $n-1$ iterations remain $a_1 – a_2 + a_3 – a_4 + \dots + (-1)^{n+1} \cdot a_n$. In a such way, our task is to put numbers from $1$ to $l$ in array so, that sum of numbers in odd positions minus sum of numbers in even positions will equal to given $d$. This means sum of numbers in odd positions must be equal $s = d + a_2 + a_4 + \dots + a_{n – n \mod 2}$. But the minimal sum can be $minv = \frac{n+1}{2}$, and the...
than $90$ degrees, we can observe $a$ from $p$. For checking this we can use scalarproduct. If scalar

Full text and comments »

  • Vote: I like it
  • +39
  • Vote: I do not like it

49.
Abstract setup of problems solvable using Linear Algebra in Competitive Programming
By timeisvaccum, history, 10 months ago, In English
Abstract setup of problems solvable using Linear Algebra in Competitive Programming Background ================== Today I gave Atcoder [ABC442](https://atcoder.jp/contests/abc442). In problem E, I observed some analogy of setup of this problem with concepts of Linear Algebra. Observations ================== 1. Monsters are depicted as vectors in R^2 From Linear Algebra perspective, every monster i at coordinates (xi,yi) is a vector [Xi Yi]^transpose in the vector space R^2.Takahashi stands at the origin (the zero vector). When he faces a monster, he is aligning his "sight vector" with the subspace spanned by that monster's vector. 2. The problem frequently asks if two monsters are in the "same direction." In Linear Algebra, two non-zero vectors u and v are collinear (linearly dependent) if one is a scalar multiple of the other. 3. Quadrant/Basis Partitioning:The space R^2 is divided by the standard basis vectors i = (1,0) and j = (0,1). We can partition the plane into two half-planes (Upper and Lower) based on the sign of the y-component (and x-comp...
"cross product"). 4. Linear Algebra doesn't naturally have a "start" and "end" for angles like $0

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

50.
Personal thoughts on learning and improvement
By Timosh, 2 months ago, In English
Personal thoughts on learning and improvement _Recently, some people have asked for advice, so I decided to write a blog._ In this blog, I will talk about my approach to problem-solving, what I think about solving problems, how do I learn techniques, data structures and/or algorithms and others. ### Solving is guessing From my interpretation, solving any problem is just some sort of guessing: making an educated guess of the solution, validating, and repeating until solved. You can speed up the "guessing procedure" by simplifiying the problem to a certain degree by, for example, not considering obviously wrong solutions. ### Abstraction and Decomposition Usually, as soon as I finish reading a problem, I try to simplify it as much as possible. For example, sorting arrays, removing elements, handling simple cases, doing greedy decisions whenever can be done, rearranging formulas to more familiar ones, or decomposing the problems into several independent problems. You might even have to solve a harder problem, just becaus...
histograms, think of numbers as a product of prime numbers, if it's a problem related to number theory

Full text and comments »

  • Vote: I like it
  • +158
  • Vote: I do not like it

51.
AtCoder Beginner Contest 137 English Solutions
By Geothermal, history, 7 years ago, In English
AtCoder Beginner Contest 137 English Solutions Although AtCoder seems to be getting back to posting English editorials, I'm continuing to release some myself in case having the extra explanations helps some people. (Sidenote: Some of the provided submissions come from after the contest itself, because I had to leave midway through, before I got the chance to debug my E or write my F.) --- #A &mdash; +-X Just use your language's max function. As $A$ and $B$ are small, we don't need to worry about integer overflow. Runtime: $O(1).$ [Click here for my submission.](https://atcoder.jp/contests/abc137/submissions/6802607) --- #B &mdash; One Clue Let's try to find the minimum and maximum values in the answer. It's fairly easy to see that all integers between them will also be in the set. To find the minimum possible position of a black stone, we place $K$ black stones such that $X$ is at the maximum position. Then, the minimum position will thus be $X-K+1$, as we have $K-1$ black stones to the left of $X$....
$. Afterwards, we have a weighted directed graph (possibly with both positive and negative weights

Full text and comments »

  • Vote: I like it
  • +34
  • Vote: I do not like it

52.
VK Cup Round 3 editorial
By Zlobober, 12 years ago, translation, In English
VK Cup Round 3 editorial [problem:542A] -------------- Let's fix the TV channel window and look for a commerical having the largest intersection with it. There are four types of commercials: lying inside the window, overlapping the window and partially intersecting the window from the left and from the right. It's easy to determine if there is overlapping commercial: it's enough to sort commercials in increasing order of the left end and then while iterating over them from left to right, keep the minimum value of a right end of a commercial. If when we pass the window $j$ and see that current value of the maximum right end is no less than $b_j$ then there exists a commercial overlapping our window and the value is equal to the $(r_i - l_i) \cdot c_i$. Among all commercials that lie inside our window we need the longest one. It can be done by similar but a bit harder manner. Let's use sweepline method. While passing through the end of the commercial $r_i$, let's assign in some data structure (like seg...
] -------------- In order to solve this task it's good to understand how does thegraph corresponding the

Full text and comments »

  • Vote: I like it
  • +97
  • Vote: I do not like it

53.
8VC Venture Cup Announcement
By scott_wu, 11 years ago, In English
8VC Venture Cup Announcement <img src="http://assets.codeforces.com/images/8vc/8vc-venturecup-logo.png" style="float:right;margin:0 1em 1em 1em"/> Hey Codeforces! I’ve worked with Addepar and the broader 8 | family of companies in Silicon Valley throughout 2014 and 2015, and it’s been an excellent experience. I would encourage everyone in the community to learn more about the great work that these companies are doing and I’m happy to announce that 8 | Partners will be hosting the 8 | VC VentureCup on Codeforces! It’ll be a fun contest and I’ve worked on the problems along with a few competitive programmers in our network. The contest will begin on February 13 and consist of two rounds. ##### ABOUT 8 | PARTNERS <a href="http://eight.vc/">8 | Partners</a>, which consists of Joe Lonsdale (co-founder of Palantir) and his core team from Formation | 8, is a Silicon Valley venture capital firm that invests in industry-transforming technology companies. The team's investment portfolio includes companies suc...
growth companies. Our software is powered by the Radius Business Graph–a proprietary data science

Full text and comments »

  • Vote: I like it
  • +477
  • Vote: I do not like it

54.
Newton School Grand Coding Contest 2021 Editorial
By Sawarnik, 5 years ago, In English
Newton School Grand Coding Contest 2021 Editorial #### [A. Thor vs Loki](https://my.newtonschool.co/playground/code/waeqyqd0i8mw/) ------------------ <spoiler summary = "Solution"> The strength of Thor is $z - x$, and that of Loki is $z - y$. Thus, the maximum strength is $\text{max}(z-x, z-y)$. Equivalently, we can also say the maximum strength is $z - \text{min}(x, y)$. Complexity: $O(1)$ </spoiler> #### [B. Archery](https://my.newtonschool.co/playground/code/lyk5chtoejlx/) ------------------ <spoiler summary = "Hint 1"> Think of what strategy to take based on the number of monsters of each type. </spoiler> <spoiler summary = "Hint 2"> Think of what to do with types that have a large number of monsters. Then, think of what to do with the other ones. </spoiler> <spoiler summary = "Solution"> The optimal strategy is: 1. First, shoot down all monsters of a particular type if there are more than $k$ of them. Do this until there are no more types with more than $k$ monsters. 2. The remaining monsters can ...
of the task is pretty straightforward. We create a new graph, where each vertex corresponds to a

Full text and comments »

  • Vote: I like it
  • +88
  • Vote: I do not like it

55.
Codeforces Round #814 (Div. 1, Div. 2) Editorial
By SomethingNew, 4 years ago, In English
Codeforces Round #814 (Div. 1, Div. 2) Editorial Sorry for not very good samples, and late editorial. It was our first round, so it was wary stressful for us, But we hope you liked the problems despite this! [problem:1719A] <spoiler summary="Hint 1"> Try to look at the parity of $n, m$. </spoiler> <spoiler summary="Hint 2"> The player who wins does not depend on player's strategy. </spoiler> <spoiler summary="Hint 3"> The only thing that the winning player depends on is the parity of $n, m$. </spoiler> <spoiler summary="Tutorial"> Note that the game will end only when the chip is in the upper right corner (otherwise you can move it $1$ square to the right or up). For all moves, the chip will move $n - 1$ to the right and $m - 1$ up, which means that the total length of all moves is $n + m - 2$ (the length of the move is how much the chip moved per turn). Since the length of any move is odd, then after any move of Burenka, the sum of the lengths will be odd, and after any move of Tonya is even. So we can find...
\leq k \leq 3$. If $k = 0$, then there is no answer, because the product of the numbers in each

Full text and comments »

  • Vote: I like it
  • +129
  • Vote: I do not like it

56.
[Need help] Shortest path, but edge has 2 cost Ai and Bi, and cost of path is prod of sum Ai and Bi
By 3509, history, 4 years ago, In English
[Need help] Shortest path, but edge has 2 cost Ai and Bi, and cost of path is prod of sum Ai and Bi ##### Source My school hosted a local ICPC format contest yesterday, this problem appeared in it. Since it was for local only, I cannot provide link for submission (sorry!) ##### Statement Given a weighted undirected graph $G$ with $n$ vertices and $m$ edges. Edge $e_i$ is a tuple $(u_i, v_i, A_i, B_i)$ denotes there is an edge connects $u_i$ with $v_i$, with cost $A_i$ and $B_i$. Consider path $u \rightarrow v$ is a sequence of edges $E: \\{e_1, e_2,... e_k\\}$, cost of $E$ is defined as product of (sum of all $A_x$) and (sum of all $B_x$) with $x$ is an edge in $E$. Calculate shortest path from node $1$ to all other nodes. ##### Contraints - $1 \leq n, m \leq 2000$ - $1 \leq A_i, B_i \leq 2000$ There is no additional guarantees ##### Sample Tests ###### Input 1 <pre class="prettyprint">4 4 1 2 2 4 3 4 4 1 4 2 1 1 1 3 3 1 </pre> ###### Output 1 <pre class="prettyprint">8 3 14 </pre> Output shortest path from $1$ to $i (2 \leq i \leq n)$: <ul> <li> ...
Given a weighted undirected graph $G$ with $n$ vertices and $m$ edges. Edge $e_i$ is a tuple $(u_i, v_i, ##### Statement Given a weighted undirected graph $G$ with $n$ vertices and $m$ edges. Edge $e_i

Full text and comments »

  • Vote: I like it
  • +31
  • Vote: I do not like it

57.
Editorial of Educational Codeforces Round 2
By Edvard, history, 11 years ago, translation, In English
Editorial of Educational Codeforces Round 2 [problem:600A] This is a technical problem. You should do exactly what is written in problem statement. [problem:600B] Let's sort all numbers in a. Now let's iterate over elements of $b$ and for element $b_j$ find the index of lowest number that is greater than $b_j$. We can do that using binary search. That index will be the answer for value $b_j$. Complexity: $O(n logn)$. [problem:600C] Let's denote $cnt_c$ &mdash; the number of occurences of symbol $c$. Let's consider odd values $cnt_c$. Palindrome can not contain more than one symbol $c$ with odd $cnt_c$. Let's denote symbols with odd $cnt_c$ as $a_1, a_2 ... a_k$ (in alphabetical order). Let's replace any one of symbols $a_k$ with symbol $a_1$, $a_{k-1}$ with $a_2$ and so on until the middle of $a$. Now we have no more than one odd symbol. If we have some let's place it in the middle of the answer. First half of answer will contain $\frac{cnt_c}{2}$ occurences of symbol $c$ in alphabetical order. The second half ...
of absolute value of cross product. So we have the following formulas: $\alpha = arccos\left

Full text and comments »

  • Vote: I like it
  • +58
  • Vote: I do not like it

58.
Insomnia'26 Editorial
By tridipta2806, history, 8 months ago, In English
Insomnia'26 Editorial ####[Problem A : Ancient Trees](https://codeforces.me/gym/680528/problem/A) Problem Idea: [user:shorya1835,2026-03-23], Problem Preparation: [user:aastik231205,2026-03-23] <spoiler summary="Hint 1"> You are allowed to use intermediate vertices in your sequence. Does it ever actually help? For any three vertices $a$, $b$, $c$, what is the relationship between $c(a,b) + c(b,c)$ and $c(a,c)$? Recall that for non-negative integers, $x + y \geq x \oplus y$. </spoiler> <spoiler summary="Answer for Hint 1"> Since, $c(a,b) + c(b,c) \geq c(a,b) \oplus c(b,c)$, Splitting the path doesn't minimize the distance at all. Hence $d(u,v) = c(u,v)$ always. </spoiler> <spoiler summary="Hint 2"> Since $d(u,v) = c(u,v)$ always, we can maintain a running mask $M$ (XOR of all Type 1 updates so far). A path with $\ell$ edges has its XOR-distance changed only if $\ell$ is odd, flipping their XOR-distance by $M$, depending only on the running XOR of Type 1 queries so far. Can you precomput...
can be modeled into a directed graph, draw out some valid graphs for small n, what kind of graphs

Full text and comments »

Tutorial of Insomnia-26
  • Vote: I like it
  • +113
  • Vote: I do not like it

59.
Cool tricks using Matrix Exponential
By tweety, history, 11 years ago, In English
Cool tricks using Matrix Exponential <p>I'm going to share with you some cool applications of matrix exponential that I learned recently.</p> #### Application 1: Counting the number of ways for reaching a vertex <p>You are given an unweighted directed graph (may contain multiple edges) containing N vertices (1 <= N <= 200) and an integer b (1 <= b <= 10^9). You are also given Q queries (1 <= Q <= 10^5). For each query you are given two vertices u and v and you have to find the number of ways for reaching vertex v starting from u after exactly b steps. (A step is passing through an edge. Each edge may be passed multiple number of times).</p> <h5>Solution</h5> <p>Let M1 be a matrix where M1[i][j] equals the number of edges connecting vertex i to vertex j. Let M2 be M1 raised to the power of b (M1^b). Now for any pair u and v, the number of ways for reaching vertex v starting from u after b steps is M2[u][v].</p> <p>Practice problem: <a href="http://codeforces.me/contest/621/problem/E">621E</a> <br><br><br> #...
an unweighted directed graph (may contain multiple edges) containing N vertices (1 <= N <= 200) and

Full text and comments »

  • Vote: I like it
  • +39
  • Vote: I do not like it

60.
Oleksandr Kulkov Contest 3 in gym + tutorial and comments
By adamant, history, 4 years ago, In English
Oleksandr Kulkov Contest 3 in gym + tutorial and comments Hi everyone! As the [Universal Cup stage 7](https://codeforces.me/blog/entry/113640) which mirrored my contest from the [Osijek Competitive Programming Camp 2023](https://codeforces.me/blog/entry/113438) just concluded, I decided to also upload the contest to gym as [contest:104234], and post the tutorial here. I hope you enjoyed the contest! My previous ICPC-style contests: * [Oleksandr Kulkov Contest 1 in gym](https://codeforces.me/blog/entry/65678) * [Oleksandr Kulkov Contest 2 in gym](https://codeforces.me/blog/entry/72656) Compiled PDF Tutorial for all problems: [link](https://codeforces.me/gym/104234/attachments/download/19319/OKC3-tutorial.pdf). To make it worth a separate blog post, I will also add some brief meta comments :) P.S. Congratulations to the team **USA1** ([user:ecnerwala,2023-03-12], [user:ksun48,2023-03-12], [user:scott_wu,2023-03-12]) for solving all the problems in-contest! [cut]<br> ### [problem:104234A] Author: [user:adamant,2023...
] Author: [user:adamant,2023-03-11] See also: **[Hadamard product and binomial convolution of

Full text and comments »

  • Vote: I like it
  • +76
  • Vote: I do not like it

61.
Codeforces Round #238 Tutorial
By gen, 13 years ago, In English
Codeforces Round #238 Tutorial #### [problem:405A] Observe that in the final configuration the heights of the columns are in non-decreasing order. Also, the number of columns of each height remains the same. This means that the answer to the problem is the sorted sequence of the given column heights. Solution complexity: $O(n)$, since we can sort by counting. #### [problem:405B] If the first pushed domino from the left was pushed to the left at position $l$, all dominoes at prefix $[1;l]$ fall down, otherwise let $l$ be 0. Similarly, if the first pushed domino from the right was pushed to the right at position $r$, all dominoes at suffix $[r;n]$ also fall down, otherwise let $r$ be $n+1$. Now, in the segment $(l;r)$ there will remain vertical dominoes and blocks of dominoes supported by the equal forces from both sides. When does a domino at position $p$ in segment $(l,r)$ remains standing vertically? One way is that it is not pushed by any other domino. This could be easily checked by looking at the ...
product of the original matrix, and flip its value after each query of type 1 and 2. Solution

Full text and comments »

  • Vote: I like it
  • +80
  • Vote: I do not like it

62.
Problems that I Authored So Far
By TsReaper, 23 months ago, In English
Problems that I Authored So Far Hi everyone! As we're reaching the end of this year and as AI becomes smarter, I'd like to write such a blog, motivated by similar blogs [by](https://codeforces.me/blog/entry/108940) [user:adamant,2024-12-22], [by](https://codeforces.me/blog/entry/108595) [user:tibinyte,2024-12-22], [by](https://codeforces.me/blog/entry/113093) [user:antontrygubO_o,2024-12-22], [by](https://codeforces.me/blog/entry/113720) [user:wuhudsm,2024-12-22], [by](https://codeforces.me/blog/entry/113687) [user:xiaowuc1,2024-12-23], [by](https://codeforces.me/blog/entry/113213) [user:jqdai0815,2024-12-23], [by](https://codeforces.me/blog/entry/118825) [user:TheScrasse,2024-12-23] and [by](https://codeforces.me/blog/entry/127391) [user:satyam343,2024-12-22]. I am a member of the [SUA Programming Contest Problem Setter Team](https://sua.ac), so most of the problems I authored are for the onsite contests prepared by our team. I would like to thank all our team members for discussing the problems with me, ...
| 3000 | data structures | | | 159 | [Sum and Product ](https://qoj.ac/problem/17763) | 2026 ICPC

Full text and comments »

  • Vote: I like it
  • +126
  • Vote: I do not like it

63.
Codeforces Round #114 — Tutorial
By Dmitry_Egorov, 15 years ago, translation, In English
Codeforces Round #114 — Tutorial I am sorry for mistakes in English and I will be glad if you tell me about them. #### [problem:168A] Аuthor ~kuniavski,2012-03-27. In this task, it was necessary to write exactly what has been described in statement. In particular, it was necessary to have $\left\lceil \frac{N\cdot Y}{100} \right\rceil $ people, who come to the meeting. For this it was necessary to create $\max(0,\left\lceil\frac{N \cdot Y}{100} \right\rceil -X) $ clones. #### [problem:168B] Аuthor ~kuniavski,2012-03-27. In this problem you had to write exactly what has been described in statment too. Read lines one by one. Also keep the last block of lines that are not amplyfying. If the next line is amplyfying (which can be checked by linear search), we print the last block, if any, and the line itself. Otherwise, remove all spaces from the string and add to the last block.[cut] It only remains to distinguish between an empty block and a block of empty lines. #### [problem:167A] Аuthor ~Alex-G...
statement as clear as it possible in this problem. Consider this graph. In particular, we consider

Full text and comments »

  • Vote: I like it
  • +99
  • Vote: I do not like it

64.
Codeforces Round #278 Editorial
By taorunz, 12 years ago, In English
Codeforces Round #278 Editorial [problem:488A] -------------- The answer $b$ is very small (usually no larger than $10$), because one of $a+1,a+2, \cdots, a+10$ has its last digit be $8$. However, $b$ can exceed $10$ when $a$ is negative and close to $0$. The worst case is $a=-8$, where $b=16$. Anyway $b$ is rather small, so we can simply try $b$ from $1$, and check whether $a+b$ has a digit 8. [problem:488B] -------------- Let's sort the four numbers in ascending order: $a, b, c, d$ (where $x_1,x_2,x_3,x_4$ are used in problem statement). So $\frac{a+b+c+d}{4}=\frac{b+c}{2}=d-a$. With some basic math, we can get $a:d=1:3$ and $a+d=b+c$. **Solution 1:** If $n=0$, just output any answer (such as ${1,1,3,3}$). If $n=1$, just output ${x,x,3x,3x}$, where $x$ is the known number. If $n=4$, just check whether the four known numbers meet the condition. If $n=2$, let $x,y$ denote the known numbers ($x \leq y$). No solution exists if $3x < y$. Otherwise we can construct a solution ${x,y,4x-y,3x}$ ...
a_n = n! \equiv 0 \mod n$. If $n$ occurs in \{a_1,…,a_{n-1}\} in the prefix product sequence $0

Full text and comments »

  • Vote: I like it
  • +25
  • Vote: I do not like it

65.
Top Classic Data Structures Problems
By coolph, 6 years ago, In English
Top Classic Data Structures Problems I want to share collection of top 50 *classical* data structures problems from [this discussion on reddit](https://www.reddit.com/r/computerscience/comments/hcmxgp/top_50_classic_data_structures_problems/). 1. [2-Sum Problem](https://www.techiedelight.com/find-pair-with-given-sum-array/) 2. [Longest Common Subsequence Problem](https://www.techiedelight.com/longest-common-subsequence/) 3. [Maximum Subarray Problem](https://www.techiedelight.com/maximum-subarray-problem-kadanes-algorithm/) 4. [Coin Change Problem](https://www.techiedelight.com/coin-change-problem-find-total-number-ways-get-denomination-coins/) 5. [0–1 Knapsack Problem](https://www.techiedelight.com/0-1-knapsack-problem/) 6. [Subset Sum Problem](https://www.techiedelight.com/subset-sum-problem/) 7. [Longest Palindromic Subsequence Problem](https://www.techiedelight.com/longest-palindromic-subsequence-using-dynamic-programming/) 8. [Matrix Chain Multiplication Problem](https://www.techiedelight.com/matrix-chain...
. [Maximum Product Subarray Problem](https://www.techiedelight.com/find-maximum- product-subarray, Product Subarray Problem](https://www.techiedelight.com/find-maximum-product -subarray-given-array

Full text and comments »

  • Vote: I like it
  • +26
  • Vote: I do not like it

66.
Codeforces Round 1132 (Div. 2) Editorial
By eugenechka.boyko.2_0-0, 44 hours ago, translation, In English
Codeforces Round 1132 (Div. 2) Editorial #### [problem:2284A1] <spoiler summary="Hint"> It is sufficient to apply operations to only two points. </spoiler> <spoiler summary="Solution"> Let us prove that the maximum area is achieved if we shift one of the points by $\lfloor \frac{n}{2} \rfloor$ steps up, and the other by $\lceil \frac{n}{2} \rceil$ steps to the right. To do this, consider the bounding rectangle of the resulting triangle after all point shifts; let its side lengths be $a$ and $b$, respectively. We will show that its maximum area is precisely $\frac{ab}{2}$. Since triangle $ABC$ is inscribed in our rectangle, at least one of its vertices must coincide with a vertex of the rectangle. Without loss of generality, let this be vertex $A$. If we denote the angles adjacent to it by $\alpha$ and $\beta$, it can be shown that the maximum area is achieved when the value $\tan \alpha \cdot \tan \beta$ is minimized, which means it is equal to $0$ for $0 \le \alpha + \beta < \frac{\pi}{2}$. ![Fig. 1](/predownload...
optimal to set $a + b = n$ with the product $ab \le \lfloor \frac{n}{2} \rfloor \lceil \frac{n}{2

Full text and comments »

  • Vote: I like it
  • +32
  • Vote: I do not like it

67.
Codeforces Beta Round #23 tutorial
By slycelote, 16 years ago, translation, In English
Codeforces Beta Round #23 tutorial <h3>A. <a href="../../../contest/23/problem/A">You're given a string...</a></h3><br />Iterate over all substrings, starting with the longest ones, and for each one count the number of appearances. The complexity is $O(L^4)$ with a small multiplicative constant.<br />[cut]<br /><h3>B. <a href="../../../contest/23/problem/B">Party</a></h3><br />It's clear that at least one person (the one with the least number of friends) will have to leave. We claim that at least two persons will leave. Indeed, suppose that only one person left, and he had $d$ friends. Then all other people had more than $d$ friends before he left, and after that they had less than $d+1$ friends, i.e. not more than $d$. So, his leaving influenced the number of friends for every other person, which means that he was friends with everyone: $d=N-1$. But he has fewer friends than everyone — a contradiction.<br /><br />So, the answer is not more than $N-2$. We'll prove that it's possible for $N-2$ people to stay (of course, ...
, if $N>1$). The graph of friendship will be the following: take a complete graph on $N$ vertices

Full text and comments »

  • Vote: I like it
  • +27
  • Vote: I do not like it

68.
Codeforces Round #205 (Div. 2) Editorial
By Igor_Kudryashov, 13 years ago, translation, In English
Codeforces Round #205 (Div. 2) Editorial [problem:353A] Let's denote the sum of numbers on the upper halves of pieces as $s_1$, and the sum on the lower halves &mdash; $s_2$. If this sums are even, than the answer is obviously $0$. Note, that if the numbers on both halves of piece have the same parity, than parity of $s_1$ and $s_2$ won't change after rotation this piece. If the numbers on halves have different parity, than parities of both $s_1$ and $s_2$ will change after rotation. Therefore, if $s_1$ and $s_2$ have different parities, than the answer is $-1$. If both $s_1$ and $s_2$ are odd, than we should check, if there is a piece with numbers of different parities. If so, the answer is $1$, otherwise, the answer is $-1$. [problem:353B] Let's say for shortness, that we put numbers, that are painted on cubes, in piles, instead of cubes themselves. Note, that the answer is the product of $c_1 \dots c_2$, where $c_i$ is the number of different numbers in the $i$-th pile. Let's consider that all numbers are diffe...
piles, instead of cubes themselves. Note, that the answer is the product of $c_1 \dots c_2$, where

Full text and comments »

  • Vote: I like it
  • +32
  • Vote: I do not like it

69.
Разбор задач Codeforces Round #137 (Div. 2)
By izban, 14 years ago, translation, In English
Разбор задач Codeforces Round #137 (Div. 2) Problem A: Note that the k-th element is copied to the end. Then the (k+1)-th element from the initial sequence is copied, then (k+2)-th, … , n-th, k-th, (k+1)-th, etc. So all the numbers on the blackboard will become equal if and only if all the numbers from the k-th to the n-th in the initial sequence were equal. It's now also obvious that the number of operations needed for it is equal to the index of the last number that is not equal to the n-th element of the initial sequence, because it's exactly the number of deletions needed to eliminate the elements that are not equal to the last one. If this number is greater than k, than answer is -1. Complexity — O(n). Problem B: Let’s store the order of the rows and columns of table. Thus, row[x] is the number of the row x in the initial table and column[x] is the number of column x in the initial table. Then, the value of an element in the row x and column y in the current table is equal to t[row[x], column[y]], where t — i...
product <= 10^7), the count of numbers in the answer (n_out or m_out) will be bigger than 10^5

Full text and comments »

  • Vote: I like it
  • +52
  • Vote: I do not like it

70.
Lattice paths and Lindström–Gessel–Viennot lemma
By miaowtin, 4 years ago, In English
Lattice paths and Lindström–Gessel–Viennot lemma In August 2022, I had a talk concerning lattice paths at a summer programming school in Khust, Ukraine. After, I realised that some aspects of my talk aren't well-known in the CP community and, in this blogpost, I'd like to very briefly and untidily (so feel free to ask for additional explanations by comments) share the main points of that talk. I hope that ideas presented in the blog will help you sometime. **1. Lattice paths** **1.1. Walks without restrictions.** **1.1.1.** We start from a rudimentary example. Consider a $N\times M$ grid and a robot (or a chip, or a ship, or anything else you wish) at $(0,0)$ (not a cell, an intersection point) which can move in the east unit direction and in the north unit direction. A route that the robot is able to make is said to be northeastern. How many northeastern paths are there? In fact, We can bijectively code any path with a corresponding string of the form $\uparrow\rightarrow\rightarrow\rightarrow\uparrow\rightarrow\dots$ o...
monomials, not numbers). The cost of a path is a product of all the unit segments in it. That is the

Full text and comments »

  • Vote: I like it
  • +198
  • Vote: I do not like it

71.
9 hardest CSES problems. Hints&solutions.
By Rvess, history, 21 month(s) ago, In English
9 hardest CSES problems. Hints&solutions. [CSES](https://cses.fi/) is a well-known resource. It has many problems from a variety of topics. Solutions to almost every problem can be found online. But for some hard problems there are no editorials yet. Getting stuck on these difficult problems can lead to frustration, which is why I decided to write solutions to them. ### [Inversion Probability](https://cses.fi/problemset/task/1728) <spoiler summary="Hint 1"> The intended solution is not difficult. The tricky part is rounding off the number. </spoiler> <spoiler summary="Hint 2"> long double doesn't work. Find out why. </spoiler> <spoiler summary="Hint 3"> Use long arithmetic. </spoiler> <spoiler summary="Solution"> For each pair $(i, j)$, the probability of it being an inversion is: \begin{cases} \displaystyle \frac{r_i &mdash; 1}{2 r_j} & \text{if } r_i \leq r_j, \\ \displaystyle \frac{2 r_i &mdash; r_j &mdash; 1}{2 r_i} & \text{if } r_i > r_j. \end{cases} The answer is the sum of probabil...
arithmetic. Let's take the denominator as twice the product of the given numbers. Compute the numerator

Full text and comments »

  • Vote: I like it
  • +58
  • Vote: I do not like it

72.
How to solve this array based problem ? | Unsolved since 5 years | Try it
By Greatest789, history, 6 years ago, In English
How to solve this array based problem ? | Unsolved since 5 years | Try it Given 2-arrays "$A$" and "$B$" of length $n$ , calculate maximum possible product of all elements of array "$C$" , where, $C[i] = A[j]*B[k] $ Or $C[i] = A[j] + B[k] $, (its your choice, what to select from both of them) for all $1<=i<=N$ Once an index 'j' and 'k' have been used from array A and B respectively, you can't use them ever again. Find the maximum possible value of C[1]*C[2]*......C[N] modulo p , where p = 1000000007. $1<=A[i]<=100000 $ $1<=B[i]<=100000 $ $1<=N<=100000 $ Example : Array A : [1,2] Array B : [4,3] Best possible array C :$ [(3+1),(4*2)] = [4,8] .$ Final answer = 4*8 = 32 which is the maximum possible product. I applied the greedy approach in the test which failed all the test cases except 1. My greedy approach was : Sort both "A" and "B", then do $C[i]=max(A[i]+B[i], A[i]*B[i]) $ Second problem of the test was : Given a graph with $N$ nodes and $M$ edges , remove any number of nodes you want to ...
Given 2-arrays "$A$" and "$B$" of length $n$ , calculate maximum possible product of all elements

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

73.
Is it a NP-hard problem?
By ShapeBlaze, history, 3 years ago, In English
Is it a NP-hard problem? Hi! One of my students got the following problem on a competition. Given a undirected graph with $N\leq 100$ vertices and $M\leq 1000$ edges. $1\leq K\leq N$ vertices are considered special and you are given their numbers. Each edge has a "safety" characteristic &mdash; a real number between $0$ and $1$. The task is to find the longest cycle, which has at least half of special vertices and the product of safety on the edges is at least $0.5$. It seems to me that this problem with $K=1$ is the same as finding the longest cycle in a graph, but as far as I know this is NP-hard. Is it unsolvable in polynomial time or did I miss something? P.S. I have a screenshot of the statement but it is in Russian. If you want &mdash; I can post it in the comments, but I warn you &mdash; it is very bad:) <spoiler summary="Statement in Russian"> It is very unclear. ![Statement](/predownloaded/43/4b/434ba12ef9bbb7dcbcf031d42dd852d68bee5e99.png) ![Explanation for samples](/predo...
Hi! One of my students got the following problem on a competition. Given a undirectedgraph

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

74.
New Year, New Content!
By nika-skybytska, 5 years ago, In English
New Year, New Content! [![thumbnail](/predownloaded/c4/7a/c47a480805335a1ddddd70237a40177b55ef0eb4.png)](https://youtu.be/KgzZHpx-DDI) (click on the thumbnail to watch a YouTube video) Welcome back! Writing this blog feels a bit odd, almost as if I'm starting all over again. For many people, this is what the New Year is all about &mdash; a fresh start. You are probably wondering what I've been doing during this spontaneous break. There is no simple answer to this question, as I was busy with numerous tasks: job, university, and the ICPC season. ### New, Slower Pace Last time I've set the pace pretty fast, releasing multiple videos a week. While taking part in several contests every week is simple, recording screencasts and explanations is not. Because of that, I want to take things slower. Let's first make it a weekly routine. Once we get there, I'll assess how we can proceed. ### Google Calendar I've set up a [google calendar](https://calendar.google.com/calendar/u/0/r?cid=bnVkdDVoNmJoO...
subsequences. The dynamic programming approach comes from the product constraint. Unfortunately, I

Full text and comments »

  • Vote: I like it
  • +39
  • Vote: I do not like it

75.
[TUTORIAL] Basic Lagrange Interpolation pt. 2
By grhkm, history, 5 years ago, In English
[TUTORIAL] Basic Lagrange Interpolation pt. 2 As promised, here's "interpolating multiple values" in $O(n\log^2 n)$. **Pre-req: Polynomial multiplication and modulos, basic lagrange interpolation knowledge (you can read my previous post [here](https://codeforces.me/blog/entry/82953))** As a reminder, polynomial mod is $O(n\log n)$. Main results: ================== Given $f(x)$ and $x_1, x_2, \cdots, x_n$, we can find $f(x_1), f(x_2), \cdots, f(x_n)$ in $O(n\log^2 n)$. Given a bunch of points $\{(x_0, y_0), (x_2, y_2), \cdots, (x_n, y_n)\}$, we can find a degree $n$ polynomial $f(x)$ such that $$\forall 0\leq i\leq n, f(x_i)=y_i$$ Why useful? ================== It helps you AC problems that you can't with $O(n^2)$. It also gives you contribution on CF --------------------------- Idea 1: ================== Since the pre-req says polynomial modulo, let's see if we can mod something to calculate some of $f(x_1), f(x_2), \cdots$ quickly. It can be seen that we can split the set of $x$ into two halves &...
the whole product divided by $(x_i-x_i)$. We can't divide by zero but limits are cool: $$\prod_{j

Full text and comments »

  • Vote: I like it
  • +85
  • Vote: I do not like it

76.
Help needed in ICPC Amritapuri 2010 problems
By bhishma, history, 9 years ago, In English
Help needed in ICPC Amritapuri 2010 problems Recently we were solving problems from past Indian ICPC regional . We weren't able to solve these 2 problems , and I couldn't find any editorial either . It would be really helpful if you guys can give me some hints to these problems. ### [Chemicals](https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=380&page=show_problem&problem=3118) [Solved] #### Description There are $N$ bottles each having a different chemical. For each chemical $i$, you have determined $C[i]$, which means that mixing chemicals $i$ and $C[i]$ causes an explosion. You have $K$ distinct boxes. In how many ways can you divide the $N$ chemicals into those boxes such that no two chemicals in the same box can cause an explosion together? #### Constraints - $T \leq 50$ - $2 \leq N \leq 100$ - $2 \leq K \leq 1000$ #### My Ideas I thought of modelling the given dependencies as a graph and we are asked to find the number of ways to partition the graph into indepen...
dependencies as a graph and we are asked to find the number of ways to partition thegraph into

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it

77.
Atcoder Beginner Contest 132 — Unofficial English Editorial
By AnandOza, 7 years ago, In English
Atcoder Beginner Contest 132 — Unofficial English Editorial Hi all, [Atcoder Beginner Contest 132](https://atcoder.jp/contests/abc132) was today. Atcoder only publishes Japanese editorials for beginner contests, so I wrote an unofficial English editorial. Hope it helps! ### [A: Fifty-Fifty](https://atcoder.jp/contests/abc132/tasks/abc132_a) After sorting the input, a "good" string will look like "AABB". Therefore, we simply sort and check for this format. <spoiler summary="Sample code"> ~~~~~ char[] s = in.next().toCharArray(); Arrays.sort(s); out.println(s[0] == s[1] && s[2] == s[3] && s[1] != s[2] ? "Yes" : "No"); ~~~~~ </spoiler> ### [B: Ordinary Number](https://atcoder.jp/contests/abc132/tasks/abc132_b) It suffices to simply check every range of 3 and see if its middle element should be counted. A simple way is to sort each range of 3 and check that the middle element remains in the middle. Runtime: $\mathcal{O}(n)$. <spoiler summary="Sample code"> ~~~~~ int n = in.nextInt(); int[] p = new int[n]; for (int i =...
exactly $3k$ in the graph. Therefore, we need to find the shortest path from $S$ to $T$ whose length is

Full text and comments »

  • Vote: I like it
  • +124
  • Vote: I do not like it

78.
How I Stay Productive in Self-Isolation
By RomeoFantastik, history, 7 years ago, In English
How I Stay Productive in Self-Isolation [Usual shameless self-advertisement!](https://www.youtube.com/watch?v=CFagJwWW7ys) Hey, guys! Lately I have seen a lot of my buddies' productivity graphs looking like this: ![ ](https://us.123rf.com/450wm/broukoid/broukoid0902/broukoid090200018/4361230-an-isolated-line-graph-going-down-on-white-background.jpg?ver=6) So, I've decided to share 3 tips from my life experience about how I manage to keep myself motivated, focus and productive as hell. P.S: I am a Computer Science student auto-isolated in my dorm room. We are talking about 40 m³ here. It's pretty easy for a guy like me to get nuts in a situation like this. So let's get it started: #### _**1. Put on a suit!**_ No bro, I'm not joking. It might sound stupid, but it's a game changer. As I said, I live in a dorm room, so it's really easy to get off track when your bed is literally 0.5 meters away from the table you study. The table you study on is the same one you eat on. Then I have the sink 2 meters away. This ...
.123rf.com/450wm/broukoid/broukoid0902/broukoid090200018/4361230-an-isolated-line- graph-going-down-on-white

Full text and comments »

  • Vote: I like it
  • +76
  • Vote: I do not like it

79.
AtCoder Beginner Contest #188 Livesolve + Editorial
By nika-skybytska, 6 years ago, In English
AtCoder Beginner Contest #188 Livesolve + Editorial [Problems](https://atcoder.jp/contests/abc188), [my solutions](https://github.com/Sky-Nik/AtCoder/tree/main/abc188), [YT link ](https://www.youtube.com/watch?v=o6sa0FQ8eoA&feature=youtu.be&ab_channel=NikitaSkybytskyi) ### A. Three-Point Shot The team behind has `min(x, y)` points, and the team ahead has `max(x, y)`, so we can check if `min(x, y) + 3 > max(x, y)`. ### B. Orthogonality Just compute inner product according to the given formula. Use `int64_t` if you are as paranoid about overflows as I am :) ### C. ABC Tournament Two finalists are max of their halves, so `left = max(a[:middle])` and `right = max(a[middle:])`. Second place is min of finalists. ### D. Snuke Prime All these interval processing problems can be solved in the same way, by splitting each interval into two events: start and end. After sorting events we can process them in a sequential fashion, maintaining the current daily cost. ### E. Peddler DP on DAG, which is already conveniently...
Just compute inner product according to the given formula. Use `int64_t` if you are as paranoid

Full text and comments »

  • Vote: I like it
  • +98
  • Vote: I do not like it

80.
Codeforces Round 970 Video Editorial (with Hints)
By aryanc403, 2 years ago, In English
Codeforces Round 970 Video Editorial (with Hints) [I'm currently live discussing the problems.](https://youtu.be/pZlCq4e21Cs) I will add problemwise timestamp after the discussion stream. You can join in if something in this blog is unclear or there are more questions. [problem:2008A] <spoiler summary="Idea"> - No of ones must be even. - If no of ones is zero, then no of twos must be even. These are necessary and sufficient conditions. </spoiler> My submission &mdash; [submission:279068120] <spoiler summary="Video Editorial"> <iframe width="853" height="480" src="https://www.youtube.com/embed/pZlCq4e21Cs?start=130" title="Codeforces Round 970 Solution Discussion | ABCDEFGH" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe> </spoiler> [problem:2008B] <spoiler summary="Hint 1"> If it is a square matrix, then N must be a perfect square. </spoiler> <spoiler su...
a graph with edge $i -> p_i$, and notice that each connected component is a cycle

Full text and comments »

  • Vote: I like it
  • +41
  • Vote: I do not like it

81.
[Gym Contest Editorial] Damascus Collegiate Programming Contest (DCPC 2015)
By RedNextCentury, history, 11 years ago, In English
[Gym Contest Editorial] Damascus Collegiate Programming Contest (DCPC 2015) I apologize for the mistake in the constraints of problem J, and for my bad English. #### Problem A: Random Fightings: $DP[i]$ is the probability that mask $i$ (i.e. the people whose indexes are equal to 1 in mask $i$) are still alive. $DP[2^n - 1] = 1$ For each mask, for every pair of alive gangsters $(i,j)$, calculate the probability of gangster $i$ dying in the next fight against gangster $j$, let us call it $p$, and add $p*DP[mask]$ to $DP[mask-2^i]$ (i.e. the same mask but with the $i^{th}$ bit switched to 0). How to calculate $p$? $p$ is the product of the probability of the $j^{th}$ gangster killing the $i^{th}$ one if they fight each other ($A_{ji}$) and the probability of having a match between them. The number of possible matches for a mask is $x*(x-1)/2$ where $x$ is the number of alive gangsters, therefore the probability of having a match between them is $2/(x*(x-1))$. #### Problem B: Rectangles: You need to cover all $x$ s ...
but with the $i^{th}$ bit switched to 0). How to calculate $p$? $p$ is the product of the

Full text and comments »

  • Vote: I like it
  • +25
  • Vote: I do not like it

82.
[Editorial]Contest Based on SUST Intra University Programming Contest 2019
By YouKn0wWho, 7 years ago, In English
[Editorial]Contest Based on SUST Intra University Programming Contest 2019 [A. Perfect Points](https://toph.co/p/perfect-points) Author: [user:YouKn0wWho,2019-12-20] <spoiler summary="Tutorial"> Here $$y=m(c+1)+c: \; c \geq 1 $$ $$ \rightarrow y \mod (c+1) = c: \; c \geq 1 $$ $$ \rightarrow y \mod c = c-1: \; c \geq 2 $$ $$ \rightarrow (y+1) \mod c = 0: \; c \geq 2 $$ Note that $m \geq 1$, so $(y+1) > c$. So we can say that $ (y+1) \; is \; composite: \; y \geq 1$ So $K^{th}$ value of $y$ is ($K^{th}$ composite number $-1$ ). How can we find it given that $K \leq 10^9$? <spoiler summary="Hint"> - [Prime Counting Function](https://codeforces.me/blog/entry/57826?fbclid=IwAR084Ea_mN7LFqr-LLooQrtJQ8jiN5g7W3PvA1_JnHuVOsHrj0DH4UIKqTo#comment-414818) - Binary Search </spoiler> </spoiler> <spoiler summary="Solution"> ~~~~~ #include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define pll pair<ll,ll> #define eb emplace_back #define ll long long #define nl '\n' #define deb(x) cerr<<#x" = "<<x<<nl #define i...
)%mod); } return 0; } ~~~~~ [E. Playing On A Directed Graph](https

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it

83.
Codeforces Beta Round #17 Tutorial
By tourist, 16 years ago, translation, In English
Codeforces Beta Round #17 Tutorial <a href="http://codeforces.me/blog/entry/447">Contest discussion</a><br><b><br>Problem A. Noldbach problem<br><br></b>To solve this problem you were to find prime numbers in range $[2..N]$. The constraints were pretty small, so you could do that in any way - using the Sieve of Eratosthenes or simply looping over all possible divisors of a number.<br>Take every pair of neighboring prime numbers and check if their sum increased by $1$ is a prime number too. Count the number of these pairs, compare it to $K$ and output the result.<br><br><b>Problem B. Hierarchy</b><br>[cut]<br>Note that if employee, except one, has exactly one supervisor, then our hierarchy will be tree-like for sure.<br>For each employee consider all applications in which he appears as a subordinate. If for more than one employee there are no such applications at all, it's obvious that $-1$ is the answer. In other case, for each employee find such an application with minimal cost and add these costs to get the answer.<br...
. Alternatively, you could use Kruskal's algorithm finding a minimum spanning tree for agraph. But

Full text and comments »

  • Vote: I like it
  • +30
  • Vote: I do not like it

84.
Max Flow Implementation
By usernameson, history, 10 years ago, In English
Max Flow Implementation #### Overview In this post I will explain with an example one way to code the Edmonds Karp max flow algorithm to solve a problem. #### The Problem The problem we study is Array and Operations http://codeforces.me/problemset/problem/498/C. The basic idea is you have a sequence of numbers and a bunch of special pairs taken from the sequence. For any of the pairs you can divide each number by a common factor greater than 1 and replace the elements in the pair with the result of this division. The question asks what is the maximum number of times you can do this. #### Converting this to a max flow problem This section is specific to the problem. You can skip it if you just want to know how to implement Edmonds Karp on a given flow network. Before we convert this problem to a max flow problem we make some observations. First if we have a pair of numbers the maximum amount of times we can perform the operation described on this pair is equal to the number of prime divisors the p...
number and the product of all the numbers paired with it and then count the prime divisors of this gcd

Full text and comments »

  • Vote: I like it
  • -13
  • Vote: I do not like it

85.
Codeforces Round #138, tutorial.
By I_love_Nastya, 14 years ago, translation, In English
Codeforces Round #138, tutorial. ### Div2 A. Parallelepiped You were given areas of three faces of a rectangular parallelepiped. Your task was to find the sum of lengths of it's sides. Let $a$, $b$ and $c$ be the lengths of the sides that have one common vertex. Then the numbers we are given are $s_1 = ab$, $s_2 = bc$ и $s_3 = ca$. It is easy to find the lengths in terms of faces areas: $a = \sqrt{s_1 s_3 / s_2}$, $b = \sqrt{s_1 s_2 / s_3}$, $c = \sqrt{s_2 s_3 / s_1}$. The answer is $4 (a + b + c)$, because there are four sides that have lengths equal to $a$, $b$ and $c$. The complexity is $O(1)$. ### Div2 B. Array You were given an array $a$ consisting of $n$ integers. Its elements $a_i$ were positive and not greater than $10^5$ for each $1 \le i \le n$. Also you were given positive integer $k$. You had to find minimal by inclusion segment $[l, r]$ such that there were exactly $k$ different numbers among $a_l, \ldots, a_r$. The definition of the "minimal by inclusion" you can read in the statement. Let us...
the elements of the first column. The elements of the first column of the product $B^{k} B^{l}$ are

Full text and comments »

  • Vote: I like it
  • +71
  • Vote: I do not like it

86.
Urge to go into Development Side of Things
By sam000013, history, 6 years ago, In English
Urge to go into Development Side of Things Hello everyone, I am sharing my thoughts with the community as to in what position I am, or what I feel right now. I do not know how exactly to describe it even. I have been inconsistent at CP since I started college due to various reasons, but mostly due lack of self-discipline, If I am being very honest. Just before a few months I learnt Graphs which was a thing that I feared because of this Image that I had created in my mind about it(I thought that Graphs would be highly complex to describe with programming and manipulating them would be even more difficult). But after giving myself push and learning through a paid course from this [site](https://codingblocks.com/) which me and my collegemates crowdfunded because we are super poor(Joking), I was able to overcome that fear and I feel as if my skills have increased but that is not very well reflected at CP because I personally feel that along with the skills of DS and Algorithms, CP is also a sport of practice and consistency both ...
what-not wherein the Developers at top-notch Product Based Companies have said that they hardly

Full text and comments »

  • Vote: I like it
  • -19
  • Vote: I do not like it

87.
Editorial of Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round)
By TheScrasse, 5 years ago, In English
Editorial of Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) [problem:1654A] Author: [user:TheScrasse,2022-02-24]<br> Preparation: [user:TheScrasse,2022-02-19] <spoiler summary="Hint 1"> Suppose you want to choose pieces of cake $i$, $j$. Can you make them adjacent in $1$ move? </spoiler> <spoiler summary="Solution"> The answer is the sum of the $2$ maximum weights. You can always pick the $2$ maximum weights: if they are $a_i$ and $a_j$ ($i < j$), you can flip the subsegment $[i, j-1]$ to make them adjacent. The result can't be larger, because the sum of the weights of any $2$ pieces of cake is never greater than the sum of the $2$ maximum weights. Iterating over all pairs of pieces of cake is enough to get AC, but you can solve the problem in $O(n \log n)$ by sorting the weights and printing the sum of the last $2$ values, or even in $O(n)$ if you calculate the maximum and the second maximum in linear time. Complexity: $O(t \cdot n^2)$, $O(t \cdot n \log n)$ or $O(t \cdot n)$ </spoiler> Official solution: [submissi...
graph between indices with an edge $i \to j$ with label $x$ if $i < j \leq i+\sqrt m$ and $\frac{a_j

Full text and comments »

  • Vote: I like it
  • +133
  • Vote: I do not like it

88.
CodeForces Beta Round #73 div. 1 analysis (particulary with div. 2)
By Zlobober, 15 years ago, translation, In English
CodeForces Beta Round #73 div. 1 analysis (particulary with div. 2) <span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: underline;vertical-align: baseline;">Problem DIV1-A, Div2-C. Trains.</span><br /><span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: none;vertical-align: baseline;">This problem can be approached from two sides - from a programmer's perspective and a mathematician's one. We consider both approaches.</span><br /><span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: none;vertical-align: baseline;"> </span><br /><span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: none;vertical-align: baseline;">First, let's write some general propositio...
just need to count the number of paths that this edge lies on it. This number is theproduct of the

Full text and comments »

  • Vote: I like it
  • +65
  • Vote: I do not like it

89.
Duality in linear programming. Part 1 — definition and construction
By adamant, history, 4 years ago, In English
Duality in linear programming. Part 1 — definition and construction Hi everyone! Previously I [wrote](https://codeforces.me/blog/entry/98334) about theoretical grounds of "aliens trick". Specifically, I introduced the concept of the Lagrangian duality and explained its connection with the trick. Today I want to elaborate a bit more on the concept of dual problems and their applications to linear programming as well as to common problems in competitive programming. I initially wanted to also write about some applications in competitive programming problems, but given that the introduction is already quite lengthy, I decided to leave it for another blog, while using most common and well-known theoretical examples here, focusing more on how to construct and interpret dual problems to begin with, rather than how to use it in contests. I think, it is a crucial first step towards using the duality in actual programming challenges. #### Prerequisites It is highly recommended to have some general understanding of basic mathematical optimization...
the dot product of $\lambda$ and $x$. **Def. 4**. A **supporting hyperplane** of a set $X \subset

Full text and comments »

  • Vote: I like it
  • +250
  • Vote: I do not like it

90.
Codeforces Round 1047 (Div. 3) Editorial
By Proof_by_QED, history, 14 months ago, In English
Codeforces Round 1047 (Div. 3) Editorial <spoiler summary="Rating Predictions"> | Predictor | A | B | C | D | E | F | G | |----------------------------------|-----|-----|-----|------|------|------|------| | [user:Proof_By_QED,2025-09-06] | 800 | 900 | 1100 | 1200 | 1400 | 1700 | 1900 | | [user:Intellegent,2025-09-06] | 800 | 900 | 1000 | 1200 | 1500 | 1900 | 2000 | | [user:RobinFromTheHood,2025-09-06] | 800 | 800 | 1100 | 1400 | 1600 | &mdash; | | [user:yse,2025-09-06] | 800 | 900 | 1100 | 1300 | 1500 | 1800 | 1900 | | [user:edeeva,2025-09-06] | 800 | 800 | 1000 | 1100 | 1400 | 1700 | 2100 | | [user:-firefly-,2025-09-06] | 800 | 800 | 800 | 900 | 1400 | 1800 | 1900 | | [user:Non-Origination,2025-09-06] | 800 | 1000 | 1000 | 1300 | 1400 | &mdash; | 2000 | | [user:satyam343,2025-09-06] | 800 | 800 | 1000 | 1200 | 1500 | 1700 | 2000 | | [user:reirugan,2025-09-06] | 800 | 900 | 900 | 1000 | 1600 | 1800 | 2000 | | [user:catgi...
order to maximize the sum of two positive numbers given that their product must stay constant, it is

Full text and comments »

  • Vote: I like it
  • +67
  • Vote: I do not like it

91.
CodeCraft'15 IIIT Hyderabad Editorial
By darkshadows, 12 years ago, In English
CodeCraft'15 IIIT Hyderabad Editorial [problem:100589A] ------------------ Given a rooted tree(at node 1) of **N** nodes,you have to handle a total of **Q** operations of type: **1 U L X**: Increase coins by **X** of all nodes at a distance of **L** from root. **2 X**: Report sum of all coins in subtree rooted at **X**. **N** <= 10<sup>5</sup> **Q** <= 10<sup>4</sup> #### Difficulty: Medium-Hard ####Explanation: This approach uses a very specific technique of maintaining a buffer of update queries and updating the whole tree once buffer size exceeds a constant limit(we maintain this limit as sqrt(M)). ~~~~~ buffer=[] q=input while q--: query = input() if query==update: buffer.add(query) else: //say query is “2 X” //the answer that has been already calculated for node X prevans= ans(X) for i=0 to buffer.size(): //add to prevans the effect of buffer[i] //let’s say buffer[i]=”1 U L...
] ------------------ Note : Since there are **N** nodes and **N** edges in the graph, the graph would be like a tree

Full text and comments »

  • Vote: I like it
  • +81
  • Vote: I do not like it

92.
[GYM] Damascus-CPC 2018 — Editorial
By RedNextCentury, history, 8 years ago, In English
[GYM] Damascus-CPC 2018 — Editorial A. Martadella Strikes Again ================== if $ R*R > 2*r*r $ print $1$, otherwise print $2$ $R$ and $r$ should be **long long** or **double** to avoid overflow [C++ Code](https://pastebin.com/1CKZu6yN) B. Amer and Graphs ================== Since the edges are undirected ,we can store the edges ${u,v}$ as $(u \le v)$ for every edge $(1 \le i \le n)$. Let's assign a unique number for every unique edge in the array, then our problem will be reduced to : Find the number of different segments of the array which have the exact same elements ( same frequencies as well for each element ). This problem is a classic hashing problem that can be solved this way : let's choose some random large prime numbers $P$ and $MOD$ ,for example $P=304933 , MOD=10^9+7$. replace every element ${x_i}$ from the array with $ P^{x_i} \% MOD $. now the final problem is about finding different segments of the array which have the same sum value $\% MOD$ . This sol...
numbers is the product of the common prime factors with the lowest power, and the $LCM$ of a group of

Full text and comments »

Tags gym
  • Vote: I like it
  • +20
  • Vote: I do not like it

93.
Problem Topics
By -Morass-, history, 9 years ago, In English
Problem Topics Good Day to you! I've been asked to make some topic-wise list of problems I've solved. Even though I couldn't involve all problems, I've tried to involve at least "few" problems at each topic I thought up (I'm sorry if I forgot about something "easy"). I've alredy made such list once anyway I've tried to include more problems now &mdash; so here it is: <spoiler summary="aho"> http://www.spoj.com/problems/ADAJOBS/ URI 2226 (5) //[NICE][NUMBERS][DP] http://www.spoj.com/problems/SUB_PROB/en/ http://codeforces.me/contest/696/problem/D 8 http://www.spoj.com/problems/AHOCUR/ 5 //Aho-Corassic + DP https://www.codechef.com/problems/LYRC (5) //Sample aho-brute-force http://codeforces.me/problemset/problem/346/B //Proposed by [user:bradyawn,2019-08-03] </spoiler> <spoiler summary="automat"> 6861 [LA] //CYK UVA 10679 //Suffix Automat http://www.spoj.com/problems/STRMATCH/ //Suffix Automat &mdash; trie might do too http://www.spoj.com/problems/NSUBST...
+ implementation UVA — 10183 10106 — Product [UVA] 10523 — Very Easy

Full text and comments »

  • Vote: I like it
  • +428
  • Vote: I do not like it

94.
Tishreen-CPC 2017 Editorial [GYM]
By RedNextCentury, 8 years ago, In English
Tishreen-CPC 2017 Editorial [GYM] First I would like to apologize for the error in the test cases of problem G. All solutions were rejudged and 3 teams/participants were affected, I am very sorry. Also, thanks to [user:Ashishgup,2018-09-28] for discovering the error. I hope you enjoyed the problems in general, below is a brief description of the solutions (if you need a detailed explanation of some problem write in the comments) Any feedback is appreciated :) A. Printing Books ================== While the number of digits left is enough, increase $X$ to the closest power of 10, and subtract the number of digits needed from $N$. Let's denote the number of digits in $X$ as $d(X)$ and the smallest power of 10 greater than $X$ as $p(X)$. ~~~ while (p(X)-X)*d(X) <= N N-=(p(X)-X)*d(X) X=p(X) ans+=p(X)-X ~~~ At the end, there might be some leftovers from $N$, if it is not divisible by $d(X)$, then the answer is -1. Otherwise, add $\frac{N}{d(X)}$ to ans. B. Ali and Wi-Fi =...
. Complexity: $O(nlog(n))$ J. The Volcano Eruption ================== Create a graph where

Full text and comments »

  • Vote: I like it
  • +20
  • Vote: I do not like it

95.
Codeforces Round #286 Editorial (Complete)
By evima, 12 years ago, In English
Codeforces Round #286 Editorial (Complete) **Edit (Jan 22, 2:45 AM UTC):** Added Div1E and the editorial is now complete. I am sorry for the delay. **Edit (Jan 21, 9:45 AM UTC):** Added the explanation for Div1C/2E, and the problem setters' codes. Div1E will need several more hours. Thank you again for your patience. First, here are some statistics on this round: <table> <tr> <td>Division</td> <td>Registrants</td> <td>Participants</td> <td>A Accepted</td> <td>B Accepted</td> <td>C Accepted</td> <td>D Accepted</td> <td>E Accepted</td> </tr> <tr> <td>1</td> <td>1364</td> <td>572 (*)</td> <td>294</td> <td>199</td> <td>8</td> <td>113</td> <td>1</td> </tr> <tr> <td colspan="3">(Estimated number of AC by me)</td> <td>800 (wrong)</td> <td>500 (wrong)</td> <td>70 (FAIL)</td> <td>90 (ok)</td> <td>5 (wrong)</td> </tr> <tr> <td>2</td> <td>4016</td> <td>2028</td> <td>1355</td> <t...
> ### Div.2 B: [problem:505B] [Problem] Given an undirected graph whose edges are

Full text and comments »

  • Vote: I like it
  • +156
  • Vote: I do not like it

96.
Codeforces Round 1090 (Div. 4) Unofficial Editorial
By nik_exists, 7 months ago, In English
Codeforces Round 1090 (Div. 4) Unofficial Editorial Since once hasn't been released, and I <s>love procrastinating on stuff that I probably should have already finished</s>, I thought I might make one. I also don't know why the links to the problems aren't working, blame CF. Apologies if anything is unclear, I'm tired. [contest:2218A] <spoiler summary="Solution"> Since $min(x, y) <= x$, and $x \leq 67$, we can set $y = 67$, so $min(x, y)$ will always equal $x$ </spoiler> [submission:369602653] [contest:2218B] <spoiler summary="Solution"> The optimal choice is to multiply every value except the largest value by -1, since they have the least contribution to the sum. </spoiler> [submission:369607814] [contest:2218C] <spoiler summary="Solution"> For a given "block" of length 3, we will be "wasting" the largest and smallest element in our block. In order to maximize the sum of the medians of the block, we note that the largest element in an array can never be the median, so we pair the largest element with the ...
$1$ trivially. For this case, just output a star graph with all nodes connected to node $1

Full text and comments »

  • Vote: I like it
  • +23
  • Vote: I do not like it

97.
A Beautiful Technique for Some XOR Related Problems
By DrSwad, history, 7 years ago, In English
A Beautiful Technique for Some XOR Related Problems ## Inspiration I'm very excited about this blog, as it took me quite a lot of effort and scavenging through the internet to completely grasp the concept of this technique(That's probably because I have almost zero knowledge in Linear Algebra or I'm just plain dumb). So I feel like I genuinely conquered a challenge, and I really want to share it with someone. But there's no way my CP friends circle will believe it, they'll think I'm just trying to show off :P So here I am, sharing it on CF. I also created a [personal blog](https://drschwad.github.io/), so that if I ever feel like sharing something again(not only about CP), I can write a blog there. I also added this same post [there](https://drschwad.github.io/2019-08-06-z2-space-xor-trick/), you can read it there if you prefer dark theme. I'll be pleased to hear any thoughts on the blog or if I can improve it in some way ^\_^ ## Introduction Since it concerns Linear Algebra, there needs to be a lot of formal stuff going on ...
of size $1 \le n \le 10^5$ with range of elements $1 \le a_i \le 70,$ such that theproduct of it's

Full text and comments »

  • Vote: I like it
  • +425
  • Vote: I do not like it

98.
Me and DeepSeek spent a weekend analyzing 8000 CF problems. Here's what we found
By ayushgirigoswami15, history, 6 months ago, In English
Me and DeepSeek spent a weekend analyzing 8000 CF problems. Here's what we found # Me and DeepSeek analyzed 1600 Codeforces contests and 8000+ problems — some interesting patterns please check this result : https://ayushgirigoswami.github.io/codeforces_analysis_report/ A few weeks ago I got curious about something most of us probably notice intuitively but rarely measure properly: * Is Codeforces getting harder over time? * Which topics are becoming more common? * Are some problems overrated or underrated? * How different are Educational rounds from regular rounds? So I wrote a Python script that pulls contest/problem data from the CF API, analyzes ratings + tags, and generates interactive visualizations. ### Report https://ayushgirigoswami.github.io/codeforces_analysis_report/ ### Source code https://github.com/Ayushgirigoswami --- ## Dataset The analysis includes: * 1600 contests * 8354 rated problems * Div.1 / Div.2 / Div.3 / Div.4 / Div.1+2 * 2011 → present Average problem rating across the dataset: **1793** --- ...
disproportionately common in Div.1. * Implementation dominates Div.2/3 but drops heavily in Div.1. *Graph

Full text and comments »

  • Vote: I like it
  • +31
  • Vote: I do not like it

99.
SOS Dynamic Programming [Tutorial]
By usaxena95, 10 years ago, In English
SOS Dynamic Programming [Tutorial] ## Introduction In this post, I am going to share my little knowledge on how to solve some problems involving calculation of **Sum over Subsets(SOS)** using dynamic programming. Thus the name **SOS DP**. I have chosen this topic because it appears frequently in contests as mediu2m-hard and above problems but has very few blogs/editorials explaining the interesting DP behind it. I also have a predilection for this since I came across it for the first time in ICPC Amritapuri Regionals 2014. Since then I have created many questions based on this concept on various platforms but the number of accepted solutions always seems to be disproportionate to the lucidity of the concept. Following is a small attempt to bridge this gap &#128521; ## Problem I will be addressing the following problem: Given a fixed array **A** of $2^N$ integers, we need to calculate &forall; x function **F(x)** = Sum of all **A[i]** such that **x&i = i**, i.e., **i** is a subset of **x**.<br> $$ F[mask] = ...
> Kindly note that these relations form a directed acyclic graph and not necessarily a rooted tree

Full text and comments »

  • Vote: I like it
  • +64
  • Vote: I do not like it

100.
Codeforces Round 993 (Div. 4) Editorial
By cry, 23 months ago, In English
Codeforces Round 993 (Div. 4) Editorial #### Special thanks to our hub of testuwuers for contributing solution explanations! #### [problem:2044A] Problem Credits: [user:cry,2024-12-15] <br> Analysis: [user:macaquedev,2024-12-15] <spoiler summary="Solution "> For any $n$, Cube can set $a$ = any integer between $1$ and $n-1$ inclusive, and set $b = n - a$. $a$ cannot be less than $1$, because then it would be non-positive, and $a$ cannot be greater than $n-1$, because then $b$ would be less than $1$, which would make it non-positive. Therefore the answer is just $n-1$ for all $n$. </spoiler> <spoiler summary="Code (Python)"> ```import sys input = sys.stdin.readline for _ in range(int(input())): print(int(input())-1) ``` </spoiler> #### [problem:2044B] Problem Credits: [user:Lilypad,2024-12-15] <br> Analysis: [user:Lilypad,2024-12-15], [user:macaquedev,2024-12-15] <spoiler summary="Solution "> The letters she reads that comprise string $b$ are just the letters that comprise string $a$, flip...
the divisors of $X$. For each ordered pair of divisors whose product is $X$, we check whether the

Full text and comments »

  • Vote: I like it
  • +98
  • Vote: I do not like it

101.
Global Round 20 Editorial
By maomao90, 5 years ago, In English
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...
cycles when considering the graph with edges $a_i \to b_i$.

Full text and comments »

  • Vote: I like it
  • +135
  • Vote: I do not like it

102.
New CSES Tasks Editorials
By Sul_A., history, 18 months ago, In English
New CSES Tasks Editorials Editorial for some of the new CSES tasks. Tasks that are trivial or too similar to already existing tasks are not included. Every time I solve a new nontrivial task, I will add it here. **NOTE: ONLY READ THE SOLUTIONS IF YOU ARE COMPLETELY STUCK AND OUT OF IDEAS. CSES tasks are the kinds of tasks you can solve at a random time by random chance. You might read a task today and solve it next week. Or next month. Or next 3 months. So read at your own risk.** ## Sorting & Searching <spoiler summary="Distinct Values Subsequences"> For each value $x$, we can include $0$ or $1$. If $f(x)$ is the number of times $x$ appears in the array, Then there are $f(x) + 1$ ways to pick $0$ or $1$ occurrences of $x$. Since every value is independent of every other values, we will take the product of $f(x) + 1$ over all $x$. This can be done with `std::map` or sorting. </spoiler> ## Dynamic Programming <spoiler summary="Mountain Range"> Let $L_i$ be the nearest greater element o...
product of $f(x) + 1$ over all $x$. This can be done with `std::map` or sorting.

Full text and comments »

  • Vote: I like it
  • +58
  • Vote: I do not like it

103.
List of Problems Having Short Statements (800 to 1500)
By levitational, history, 5 weeks ago, In English
List of Problems Having Short Statements (800 to 1500) ## List of Problems Having Short Statements (800 to 1500) Long, wordy statements can be exhausting, especially for beginners. So here is a list of problems with **short and easy-to-read statements** in the **800–1500** range, a companion to [Abdullah500's list for 1600–3000](https://codeforces.me/blog/entry/146051). **Notes:** - Every problem here has a statement of **under 1000 characters** (input/output and samples not counted). - Within each rating, problems are listed in order of problem ID, **not** sorted by statement length. - Ratings are as of April 2026 and may shift a little over time. - Short statement does not always mean an easy idea. Some of these are tricky! - The data comes from [alwa97/codeforces-1000](https://github.com/alwa97/codeforces-1000). Many thanks to the author. I picked about 50 problems per rating from there, so check that repo if you want even more. **800** 1. [41A &mdash; Translation](https://codeforces.me/problemset/problem/41/A) 2. [5...
/A) 38. [1406B — Maximum Product ](https://codeforces.me/problemset/problem/1406/B) 39, /problemset/problem/1364/A) 38. [1406B — Maximum Product ](https://codeforces.me/problemset

Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it

104.
Editorial for VK Cup 2015 — Finals
By Zlobober, history, 11 years ago, translation, In English
Editorial for VK Cup 2015 — Finals Thanks everybody for participating. Tasks follow in the order of the original contest (the mirror order is given in the brackets). [problem:562A] -------------- (in mirror: [problem:566C]) Let's think about formal statement of the problem. We are given a tricky definition of a distance on the tre: $\rho(a, b) = dist(a, b)^{1.5}$. Each vertex has its weight $w_i$. We need to choose a place $x$ for a competition such that the sum of distances from all vertices of the tree with their weights is minimum possible: $f(x) = w_1 \rho(1, x) + w_2 \rho(x, 2) + \ldots + w_n \rho(x, n)$. Let's understand how function $f(x)$ works. Allow yourself to put point $x$ not only in vertices of the tree, but also in any point inside each edge by naturally expanding the distance definition (for example, the middle of the edge of length $4$ km is located $2$ km from both ends of this edge). **Fact 1**. For any path $x \in [a, b]$ in the tree the function $\rho(i, x)$ is convex. Actually, the ...
of a star graph (i. e. the graph consisting of a vertex with several other vertices attached to it

Full text and comments »

Tutorial of VK Cup 2015 - Finals
  • Vote: I like it
  • +100
  • Vote: I do not like it

105.
CSES Additional Problems I (new problems only) Tutorial
By cry, 15 months ago, In English
CSES Additional Problems I (new problems only) Tutorial Hello Codeforces. I was stuck on a 3 hour flight with nothing to do, so what better way to spend my time than catching up on the new CSES problems. But it turns out I finished those too quick so I guess I'm writing the solutions for some of them here. No one probably asked. This will only cover the new problems from the 2025 update and in the **Additional Problems I** section. For old problem solutions you can probably find them somewhere on the internet. For new problems not in this section, some of their solutions are in [this blog](https://codeforces.me/blog/entry/142894). ### [Distinct Values Sum](https://cses.fi/problemset/task/3150/) <spoiler summary="Smash Me"> Consider each distinct value separately. Say we are focused on $x$ and denote the indices where $x$ occurs in $a$ as $b_1, b_2, \ldots, b_k$. We want to count the number of subarrays that covers at least one element in $b$. Let's break $[1, n]$ into intervals separated by each $b_i$, so we have intervals $[...
can iterate over all intervals and add the product — this is the contribution for this integer

Full text and comments »

  • Vote: I like it
  • +82
  • Vote: I do not like it

106.
Codeforces Round #198 — Editorial
By fchirica, 13 years ago, In English
Codeforces Round #198 — Editorial [problem:340A] ------------------ You are given a range $[A, B]$. You're asked to compute fast how many numbers in the range are divisible by both $x$ and $y$. I'll present here an $O(log(max(x, y))$ solution. We made tests low so other not optimal solutions to pass as well. The solution refers to the original problem, where $x, y \le 10^9$. Firstly, we can simplify the problem. Suppose we can calculate how many numbers are divisible in range $[1, X]$ by both $x$ and $y$. Can this solve our task? The answer is yes. All numbers in range $[1, B]$ divisible by both numbers should be counted, except the numbers lower than $A$ (1, 2, ..., A &mdash; 1). But, as you can see, numbers lower than A divisible by both numbers are actually numbers from range [1, A &mdash; 1]. So the answer of our task is f(B) &mdash; f(A &mdash; 1), where f(X) is how many numbers from 1, 2, ..., X are divisible by both x and y. For calculate in $O(log(max(x, y))$ the f(X) we need some math. If you don't ...
(also called cross product or ccw function). Without it, this explanation will make no sense. The

Full text and comments »

  • Vote: I like it
  • +130
  • Vote: I do not like it

107.
Reflection on my past authored problems
By AkiLotus, history, 3 years ago, In English
Reflection on my past authored problems Hello Codeforces! This is not a round announcement, however. I realize it's around 4 years since my last rated participation, and 3 years since my last problemsetting contribution. I think I have never said a proper goodbye to competitive programming since then. I know, I know, this is not an airport, thus my departure is not mandatory. But after all, this is a free space of my blog entries after all. Besides, today is my 25th cake day, and I just feel nostalgic reflecting everything I have gone through. Thus, rather than just saying farewell, I'd like to, in an absolutely styled late attempt, jump on the [trend](https://codeforces.me/blog/entry/113715) and reflect on the past programming problems that I have authored. My format would be a bit different though. I prefer to write in my own style and convey my thoughts the way I feel comfortable. ;) Okay, first and foremost, I'll only consider those available in official Codeforces rounds. I've done quite a myriad of work...
segment product, here I asked for the totient value of that product. Should spice things up a bit for

Full text and comments »

  • Vote: I like it
  • +105
  • Vote: I do not like it

108.
Codeforces Round 1073 (Div. 1, Div. 2) Editorial
By nifeshe, 10 months ago, In English
Codeforces Round 1073 (Div. 1, Div. 2) Editorial Special thanks to [user:reirugan,2026-01-17], [user:weirdflexbutok,2026-01-17] and [user:intellegent,2026-01-17] for helping with editorials. [problem:2191A] - Idea: [user:nifeshe,2026-01-17] - Solution: [user:nifeshe,2026-01-17] - Editorial: [user:reirugan,2026-01-17] <spoiler summary="Hints"> <spoiler summary="Hint 1"> Without the "after sorting condition", there are only two ways to color the cards. </spoiler> </spoiler> <spoiler summary="Solution"> Without the "after sorting condition", there are only two ways to color the cards. We must have that $a$ is alternating in color. Without loss of generality, color the odd indices red and the even indices blue. This uniquely colors every card. Now, let's sort the array $a$, while also keeping track of the colors; one way to do this is by sorting it as a vector of pairs. Then we simply have to verify that no two adjacent cards are the same color. Alternatively, you can use the fact that $a$ is a permutation, ...
l_1 \le i \le r_1,\ l_2 \le j \le r_2\}$ (We'll call this the XOR Cartesian product). Let's try to

Full text and comments »

  • Vote: I like it
  • +150
  • Vote: I do not like it

109.
Problems that I authored so far
By TheScrasse, history, 3 years ago, In English
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),...
solution. [cc SUMPRODSEG \- Sum Product Segments](https://www.codechef.com/problems

Full text and comments »

  • Vote: I like it
  • +75
  • Vote: I do not like it

110.
[Tutorial] Abstract Proofs of DP Algorithms
By Proofy, 15 months ago, In English
[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 ...
acyclic graph or DAG (sometimes weighted). Thus, we will continue discussing DP calculations on

Full text and comments »

  • Vote: I like it
  • +79
  • Vote: I do not like it

111.
Efficient 3D Convex Hull Tutorial
By Monogon, history, 6 years ago, In English
Efficient 3D Convex Hull Tutorial _Warning: The following contains graphic depictions of geometry, precision errors, and degenerate cases. Viewer discretion is advised._ ### Prerequisites I assume the reader is familiar with: - 2D Convex Hulls - 3D Vector Operations (dot and cross products) ### Introduction Recall that in the 2D convex hull problem, you are given a set of 2D points, and you must compute the smallest convex polygon containing all the given points. By convex, we mean that for any two points $A$ and $B$ inside the polygon, the entire line segment $AB$ is also inside the polygon. The problem in 3D is completely analogous. You are given $n$ 3D points, and you must compute the smallest convex polyhedron containing all the given points. Similarly, a polyhedron is convex if for any two points $A$ and $B$ inside the polyhedron, the line segment $AB$ is also inside the polyhedron. In the 2D case, it is more obvious what the output is. We can simply output a circular list of vertices on the ...
Delaunay Triangulation. It is the graph that connects two points if their Voronoi cells share a

Full text and comments »

  • Vote: I like it
  • +393
  • Vote: I do not like it

112.
Top-10 результатов в области алгоритмов за 2011 год
By AlexErofeev, 15 years ago, translation, In English
Top-10 результатов в области алгоритмов за 2011 год <p>Пока участники Codeforces развлекались, выясняя, кто из них самый аутентичный JKeeJle30, <a href="http://11011110.livejournal.com/">David Eppstein</a> подвел итоги ушедшего года в области Computer Science. Изучив появившиеся за этот год препринты на <a href="http://arxiv.org">arxiv.org</a> в разделе cs.DS (да, поэтому результаты <a href="http://www.eecs.berkeley.edu/%7Evirgi/matrixmult.pdf">про перемножение матриц</a> сюда не попали) он выбрал десятку самых понравившихся ему. Вот они, в хронологическом порядке:<br /><br />[cut]<br /><br /><a href="http://arxiv.org/abs/1103.0534">Solving connectivity problems parameterized by treewidth in single exponential time</a>. В первую очередь обращает на себя список авторов - Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan van Rooij, and Jakub Onufry Wojtaszczyk. Немного о терминологии: декомпозиция дерева - это отображение графа на дерево, когда каждая вершина графа отображается на некоторое поддерево, причем если вер...
, CONNECTED ODD CYCLE TRANSVERSAL, MAXIMUM FULL DEGREE SPANNING TREE и GRAPH

Full text and comments »

  • Vote: I like it
  • +157
  • Vote: I do not like it

113.
[Editorial] Newton School December 2021 Contest
By dnshgyl21, history, 5 years ago, In English
[Editorial] Newton School December 2021 Contest Credits: [user:Lubba_Lubba,2021-10-30], [user:dnshgyl21,2021-10-30], [user:Sawarnik,2021-10-30], [user:Xzirium,2021-10-30] #### [A. AC or not?](https://my.newtonschool.co/playground/code/stlxznqa697h/) ------------------ <spoiler summary = "Solution"> Take the input in variable $n$. So if $n == 1$, print $AC$, else print $WA$. </spoiler> #### [B. ABBA](https://my.newtonschool.co/playground/code/kr38ahzcg1br/) --------------------- We solve this problem in cases: Firstly, we take the case where all the characters of the string are either ‘a’ or ‘b’. For this do not require to perform any operations as every character of the string is equal. Secondly, we take the case where ‘a’ and ‘b’ both exist at least once. Here we can either make all the characters ‘a’ or ‘b’. We try to calculate the minimum operations required to make all characters ‘a’. We also observe that there exists a character ‘b’ with adjacent character ‘a’ since ‘a’ and ‘b’ both exist at least once. We...
because the product of all primes upto $43$ is already greater than $10^{16}$, and for each prime upto

Full text and comments »

  • Vote: I like it
  • +28
  • Vote: I do not like it

114.
UTPC Spring 2024 Open Contest Editorial
By UTPC_Admin, history, 3 years ago, In English
UTPC Spring 2024 Open Contest Editorial Hope you enjoyed our contest! The editorial is below: [A &mdash; Skipping Songs](https://codeforces.me/gym/105109/problem/A) Author: [user:sg2themax,2024-04-21] <spoiler summary="Solution"> For this problem, you maintain an index counter pointing to the current song, starting at 0. At each step, you always ensure that you mod by the length of the record. You start off by playing the song at the index of the first number. After printing each song, you increment by one since Noah has "finished listening" to it. Then, you add the number of skips, print the next song, and repeat. </spoiler> [B &mdash; 6th heaven](https://codeforces.me/gym/105109/problem/B) Author: [user:blueberryJam,2024-04-21] <spoiler summary="Solution"> We first check whether the conditions can be satisfied, then if so compute the number of arrangements. #### Pruning Consider a situation in which a disk appears three times or more among all the distinct pairs. This is impossible to arrange...
$. Then checking the graph (more specifically, forest) for these conditions can be be done in $\mathcal{O

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it

115.
Set algorithm(rev.2)
By Sanae, history, 15 months ago, In English
Set algorithm(rev.2) # Set algorithm Part I Sometimes we may meet with some functions $S\rightarrow V$(S is a set,V is a value),and we need to handle some transformations on it. The article is for beginners whick is much easy, and I may continously update the article. There are some features. First the problem always give small $n$,such as $n\leq 15,n\leq20$. Second,the time complexity is always $O(n2^n),O(3^n),O(n^22^n)$. Let's do some assumption: The values form a ring and they contain ring operations like addition,substraction,multification or division in constant time. ## FWT/FMT The most classical one is FWT/FMT. ### Problem Define $a(S),b(S)(S\subseteq U)$ on a set. Get all $c(S)=\sum\limits_{i \oplus j=S}a_ib_j\qquad \oplus \text{is} \ \textrm{and,or,xor}$ The general idea: Let $a, b, c$ be maps (functions) from a set $S$ to a value domain $V=(N/Q/C\cdots)$. We define a transformation $\text{FWT}$ (Fast Walsh Transform) as a map from the space of such functi...
: $\text{FWT}$ can be computed in $O(n \log n)$ time. 3. Pointwise product property: For all $i \in S

Full text and comments »

  • Vote: I like it
  • +105
  • Vote: I do not like it

116.
[Training] [Arabic] ACM JCPC Summer Training 2018
By Corvus, history, 8 years ago, In English
[Training] [Arabic] ACM JCPC Summer Training 2018 Hello Codeforces, From 27/8/2018 to 6/9/2018 the JCPC Summer Training 2018 was held, two weeks covers varied topics consists of 4 different levels 1 &mdash; 4 and Level 1 and 2 consists of 5 lectures and Level 3 and 4 consists of 4 Lectures. The training is recorded and published on youtube on [user:SolverToBe,2018-09-02] channel *note: language of training is Arabic. **Level 1** ----------- **Lecture 1** &mdash; Presented By Mohammad Zuhair [user:Zuhair,2018-09-02] <spoiler summary="STL Data Structures"> Part 1 | [Vector](https://www.youtube.com/watch?v=svZA0aRRYvg) Part 2 | [Pair](https://www.youtube.com/watch?v=8W_lryPTj-s) Part 3 | [Complexity](https://www.youtube.com/watch?v=ZBrzms-78iQ) Part 4 | [Queue](https://www.youtube.com/watch?v=dcr8SzMAdT4) Part 5 | [Stack](https://www.youtube.com/watch?v=ZTQiPSCDIqo) Part 6 | [Priority Queue](https://www.youtube.com/watch?v=ZDR4STKNkxQ) </spoiler> **Lecture 2** &mdash; Presented By Nada Al-Shamayleh [us...
] Part 1 | [Graph Representation](https://www.youtube.com/watch?v

Full text and comments »

  • Vote: I like it
  • +135
  • Vote: I do not like it

117.
[Training] [Arabic] ACM Advanced Training 2018 — PSUT
By Corvus, history, 8 years ago, In English
[Training] [Arabic] ACM Advanced Training 2018 — PSUT Hello Codeforces, From December 2017 to January 2018 the ACM Advanced Training 2018 was held in PSUT, covers varied topics consists of 5 Lectures. The training is recorded and published on youtube on [user:SolverToBe,2018-09-14] channel *note: language of training is Arabic. ### **Lecture 1** Presented By Mohammad Abu Aboud [user:Hiasat,2018-09-14] <spoiler summary="Combinatronics I"> Part 1 | [Rule of Sum and Product and Inclusion Exclusion](https://www.youtube.com/watch?v=7qQCQlSHsjU&list=PLPSFnlxEu99HgAEayVzwxfLo0jwUU3rQD&index=1) Part 2 | [Permutation and Combination](https://www.youtube.com/watch?v=TDHiHSfRxCM&list=PLPSFnlxEu99HgAEayVzwxfLo0jwUU3rQD&index=2) Part 3 | [Stars And Bars Problem](https://www.youtube.com/watch?v=DES5yGZpvxw&list=PLPSFnlxEu99HgAEayVzwxfLo0jwUU3rQD&index=3) Part 4 | [Problem Arrays &mdash; CodeForces 57C](https://www.youtube.com/watch?v=eU9_C7DKiys&list=PLPSFnlxEu99HgAEayVzwxfLo0jwUU3rQD&index=4) Part 5 | [Problem Bad Subsequenc...
"> Part 1 | [Rule of Sum and Product and Inclusion Exclusion](https://www.youtube.com/watch?v

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it

118.
Codeforces Trainings Season 1 Episode 4: Editorial
By Xellos, 13 years ago, In English
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...
, as the number of marbles on the board increases in every turn), the graph of positions is a DAG

Full text and comments »

  • Vote: I like it
  • +148
  • Vote: I do not like it

119.
Some thinking about randomization.
By Furioso_Slient, history, 11 months ago, In English
Some thinking about randomization. ## Introduction Chinese Version:[Link](https://www.luogu.com.cn/article/gt9xd9oo) **UPD#1 18.12.25: Fixed relevant typos and rigorousness errors; added the randomization concept in Treap.** Mention "randomization" and most people's first reaction is probably flipping a coin to bet on `YES` or `NO`. Randomization itself, often seen as an "unorthodox method" (or "dark art"), is generally discarded by teachers in standard educational institutions and is rarely explained in depth. However, in reality, the power of randomization is beyond your imagination. ## Magical Randomization Randomization essentially means shuffling a set of data to make it lose some of its original properties, or to grant it new properties. So, what’s the use of these so-called new properties? Let’s taste a few problems: ### Example 1: Countering Extreme Data Suppose you need to implement a sorting algorithm, but you choose the unstable Quick Sort. Suddenly, a mysterious hacker from Code...
. Discretizing the points we query can effectively disrupt the graph shapes that hinder our backtracking

Full text and comments »

  • Vote: I like it
  • +107
  • Vote: I do not like it

120.
A Problem on Perfect Matching
By t3rminated, 11 years ago, In English
A Problem on Perfect Matching I was solving [this](http://www.codechef.com/JAN14/problems/SEAGRP/) its problem on perfect matching in a graph.I have to tell whether a graph can be perfect matched.I used [tutte matrix](http://en.wikipedia.org/wiki/Tutte_matrix) and [Gaussian elimination](http://en.wikipedia.org/wiki/Gaussian_elimination) method to find whether a perfect matching exists but i don't know why my code doesn't works , please help! ~~~~~ #include "bits/stdc++.h" using namespace std; #define ll long long #define mod 10000+7 #define MAX 101 ll r,i,j,k; ll lcm(ll x,ll y) { ll t; while (y != 0) { t=y; y=x%y; x=t; } return x; } ll random_number_generator() { // Declare variable to hold seconds on clock. time_t seconds; // Get value from system clock and // place in seconds variable. time(&seconds); // Convert seconds to a unsigned // integer. srand((unsigned ll) seconds); // Output random values. return (rand()+mod) % ...
matching in a graph.I have to tell whether a graph can be perfect matched.I used [tutte matrix](http

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

121.
National Competitive Programming Challenge — Editorial
By eulmelk, 11 months ago, In English
National Competitive Programming Challenge — Editorial Here is the link to the contest: [Link](https://codeforces.me/contestInvitation/6071a436743e70518e953453aadcf924bca069aa) ### [A. The Blacksmith](https://codeforces.me/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...
product, so the result must be −1. ~~~~~ t = int

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

122.
Codeforces Round #196 — Problems Analysis
By gojira, 13 years ago, translation, In English
Codeforces Round #196 — Problems Analysis [problem:337A] -------------- First, let's sort the numbers `f[i]` in ascending order. Now assume that the smallest jigsaw puzzle which the teacher purchases consists of `f[k]` pieces. Obviously, she should buy the smallest `n` puzzles which are of size `f[k]` or greater to minimize the difference. These are the puzzles `f[k], f[k+1], ..., f[k+n-1]` (this is not correct when `f[i]` are not distinct and `f[k]=f[k-1]`, but such cases can be skipped). The difference between the greatest and the least size of the puzzles in such set is `f[k+n-1]-f[k]`. To choose the optimal `f[k]`, we can test every `k` between 1 and `m-n` and pick the one producing the least difference. The full algorithm is as follows: ~~~~~ read(n, m, f[1..m]) sort(f[1..m]) best = INFINITY for k = 1 to m-n best = min(best, f[k+n-1] - f[k]) print best ~~~~~ [cut] - [problem:337B] --------- Suppose that the width and height of the screen are `W` and `H` correspondingly. Since `W:H = a:b...
from 1 to `q`. Since `q` is no more than a product of two numbers from the input and these numbers

Full text and comments »

  • Vote: I like it
  • +171
  • Vote: I do not like it

123.
Atcoder Beginner Contest 143 — Unofficial English Editorial
By AnandOza, history, 7 years ago, In English
Atcoder Beginner Contest 143 — Unofficial English Editorial Hi all, [Atcoder Beginner Contest 143](https://atcoder.jp/contests/abc143) was today. I wrote an unofficial English editorial. Hope it helps! ### [A: Curtain](https://atcoder.jp/contests/abc143/tasks/abc143_a) The curtains can cover a maximum of $2B$. So either they don't cover the whole window and the remainder is $A-2B$, or they do and the remainder is $0$. So the answer is $\max(0, A-2B)$. Runtime: $\mathcal{O}(1)$. <spoiler summary="Sample code"> ~~~~~ int a = in.nextInt(), b = in.nextInt(); out.println(Math.max(0, a - 2 * b)); ~~~~~ </spoiler> ### [B: TAKOYAKI FESTIVAL 2019](https://atcoder.jp/contests/abc143/tasks/abc143_b) We can simply loop through every pair (taking care not to double count) and add the health points restored. Runtime: $\mathcal{O}(N^2)$. <spoiler summary="Sample code"> ~~~~~ int n = in.nextInt(); int[] d = in.readIntArray(n); long answer = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { answ...
code) by [user:Tejs,2019-10-21]: The product can be rewritten as $\frac{1}{2} \left[ \left(\sum_i

Full text and comments »

  • Vote: I like it
  • +101
  • Vote: I do not like it

124.
Codeforces Round #338 (Div. 2) editorial
By maxkvant, 11 years ago, translation, In English
Codeforces Round #338 (Div. 2) editorial #### [problem:615A] (Author: [user:TheWishmaster,2016-01-08]) Let's make a counter of number of buttons that switch every lamp off. If there is a lamp with zero counter, output NO, otherwise YES. code: [submission:15260902] #### [problem:615B] (Author: [user:TheWishmaster,2016-01-08]) Way of solving &mdash; dynamic programming. We are given a graph of n vertices and m edges. We will calculate dp[i] &mdash; a maximum length of tail that is ending in i-th vertex. We can simply update dp by checking all the edges from i-th vertex(which are leading to vertices with bigger number), and trying to update them. When we have this dp, we can check the answer easily. code: [submission:15260851] #### [problem:615C] (Author: [user:maxkvant,2016-01-08]) The idea is that if can make a substring t[i, j] using k coatings, then we can also make a substring t[i + 1, j] using k coatings. So we should use the longest substring each time. Let n = |s|, m = |t|. On each stage we will s...
of solving — dynamic programming. We are given a graph of n vertices and m edges. We will

Full text and comments »

  • Vote: I like it
  • +30
  • Vote: I do not like it

125.
MCO 2025 Editorial
By Evirir, history, 19 months ago, In English
MCO 2025 Editorial [problem:606535A] Problem idea: [user:MGod,2025-04-26]<br> Problem preparation: [user:zscoder,2025-04-26] <spoiler summary="Solution"> **Observation 1:** We denote the string at time $t$ to be $S(t)$. Then $S(t) = S(t-1) + S(t-2)$ where $+$ represents string concatenation. **Proof:** We proceed using mathematical induction. The base case $t=2$ can be easily proven by hand. For our inductive step, we wish to show that $S(t) = S(t-1) + S(t-2)$, given that the observation is true time $t-1$. We can split the string $S(t-1)$ into two sections, which are $S(t-2)$ and $S(t-3)$. By definition, performing the operation of replacing $1$ with $10$ and $0$ with $1$ on each of these parts will make the two parts $S(t-1)$ and $S(t-2)$ respectively, which in turn results in $S(t) = S(t-1) + S(t-2)$. **Subtask 1: $Q=1, r \leq 300 000$** The binary string can be generated by brute force, manually performing the operations until the length of the string exceeds $300 000$. The number ...
can build a graph where every district is connected to the rows or columns it occupies. To find the

Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it

126.
Tinkoff Challenge — Final Round Editorial
By zscoder, history, 9 years ago, In English
Tinkoff Challenge — Final Round Editorial <spoiler summary="Bank Robbery"> Author : [user:zscoder,2017-05-13] This is a simple implementation problem. We iterate through all banknotes one by one and check if Oleg can take each of them. If a banknote is at position $x$, then Oleg can take it if and only if $b < x < c$. This can be checked in $O(1)$ time. Thus, the total complexity is $O(n)$. Note that the information on the starting position of Oleg is useless here. <spoiler summary="Code"> ~~~~~ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<ll> vi; typedef long double ld; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; typedef set<int>::iterator sit; typedef...
list together. Suppose there are $k$ such groups. For simplicity, we can create a newgraph where

Full text and comments »

  • Vote: I like it
  • +126
  • Vote: I do not like it

127.
[Editorial] Newton School August 2022 Contest
By dnshgyl21, 4 years ago, In English
[Editorial] Newton School August 2022 Contest #### [A. The Dragon Eggs](https://my.newtonschool.co/playground/code/w429jvr8k2wj/) ------------------ <spoiler summary = "Solution"> ```C++ #include<bits/stdc++.h> using namespace std; ``` signed main() { int g, s, a, b; cin >> g >> s >> a >> b; cout << ((g * a >= s * b) ? "Gold" : "Silver"); return 0; } </spoiler> #### [B. The Clash of the Houses ](https://my.newtonschool.co/playground/code/qr4j78jsds5a/) ------------------ <spoiler summary = "Solution"> Since $i^{th}$ and ${i+k/2}^{th}$ character must be same, and also first half of string is equal to last half of string, this implies that the answer is "1" if and only if count of $1s$ is divisible by 4. </spoiler> <spoiler summary = "Code"> ```C++ #include<bits/stdc++.h> using namespace std; signed main() { int t; cin >> t; for(int i=0; i<t; i++) { int n; cin >> n; string s; cin >> s; int cnt = 0; for(int j=0; j<n; j++) { if(s[j] == '1') cnt++; } if(cnt % 4 ...
connected graph with one cycle. If we consider this new node to have the colour black, we can see that the

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it

128.
Beginner's Guide to Greedy
By dominique38, history, 9 months ago, In English
Beginner's Guide to Greedy _This blog post is a submission for the [Codeforces Month of Blog Posts Pt. III challenge](https://codeforces.me/blog/entry/149422). Thank you [user:cadmiumky,2026-02-10] for the initiative!_ This is how I wish I had been introduced to Greedy. Learning _how to prove_ is the truly valuable skill, one that I believe good Greedy problems test rigorously. ### **Introduction** After struggling with proofs for quite a while, there are a few things I realized. Greedy proofs are very dependent on the rules of the problem. Loosely speaking each optimization problem gives you observations, from those observations, you realize that if you take certain choices while avoiding all others, then it will always be optimal. That realization is termed **Greedy**. There are a lot of optimization problems, but only a small subset allows you to break the problem into smaller independent subproblems where solving them optimally leads to the best global answer. This property, known as Optimal Sub...
< j$ (so $a_i \le a_j$) where $b_i > b_j$.The current product contribution is $P_{\text{current

Full text and comments »

  • Vote: I like it
  • +48
  • Vote: I do not like it

129.
Linear Basis (Xor Basis Extended)
By errorgorn, 5 years ago, In English
Linear Basis (Xor Basis Extended) As part of the graduation requirements for my school, I have to complete a simple research project, so I decided to do something related to data structure and algorithms. I believe I have come out with a data structure that maintains the basis of vectors in $(\mathbb{Z}/m\mathbb{Z})^d$, where $m$ **may not be prime**. Since this was related to competitive programming, I think it is a good idea to share it here. Hopefully, this algorithm is actually novel :P I would like to thank: - [user:icypiggy,2021-12-26] for being my research mentor and tolerating my dumb questions - [user:rama_pang,2021-12-26] and [user:adamant,2021-12-28] for their helpful suggestions and comments Please comment under the blog or message me on codeforces if any parts are unclear or wrong. Also, I hope that some LGMs can help solve the open problems in this blog. # Introduction Maintaining the basis of vectors in $(\mathbb{Z}/2 \mathbb{Z})^d$, also known as the xor basis algorithm is a well-studie...
internal group direct product of cyclic groups whose orders are prime powers. So, $G=\mathbb{Z}/p_1^{k_1

Full text and comments »

  • Vote: I like it
  • +381
  • Vote: I do not like it

130.
Codeforces Round 1132 (Div. 2) — Editorial (Unofficial)
By buachudanike, history, 4 days ago, In English
Codeforces Round 1132 (Div. 2) — Editorial (Unofficial) ##### NOTE: THIS IS AN UNOFFICIAL EDITORIAL FOR THE CONCERNED ROUND SINCE THEY WERE TAKING TOO LONG [A1. 15K4JR3B (Easy Version)](https://codeforces.me/contest/2284/problem/A1) <spoiler summary="Tutorial"> Both versions have the same underlying idea: we want to maximize the product of two sums. The optimal construction places one point at $(x, 0)$, another at $(0, y)$, and the third at the origin. The doubled area of the resulting triangle is $$ xy. $$ In the easy version, every move has length $1$. Therefore, if we split the $n$ operations into two groups, the sums of the groups are simply their sizes. Let the sizes be $x$ and $n-x$. We need to maximize $$ x(n-x). $$ This product is maximized when the two groups are as balanced as possible. Hence, we take $$ x = \left\lfloor\frac{n}{2}\right\rfloor, \qquad n-x = \left\lceil\frac{n}{2}\right\rceil. $$ The answer is therefore $$ \boxed{\left\lfloor\frac{n}{2}\right\rfloor \left\lceil\frac{n}{2...
summary="Tutorial"> Both versions have the same underlying idea: we want to maximize theproduct of two

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it

131.
[Tutorial] Investigating the Harmonic Numbers
By Proofy, 3 years ago, In English
[Tutorial] Investigating the Harmonic Numbers #### **Introduction** This blog contains well-known facts and techniques about Harmonic Numbers that are scattered all over editorials of some problems, comments, and some parts of blog posts. The place where I found most of the facts explained here is the brilliant blog by [user:Nisiyama_Suzune,2023-07-08] about [Möbius inversion](https://codeforces.me/blog/entry/53925). However, for the untrained eye, this blog may seem as if it's investigating something advanced and the facts explained inside will be missed. Moreover, there were some omitted proofs, so I thought it would be nice to collect all these facts/techniques in one place and add their proofs in (hopefully) an understandable but precise style, which would be useful for many. ---- For starters, the $n$th harmonic number, $H_n$, is the sequence $\displaystyle H_n = \sum_{i = 1}^{n}\frac{1}{i}$. We will investigate two techniques related to this sequence. ---- #### **1. Upper bound for Harmonic Numbers** We b...
\in O(\log n)$ This can be noted by observing the graph of $f(x) = \frac{1}{x}$ and

Full text and comments »

  • Vote: I like it
  • +140
  • Vote: I do not like it

132.
2019 Summer PtzCamp, Day 8: XIX Open Cup Onsite, Editorial
By skywalkert, history, 5 years ago, In English
2019 Summer PtzCamp, Day 8: XIX Open Cup Onsite, Editorial This editorial corresponds to [contest:103652], a.k.a "Jingzhe Tang Contest 2", held on Sept. 1st, 2019. Moreover, this problem set is a selection of "CCPC-Wannafly Winter Camp 2018, Day 2 (Div. 1 & Div. 2)" held on Jan 30th, 2019. Feel free to comment on the tutorials listed in the following (with some follow-up questions left to readers). Hope you enjoy solving these problems. --- [problem:103652A] <spoiler summary="solution"> The number of updates can be counted as the number of ordered pairs $(u, v)$ such that when $u$ is going to be removed, there exists at least one path between $u$ and $v$. If the path between $u$ and $v$ is unique in the original graph, we can conclude that pair exists if $u$ is the first removed node on the path with respect to an order, and $\frac{1}{cnt(u, v)}$ of all possible orders would meet this condition, where $cnt(u, v)$ is the number of nodes on the unique path between $u$ and $v$ (inclusive). In other cases, there exist exactly tw...
between $u$ and $v$. If the path between $u$ and $v$ is unique in the original graph, we can

Full text and comments »

  • Vote: I like it
  • +92
  • Vote: I do not like it

133.
Editorial CodeHurdle Athlos 06
By amartya110, 5 months ago, In English
Editorial CodeHurdle Athlos 06 We want to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated! [contest:697296] [problem:697296A] Writer: [user:amartya110,2026-01-19] <spoiler summary="Hint"> Consider the best possible opening move for Alice. Is there a move she can make that immediately removes all future options for Bob?</spoiler> <spoiler summary="Editorial"> Any positive integer $n$ can be uniquely factored into $n = S \cdot M$, where $S$ is the largest perfect square that divides $n$, and $M$ is a strictly square-free integer. This is a finite game of perfect information, but we don't need Nim-values or Grundy's Theorem because there is a dominating "instant win" strategy. * If $n$ is initially square-free, it has no perfect square divisors $> 1$. Alice has no valid moves on turn 1 and loses immediately. * If $n$ is not square-free, Alice can simply choose to divide $n$ by $S$ (the largest perfect square divisor) on her very first...
directed edges: $\vec{AB}$, $\vec{BC}$, and $\vec{CA}$. We can check this using the 2D crossproduct

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

134.
Codeforces Round 1107 (Div. 3) Editorial
By wakanda-forever, 5 months ago, In English
Codeforces Round 1107 (Div. 3) Editorial Thanks for participating. I apologize for the unexpectedly hard B. Apart from that, I hope you liked the problems and enjoyed the round! I would like to thank [user:Proof_by_QED,2026-06-24], [user:Forge,2026-06-30], and [user:awesomeguy856,2026-06-24] for pointing out an elegant $\mathcal{O}(n)$ solution for problem G. I would also like to thank [user:temporary1,2026-06-25] for helping me write the editorial for problem F and [user:Forge,2026-06-30] and [user:reirugan,2026-06-30] for proofreading the editorial. <div style="height:32px"></div> <spoiler summary = "Rating predictions"> <table border="1" cellspacing="0" cellpadding="10" style="border-collapse: collapse; text-align: center; margin: auto;"> <thead> <tr style="background-color: #f0f0f0;"> <th style="text-align: center;">Predictor</th> <th style="text-align: center;">A</th> <th style="text-align: center;">B</th> <th style="text-align: center;">C</th> <th style="text-align...
not lie on $P(u,v)$. Start from $w$ and walk towards the path $P(u,v)$. Since thegraph is a tree

Full text and comments »

  • Vote: I like it
  • +98
  • Vote: I do not like it

135.
I built an ultra fast AI workspace — test its limits with tough coding problems
By M_Sameer, history, 2 months ago, In English
I built an ultra fast AI workspace — test its limits with tough coding problems Hey guys,I wanted to share a project I've been grinding on lately called [SMS AI](https://sms-ai-delta.lovable.app/).Before anyone asks, I want to clarify how it was made. I actually wrote the code and built the backend systems myself. I did not use an AI generator to spit out the project. I only utilized Lovable as a compiler and environment to run my code, test the preview layout, and push it live to a URL.My biggest goal was to get rid of that annoying delay you get with normal wrappers. Right now, it streams code blocks and answers with under 100ms first token response latency, which feels incredibly responsive.Features included:A code generator that highlights algorithmic scripts instantly.Document reading tool powered by global edge connections.Multi-modal chat with streaming memory.It is live on Product Hunt right now because I want to look closely at my custom admin dashboard metrics under a heavy traffic spike. I would really appreciate it if you guys could throw your most com...
memory.It is live on Product Hunt right now because I want to look closely at my custom admin dashboard

Full text and comments »

  • Vote: I like it
  • -21
  • Vote: I do not like it

136.
Beginner DSA Curriculum Made by Me
By ahnaf_cp, history, 22 months ago, In English
Beginner DSA Curriculum Made by Me Hello, Codeforces community! As a beginner in competitive programming, diving into Data Structures and Algorithms (DSA) can feel overwhelming. To make it more approachable, I decided to create my own DSA curriculum tailored for beginners like myself. This curriculum is structured, beginner-friendly, and covers the essential concepts you need to progress in problem-solving and competitive programming. I’d love to share it with you all! Let’s dive in. --- ## Why Create This Curriculum? When I started my journey in programming, I faced these common challenges: - Lack of a clear roadmap. - Getting stuck on advanced topics without mastering the basics. - Feeling lost with random tutorials and problem sets. This curriculum addresses these issues by providing a **structured, progressive approach** to learning DSA. It’s designed to build a solid foundation, grow confidence, and gradually tackle harder problems. --- ## Curriculum Overview ### 1. **Foundations of...
://codeforces.com/problemset/problem/1360/B) - [Codeforces — B. Maximum Product ](https

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it

137.
[Tutorial] Fully Dynamic Trees Supporting Path/Subtree Aggregates and Lazy Path/Subtree Updates
By smax, 4 years ago, In English
[Tutorial] Fully Dynamic Trees Supporting Path/Subtree Aggregates and Lazy Path/Subtree Updates Hey everyone! Usually when I post stuff on CF I just drop an external link to my blog, but this time I would like to also paste the same content natively on CF to see if it leads to more engagement. You can read the exact same article on my blog [here](https://mzhang2021.github.io/cp-blog/ds5/). Also, special thanks to [user:alien_lover,2022-06-10] and [user:gabrielwu,2022-06-10] for proofreading. --- ## Motivation We will solve **[this problem](https://dmoj.ca/problem/ds5)**. ## Prologue The original name of this problem is [SONE1](https://darkbzoj.cc/problem/3153), originating from the fiery depths of Chinese OI. Amazingly, the Chinese have figured out how to augment the link/cut tree to solve this problem (ref [1](https://www.cnblogs.com/clrs97/p/4403244.html), [2](https://blog.csdn.net/iamzky/article/details/43494481)). Maintaining subtree aggregates with a LCT isn't difficult, and there's a well-known [Codeforces article](https://codeforces.me/blog/entry/67637) ...
graph we are representing. This is not to be confused with the structure of the LCT data structure

Full text and comments »

  • Vote: I like it
  • +259
  • Vote: I do not like it

138.
Good Bye 2022 -- Editorial
By Nanako, 4 years ago, In English
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...
think about how it's related to graph theory. Try to

Full text and comments »

  • Vote: I like it
  • +243
  • Vote: I do not like it

139.
Tutorial on FFT/NTT — The tough made simple. ( Part 2 )
By sidhant, history, 10 years ago, In English
Tutorial on FFT/NTT — The tough made simple. ( Part 2 ) <h1> Welcome to Part 2</h1> Firstly, I am assuming that you have been through the [Part 1](http://codeforces.me/blog/entry/43499) of this blog. Okay so in hindsight I now see the drawbacks there were in my explanation of the roots of unity and how the divide and conquer works in FFT. <b>So in this blog I would be aiming to give you a visual intuition of what really FFT exploits over the trivial classical DFT. Also I would be covering up NTT and sharing a nice trick that I got to know about while learning NTT.</b> <h2> Visual Intuition of FFT $\rightarrow$ </h2> The part of converting the polynomial from coefficient form to point value form in $N\cdot \log_2 N$ instead of the trivial $N^2$ would be elaborated upon in this section as I find the dry mathematical explanation to be rigorous but not intuitive. In the notation below I have referred to $n$ complex $n^{th}$ roots of unity as powers of $w_n^{1} = e^{2\pi \cdot i/n}$ Assume that you have a $8$ terms ($7$ degre...
you mark the 8th roots of unity on a graph it is regular octagon whose vertices are making angle $0

Full text and comments »

  • Vote: I like it
  • +116
  • Vote: I do not like it

140.
A problem on Tree
By Yellow.Flash, history, 9 years ago, In English
A problem on Tree Hi , i need help in [this question](https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/skrtel/description/) Problem statement in short : **Given a tree,every node has a value written on it.** **There will be several queries of two types:** **1 &mdash; update value of any node of tree** **2 &mdash; tell if the product of values of node on path from u to v is divisble by k** **All constraints are of order 10^5.** Editorial is not properly explained. Thanks
types:** **1 — update value of any node of tree** **2 — tell if the product of

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

141.
Algorithms repo on github
By levonog, 7 years ago, In English
Algorithms repo on github Hi all! Several months ago I decided to write down all the algorithms I know (and don't know) in one Visual Studio project for reusing, remembering, preparing to the interviews and easy learning of new algorithms and compose them in the one big library. I have implemented some part of this library, but before going deeper I want to provide some examples of library current usages: <spoiler summary="Example"> For example, you can compute Fibonacci n-th element using matrix exponentiation by writing the following code: ~~~~~ #include <iostream> #include <Math/Math.h> using namespace std; int main() { algo::Matrix<int> mat{ {1, 1}, { 1, 0 } }; algo::Matrix<int> neutral{ {1, 0}, { 0, 1 } }; algo::Matrix<int> fib { {1, 1} }; mat = algo::bin_pow(mat, 7, neutral, algo::matrix_mul<int>); fib = algo::matrix_mul(fib, mat); cout << fib[0][0]; // prints 34 } ~~~~~ After this code compiles another file is generated that do not contain any of r...
::UpdateType::Sum); // update type (assigning, product or sum for now) vector ans(n

Full text and comments »

  • Vote: I like it
  • +69
  • Vote: I do not like it

142.
TheForces Round #43 (DIV2-Forces) Editorial
By wuhudsm, history, 16 months ago, In English
TheForces Round #43 (DIV2-Forces) Editorial Reminder: We welcome you to participate in the official DIV1/DIV2 round scheduled on the 31st! [A](https://codeforces.me/gym/106014/problem/A) Idea:[user:tamzid1,2025-07-25] <spoiler summary="solution"> We can see if $x$ is a perfect square, $x^x$, $x^{(x^x)}$, $\ldots$ are also perfect square. Proof: assume $x=y^2$, $x^z=(y^z) \cdot (y^z)$. So the answer is the number of perfect squares not greater than $n$. There are exactly $\lfloor \sqrt{n} \rfloor$ integers $x$ (with $1 \leq x \leq n$) such that $x$ is a mystic number. </spoiler> <spoiler summary="code(C++)"> ```cpp #include <iostream> #include <cmath> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; cout << static_cast<int>(sqrt(n)) << '\n'; } return 0; } ``` </spoiler> <spoiler summary="Rate the Problem"> Amazing problem: Goo...
] #### 1. Observation The product of: — Number of non

Full text and comments »

  • Vote: I like it
  • +28
  • Vote: I do not like it

143.
Editorial for CodeHurdle Athlos 03
By amartya110, 8 months ago, In English
Editorial for CodeHurdle Athlos 03 We want to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated! [Contest Link](https://codeforces.me/contestInvitation/757663ba04187f27abf08bbf2fa40710f1777b4f) ### [A — Modular Station Assembly](https://codeforces.me/gym/677155/problem/A) Writer: [user:amartya110,2026-01-19] <spoiler summary="Editorial"> Even Dimensions: If $n$ or $m$ is even, the grid can be perfectly tiled using only $1 \times 2$ I-Beams, making the answer YES.Thin Grids: If $n=1$ or $m=1$ (and the other is odd), the C-Core module cannot fit physically as it requires a $2 \times 3$ footprint, leaving an odd area that $1 \times 2$ beams cannot fill (NO).Small Odd Grids ($3 \times 3$): Although the area is 9, placing a $2 \times 3$ footprint C-Core in a $3 \times 3$ space creates geometric obstructions that prevent the remaining 4 cells from forming two valid $1 \times 2$ blocks (NO).Large Odd Grids: For all other odd $n, m \ge 3$, there is sufficient...
$ can reach $10^{14}$, the product $a \cdot x$ can exceed the capacity of a 64-bit integer

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

144.
Russian Code Cup 2017 Finals — Results and Editorial
By RussianCodeCup, history, 9 years ago, In English
Russian Code Cup 2017 Finals — Results and Editorial First of all, congratulations to [user:moejy0viiiiiv,2017-09-10] for winning, [user:LHiC,2017-09-10] and [user:jcccccccccccccccccccccsb,2017-09-10] for coming second and third. The Final Round proved to be quite challenging, and we are happy that the results are tight. The round was prepared by [user:Aksenov239,2017-09-10], [user:GShark,2017-09-10], [user:izban,2017-09-10], [user:manoprenko,2017-09-10], [user:niyaznigmatul,2017-09-10], [user:qwerty787788,2017-09-10] and [user:SpyCheese,2017-09-10], supervisor [user:andrewzta,2017-09-10]. Special thanks for this round goes to [user:izban,2017-09-10] who is the author of problems D, E and F, and also gave a lot of important comments for all problems of the round. Now let us move on to the editorial. <div class="problem-statement"><div class="header"><div class="title">A. Set Theory</div></div><div class="tutorial"><p>First let us prove that the answer is always <span class="tex-font-style-tt">YES</span>.</p><p>Let us iterate ove...
>Let us consider the following similarity graph: the vertices

Full text and comments »

  • Vote: I like it
  • +47
  • Vote: I do not like it

145.
Errichto's categories list
By thecoolkid, history, 6 years ago, In English
Errichto's categories list hello I recently came upon this list of categories made by Errichto and I think it's great but I don't know in which order one should start or what are some topics that are must know and others that I can learn later? ### **categories** Implementation; vectors and sets * Binary search * Prime sieve; prime check in O(sqrt(N)) Dynamic Programming &mdash; Fibonacci numbers, prefix sums * Sorting * Greedy * Ad-hoc Graphs &mdash; graph representation, BFS, DFS, trees * Geometry &mdash; distance between two points Bitmasks Two pointers, sliding window Data structures &mdash; sqrt decomposition, segment trees, Fenwick/BIT, persistent structures, Policy-Based-DS, treaps, BST Ternary search Interactive problems LIS LCS Maths Number theory Combinatorics, probability, EV Find & Union Game theory &mdash; NIM, Grundy Hashing Strings &mdash; KMP, Z Geometry &mdash; cross product, convex hull Matrix exponentiation Divid...
sums * Sorting * Greedy * Ad-hoc Graphs — graph representation, BFS, DFS, trees

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it

146.
MemSQL Start[c]UP 2.0 Round 1 and 2 Editorials
By AlexSkidanov, 12 years ago, In English
MemSQL Start[c]UP 2.0 Round 1 and 2 Editorials Round1 ====== Problem B --------- The critical observation in this problem is that the points will be at the corners or very close to the corners. After that one simple solution would be to generate a set of all the points that are within 4 cells from some corner, and consider all quadruplets of points from that set. Problem C --------- When the magician reveals the card, he has $1 \over k$ chance to reveal the same exact card that you have chosen. With the remaining ${k-1} \over k$ chance he will reveal some other card. Since all the cards in all $m$ decks are equally likely to be in the $n$ cards that he uses to perform the trick, he is equally likely to reveal any card among the $n \times m - 1$ cards (-1 for the card that you have chosen, which we assume he has not revealed). There are only $m - 1$ cards that can be revealed that have the same value as the card you chose but are not the card you chose. Thus, the resulting probability is ${1 \over k} + {{k-1} \over k} \time...
product of numbers of occurrences of the suffix in each of the strings. Since you do have shortcuts

Full text and comments »

  • Vote: I like it
  • +94
  • Vote: I do not like it

147.
Codeforces Round 1045 (Div. 2) Editorial
By henotrix, 15 months ago, In English
Codeforces Round 1045 (Div. 2) Editorial Unfortunately, the round turns out to be very unbalanced :( I'm deeply sorry about this issue. I hope you still enjoy the problems. <spoiler summary="Rate the contest! (definitely not copied from past contests)"> <spoiler summary="Quality"> * Excellent contest * Good contest * Average contest * Bad contest * Horrible contest </spoiler> <spoiler summary="Difficulty"> * Trivial contest * Easy contest * Average contest * Hard contest * Impossible contest </spoiler> </spoiler> [problem:2134A] <spoiler summary="Hint 1"> Check the parity of numbers $a$, $b$, and $n$. </spoiler> <spoiler summary="Solution"> Let us first consider the $b$ blue cells. Since all $b$ cells appear in the final painting, for the coloring to be symmetric, they must be placed at the middle of the grid...
$ such that $\gcd(x,k) = 1$, and set $g = x$. Note that $g \leq 29$, since $k \leq 10^9$ and theproduct

Full text and comments »

  • Vote: I like it
  • +199
  • Vote: I do not like it

148.
HCW '19 Team Round Editorial
By low_, history, 7 years ago, In English
HCW '19 Team Round Editorial This is an editorial blog for [contest:102279]. Any further question can be asked in the comments, I'll try to answer all the questions. Please, do not private message or email me, your question could be the same as others', and I really hate to answer one question multiple times. >:( [problem:102279A] ------------------ Author: [user:low_,2019-07-22]. <spoiler summary="Tutorial"> To solve the problem, you'll only need to note that in $(N+1)$-th turn: Seo moved through exactly $(N+1)*V_s$ property, that is exactly $V_s$ full round of the board, so that he end up in $1$ afterwards. The same happens with B21 and Lowie. After that, the game keeps repeating itself. We can conclude that: if there isn't any event of one paying other in the first $3*(N+1)$ turns, it will never happen, so we can output $3000000000$. Otherwise, we can find the first event of it by brute force in $O(3*(N+1))$ time complexity. Maximum time complexity: $O(3*(N+1))$. </spoiler> [problem:102279B]...
can ask for a subsegment of length $2$ and find out both element 100% correctly (because theproduct

Full text and comments »

  • Vote: I like it
  • +27
  • Vote: I do not like it

149.
Russian Code Cup Qual 2 — Editorial
By RussianCodeCup, history, 10 years ago, translation, In English
Russian Code Cup Qual 2 — Editorial <h2>A. Very Important Persons</h2> <p>There are two main ways to solve the problem.</p><p>The first way is to assign guests to seats by diagonals, starting from the seat (1,&thinsp;1). You should be careful with considering cases <i>n</i>&thinsp;&lt;&thinsp;<i>m</i> and <i>m</i>&thinsp;&lt;&thinsp;<i>n</i> when implementing traversal. </p><p>The second way is a more common solution which however requires more advanced algorithm. Let us run BFS from (1,&thinsp;1) and assign seats to guests in order they are popped from the queue, starting from the most important one.<h2>B. Least Common Multiple</h2> <p>Let <i>p</i>&thinsp;/&thinsp;<i>q</i> be divisible by both <i>a</i>&thinsp;/&thinsp;<i>b</i> and <i>c</i>&thinsp;/&thinsp;<i>d</i>, all fractions are irreducible. So the numbers (<i>p</i>&thinsp;/&thinsp;<i>q</i>):&thinsp;(<i>a</i>&thinsp;/&thinsp;<i>b</i>)&thinsp;=&thinsp;(<i>p</i>&middot;<i>b</i>)&thinsp;/&thinsp;(<i>q</i>&middot;<i>a</i>) and (<i>p</i>&thinsp;/&thinsp;<i>q</i>):&thin...
do it consider the given array as a directed graph, if a[i] = j

Full text and comments »

  • Vote: I like it
  • +34
  • Vote: I do not like it

150.
[Gym Contest Editorial] Egyptian Collegiate Programming Contest (ECPC 2015)
By RedNextCentury, 11 years ago, In English
[Gym Contest Editorial] Egyptian Collegiate Programming Contest (ECPC 2015) **Note:** All complexities mentioned in this editorial are per test case. ### A: Arcade Game Let $perm$ be the number of permutations for the digits of $n$. First, sort all these permutations in decreasing order and give each permutation a rank (0 is the largest permutation, 1 is the second largest and so on). $ans[0]=0$ $ans[1]=\displaystyle \frac{1}{perm}$ $ans[rank]=\displaystyle \frac{1}{perm} * (1+ans[rank-1]+ans[rank-2]+...)$ find the rank of $n$ and print it's value from the array. Note: the relation mentioned above can be reduced to: $ans[rank] = \displaystyle \frac{(perm+1)^{rank-1}}{perm^{rank}} $ Which could be written as (to avoid overflow): $ans[rank] = \displaystyle \frac{(\frac{perm+1}{perm})^{rank-1}}{perm} $ Complexity: $O(rank)$ ### B: Unlucky Teacher There are two ways for an answer to a question to be unique: 1) this question was answered correctly in one of the papers. 2) this question was answe...
: Connecting Graph In this solution, I am going to use a more basic version of DSU, which is

Full text and comments »

  • Vote: I like it
  • +41
  • Vote: I do not like it

151.
CSES Mathematics Section Tutorial
By divyamsingal01, 6 years ago, In English
CSES Mathematics Section Tutorial So I did not find a tutorial for Maths section of CSES on codeforces, so thought of writing one. I have put all my codes on https://github.com/div5252/CSES-Problem-Set. **This tutorial covers 29 questions of Mathematics Section of CSES.** **1. Josephus Queries** <spoiler summary="Tutorial"> We will solve the problem recursively, reducing the problem by at least half at each step. If $k<\frac{n}{2}$, we can see that the answer would be $2k$. Otherwise, we have removed all the even positions. The odd positions can be renamed from $1,2,\dots,\frac{n}{2}$ and we can recursively find the solution for it. And then we can re-map back to our original $n$ by multiplying by $2$ and subtracting $1$. Time complexity is $O(logn)$. </spoiler> <spoiler summary="Code"> ~~~~~ ll f(ll n,ll k) { if(n==1) return 1; if(k<=(n+1)/2) { if(2*k>n) return (2*k)%n; else return 2*k; } ll temp=f(n/2,k-(n+1)/2); if(n%2==1) return 2*temp+1; ...
}{x_n-1})$. Product of divisors is $num^{\frac{d(num)}{2}}$, where num is the number given (in form

Full text and comments »

  • Vote: I like it
  • +92
  • Vote: I do not like it

152.
My Pupil's editorial for Codeforces Round 976 (Div. 2) and Divide By Zero 9.0 -
By Orn0, 2 years ago, In English
My Pupil's editorial for Codeforces Round 976 (Div. 2) and Divide By Zero 9.0 - I recently took part in [contest:2020], and I performed ... poorly (only A after 6 bad submissions). Thinking about this traumatizing experience, I first tried to find excuses. I entered 15 minutes late, I was sick and unprepared. But I realized that there were more to learn from it, and I wanted to try and produce a custom editorial of the first 4 problems in the contest to better understand and share what I did wrong (and also perhaps right thing :)).<br> Welcome to my humble editorial ##[problem:2020A] The first step was to understand the structure of the optimal solution. For given $n$ and $k$, the optimal number of operations is obtained by removing the largest possible portions of $n$ of the form $k^x$ at each step, i.e. finding the largest $x$ such that $k^x \leq n$. The algorithm is as follows : ``` while n > 0 x = findLargestX(n,k) while n-k^x > 0 n -= k^x ``` I was quickly able to see that the answer is the sum of the digits of $n$ in ba...
terms of product, there are more even number than odd number. Taking two

Full text and comments »

  • Vote: I like it
  • +32
  • Vote: I do not like it

153.
Meta Hacker Cup 2025 — Round 1 Editorial
By algoslayer, 13 months ago, In English
Meta Hacker Cup 2025 — Round 1 Editorial Hey everyone I recently participated in **Meta Hacker Cup 2025 Round 1** and I’m thrilled to share that I secured **Rank 333 / 13,676** with a **perfect score of 105/105**, successfully solving every problem from **A1 → D**! I've qualified for Round 2 of the Meta Hacker Cup 2025! Round 1 was a fantastic set of problems, and I managed to solve all of them for a full score. This post includes **my hints, solution approaches, and final codes** for all problems — written to help learners strengthen their **DSA and problem-solving** intuition. [A1: Snakes Scales (Chapter 1) :](https://www.facebook.com/codingcompetitions/hacker-cup/2025/round-1/problems/A1) <spoiler summary="Hint"> Snake must walk from platform 1 to N. To get from platform $i$ to $i+1$, he needs a ladder of height $|A_i - A_{i+1}|$. Since he brings only one ladder, it must be tall enough for the hardest (i.e., highest) adjacent jump in the entire path. </spoiler> <spoiler summary="Solution"> The s...
real problem is: for a given height $h$, can you visit all platforms? Think of this as agraph

Full text and comments »

  • Vote: I like it
  • -46
  • Vote: I do not like it

154.
I built a Codeforces coach that lives in Telegram
By Tedacodder, history, 5 days ago, In English
I built a Codeforces coach that lives in Telegram # I built a Codeforces coach that lives in Telegram ### Daily problems, contest alerts and class leaderboards. No app to install. --- Every competitive programmer knows the routine. You open Codeforces, scroll for a problem near your level, pick one, and by the time you're finally in the zone, **twenty minutes are gone**. I wanted something simpler: a problem should arrive **where I already am**, which is Telegram. So I built **[@AlgoryvaBot](https://t.me/AlgoryvaBot)**. --- ## What it does ### Problems on demand Send `/random 1200-1600 dp graphs` and get a problem in that rating band with those tags. Connect your handle once, and it **skips everything you've already solved**. ### A daily problem One challenge, chosen for you, every day. It's the **same problem for everyone** that day, so it's easy to talk about with friends. ### Contests without the tab-switching - `/contests` shows what's coming up. - `/next` shows the one starting soonest. - You ...
**. That limit shapes the product. Checking fifty accounts takes a couple of minutes, and the bot **says

Full text and comments »

  • Vote: I like it
  • -27
  • Vote: I do not like it

155.
Unlabeling combinatorial species (cycle index series)
By adamant, history, 4 years ago, In English
Unlabeling combinatorial species (cycle index series) Hi everyone! In my [previous blog](https://codeforces.me/blog/entry/103979), I wrote about how generating functions can be used to enumerated labeled species. In this blog, I want to continue the topic by writing about how one can account for different kinds of symmetries when counting different combinatorial structures. Ultimately, we will end up deriving and hopefully understanding the analogue of [Pólya enumeration theorem](https://en.wikipedia.org/wiki/Pólya_enumeration_theorem) in species. Difficulty: ★★★★☆ Prerequisites: - Familiarity with combinatorial species (see my [prev. blog](https://codeforces.me/blog/entry/103979)), OR - Very good intuition with enumerative combinatorics, genfuncs and recap below. I will try to use plain language rather than formulas as much as possible, as it seems to be the preferred format for readers. ## Recap Below is a very brief recap of the most important things from the previous article. I tried to keep it as informal as p...
as the vertices of a graph, the pairs of brackets in a bracket sequence, etc. For example, you may

Full text and comments »

  • Vote: I like it
  • +177
  • Vote: I do not like it

156.
Codeforces Round 901 (Div. 1, Div. 2) Editorial
By Gellyfish, 3 years ago, In English
Codeforces Round 901 (Div. 1, Div. 2) Editorial ## [problem: 1875A] <spoiler summary="Tutorial"> We can use one tool each time the timer reaches to $1$, then the answer will be $\sum_{i=1}^n \min(a - 1, x_i) + b$. This can prove to be optimal. Because for each tool, if we use it when the timer is $c$, its contribution to the answer is $\min(x_i, a - c)$. We can't use the tool when the timer is less than or equal to $0$ because the bomb will explode before that, so $c=1$ is the optimal. Time complexity: $O(n)$ per test case. Memory complexity: $O(1)$ per test case. </spoiler> <spoiler summary="Code"> ```c++ #include<bits/stdc++.h> using namespace std; int n = 0, a = 0, b = 0; long long ans = 0; inline void solve(){ scanf("%d %d %d", &a, &b, &n); ans = b; for(int i = 0, x = 0 ; i < n ; i ++){ scanf("%d", &x); ans += min(a - 1, x); } printf("%lld\n", ans); } int T = 0; int main(){ scanf("%d", &T); for(int i = 0 ; i < T ; i ++) solve(); return 0; } ``` </spoiler> ## [probl...
complexity $O(n^4)$ using Lagrange Interpolation. The only thing we need to do is the dotproduct

Full text and comments »

  • Vote: I like it
  • +220
  • Vote: I do not like it

157.
2015 Facebook Hacker Cup Round 1
By yongwhan, 12 years ago, In English
2015 Facebook Hacker Cup Round 1 ## **General Comment** I did not spend too much time on thinking about the execution time since the 6-minute is usually much more than the required in the usual online contest (e.g., 2 seconds for CodeForces for instance). So, for each problem, I took whichever way leading me to code reliably. Also, for each problem, I did lots of stress testing since I screwed up few contests (e.g., the large input in the previous Google Code Jam) before by not fully testing my codes with respect to the full constraint given by the problem. For A and C, I generated the edge cases manually and compared the computed answers from the brute force approaches and made sure they match. For B and D, I generated the theoretical worst case to make sure they are handled properly using my codes. Thankfully, I hit few segmentation fault problems 4-5 hours into the contest, from which I tried few approaches to increase the stack size; manipulating the size limit in `#include<sys/resource.h>` did the trick ...
was probably the intended solution. By the way, since the product of first 9 primes is already

Full text and comments »

  • Vote: I like it
  • +47
  • Vote: I do not like it

158.
Hack me! (CF Round #263, Div. 2)
By kostka, 12 years ago, In English
Hack me! (CF Round #263, Div. 2) Welcome again! I decided to split statistics for both division. Post for first division <strike>will be added later</strike> is <a href="http://codeforces.me/blog/entry/13572">here</a>. So, let's look at hacks in [contest:462]. <small><strike>Some statistics are missing &mdash; I have some problems with downloading all data (Codeforces seems little crowded today). They will be also added later.</strike></small> **Update**: Europe went asleep, so I added missing stats. [cut] <h3>Stats</h3> Problem | Successful hacks | Unsuccessful hacks | Other | Sum | :---:|:---:|:---:|:---:|:---:| [problem:462A] | 5 (17%) | 25 (83%) | 0 (0%) | 30 | [problem:462B] | 1193 (71%) | 188 (11%) | 306 (18%) | 1687 | [problem:462C] | 0 (0%) | 55 (36%) | 98 (64%) | 153 | ### Fastest hackers Problem | Time | Hacker | Defender | Hack :---:|:---:|:---:|:---:|:---:| [problem:462A] | 00:50:08 | [user:ak.bewildered,2014-08-26] | [user:abdohammam95,2014-08-26] | <a href="http://codefo...
product should be long long and the result is correct (`10000000000`). #### [problem:462C] We

Full text and comments »

  • Vote: I like it
  • +113
  • Vote: I do not like it

159.
Codeforces Round #191 — Tutorial
By fchirica, 13 years ago, In English
Codeforces Round #191 — Tutorial [problem:327A] I’ll present here the O(N ^ 3) algorithm, which is enough to solve this task. Then, for those interested, I’ll show a method to achieve O(N) complexity. **O(N ^ 3) method:** The first thing to observe is that constrains are slow enough to allow a brute force algorithm. Using brute force, I can calculate for each possible single move the number of 1s resulting after applying it and take maximum. For consider each move, I can just generate with 2 FOR loops all indices i, j such as i <= j. So far we have O(N ^ 2) complexity. Suppose I have now 2 fixed vaIues i and j. I need to calculate variable cnt (initially 0) representing the number of ones if I do the move. For do this, I choose another indice k to go in a[] array (taking O(N) time, making the total of O(N ^ 3) complexity). We have two cases: either k is in range [i, j] (this means i <= k AND k <= j) or not (if that condition is not met). If it’s in range, then it gets flipped, so we add to count variable 1 – ...
of product” and we get 2 * 2 * 2 … * 2 (i – 1 times) = 2 ^ (i – 1). Applying “rule ofproduct” on

Full text and comments »

  • Vote: I like it
  • +86
  • Vote: I do not like it

160.
[Tutorial] A New Perspective on Numbers and Operators: Introducing Group Theory
By UnexpectedValue, 21 month(s) ago, In English
[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://codeforces.me/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://codeforces.me/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...
, assume after product they belongs to class $[x]_n$ , without loss of generality $c>b$ , hence $k_2

Full text and comments »

  • Vote: I like it
  • +93
  • Vote: I do not like it

161.
Divide by Zero 4.0 Summary
By usaxena95, history, 11 years ago, In English
Divide by Zero 4.0 Summary ##Statistics Total Users/Teams who have made a submission: **754** Total Submissions: **4212** Number of distinct users/teams with correct submissions: **498** [Contest Link]( https://www.codechef.com/DIBZ2016) [Feedback form](http://goo.gl/forms/cMY4KZLEJV) --- ##Winners <li>Rank 1: [user:Sumeet.Varma,2016-01-31]</li> <li>Rank 2: [user:amankedia1994,2016-01-31]</li> <li>Rank 3: [user:PrashantM,2016-01-31]</li> --- The Editorials of the following problems are prepared by me, [user:aditya1495,2016-01-31] and [user:_shil,2016-01-31]. --- ##Shil and RasenShuriken (setter: [user:_shil,2016-01-31])<br> Total number of pairs such that their product is even. Count total number of odd numbers = x.<br> Product of two numbers is odd if the both numbers are odd.<br> Ans = **N*(N-1)/2 &mdash; x*(x-1)/2** --- ##Shil Loves Exclusive Or (setter: [user:_shil,2016-01-31])<br> Use the fact that Xor of 2x and 2x+1 is 1.<br> Therefore xo...
product is even. Count total number of odd numbers = x. Product of two numbers is odd if the both

Full text and comments »

  • Vote: I like it
  • +52
  • Vote: I do not like it

162.
10 Beginner Mistakes That Cost Me AC on Codeforces
By OmarSecondAccount, history, 6 weeks ago, In English
10 Beginner Mistakes That Cost Me AC on Codeforces # Small Competitive Programming Mistakes That Cost Me AC ![10 Beginner Mistakes](/predownloaded/69/f1/69f1327e681720d30d7b5263dbbd0664bd4ff82e.png) Hi everyone! I am still learning competitive programming, and recently I noticed that many of my wrong submissions were not caused by difficult algorithms. They were caused by very small mistakes. So I decided to collect some of the mistakes that cost me AC, especially for beginners. [cut] ## 1. Using `int` when the answer needs `long long` Sometimes every individual value fits inside `int`, but their product or total sum does not. For example: ```cpp int n = 100000; int x = 100000; cout << n * x; ``` `n * x = 10^10`, which does not fit inside a 32-bit `int`. A safer version is: ```cpp long long ans = 1LL * n * x; ``` The important part is `1LL`. --- ## 2. Forgetting that integer division removes the decimal part Consider: ```cpp int x = 25; double p = x / 100; ``` You migh...
`long long` Sometimes every individual value fits inside `int`, but their product or total sum

Full text and comments »

  • Vote: I like it
  • -14
  • Vote: I do not like it

163.
Editorial: Codeforces Beta Round #83
By Atef, 15 years ago, In English
Editorial: Codeforces Beta Round #83 <p></p><div><h3 style="text-align: center;"><a href="http://codeforces.me/contest/108/problem/A">Palindromic Times</a><br></h3></div><div><div><div style="text-align: center; ">Writer:&nbsp;<span class="Apple-style-span" style="font-family: verdana, arial, sans-serif; font-size: 14px; background-color: rgb(255, 255, 255); "><a href="http://codeforces.me/profile/Atef" title="Captain Atef" class="rated-user user-violet" style="font-family: arial; font-weight: bold; color: rgb(0, 0, 204); text-decoration: none !important; ">Atef</a></span></div><div style="text-align: center; "><br></div><div>In this problem it was required to find next palindrome on a digital clock. Since the lowest unit of time used $1$ minute, and there are only $24 * 60$ minutes in a day, one could simply go through each minute starting from the time given in the input plus $1$ minute, until finding a palindrome. If no palindrome is found till the end of the day $23:59$, the output should then be $00:00$.</div><div><...
a graph of houses as nodes and one-way pipes as edges. The problem states that thegraph will

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

164.
Challenge24 2012 — Finals
By Nickolas, 15 years ago, translation, In English
Challenge24 2012 — Finals Challenge24 finals are finally over, and as usual, I hurry to share my impressions about them. The impressions are sponsored by team Progopedia (Andrii Maksay a.k.a. [user:maksay,2012-05-03], Sergii Dymchenko a.k.a. [user:kit1980,2012-05-03] and me). Such things are the best to write immediately after the contest, while the emotions still invade you. Of course, one can start writing them while still in the competition (and last year I did so --- I was pretty useless at night anyways), but this year we felt alert and fought for the points till the last minutes of the contest, so the blog post was postponed. The main part of Challenge 24 took a bit less than 48 hours: registration and optional sightseeing on Friday, the round itself from Saturday morning to Sunday morning, and winners announcement and closing ceremony (for the toughest contestants who don't really need all that sleep) on Sunday noon. [cut] We arrived on Friday mid-afternoon, and went to the university immediatel...
calculation of a product of numbers module 10..07. The simplicity of the solution was tainted by an

Full text and comments »

  • Vote: I like it
  • +73
  • Vote: I do not like it

165.
CC Wing Selection Contest 2026
By vishwas_16.0, history, 3 months ago, In English
CC Wing Selection Contest 2026 Editorial CC Wing Selection Contest 2026 ================== [contest:709193] ------------------ </br> [Invitation Link](https://codeforces.me/contestInvitation/6272dbd500a98e5b9fb8fdc43969fd8573242e5a) </br> [Problem A : Terms and Conditions](https://codeforces.me/gym/709193/problem/A) <br> Author : [user:vishwas_16.0,2026-08-12] <spoiler summary="Hint 1"> The input is irrelevant. The required output is fixed and must be printed exactly as given.</spoiler> <spoiler summary="Solution"> This is a direct output problem. We are given a single string as input, but regardless of what the input contains, we must print the four Terms and Conditions exactly as specified in the statement. Since the required output is constant, there is no need to process the input. Just print: You confirm that you are a IIIT Allahabad Batch 2029 student. You understand that providing false information, copying code may result in removal from the wing. You accept that parties wil...
) into a new directed graph. A deletable edge (1, v) can be deleted only if it isn't in the new

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

166.
Teamscode Summer 2023 Editorial
By hyforces, history, 3 years ago, In English
Teamscode Summer 2023 Editorial This is the editorial for the recent Teamscode Summer 2023 contest, and the problems are open for upsolving on this [gym](https://codeforces.me/gym/104520). Problems were prepared by [user:oursaco,2023-08-22], [user:dutin,2023-08-22], [user:thehunterjames,2023-08-22], [user:Bossologist,2023-08-22], [user:Esomer,2023-08-22], [user:danx,2023-08-22], [user:codicon,2023-08-22], [user:willy108,2023-08-22], and [user:hyforces,2023-08-22]. The problems were tested by [user:omeganot,2023-08-22], [user:codicon,2023-08-22], [user:cry,2023-08-22], [user:skye_,2023-08-22], [user:Litusiano_,2023-08-22], and [user:apple_method,2023-08-22]. ### [A. Who is cooking?](https://codeforces.me/gym/104520/problem/A) <spoiler summary="Solution"> danx </spoiler> <spoiler summary="Code"> ~~~~~ print("Esomer") ~~~~~ </spoiler> ### [B. Restaurant Sorting](https://codeforces.me/gym/104520/problem/B) <spoiler summary="Solution"> The answer is $n - $ the longest prefix of the array where a...
then the product would be multiple of $x$. So, the minimum number of clues is $k$ and we discard all

Full text and comments »

  • Vote: I like it
  • +84
  • Vote: I do not like it

167.
A2SV Contest #24 Editorial
By nuredinbederu10k, history, 15 months ago, In English
A2SV Contest #24 Editorial [Here](https://codeforces.me/contestInvitation/3f06f4e1ac120eedc5edd3945965af03bdf0976a) is the link to the contest. All problems are from Codeforces' problem set [A. Life of a Flower](https://codeforces.me/gym/626626/problem/A) <spoiler summary="Solution"> We are given an array of length $n$ that represents whether Petya watered his flower each day. Each element $a_i$ is either: - $1$ → the flower **was watered** - $0$ → the flower **was not watered** The flower begins at a height of **$1$ cm** on **day 0** (before processing any input days). --- ## Simulation Logic We iterate through the array starting from index $1$ (the **second day**), and at each step, we examine the **current** element $a_i$ and the **previous** element $a_{i-1}$. There are **four possible scenarios**: --- - **Case 1:** $a_i = 1$ and $a_{i-1} = 1$ → The flower was watered **both yesterday and today** → It grows by **$5$ cm** → `height += 5` --- - **Case...
) ``` [B. Make Product Equal One](https://codeforces.me/gym/626626/problem/B

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

168.
Editorial: VII UnBalloon Contest
By arthur_9548, 6 months ago, In English
Editorial: VII UnBalloon Contest We hope everyone enjoyed the problems of [contest:106523]! This editorial contains the description of the solutions and their implementation. Feel free to discuss them in the comments! #### Problem A - Idea: [user:lucassala,2026-05-17] - Preparation: [user:lucassala,2026-05-17] <spoiler summary="Solution"> This is a classic problem where we can solve the queries offline. First, we receive all the queries, calculate the response for each node, and then respond. To calculate the response for each node, we will perform a DFS starting at vertex $1$ and create a map where we maintain the frequency of each color along the path from the root to the current node in the DFS. When we enter a new vertex, we add $1$ to the frequency of the current vertex's color in the map, and when we leave that node, we subtract $1$ from that color's frequency. Furthermore, we must ensure that all colors in the map have a positive frequency, removing any colors that reach a frequency of $0$ from the map...
. Consider the functional graph induced by $L'$, where $i$ has an edge to $min(N+1, L'_i)$ and $N+1

Full text and comments »

  • Vote: I like it
  • +23
  • Vote: I do not like it

169.
Code Clash 2026 Editorial
By atigdng, history, 10 months ago, In English
Code Clash 2026 Editorial We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated! [A &mdash; Love of Equal Arrays](https://codeforces.me/gym/663466/problem/A) Idea: [user:nimish.agarwal.2006,2026-01-11]<br> Implementation: [user:nimish.agarwal.2006,2026-01-11] <spoiler summary="Hint"> For any index $i$, it is always possible to make $a_i = b_i$ in at most $2$ moves. </spoiler> <spoiler summary="Tutorial"> Now there are four possible cases for a fixed index $i$. 1) If $a_i = b_i$, then no operation is required. 2) If $a_i \bmod b_i = 0$, then we can multiply $b_i$ by $\frac{a_i}{b_i}$, and make $a_i$ and $b_i$ equal using one operation. 3) If $b_i \bmod a_i = 0$, then we can multiply $a_i$ by $\frac{b_i}{a_i}$, and make $a_i$ and $b_i$ equal using one operation. 4) Otherwise, we can multiply $a_i$ by $b_i$ and $b_i$ by $a_i$, making them equal in two operations. The answer is obtained by summing the minimum number ...
walk inside it. Since the graph is a tree, the path

Full text and comments »

  • Vote: I like it
  • +23
  • Vote: I do not like it

170.
Codeforces Round #857 Editorial
By vaaven, 4 years ago, translation, In English
Codeforces Round #857 Editorial [problem:1802A] ------------------ Idea: [user:Aleks5d,2023-03-13], Preparation: [user:vaaven,2023-03-13] <spoiler summary="Solution"> Let's show a construction that maximizes the number of likes. We need to first leave all the likes that we can put, and only then delete them. To minimize the number of likes, we need to delete the like (if we can) immediately after we post it. The code below implements these constructs. </spoiler> <spoiler summary="Code"> ~~~~~ #include "bits/stdc++.h" using namespace std; void solve() { int n; cin >> n; int likes = 0, dislikes = 0; for (int i = 0; i < n; i++) { int x; cin >> x; if (x > 0) likes++; else dislikes++; } for (int i = 1; i <= n; ++i) { if (i <= likes) cout << i << ' '; else cout << likes * 2 - i << ' '; } cout << '\n'; for (int i = 1; i <= n; ++i) { if (i <= dislikes * 2) cout << i % 2 << ' '; el...
store an acceptable price range. The answer will be the product of the lengths of the ranges over all

Full text and comments »

  • Vote: I like it
  • +125
  • Vote: I do not like it

171.
2017 CMUT BeihangU Contest, Editorial
By skywalkert, history, 7 years ago, In English
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...
-01] As the graph is a cactus graph, it is no doubt that one edge

Full text and comments »

  • Vote: I like it
  • +49
  • Vote: I do not like it

172.
Codequest 2.0 — Editorial
By accord, history, 8 months ago, In English
Codequest 2.0 — Editorial ### [Problem A &mdash; A "tiny" love story](https://codeforces.me/gym/680185/problem/A) Problem Idea by: [user:notalone008,2026-03-25] <br> Problem Preparation by: [user:notalone008,2026-03-25] <br> <spoiler summary="Solution"> The clock only shows values from **0 to 59** and wraps around (modulo 60). The only thing to be checked here was if the call duration was a multiple of 60 seconds or not. - If s % 60 == 0 → print "NO" - Else → print "YES" </spoiler> <spoiler summary="Code"> ~~~~~ #include <bits/stdc++.h> using namespace std; //--------code begins here-------- void solve() { int s; cin >> s; if(s % 60) cout << "YES"; else cout << "NO"; } int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int T = 1; cin >> T; while (T--) { solve(); cout << endl; } return 0; } ~~~~~ </spoiler> ### [Problem B &mdash; God is 1 and his name is 1](https://codeforces.me/gym/680185/problem/B) Problem Ide...
; } ~~~~~ ### [Problem D — Product Pairs](https://codeforces.me/gym/680185/problem

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it

173.
Code League — National Competitive Programming Contest — Round 2 — Editorial
By eulmelk, 5 months ago, In English
Code League — National Competitive Programming Contest — Round 2 — Editorial Here is the link to the contest: [Link](https://codeforces.me/contestInvitation/f528fcc29732183e36f82a0adfdc6dbac0743f3f) ### [A. Free Coupon](https://codeforces.me/gym/690685/problem/A) <spoiler summary="Rate the Problem"> - **How good is this problem?** - Very Good - Good - Bad - Very Bad - **How hard is this problem?** - Very Easy - Easy - Hard - Very Hard </spoiler> <spoiler summary="Hint"> Which items should be taken using coupons? <spoiler summary="Answer"> Since a coupon can be used on any item regardless of its price, it is always best to use coupons on the most expensive items. This allows us to spend our coins only on cheaper items. </spoiler> </spoiler> <spoiler summary="Solution"> The problem asks us to find the maximum number of items Abenezer can obtain given $k$ coins, with the offer that every $b$ items bought with coins yiel...
> Can you model this as a graph problem?

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

174.
Infoleague Spring 2022 Round Editorial
By Gheal, 5 years ago, In English
Infoleague Spring 2022 Round Editorial <spoiler summary="Vote your favourite problem"> <spoiler summary="Div 2"> Div 2A &mdash; The Hatchet Div 2B &mdash; Floor Or Xor Div 2C &mdash; Yet Another Constructive Problem Didn't participate, idc </spoiler> <spoiler summary="Div 1"> Div 1A &mdash; Bamboo Coloring Div 1B &mdash; Xor Or Floor Div 1C &mdash; Jump Didn't participate, idc </spoiler> </spoiler> [103633A &mdash; The Hatchet](https://codeforces.me/gym/103633/problem/A) ------------------ Author: [user:tibinyte,2022-03-30] <spoiler summary="Rate Problem"> 1700 or less 1800 1900 2000 2100 or more Didn't solve it, idk </spoiler> <spoiler summary="Solution"> ### Subtask 1 : $N \le 10^2$ This subta...
in the product of all $a_i$, and exactly once in the product of all $b_j$. Therefore, we can

Full text and comments »

  • Vote: I like it
  • +30
  • Vote: I do not like it

175.
Codeforces Round 1065 (Div. 3) Editorial
By reirugan, 12 months ago, In English
Codeforces Round 1065 (Div. 3) Editorial I hope you all enjoyed the contest! Special thanks to - [user:djm03178,2025-11-18] for suggesting the inclusion of C1, and for helping with test writing on all problems, especially F - [user:satyam343,2025-11-18] for helping me solve H - [user:Dominater069,2025-11-18] for providing the idea for one of the solutions to E - [user:Intellegent,2025-11-18] for providing one of the proofs for the solution to D, and for providing the idea for one of the solutions to F <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> #### [...
{pre}_{i-1}$ to $\mathrm{suf}_i$ to $p_i$. Since the graph consisting of these paths is connected, it

Full text and comments »

  • Vote: I like it
  • +129
  • Vote: I do not like it

176.
TeamsCode Spring 2025 Contest Editorial
By HaccerKat, history, 19 months ago, In English
TeamsCode Spring 2025 Contest Editorial Sorry for the long wait. All problems were written, prepared, and editorialized by [user:Yam,2025-03-23], [user:hyforces,2025-04-14], [user:culver0412,2025-04-15], [user:HaccerKat,2025-03-23], [user:alexlikemath007,2025-03-23], [user:jay_jayjay,2025-03-23], [user:n685,2025-03-23], [user:Mustela_Erminea,2025-03-23], [user:Jasonwei08,2025-03-23], [user:eysbutno,2025-03-23], [user:training4usaco,2025-03-23], [user:Nyctivoe,2025-03-23], and [user:gggg0,2025-03-23]. The problems (with problem credits) can be found in the [Novice Gym](https://codeforces.me/gym/105819) and [Advanced Gym](https://codeforces.me/gym/105818). Also thanks to our testers for providing valuable feedback and to our logistics and web team for making TeamsCode possible! [Novice A/](https://codeforces.me/gym/105819/problem/A)[Advanced A: Lily Pads](https://codeforces.me/gym/105818/problem/A) ================================================================================================================= <spoi...
First Search, Breadth First Search, or Disjoint Set Union to find connected components in agraph, and

Full text and comments »

  • Vote: I like it
  • +30
  • Vote: I do not like it

177.
School Team Contest #1 (Winter Computer School 2010/11): Tutorial
By natalia, 16 years ago, translation, In English
School Team Contest #1 (Winter Computer School 2010/11): Tutorial <div><div><b>Problem A</b></div><div><br></div><div>To get the maximal possible result you have just to sort summands in non-decreasing order by coefficients (counting coefficients with preceeding signs + and -). You should not pay attention to 'a++' or '++a'! The question is: why is it true?&nbsp;</div><div><br></div><div>First, consider an expression with only 'a++'. Then our assertion is obvious: it is better to multiply 'a' by small coefficients when it has small value, and by large coefficients, when it becomes larger. The same also takes place in case of negative coefficients or a-value. Of course, it is not a rigorous proof. I hope you will think on it if you haven't get it yet.</div><div><br></div><div>Second, consider the expression $k*a+++k*++a$, where $k$ is some coefficient equal for both summands. Let initial value of 'a' equals to $a_0$. Calculating the value of the expression both ways, we obtain: $k * a_0 + k * (a_0 + 2) = k * (a_0 + 1) + k * (a_0 + 1)$. So in this case...
> Problem I Consider only the part of the graph reachable

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

178.
IICPC Quantfest 2025 Prelims Editorials
By _Aditya_Jain_, 15 months ago, In English
IICPC Quantfest 2025 Prelims Editorials ![Poster](/predownloaded/12/40/124090bc62a78fc532e0e95ea0d7d78a659b5a56.jpg) <br> We hope you enjoyed the problems in both part 1 and 2 of the contest! You can find the editorials for the problems below: <spoiler summary="Rate the contest!"> <spoiler summary="Quality"> Excellent contest <br> Good contest <br> Average contest <br> Bad contest </spoiler> <spoiler summary="Difficulty"> Trivial contest <br> Easy contest <br> Average contest <br> Hard contest </spoiler> </spoiler> [Paper 1, Problem B (Stat Expo)](https://codeforces.me/gym/631185/problem/B) <spoiler summary="Tutorial"> We need to count sequences of $n$ tens and $m$ thirties such that at every prefix, the number of tens is at least twice the number of thirties. Define $f(n,m)$ as the number of valid sequences with $n$ tens and $m$ thirties: $$ f(n,m...
/631185/problem/E) We want to represent the situation as a graph with $6

Full text and comments »

  • Vote: I like it
  • +69
  • Vote: I do not like it

179.
Round #14 tutorial
By AlexBelc, 15 years ago, In English
Round #14 tutorial [A. Letter](http://www.codeforces.com/contest/14/problem/A) ================== When searching for the result all we have to do is to save the minimum and the maximum value for line/column indexes where we find an '*' character. The result consists of a submatrix, from (lmin,cmin) to (lmax,cmax). The result is obtained in O(nxm). [B. Young Photographer](http://www.codeforces.com/contest/14/problem/B) ================== At the beginning determine the intersection of all the n segments (beware when a>b). If the intersection is void then the answer is -1, otherwise determine the distance from the photographer's location to that segment. This algorithm needs O(1) memory and O(n) operations. [C. Four Segments](http://www.codeforces.com/contest/14/problem/C) ================== It is useful to define some structures, such as POINT and SEGMENT and a function to verify if two POINTS are equal, and a criteria for ordering the POINTS. Create an array consisting of all distinct endpoints an...
product is saved. The number of operations depends on how the graph is represented. If we use

Full text and comments »

  • Vote: I like it
  • -12
  • Vote: I do not like it

180.
Editorial for BIT-O-MANIA
By aryan_lem, history, 2 years ago, In English
Editorial for BIT-O-MANIA [A. Nobita and Shizuka](https://codeforces.me/group/hUywLYmr80/contest/556798/problem/A) ================== Author: [user:aryan_lem,2024-10-10] <spoiler summary="Editorial"> To calculate the piece with maximum area, we need the maximum length and maximum breadth. The difference between two successive horizontal cuts gives us the the breadth of smaller rectangular pieces. Similarly, the difference between two successive vertical cuts gives us length of smaller rectangular pieces. Thus, the problem boils down to calculating maximum among all successive horizontal and vertical cuts. The final answer will be the product of these two values. The time complexity for each test case will be: _**O(n)**_. </spoiler> <spoiler summary="Code"> ~~~~~ #include<bits/stdc++.h> using namespace std; #define int long long int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m;cin>>n>>m; int x,y;cin>>x>>y; int m1=0,m2=0; int...
final answer will be the product of these two values. The time complexity for each test case

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

181.
Editorial for Insomnia'25
By shorya1835, 20 months ago, In English
Editorial for Insomnia'25 [A \- XO-OR](https://codeforces.me/gym/590997/problem/A) <spoiler summary="Solution"> To solve this problem optimally, we need to ensure that we maximize the size of the set $S$ while satisfying the given constraints on XOR and OR operations. A necessary condition for a valid set is that $ y $ must be a **subset** of $ v $. In terms of bits, this means every bit that is set in $ y $ must also be set in $ v $. If $ y > x $, then at least one bit in $ y $ is missing from $ x $, making it impossible to construct a valid set where the XOR of elements results in $ y $. Thus, in such cases, the answer is immediately $ -1 $. To understand how we construct valid sets, consider forming all possible subsets of the bits set in $ v $. The total number of such subsets is $ 2^{pc} $, where $ pc $ is the number of set bits in $ v $. Each individual bit contributes exactly $ 2^{(pc - 1)} $ times across all subsets, meaning the overall XOR of the entire set cancels out to $ 0 $ when $ pc \ge...
**bipartite matching** problem. Consider a graph with $n$ nodes where: 1. The odd numbers from $1$ to $n

Full text and comments »

Tutorial of Insomnia 2025
  • Vote: I like it
  • +73
  • Vote: I do not like it

182.
My first Div. 4 contest Editorial
By Mitpro, 10 months ago, In English
My first Div. 4 contest Editorial I am very sorry for problem F, and M, solution for them are wrong, F is fixed, but M is not I hope you enjoyed the contest! Thank you for participating! This is my first round on Codeforces, so there might be many mistakes, I would be happy to hear your feedback in the comments. ### [663295A &mdash; Jack and time](https://codeforces.me/contests/663295/problem/A) Approach: [user:Mitpro,2025-05-26] <spoiler summary="Hint"> <spoiler summary="Hint1"> What is the number seconds in $1$ hour and $1$ minute? </spoiler> <spoiler summary="Hint2"> Try using $\bmod$ operator and $\div$ operator </spoiler> </spoiler> <spoiler summary="Editorial"> ### [663295A &mdash; Jack and time](https://codeforces.me/contests/663295/problem/A) This problem is a straightforward one involving conversion of total seconds into hours, minutes, and seconds. We know: - 1 hour = 3600 seconds - 1 minute = 60 seconds So the conversion goes as: let $s$ be the seconds, $hours =...
values in b and check whether their product is divisible by $m$. Any number

Full text and comments »

  • Vote: I like it
  • +32
  • Vote: I do not like it

183.
A Community-Driven Problem Solving Guide For Codeforces
By omtheprogrammer1, history, 5 weeks ago, In English
A Community-Driven Problem Solving Guide For Codeforces # A Community-Driven Problem Solving Guide For Codeforces ## Contribute First. Read This After. This blog is **not** a finished tutorial. This blog is an **invitation**. If you have ever opened a Codeforces problem, stared at it for 20 minutes, and thought: > **"I know some algorithms... so why can I still not start?"** then this repository is for you. # **[GitHub Repository](https://github.com/OmReddyEnduri/A-Community-Driven-Problem-Solving-Guide-For-Codeforces-Problems/tree/main)** Inside that repository there is a **`.txt` invitation file**. **Please open the repository, read that file first, and then contribute.** That file explains: - why this guide exists - how we want to build it - how you can add your ideas - why even a small contribution is enough > **Do not wait until you feel "good enough" to help.** > > **If you have struggled with Codeforces problems, you already have something worth sharing.** --- # Why This Exists Codefo...
contributions are the product.** --- # Final Call I will say it one last time, because this is

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

184.
TeamsCode Summer 2024 Contest Editorial
By xug, 2 years ago, In English
TeamsCode Summer 2024 Contest Editorial The [TeamsCode Summer 2024 Virtual Programming Contest](https://codeforces.me/blog/entry/131526) was held on Sunday, July 28. The problems were written and prepared by [user:Yam,2024-07-14], [user:hyforces,2024-07-14], [user:oursaco,2024-01-20], [user:willy108,2024-07-14], [user:jay_jayjay,2024-07-14], [user:HaccerKat,2024-07-14], [user:xug,2024-07-14], [user:yash_9a3b,2024-07-14], [user:Red0,2024-07-16], and [user:superhelen,2024-07-16]. The problems (with problem credits) can be found in the [Novice Gym](https://codeforces.me/gym/105283) and [Advanced Gym](https://codeforces.me/gym/105284). [user:lunchbox,2024-08-02] solved all the problems during testing and provided valuable feedback. [Novice A /](https://codeforces.me/gym/105283/problem/A)[ Advanced A: P!=NP](https://codeforces.me/gym/105284/problem/A) === <spoiler summary = "Hint"> Try simplifying the equations by dividing by $p$, then think about which values of $p$ would produce a valid value of $n$. </spoiler> ...
simplicity, let's consider the input as a graph of $n$ nodes and $a_{ij}$ denotes the edge from

Full text and comments »

  • Vote: I like it
  • +24
  • Vote: I do not like it

185.
[GYM] 2017 Bangladesh National High School Programming Contest ( National Round, Senior Group ), NHSPC 2017 Tutorial
By prophet_ov_darkness, 10 years ago, In English
[GYM] 2017 Bangladesh National High School Programming Contest ( National Round, Senior Group ), NHSPC 2017 Tutorial Tutorials are written by corresponding problem authors. I'm just assembling all those tutorials in one place. ### [problem:101353A] Problem Author: [user:raida_ash,2017-04-20], Tester: [user:khairat,2017-04-20] It is a simple ad-hoc problem. We can solve it in $\mathcal{O}(n)$. Simply iterate over all the bottles and add the amount of liquid spilled to the answer. <spoiler summary="Problem Author's Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; main() { //freopen("in1.txt","r",stdin); //freopen("out1.txt","w",stdout); int n,m,c[100005],t; long long int ans; scanf("%d",&t); while(t--) { ans = 0; scanf("%d %d",&n,&m); for (int i=0; i<n; i++) { scanf("%d",&c[i]); ans += ceil((double)((c[i]*1.0)/m))*m - c[i]; } printf("%lld\n",ans); } return 0; } ~~~~~ </spoiler> ### [problem:101353B] Problem Author: [user:tanzon0xA5,201...
product. Actually, we are trying to divide every number with whatever common divisor it shares with

Full text and comments »

  • Vote: I like it
  • +39
  • Vote: I do not like it

186.
Editorial for CodeHurdle Athlos 01
By amartya110, 10 months ago, In English
Editorial for CodeHurdle Athlos 01 We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated! * Special thanks to the tester [user:Ajay_2705,2026-01-19] in the last moment, correcting Problem C. [Contest Link](https://codeforces.me/contestInvitation/701bbd9bb27890c9f44ff4ceb70e38f74e0844d6) [](https://codeforces.me/contestInvitation/701bbd9bb27890c9f44ff4ceb70e38f74e0844d6) ### A — The Dual-Core Conflict Writer: [user:amartya110,2026-01-19] <spoiler summary="Editorial"> In this game to win, Alice has to choose one 2 and all 3 in his first chances only otherwises he loses. So, if he have number 2 less than two then he lose otherwise win. </spoiler> <spoiler summary="Solution"> ```c++ #include <bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; vector <int> a(n); int x=0; for(int i=0;i<n;i++){ cin>>a[i]; if...
-free if its product contains no repeated prime factor. Key Observations 1. Each prime factor can

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

187.
Intra-Pilani Educational Contest : Editorial
By hzzt_2004, 2 weeks ago, In English
Intra-Pilani Educational Contest : Editorial Thanks for participating! This is the first iteration in a series of educational contests held in BITS Pilani, Pilani Campus. The editorial for all seven problems is below. Open the hints one at a time before reading the rest. Contest link -> https://codeforces.me/contestInvitation/3ad0b848ae9e772cb849a80f90943647a6ee9b6c The problems were authored by [me](https://codeforces.me/profile/hzzt_2004), and tested by [user:keeshu,2026-10-26] and [user:Ultimateyagyik22,2026-10-26] Congratulations to the top 3: [user:sidat,2026-10-26], [user:ameasa,2026-10-26], [user:jagannathpisharody,2026-10-26]! <hr/> <b>A. AAAAAAAAAAAAAA</b> <spoiler summary="Hint 1"> Write the first few screaming numbers in decimal and see how each one relates to the previous one. </spoiler> <spoiler summary="Hint 2"> Adding one more digit $A$ on the right changes the number in a simple way. Can you simulate that directly, keeping everything modulo $10^9+7$? </spoiler> <spoiler summary="Obser...
), then multiply by $10$ and by $15^{-1}$, reducing modulo $p$ after each product. Time: $O(\log n

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

188.
Editorial for CCxEnigma: Tesseract '26 (IIIT Vadodara)
By Mr.Quantum_1915, 9 months ago, In English
Editorial for CCxEnigma: Tesseract '26 (IIIT Vadodara) Tesseract '26 Editorial ================== Hello Everyone! Hope you enjoyed **[CCxEnigma: Tesseract '26](https://codeforces.me/blog/entry/150726)** conducted by [IIITV Coding Club](https://iiitvcc.vercel.app/home) and Mathematics Club at IIIT Vadodara. Thank you for participating in the contest. Hope you had fun solving the problems with the new Sandbox twist :) This was the first time a reverse coding event was hosted in this **style**! _Feel Free to give some feedback in comments whether you **liked** it, suggestions for **improvement**, or ideas for the **Next** Edition :)_ Here are the official tutorials for the problems. Access the Sandbox here &mdash; [_SANDBOX_](https://tesseract-2k26.vercel.app/sandbox) ### [Problem A: DDR4 Shortage](https://codeforces.me/gym/668703/problem/A) Author: [user:Mr.Quantum_1915,2026-02-01] <spoiler summary="Hint"> Try entering aa and aaa in the sandbox. aa (Length 2) $\to$ 2a (Length 2). No space is saved, so i...
before $U$. This suggests a directed graph where edges represent dependencies. Also, look out for

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

189.
ICPC de Tryst 2025 Editorial
By Proelectro444, 20 months ago, In English
ICPC de Tryst 2025 Editorial I hope you liked the contest. We apologize for the inconvenience caused due to the problem $I$. ### [problem:595453A] --- **Author:** [user:Proelectro444,2025-03-13] <spoiler summary="Solution"> #### Inspiration [https://codeforces.me/problemset/problem/1748/b](https://codeforces.me/problemset/problem/1748/b) **Why the Classic Two-Pointer Technique Fails:** The classic two-pointer technique relies on a monotonicity property; that is, if an array is diverse then every subarray of it should also be diverse, or if an array is not diverse then none of its subarrays are diverse. However, the diverse property does not behave monotonically, so a straightforward application of the two-pointer method does not work. Instead, we modify the approach and compute the count in $\max(a)$ steps. In the $m^\text{th}$ iteration, we compute the number of diverse subarrays that have exactly $m$ distinct elements. Notice that if a subarray has exactly $m$ distinct elements, then ...
weight of any edge in the complete graph, that is the range of the function $d$, is $\{0,1,2,3

Full text and comments »

  • Vote: I like it
  • +65
  • Vote: I do not like it

190.
A problem collection of ODE and differential technique
By Moody_Nabil, history, 5 years ago, In English
A problem collection of ODE and differential technique A problem collection of ODE and differential technique ====================================================== This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them. For those who are interested in well-known problems in China. Thank [user:Elegia,2021-10-21] and [uset:djq_cpp] for developing this technique. Thank [user:Miracle03,2021-10-21] for reviewing this article. [Chain Reaction](https://uoj.ac/problem/50) in UOJ Round 3 By [user:vfleaking,2021-10-21] **Statement** ​ You are given a set A, you need to compute gi=12∑j,k(i−1j)(i−1−jk)gjgk where i−1−j−k∈A. **Solution** ​ Let the EGF of g be x(t) and EGF of A be a(t). Thus x′(t)=12a(t)x2(t)+1. We can solve this equation by D&C and FFT in O(nlog2n). But there is a slower solution in O(nlogn). ​ For a polynomial equation f(x(t))=0, we can use the Newton's method to solve it. If we find a polynomial xn that x≡xn(modtn). We can derive the ...
, dimVw≤dimVudimVv, u∗v is the Hadamard product here. If u∈D, v is algebraic and v(0)=0, then w=u

Full text and comments »

  • Vote: I like it
  • -95
  • Vote: I do not like it

191.
Code Release for TheForce Round #42 Top 10
By wuhudsm, history, 19 months ago, In English
Code Release for TheForce Round #42 Top 10 Hello, Codeforces. Today, as the main manager of a contest, I have decided to release the code for [TheForce Round # 42](https://codeforces.me/gym/105846) Top 10. The reason for this decision is that during the middle of the contest, we noticed unusual standings: ![ 2025-04-18 000415.png](https://s2.loli.net/2025/04/18/inqucELoWUXfOra.png) As a convention of codeforces, the code of all participants after the contest will be made public. I have decided to do the same thing here, and I believe that if you are a normal and honest participant, it will not infringe upon any of your rights. Also, we are checking the code of the participants and making cautious judgments. The allocation of prizes and the calculation of TheForce Rating will be delayed. Sorry for any inconvenience caused. We sincerely hope to maintain a fair and honest competitive environment for all participants. Integrity is the cornerstone of programming contests, and we believe that upholding these values...
{ // Reference: // R. Tarjan, // Depth-First Search and Linear Graph Algorithms struct scc_graph { public

Full text and comments »

  • Vote: I like it
  • +20
  • Vote: I do not like it