I compiled a list of almost all useful blogs ever published on Codeforces [update: till 09.06.2021] <h3 style="color:red">If there are any blogs that I have missed, please tell in the comment section. Thank you.</h3> # Mathematics Stuff - [Number Theory in Competitive Programming [Tutorial]](https://codeforces.me/blog/entry/46620) - [Number of points on Convex hull with lattice points](https://codeforces.me/blog/entry/62183) - [FFT, big modulos, precision errors.](https://codeforces.me/blog/entry/48465) - [Number of ways between two vertices](https://codeforces.me/blog/entry/19078) - [Mathematics For Competitive Programming](https://codeforces.me/blog/entry/76938) - [FFT and NTT](https://codeforces.me/blog/entry/19862) - [Burnside Lemma](https://codeforces.me/blog/entry/51272) - [Number of positive integral solutions of equation 1/x+1/y=1/n!](https://codeforces.me/blog/entry/76836) - [On burnside (again)](https://codeforces.me/blog/entry/64860) - [Simple but often unknown theorems/lemmas/formula? Do you know?](https://codeforces.me/blog/entry/55912) - [Probabili...

Full text and comments »

System marks KACTL LCA code as cheating for many participants After competing today in [contest:1304], I received the following message from [user:System,2020-02-15]: _Attention!_ _Your solution [submission:71152328] for the problem 1304E significantly coincides with solutions [user:ksun48,2020-02-15]/[submission:71134293], [user:hoke_t,2020-02-15]/[submission:71152328], [user:Venia,2020-02-15]/[submission:71156816], [user:hanga97,2020-02-15]/[submission:71159069]. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your ...

Full text and comments »

Online LCA и подвешивание деревьев друг за друга. O(log n) Наименьший общий предок и подвешивание деревьев друг за друга (Online) && (O(log n)). ================== ### Постановка задачи: **Дается изначально лес подвешенных деревьев. Дальше следуют запросы двух видов:** - Найти наименьшего общего предка двух вершин a и b, или вывести то, что они в разных деревьях. - Провести ребро между вершиной u и вершиной v. Гарантируется, что вершины u и v в разных деревьях, а также что, вершина u это корень дерева. (Получается после проведения ребра между вершиной u и v, они сольются в одно дерево, корнем которого будет корень дерева, в котором была вершина v)  _*Пример соединения двух деревьев, путем проведения ребра между двумя вершинами, выделенными красным*_ Решение: ------------------ Напомню, что задачу о нахождении **LCA** ( _Lowest Common Ancestor_ ) сводится к задаче **RMQ** ( _Range minimum query_ ), или по-русски, минимум на отрезке. Более подробно про эт...

Full text and comments »

ICPC Indonesia COMPFEST 12 Multi-Provincial Contest Online Mirror Editorial Hi everyone, sorry for the considerable delay. It turns out, we were exhausted yesterday from supervising two contests back-to-back. We are surprised by the number of participants in the online mirror. And I hope you enjoy the problems :) Our big surprise was problem B. We were setting it to be a medium problem. Turns out, maybe the observation is not that obvious. **fun fact:** Initially, we don't plan to have any particular naming theme other than the obligatory first letter matches the problem order. However, when naming 6 out of 9 problems, one of my committee member noticed that **5 problems** have A of B theme. So, we decided to continue using this theme. Here are the authors and first solvers for all problems: **A &mdash; Arena of Greed** Author: [user:julianfernando,2020-09-28] Expected difficulty: Medium Tag: greedy First solver: [user:kotamanegi,2020-09-28] **B &mdash; Blue and Red of Our Faculty!** Author: [user:dewa251202,2020-09-28], [user:...

Full text and comments »

Finding Biconnected Components Today’s contest Div1 C—I didn’t know there was something called “biconnected components,” or that they could be found easily using bridges in O(n + m) (I should have studied that :( ). But I wrote this during the contest: ~~~~~ int n; //LCA,DSU Templates void solve() { int m; cin >> n >> m; DSU dsu(n + 1); // DSU to merge nodes connected through cycles DSU dsu1(n + 1); // DSU to build initial spanning tree vector<pair<int, int>> edges, nonTreeEdges; vector<int> dp(n + 1, 0); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; edges.push_back({a, b}); } // Build initial spanning tree and separate back edges for (auto [u, v] : edges) { // dsu1.join returns true if u and v are in different components if (dsu1.join(u, v)) { adj[u].push_back(v); adj[v].push_back(u); } else { // back edges nonTreeEdges.push_back({u, v});...

Full text and comments »

[Tutorial] Path sum queries on a tree using a Fenwick tree ## Introduction I've come across several problems that require you to be able to efficiently find the sum of some values on a path from $A$ to $B$ in a tree. One can solve these problems using tree decomposition techniques like heavy-light decomposition or centroid decomposition, but that's a bit of an overkill and not very elegant in my opinion. In this blog post, I will describe a way to solve these types of problems using just a DFS, a Fenwick tree, and LCA (as well as a way to solve JOIOC 2013 Synchronization this way). **Note: Whenever I talk about edge $(u, v)$ in this post, I assume that $u$ is the parent of $v$.** ## Prerequisites - DFS - Preorder traversal (DFS order) - Fenwick tree - Binary lifting and LCA ## The idea Say you have the following problem: > Given a tree with $N$ nodes, each node $i$ has a value $a_i$ that is initially 0. Support the following 2 types of operations in $O(\log N)$ time: > > 1. Increase the value of $a_i$ by $X$ > 2....

Full text and comments »

Online Assessment Question of ZEPTO SDE Here are the three problem that came in ZEPTO SDE, all of them based on someway or the other standard tree/graph ideas. Some of them are recurring hacker-earth problems that pop up here and there in some random OAs. I feel like this can be a good exercise on trees. **Problem 1: Maximum candies** Given a tree of N nodes and N-1 edges rooted at node 1, with exactly one candy placed at each node. Let's say the cost of the candy placed on ith node is ai, You have K amount of money. Now, you will choose exactly one node (say, u) and will start buying the candies placed on the path from node u to the root until you run out of money, that is, first, you will buy the candy placed at node u, then the candy placed at the ancestor of u, then its ancestor and so on until you run out of money or you reach root node. Also, you cannot skip over a node without buying the candy placed at that node. Calculate the maximum number of candies in a given amount of money you can buy by choosing exact...

Full text and comments »

An O(q log n) online solution of CSES Increasing Array Queries problem [This problem](https://cses.fi/problemset/task/2416/) can be solved in many ways. But I found no online technique editorial which I followed to solve (using binary lifting) this problem. That's why I decided to write this solution blog where I'll discuss the solution from scratch, so that anyone who didn't solve the problem yet, can take help from this blog. Let's dive into the solution. **Update:** [Here](https://codeforces.me/blog/entry/132375) is the solution involving no data structures and just using only suffix sums and binary search. **Pre-requisites:** Binary lifting, finding the index of next greater element for all indices using monotonic stack. ## How to approach the solution Let's first think about the naive $O(nq)$ solution. For each query of range $[l,r]$, the answer is $\sum_{i=l}^r \textrm{max}_{j=l}^i(a_j) - a_i$. We can calculate it using a loop within a query easily. By keeping track of the prefix maximum of range $[l, i]$, we can find out the $\...

Full text and comments »

Hybrid Tutorial #-2: Centroid Decomposition **See the [original post](https://codeforces.me/blog/entry/81317) on Codeforces for a playlist of all similar tutorials and also more information about what this is.** # "Intro" *Timestamp: [00:00](https://youtu.be/-DmMLQCmz94)* This is a "hybrid tutorial" &mdash; it has both a blog and a video component. See my original post for more explanation of what this is and also a playlist of all past tutorials. You can view the full video [here](https://youtu.be/-DmMLQCmz94). This tutorial is on centroid decomposition, a cool concept that has many uses in different problems. It's also another "decomposition" technique, one of many. I feel like this subject in particular doesn't have many great tutorials online that really capture the essence of what we do with the technique, so hopefully, I can improve that with this one. # Notation We'll use $0$-indexing for the whole tutorial, and the example problem will also be $0$-indexed. In addition, "vertex" and "node" mean the same...

Full text and comments »

Maintaining mst with online edge insertions — no LCT needed This blog is about maintaining mst with online edge insertions (or msf &mdash; minimum spanning forest to be exact) by using a data structure I came up with in $O(\log n)$ for edge insertion. although this problem can solved quite easily for anyone who knows LCT (link-cut tree), coding LCT is not really practical and has really bad constants. The data structure I present has very good constants because as you'll see all it does is manipulation on arrays. For obvious reasons that will be shown later I have called this data structure "weighted DSU". **Warmup problem** ================== The problem is stated as follows: you are given an undirected graph where each edge has a time $t_i$. you are asked to answer queries of the form "what is the smallest time t such that you can get between u and v with all edges in time $<= t$". This problem is analogous to calculating the msf of the graph where the weights are the times and being able to answer what is the maximum on the simple path ...

Full text and comments »

[Tutorial] Reachability Tree / DSU-tree This is not to be confused with [DSU on Tree (Sack)](https://codeforces.me/blog/entry/44351). ### What can a Reachability Tree do? Suppose you are given a weighted (connected) undirected graph of $N$ vertices and $M$ edges. Let's define an ordering of the edges, for example, the edges are ordered in the ascending/descending order of their weights. The reachability tree can help you with: - Find the minimal/maximal weight of the edges when traversing from vertex $u$ to vertex $v$. - Find the set of vertices that are reachable from a given vertex using the first $x$ edges, for some arbitrary $x$. You can store some information in this set of reachable vertices, such as the maximum value or the sum of values of all the reachable vertices. ### Constructing a Reachability Tree The reachability tree is a rooted tree that consists of $N + M$ nodes. The tree will have $N$ leaves which represent the original vertices of the graph, and the rest of $M$ internal nodes represent th...

Full text and comments »

Some Persian videos to learning algorithms Hi! I was teacher of some online courses for students preparing themselves for IOI. I recorded my course sessions in some video files and they can be useful for Iranian (or who knows Persian) high school and also university students. If anybody wants the videos contact me here or my Gmail with address [email protected] or telegram id @kerpoo . The first course was about **introduction to programming with C++** and the content of the course was: 1. Introduction to the general programming tools with c++ syntax (Variables, Arrays, Conditions, Loops, Functions & ...) 2. Recursive functions 3. Time and memory complexity 4. Sort algorithms and implementation of Merge-sort 5. Algorithms about Prime numbers and Eratosthenes sieve 6. Introduction to big numbers and their algorithms 7. Introduction to binary search trees (BST) 8. Working with files by fstream library 9. Introduction to important libraries and structures for competitive programming (Pair, V...

Full text and comments »

K-th smallest edge on a tree's path, a tutorial about its approaches In this blog I will be talking about a problem that I consider instructive and interesting, because it has several solutions from which some tricks can be learned. ### Prerrequisites: * Tree basic theory * Binary Search * Euler Tour * Lowest common ancestor * Persistent Segment Tree. Note that you don't need all of them for each approach. ### Tricks or techniques that you can learn with the discussion of this problem: * Some square root application in descomposition of search space of queries * How to know in $O(1)$ if a node is an ancestor of some other node in a tree * Parallel Binary Search * The persistent segment tree can be builded over a tree ### Story: I created a version of this problem a while ago (which will be left as bonus challenge at the end of this blog), and I thought to put it in a contest that I am planning (Maybe not in the near future). But then ~dmga44,2021-04-11 (thanks to him for discussing this problem with me, and provide feed...

Full text and comments »

Good Bye 2014 Editorial First of all, sorry for the late editorial. I was too exhausted and immediately went to bed after the round finished, and didn't write the editorial. There are many pictures in this editorial, to cover up my poor English skills! If you have detected any errors or have questions, feel free to ask questions by comments. Unfortunately, the authors only know English, so we can't answer you if you write comments in Russian. ## [problem:500A] Let's assume that I am in the cell $i$ ($1 \le i \le n$). If $i \le n-1$, I have two choices: to stay at cell $i$, or to go to cell $(i + a_{i})$. If $i = t$, we are at the target cell, so I should print "YES" and terminate. If $i > t$, I cannot go to cell $t$ because I can't use the portal backwards, so one should print "NO" and terminate. Otherwise, I must go to cell $(i + a_{i})$. Using this method, I visit each cell at most once, and there are $n$ cells, so the problem can be solved in linear time. #### What is test 13? There are 9...

Full text and comments »

Algorithm Gym :: Data structures Today I want to introduce you some very very useful data structures. In this lecture, we are trying to improve your data structures skills, stay with us and click on **read more**. [cut] Important data structures : Trees ----- Trees are one of the most useful data structures.A tree is a connected-acyclic graph.There are too many types of trees, like : rooted trees, weighted trees, directed trees, tries, etc. Partial sum ----------- There are two types of problems solvable by partial sum. 1.Problems which you are asked to answer some queries about the sum of a part of elements (without modify queries). Solution of all of this problems are the same. You just need to know how to solve one of them. Example : You are asked some queries on an array $a_1,a_2,...a,_n$. Each query give you numbers $l$ and $r$ and you should print $a_l + a_{l+1} + ... + a_r$ . Solution : You need to build another array $s_1, s_2, ..., s_n$ which $s_i = a_1 + a_2 + ... + a_i$ ...

Full text and comments »

Codeforces Round #299 Editorial ### [problem:535A] First of all check if $n$ is one of the values $0, 10, 11, …, 19$. Then, let’s have array $x[]$ = {"", "", "twenty", "thirty", …, "ninety"} and $y[]$ = {"", "one", …, "nine"}.  Let $a = \frac{n}{10}$ and $b = n\ modulo\ 10$. If $n$ is not one of the values above, then if $a=0$, print $y[b]$, else if $b=0$ print $x[a]$ otherwise print $x[a]$-$y[b]$. Time complexity: $O(1)$ [Code](http://ideone.com/mytb2L) by [user:SoroushE,2015-04-02] [Another Code](http://ideone.com/CqgNe5) by [user:PrinceOfPersia,2015-04-05] [Another Code](http://ideone.com/dqiMNL) by [user:Haghani,2015-04-08] [Python Code](http://ideone.com/6tZmNF) by [user:Zlobober,2015-04-04] ### [problem:535B] Sol1: Consider $n$ has $x$ digits, $f(i) = $ decimal representation of binary string $i$, $m$ is a binary string of size $x$ and its $i-th$ digit is 0 if and only if the $i-th$ digit of $...

Full text and comments »

I made a free browser-based CP Tool for graph visualization, calculators, grids, and resources Hello Codeforces! I wanted to share a tool I’ve been building for competitive programming: [https://cptoolapp.web.app/](https://cptoolapp.web.app/) CP Tool is a free web app that runs directly in the browser. There is no login, no setup, and no backend server needed for the actual tools. Just open the site and use it. What it currently includes: - Interactive graph editor - Graph parsing from common input formats - Algorithm visualization/playback for things like BFS, Dijkstra, MST, SCC, topological sort, bridges/articulation points, tree diameter, LCA, subtree size, etc. - CP calculators for number theory, combinatorics, bit operations, matrices, and strings String algorithm helpers like KMP, Z-function, rolling hash, Manacher, trie, Aho-Corasick, suffix array, and suffix automaton - Grid/coordinate helper for geometry-style and compressed-grid problems - Curated CP resources: platforms, practice ladders, references, tools, and communities - Documentation inside ...

Full text and comments »

A general approach to solve subree distinct values queries! Hello Codeforces ,today I want to introduce a technique that can solve some problems related to distinct values queries on a subtree .The only way I know to solve array distinct values queries with updates is using MO's algorithm .The approach I will introduce can solve the subtree version of this problem online with updates in $O((N+Q)log^2(N))$.So let's get started. **Prerequisites:** 1.Heavy light decomposition (it's enough to know how it works and how to implement it). 2.Lowest common ancestor. 3.Euler tours (not necessary for this specific problem but I will use it to prove some fact). **Problem Statement:** You are given a tree rooted at vertex 1. You have to perform two types of queries: 1 $i$ $val$ : update the value of node $i$ to $val$. 2 $u$ : output the sum of distinct values in the subtree of node $u$. **Solution:** Whenever you encounter such a strange problem try to make a shift in perspective .What is the first thing you thought when you ha...

Full text and comments »

Отбор в кружок олимпиадного программирования «Тинькофф» 2021-2022 Всем привет! Начинается новый учебный год, вместе с ним стартует и сезон олимпиад. Этот пост будет полезен школьникам, которые хотят заниматься олимпиадным программированием, но не знают где. Сейчас открыт отбор в кружок по олимпиадному программированию «Тинькофф Поколение». Один из классных плюсов кружка — он абсолютно бесплатный, но нужно написать вступительный контест, который открыт **до 12 сентября включительно**. Зарегистрироваться и начать решать можно здесь: [algocode.ru](https://algocode.ru). Ниже мы постараемся подробнее описать как все устроено в кружке. Если у вас останутся вопросы, задать их можно в комментариях к посту или в telegram (внизу есть наши контакты). Каждый год мы стараемся быть лучше и действительно полезными, так что в этом году кружок будет еще интереснее. ## Про формат занятий По результатам отборочного контеста мы разделим участников на учебные параллели. У каждой параллели есть своя группа преподавателей, которые будут читать лекции, п...

Full text and comments »

Codeforces Round 1000 (Div. 2) — Editorial <spoiler summary="Rating Predictions"> | Handles | A | B | C | D | E | F1 | F2 | | ---------------- | --- | ---- | ----------- | ----------- | ----------- | ---- | ----------- | | ~Proof_by_QED,2025-01-20 | 800 | 1000 | 1500 | 2200 | 2400 | 1800 | 2600 | | ~chromate00,2025-01-20 | 800 | 1100 | 1500 | 2100 | 2300 | 1800 | 2700 | | ~redpanda,2025-01-20 | 800 | 900 | 1400 | 2000 | 2400 | | | | ~larush,2025-01-20 | 800 | 1100 | 1600 | 2100 | | | | | ~FairyWinx,2025-01-20 | 800 | 900 | 1500 | 2000 | 2400 | 1800 | 2500 | | [user:priyanshu.p,2025-01-20] | 800 | 1200 | 1500 | 2000 | 2500 | 2000 | | | ~Intellegent,2025-01-20 | 800 | 1000 | 1400 | 2000 | 2200 | 2000 | 260...

Full text and comments »

Palindromic tree: behind the scenes Hi everyone! As some of you may know, on this summer camp in Petrozavodsk [user:MikhailRubinchik,2014-09-25] presented a new data structure, palindromic tree. I had the honor to participate in the study of the structure for the six months before that, and I want to tell about it now :) [cut]<br> But firstly a brief explanation. If you alredy know basic ideas of the structure, you may go to the <a href="#inter">interest part</a>. Let's to each palindrome assign corresponding string equal to its right half, i.e., its radius and the boolean variable indicating its parity. Now let's merge all our radii of subpalindromes of string $S$ in two prefix trees for even and odd lengths separately. Claim: such trie will be $\mathit O(n)$ in memory. Indeed, there can be no more than $n$ distinct subpalindromes in the string, and each node in trie corresponds with only one unique palindrome. Therefore, we have no more than $n + 2$ nodes. Let's show that such structure can be constructed ...

Full text and comments »

Fenwick Tree generalization using Centroids Hello, Codeforces community! (Again) After asking many times, I realized that the central idea of this blog was not being understood, and I’ve finally decided to rewrite it. This time I want to be clearer and provide more details. This is not about the classic centroid decomposition, but I’ll try to keep it self-contained so the concept is understandable within this blog. --- ## What is a Centroid? In a tree, a centroid is a node that, when removed along with its incident edges, minimizes the size of the largest remaining connected component, see figure 1. <center> <img src="/predownloaded/03/3f/033f954d1d44920150b706caa12c0045f41bced4.png" alt="centroid of a tree and remaining components"> <br> <I>figure 1. Centroid of a tree and remaining components</i> </center> **Claim**: Let $W(v)$ be the size of the largest component after removing node $v$, and $n$ be the total number of nodes. If $v$ is a centroid, then: $$W(v) \le \frac{n}{2}$$ **Proof**: Supp...

Full text and comments »

[Tutorial] Square root decomposition and applications A brief introduction into the applications of square root decomposition ================== Square root decomposition is the process of separating a structure of size $O(N)$ into $O(\sqrt{N})$ "blocks" of size $O(\sqrt{N})$ each, in a way that aids manipulation of the entire structure. Square root decomposition is extremely versatile. Some of its most well-known use cases are: - answering queries on a static array, with methods such as Mo's algorithm or block precomputation - "lazy" brute force modifications, where it is easy to query an entire block, but tag pushing isn't obvious - separating objects based on a threshold, when there exists both an $O(x)$ algorithm and an $O(n/x)$ algorithm In this tutorial we will walk through multiple types of square root decomposition. Answering queries on a static array, offline (Mo's algorithm) --- Consider a problem where we are asked to find the answer for certain intervals $[l,r]$. We can't quickly compute the answer for an ar...

Full text and comments »

MST for Vertices ! ## Motivation MST, or Minimum Spanning Tree, is an acyclic subgraph of a graph, where the total weight of its edges is minimal. Their properties are often used in problems with edge-weighted graphs. But what about node-weighted graphs? A problem structured on edges can often be modified to one based on nodes. In such situations, data structures and algorithms analogous to those used for edges can be applied. Let's look at one such problem! ### The Minimax problem The minimax path problem involves finding the minimum of the maximum edge weights among all possible paths between two vertices, $i$ and $j$. And it turns out that, the minimax path always is a part of the MST! <spoiler summary="Why?"> A good way to get the intuition is by thinking what if no minimax path lie on the MST? It comes back to the edges we choose in a cycle. We cut the edge with the highest weight to make the MST so among all paths that were accessible in the original graph, only the ones with the heaviest ...

Full text and comments »

Help to improve my way of practice I am doing CF for about one year. But still , I am newbie here. It is not like that A,B seem so hard.I become so nervous during cf round . During contest suddenly my head becomes blank and I feel like I am caged and so I cannot think further . As a result , I cannot come to solution for any problem further . It is destroying my confidence level day by day. And during practice , I do not follow any particular strategy . Because I get confused what to do! Sometimes I solve from cf according to junior practise sheet(provided by an arabian coach may be, found online), sometimes I solve from light oj/uva and sometimes I learn Algorithms . Algorithms I know - Bfs,dfs,mst,dijkstra,nim,trie,kmp,binary search,matrix exponentiation, dp(coin change,knapsack,LCS,LIS,edit distance) I have solved average 9 to 10 problems on these topics. I know more algorithms like segment tree,LCA etc on which I have just solved 2 to 3 problems. I will be grateful if anyone will share...

Full text and comments »

Queries on tree — Codechef Hello . I tried to solve [this problem](https://www.codechef.com/problems/TAQTREE) but [my submission](http://ideone.com/ltyDQ7) got [SIGSEGV](https://www.codechef.com/viewsolution/8539192) for one of tests and I can't find reason! I used huge random and clever inputs many times for my solution and test them with online judge compile options but it pass all of them without problem. Can someone help me ? Little Details : I wrote comment for codes and I used ... for solving problem >> Dfs Order + Segment Tree , actually I found path from root to all nodes and updated them with help of segment tree on range that are under related node in dfs order. So Answer is : ans(u) + ans(v) &mdash; 2*ans( lca(u,v) ); for finding LCA >> EulerTour + SparseTable

Full text and comments »

Editorial - Insomnia 2026 [A. The Oracle's Curse](https://codeforces.me/gym/682678/problem/A) ================== Author: [user:aditya1977,2026-04-27] <spoiler summary="Explanation"> <h3>Observation</h3> An alarm rings when a stock with a low starting price passes a stock with a high starting price. Since all stocks go up by exactly $1$ every day, a lower stock can only pass a higher stock if the higher one hits its maximum limit and stops growing. Once it passes, it stays ahead forever. Because the total number of alarms only goes up over time (it never goes back down), we can easily use <b>Binary Search</b>. In coding terms, when a smaller starting value overtakes a larger one, we call this an <b>inversion</b>. <hr> <h3>Definition</h3> Let $N$ be the number of stocks and $g$ be the target alarms. First, we sort all stocks by their starting prices $s_i$. Each stock is stored as a pair: $$ E_i = (s_i, u_i) $$ For any guessed day $D$, the new projected price $P_i$ of the $i$-th stock...

Full text and comments »

question about tree [solved] classical problem: add delta to all nodes on the path to u->v, it is basically adding delta to u and v, then val[lca(u,v)]-=delta, then just use dfs to find answer. My question is to ask: is there a way to answer online? Like let us say we have q<=1e5 queries and n<=1e5: is there a way to find value of a node during queries? (just curious)

Full text and comments »

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

Full text and comments »

Editorial: XIII UnB Contest Mirror We hope everyone enjoyed the problems of [contest:106159]! This editorial contains the description of the solutions and their implementation. Feel free to discuss them in the comments! #### Problem A - Author: [user:PedroPacoca,2025-11-05] - Coauthor: [user:duduFreire,2025-11-05] <spoiler summary="Solution"> In this problem, we want to count the number of strings of length $n$ that have at least one occurrence of the given substring. To do this, we will use the Knuth-Morris-Pratt (KMP) algorithm and the automaton constructed from it, with a complexity of $O(m)$. If $n$ were small, we could solve this problem using dynamic programming, calculating, for each $1 \leq i \leq n$, how many ways we can reach state $0 \leq j \leq m$ of the automaton (representing a string with the last $j$ characters equal to the first $j$ of $s$). This solution has $n \cdot m$ states with transitions of the size of the alphabet, resulting in a time complexity of $O(26 \cdot n \cdot m)$, which is...

Full text and comments »

Editorial: OPC Good Bye Thank you for taking part in $\textbf{OPC Goodbye 2025}$. This editorial walks through the core ideas and solution strategies behind each problem. We hope it helps you learn something new and refine your approach to competitive programming. If you have any reviews please put them in this [Google Form](https://docs.google.com/forms/d/e/1FAIpQLSeguT9leXrI3tyrmjwhXSfqj4LVF16zE5AIzKx-bcLHJclDRQ/viewform?usp=sharing&ouid=115085258461331858898). Contest Link: [Link](https://codeforces.me/group/hUywLYmr80/contest/660904) ### [A. Make It Organised](https://codeforces.me/group/hUywLYmr80/contest/660904/problem/A) <spoiler summary="Hint 1"> For each position, think: *how many times do I divide this number by 2 until it becomes the parity I need (even/odd)?* If it never reaches that parity, this pattern is impossible. </spoiler> <spoiler summary="Solution"> We observe that there are only two possible valid arrangements of parities in the final array: even, odd, ev...

Full text and comments »

International Odoo Programming Contest 2024 Editorial This is the editorial for the first edition of the [International Odoo Programming Contest](https://codeforces.me/gym/105056) Author: [user:pauloamed,2024-03-27] [problem:105056A] <spoiler summary="Editorial"> Implement exactly what is being asked. That is, check if the input is a string of the format [email protected]: - has @odoo.com as a suffix - $S$ is size $2$, $3$ or $4$ - $S$ is composed only of lowercase letters </spoiler> <spoiler summary="Solution C++"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main() { const string suffix = "@odoo.com"; string s; cin >> s; int last_pos_at = s.find_last_of('@'); if(last_pos_at == string::npos || s.substr(last_pos_at) != suffix) {cout << "no\n"; return 0;} if(last_pos_at < 2 || last_pos_at > 4) {cout << "no\n"; return 0;} for(int i = 0; i < last_pos_at; i++) { if(s[i] < 'a' || s[i] > 'z') {cout << "no\n"; return 0; } } cout << "yes\n"; } ~~~~...

Full text and comments »