A problem collection of ODE and differential technique, This is a simplified version of this problem: We define the weight of a
sequence $a_1, a_2, \dots, You can submit this problem here [Little Q's sequence](https://loj.ac/problem
/6703). However, you
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | maspy | 150 |
| 3 | Um_nik | 146 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | DNR | 133 |
| 8 | nik_exists | 131 |
| 8 | Dominater069 | 131 |
| 10 | Proof_by_QED | 130 |
→ Find user
→ Recent actions
You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:
305— search for 305, most probably it will find blogs about the Round 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
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 ...
2.
Editorial for Hello 2024 ### [problem:1919a]
Author: [user:maomao90,2024-01-02]
<spoiler summary="Hint 1">
When does the game end?
</spoiler>
<spoiler summary="Solution">
Depending on whether the player chooses to exchange wallets with their opponent on step $1$, $1$ coins will be removed from either the opponent's wallet or the player's wallet. This means that if either of the players still has remaining coins, the game will not end as at least one of the choices will still be valid.
The only way that the game ends is when both players have $0$ coins. Since each operation decreases the total amount of coins by exactly $1$, the only way for Alice to win the game is if $a + b$ is odd.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int a, b; cin >> a >> b;
if ((a + b) % 2 == 0) {
cout << "Bob\n";
} else {
cout << "Alice\n";
}
}
...
Solve the problem if you have to split the array into $k$ subsequences, ### [problem:1919a] Author: [user:maomao90,2024-01-02] When does
Tutorial of Hello 2024
3.
Tutorial on Permutation Tree (析合树） So my O level Chinese exam is in 2 days so I decided to learn a data structure that I can only find [resources](https://oi-wiki.org/ds/divide-combine/) for in Chinese. I thought I might as well write a tutorial in English.
This data structure is called 析合树, directly translated is cut join tree, but I think permutation tree is a better name. Honestly, after learning about it, it seems like a very niche data structure with very limited uses, but anyways here is the tutorial on it.
Thanks to [user:dantoh,2020-06-16] and [user:oolimry,2020-06-16] for helping me proofread.
### Motivation
Consider this [problem](https://codeforces.me/contest/526/problem/F). We are given a permutation,$P$ of length $n$. A good range is a contiguous subsequence such that $\max\limits_{l \leq i \leq r} P_i - \min\limits_{l \leq i \leq r} P_i = r-l$. This can be thought of the number of contiguous subsequence such that when we sort the numbers in this subsequence, we get contiguous values. Count the...
Consider this [problem](https://codeforces.me/contest/526/problem/F). We are
given a permutation
4.
[Tutorial] Simulated Annealing in Competitive Programming Hi Codeforces!
I've recently noticed a lack of simulated annealing tutorials, so I decided to make one. It all started when I was trying to "cheese" [problem:1556H] after the contest. In general, simulated annealing is a pretty niche topic, but it can sometimes lend you unintended solutions for very hard problems. It's also very useful in contests like Google Hashcode, where you can add simulated annealing to an already good solution to make it a lot better. Simulated annealing's name and terms are derived from physical annealing, the process of letting metals or glass cool down and harden while removing internal stresses.
An Overview
------------------
Simulated Annealing is an approximation algorithm. It's generally useful in problems with low constraints (i.e. $n \leq 50$ or $n \leq 100$) where you need to find the minimum/maximum of something over all possible states (and there are usually way too many of them to check). In general, it's good at finding the global maximum...
make one. It all started when I was trying to "cheese" [problem:1556H] after
the contest. In general, Example Problems ------------------ - Try implementing TSP - [USACO subsequence
reverse](http
5.
[Tutorial] On Range LIS Queries, Part 1 Hello, Codeforces!
At some point of life you want to make a new data structure problem with short statement and genius solution. LIS (Longest Increasing Subsequence) is a classic problem with beautiful solution, so you come up with the following problem:
* Given a sequence $A$ of length $N$ and Q queries $1 \le i \le j \le N$, compute the length of Longest Increasing Subsequence of $A[i], A[i + 1], \ldots, A[j]$.
But on the other hand this looks impossible to solve, and you just give up the idea.
I always thought that the above problem is unsolved (and might be impossible), but very recently I learned that such queries are **solvable** in only $O(N \log^2 N + Q \log N)$ time, not involving any sqrts! The [original paper](https://arxiv.org/abs/0707.3619) describes this technique as *semi-local string comparison*. The paper is incredibly long and uses tons of scary math terminology, but I think I found a relatively easier way to describe this technique, which I will show in t...
short statement and genius solution. LIS (Longest Increasing Subsequence) is a
classicproblem with, solution. LIS (Longest Increasing Subsequence) is a classic problem with
beautiful solution, so you, * [Yosupo Judge: Prefix-Substring LCS](https://judge.yosupo.jp/problem
/prefix_substring_lcs, The All-Pair LCS problem can be a problem of independent interest. For example,
it has already
6.
Problem Topics Good Day to you!
I've been asked to make some topic-wise list of problems I've solved. Even though I couldn't involve all problems, I've tried to involve at least "few" problems at each topic I thought up (I'm sorry if I forgot about something "easy"). I've alredy made such list once anyway I've tried to include more problems now — so here it is:
<spoiler summary="aho">
http://www.spoj.com/problems/ADAJOBS/
URI 2226 (5) //[NICE][NUMBERS][DP]
http://www.spoj.com/problems/SUB_PROB/en/
http://codeforces.me/contest/696/problem/D 8
http://www.spoj.com/problems/AHOCUR/ 5 //Aho-Corassic + DP
https://www.codechef.com/problems/LYRC (5) //Sample aho-brute-force
http://codeforces.me/problemset/problem/346/B //Proposed by [user:bradyawn,2019-08-03]
</spoiler>
<spoiler summary="automat">
6861 [LA] //CYK
UVA 10679 //Suffix Automat
http://www.spoj.com/problems/STRMATCH/ //Suffix Automat — trie might do too
http://www.spoj.com/problems/NSUBST...
Problem Topics, /contest/1183/problem/H (4) //[NICE][SUBSEQUENCE][NEXT]
https://codeforces.me/contest/1183/problem, http://codeforces.me/contest/145/problem/E (5) //[NICE]//Bit swap + subsequence, http://codeforces.me/contest/934/my (4) //Subsequence, http://www.spoj.com/problems/ADFRUITS/ (3) //Very simple (substring ==
subsequence), http://www.spoj.com/problems/DCEPC810/ (4) //VERY VERY NICE — Subsequence
2pointers+2bools, https://codeforces.me/contest/1183/problem/E (4) //[NICE][SUBSEQUENCE][NEXT], https://codeforces.me/contest/1183/problem/H (4) //[NICE][SUBSEQUENCE][NEXT]
7.
MIT Mystery Hunt Disclaimer: This blog is not about competitive programming; you probably will not learn anything about algorithms and data structures. In other words, it doesn't qualify for [this initiative](https://codeforces.me/blog/entry/110840), but I want to give a link to it anyways because I think it's cool.
I love solving problems. No, seriously. I LOVE it. The mindset described in [this blog](https://codeforces.me/blog/entry/91114) is 100% how I feel. But it is not constrained to competitive programming problems. I loved math problems for a much longer time, and physics was somewhere there. But I also love solving puzzles. And playing puzzle games on the computer (well, on consoles). And participating in intellectual games. I am not as good in them as in cp, but it was never about being good for me, I just love the process.
And I think that there might be some people with a similar love for puzzles among competitive programmers, this is why I decided to write this blog on CF <s>and no...
from the statement and writing down words. Then half an hour more for problem
F. Then we just gave up, prepared some words with ICPC subsequence, sure, but to include them into a
text about aproblem..., subsequence ICPC. Seriously?
8.
[Tutorial] Collection of little techniques #### Introduction
There are a number of "small" algorithms and facts that come up again and again in problems. I feel like there I have had to explain them many times, partly because there are no blogs about them. On the other hand, writing a blog about them is also weird because there is not that much to be said. To settle these things "once and for all", I decided to write my own list about about common "small tricks" that don't really warrant a full tutorial because they can be adequately explained in a paragraph or two and there often isn't really anything to add except for padding.
This blog is partly inspired by [user:adamant,2022-03-15]'s [blog](48417) from a few years ago. At first, I wanted to mimic adamant's blog structure exactly, but I found myself wanting to write longer paragraphs and using just bolded sentences as section headers got messy. Still, each section is short enough that it would not make much sense to write separate blogs about each of these things.
A...
a DAG.** Consider the following problem. Given a DAG with $n$ vertices and $m$
edges, you are given
9.
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...
2025 Day 1 | | | 168 | March 2025 | [Simple Subsequence
](https://codeforces.me/gym/105820/problem, ) | | | 163 | January 2025 | [Not-So-Long Increasing Subsequence
](https://codeforces.me/gym/105666/problem/C
10.
How to Solve Questions [Dominater Version] Recently, I got a request asking me to write down my thought process while solving questions. So, here is the promised blog.
I would like to thank [user:Iceknight1093,2024-08-30], [user:qwexd,2024-08-30], [user:Sana,2024-08-30], [user:Everule,2024-08-30] and [user:NovusStellachan,2024-08-30] for proof reading and suggesting edits in the blog. Special thanks to [user:satyam343,2024-08-30] for discussing most of the blog with me.
<h3> 1. Overview </h3>
The blog contains my solutions to $7$ problems in a wide range of ratings, starting from $1200$ all the way upto $2700$. Each problem has a step-by-step solution and you can notice how there are no large jumps in logic, but everything comes naturally. I do not claim that this is always possible in each problem, however I solve majority of CF problems in such a manner.
There are certainly other high rated people who will have completely different methods of solving. However, this is about what works for me. There are some meta ...
- Considering the Decision Version of the Problem instead. Especially useful in
Counting problems, Let's try to fix the LCM of the subsequence to be $x$ and then calculate
longest sequence. Only try, problem. So, we want to find the longest subsequence $b$ of $a$ such that and
$LCM(b_i) = x
11.
Run-twice (aka communication) problems with Polygon and testlib.h ### Introduction
_Run-twice_ problems (also called _multipass_ or _communication_ problems) are problems in which your program is executed twice. Here are some examples:
- [problem:2054A] from the TON marathon.
- Problems D, G and K from [Universal Cup Season 2 Stage 5](https://assets.ucup.ac/statements/statements-2-5.pdf).
- All problems from [Universal Cup Season 2 Stage 16](https://assets.ucup.ac/statements/statements-2-16.pdf).
- [Flash](https://boi2019.eio.ee/wp-content/uploads/2019/04/flash.en_.pdf) from BOI 2019 (this one is actually more complicated, but the premise is the same — there are multiple instances of your program which cannot share data except through the interactor.
As you can see, there are many ways this format can be used, but the common themes are encoding/decoding, compression/decompression, constructing a bijection and similar ideas. The general principle is that you have to implement two functions and the second function has to somehow use t...
If the subsequence contains $n$, remove it. Otherwise, add it., problems in which your program is executed twice. Here are some examples: - [
problem:2054A] from, **Problem.** Let $A_n$ be the set of even-length subsequences of the array $[1,
2, \ldots, n]$ and
12.
Longest subsequence which is a union of K increasing subsequences I was reading [user:mango_lassi,2022-03-24]'s [blog](https://codeforces.me/blog/entry/98167) and in one of the [paper](https://www.sciencedirect.com/science/article/pii/0001870874900310) referred in his blog, I found a $O(N^2)$ algorithm for constructing a longest k-increasing subsequence (a subsequence of maximum length which is a union of k increasing subsequences). While implementing it, [user:koosaga,2022-03-24] told me about the problem E in "AMPPZ-2015 MIPT-2015 ACM-ICPC Workshop Round 1" (id #6275 in opentrain) where the problem asks to construct such subsequence with constraint $N \le 2 \cdot 10^5$ and $K \le 20$.
The official solution runs in $O(N \cdot K \cdot (K + \log(N)))$. The first half seems to be doing the RSK mapping, but I couldn't figure out why the second half works. It seems to be unrolling the mapping from the back, and maintaining $K$ intervals for each row in the tableau. And the editorial only explains the first half. Can someone please explain why it work...
Longest subsequence which is a union of K increasing subsequences, " (id #6275 in opentrain) where the problem asks to construct such subsequence
with constraint $N
13.
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 ...
identify. The most common scenario involves: you'll be given an array of
numbers, and then theproblem asks, /959/problem/F)
14.
Codeforces Round #300 Editorial (+challenges) As usual, a challenge comes with every problem. I tried not to repeat the mistakes of my previous editorials and made sure that all challenges have a solution =) (except for the _italics_ parts that are open questions, at least for me). Go ahead and discuss them in the comments! General questions about problems and clarification requests are welcomed too.
**UPD**: I added codes of my solutions for all the problems. I didn't try to make them readable, but I believe most part of them should be clear. Feel free to ask questions.
[problem:538A]
Let me first clarify the statement (I really wish I didn't have to do that but it seems many participants had trouble with the correct understanding). You had to erase exactly one substring from the given string so that the rest part would form the word `CODEFORCES`. The (somewhat vague) wording `some substring` in the English translation may be the case many people thought that many substrings can be erased; still, it is beyond my understa...
**Challenge (medium)**. Given the same data (that is, a subsequence $h_{d_i}$
for a sequence $h_i, As usual, a challenge comes with every problem. I tried not to repeat the
mistakes of my previous
Tutorial of Codeforces Round 300
15.
Yandex.Algorithm 2017, third elimination round: editorial (with challenges, bells and whistles) This time I've decided to play with spoilers to faciliate the presentation as some of the guys here did before. Tell me what you think about this write-up!
#### Problem A. Shifts
Topics: dynamic programming.
Summary: the first "hard" problem of the contest. Knowing your basic DP problems helps a lot, but coming up with the precisely correct solution may take a lot of persistence.
Solution: Suppose that we are allowed to make left circular shifts as well as right ones.
<spoiler summary="Can you solve the problem in this case?">
First of all, making a shift is effectively moving a character to a different position in the string. Clearly, moving a character more than once makes no sense since we could have just moved it to its final destination instead without wasting any operations. Also, it obvious that the number of occurences of each character should be the same in both strings since it is preserved by shifts.
Now, consider the characters that are *not* moved by ...
We can see that the minimal number of, did before. Tell me what you think about this write-up! #### Problem A. Shifts
Topics
16.
Good Bye 2016 — hints and codes You can download my codes to all problems [here](http://www.filedropper.com/codes_1).
I will write a full editorial in the next few days.
Now you can read hints and short solutions.
[problem:750B]
<spoiler summary="hint">
Create a variable that will denote your current distance from the North Pole.
What are allowed values of this variable?
When can't we go West or East?
</spoiler>
[problem:750C]
<spoiler summary="hint1">
Let $x$ denote the initial rating (or his final rating, whatever is easier for you to think about).
The information that Limak is in some division in the $i$-th contest gives us some inequality for $x$.
Can you see it?
</spoiler>
<spoiler summary="hint2">
For every contest we know that the current rating is $x$ increased by some prefix sum of c_i (changes of rating).
If Limak is in the division 1, we have inequality x+prefSum >= 1900 so we have x >= 1900-prefSum.
If Limak is in the division 2, we have inequality x_prefSum <= 1899 so it is ...
write a full editorial in the next few days. Now you can read hints and short
solutions. [problem, It's often helpful to think about an algorithm to solve some easier problem. To
check if a string
Tutorial of Good Bye 2016
17.
[Tutorial] Solving Interval Problems with Geometry There are a lot of programming problems where a collection of intervals comes up, either directly or indirectly. In this tutorial, I want to present a nice way to visualize a collection of intervals, and how you can solve problems with it.
An interval $[l, r]$ is just a pair of integers $l$ and $r$ such that $l\le r$. Let's make a 2D plot where the horizontal axis is $l$ and the vertical axis is $r$. Then our interval will be represented by the 2D point $(l, r)$. But an interval is more than just a pair of numbers: it describes the set of points $x$ such that $l\le x\le r$.
How can we visually tell whether a number $x$ is covered by an interval? Well, we can represent it by a point $(x, x)$ in the plane. Then we can imagine that the interval's 2D point can see down and right, and the interval covers all the points it can see.
Here's an example where we see how the interval $[2, 4]$ covers the points $2$, $3$, and $4$.
<center>
<img src="/predownloaded/60/b8/60b8b63a2b9682f...
decreasing subsequence problem.
18.
Codeforces Round #315 Editorial [problem:569A]
Suppose we have downloaded $S$ seconds of the song and press the 'play' button. Let's find how many seconds will be downloaded when we will be forced to play the song once more. $\frac{x}{q} = \frac{x-S}{q-1}$. Hence $x=qS$.
Solution: let's multiply $S$ by $q$ while $S<T$. The answer is the amount of operations.
Complexity — $O(\log T)$
[problem:569B]
Let's look at the problem from another side: how many numbers can we leave unchanged to get permutation? It is obvious: these numbers must be from $1$ to $n$ and they are must be pairwise distinct. This condition is necessary and sufficient.
This problem can be solved with greedy algorithm. If me meet the number we have never met before and this number is between $1$ and $n$, we will leave this number unchanged. To implement this we can use array where we will mark used numbers.
After that we will look over the array again and allocate numbers that weren't used.
Complexity — $O(n)$.
...
[problem:569A] Suppose we have downloaded $S$ seconds of the song and press the
'play' button, subsequence of length $len$. (This is one of the common solution for LIS problem
).
Tutorial of Codeforces Round 315 (Div. 1)
Tutorial of Codeforces Round 315 (Div. 2)
19.
[Tutorial]Using Segment Trees to solve Dynamic Programming problems Both segment trees and dynamic programming are common topics in competitive programming. Sometimes, they even appear together. In this blog, we will mostly use segment trees as a black-box. As such, it is not necessary (though it is highly recommended) to know segment trees to understand this blog. Let's begin.
###Longest Increasing Subsequence(LIS)
_"You are given an array $v$ containing $N$ integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one._
_A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements."_
This problem is most often solved using binary search. There are countless tutorials about this method, so I will not discuss it in detail. However, there exists a more general way to solve it using segment trees.
Since we only care about the order of the elements and not a...
dynamic programming. Let $dp(i, j)$ be the length of the longest increasing
subsequence consisting, increasing subsequence in the array, i.e., the longest subsequence where every
element is larger than the, ###Longest Increasing Subsequence(LIS), _A subsequence is a sequence that can be derived from the array by deleting
some elements without
20.
CSES DP section editorial Edit: More dp tasks have been added to CSES since this blog was created. For solutions to those problems, check out [user:UnexpectedValue,2023-02-14]'s blog [here](https://codeforces.me/blog/entry/111675).
I'm using bottom-up implementations and pull dp when possible. Pull dp is when we calculate each dp entry as a function of previously calculated dp entries. This is the way used in recursion / memoization. The other alternative would be push dp, where we update future dp entries using the current dp entry.
I think [CSES](https://cses.fi/problemset/list/) is a nice collection of important CP problems, and would like it to have editorials. Without editorials users will get stuck on problems, and give up without learning the solution. I think this slows down learning significantly compared to solving problems with editorials. Therefore, I encourage others who want to contribute, to write editorials for other sections of CSES.
Feel free to point out mistakes.
## Dice Combin...
## Increasing Subsequence (1145) This is a classical problem called **Longest
Increasing
21.
[Tutorial] Simulating Cost Flow You can also read this on my blog: https://mzhang2021.github.io/cp-blog/simulating-cost-flow/
Thanks to [user:gabrielwu,2023-07-19] for proofreading.
---
This post assumes knowledge of [min/max cost flow](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem) and a rough understanding of the high-level methods for solving (successive shortest path and cycle canceling). Knowledge of specific algorithms and implementation details are not expected. Also solutions to some problems will use [Aliens trick](https://web.archive.org/web/20210511092429/http://www.serbanology.com/).
---
The cost flow problem is a well-known problem in literature that a whole slew of competitive programming problems can be formulated as. Unfortunately, competitive programming problems typically have constraints set too high for directly running even the most state of the art cost flow algorithm. However, in certain problems the flow network will have a very specific setup that allows us to figure ...
- [Codeforces 280D: k-Maximum Subsequence
Sum](https://codeforces.me/contest/280/problem/D
22.
Editorial of Codeforces Round 1053 (Div. 1, Div. 2) [problem:2151A]
Author: [user:TheScrasse,2025-09-21]<br>
Preparation: [user:TheScrasse,2025-09-21]
<spoiler summary="Hint 1">
There are two types of subarrays.
</spoiler>
<spoiler summary="Hint 2">
If there exists $a_i \geq a_{i+1}$, how many times can the subarray appear?
</spoiler>
<spoiler summary="Solution">
- If there exists an $i$ such that $a_i \geq a_{i+1}$, we have $a_i = k$ for some $k$, $a_{i+1} = 1$. The subarray $[k, 1]$ appears only once on the blackboard (when James writes $1, \ldots, k$ and then $1, \ldots, k+1$). Since $a_1, a_2, \ldots, a_m$ contains $[k, 1]$, it must appear at most once as well, but the statement guarantees that it appears at least once, so the answer is $1$.
- Otherwise, the array $a_1, a_2, \ldots, a_m$ can be rewritten as $l, l+1, \ldots, r$, and it appears when James writes $1, \ldots, r$, then when James writes $1, \ldots, r+1$, ..., then when James writes $1, \ldots, n$ (so $n-r+1$ times in total).
Complexity: $O(n)$
</...
Now, let's solve the above problem again, but we are given a prefix of the
binary string. Let $Z, Now, to solve the problem, let's enumerate the length of the common prefix of
$s$ and $t$, and then, [problem:2151A] Author: [user:TheScrasse,2025-09-21]
Preparation: [user:TheScrasse,2025-09
Tutorial of Codeforces Round 1053 (Div. 1)
Tutorial of Codeforces Round 1053 (Div. 2)
23.
Dynamic Programming Optimizations Several recent problems on Codeforces concerned dynamic programming optimization techniques.
The following table summarizes methods known to me.
<table>
<tr>
<th>Name</th>
<th>Original Recurrence</th>
<th>Sufficient Condition of Applicability</th>
<th>Original Complexity</th>
<th>Optimized Complexity</th>
<th>Links</th>
</tr>
<tr>
<td><small>Convex Hull Optimization1</small></td>
<td nowrap><small>$dp[i] = min_{j<i}\{dp[j]+b[j] \star a[i]\}$</small></td>
<td nowrap>$b[j] \geq b[j+1]$<br/><small><s>optionally</s> $a[i] \leq a[i+1]$</small></td>
<td nowrap>$O(n^2)$</td>
<td nowrap>$O(n)$</td>
<td nowrap><small>[1](https://web.archive.org/web/20181030143808/http://wcipeg.com/wiki/Convex_hull_trick) [2](https://cp-algorithms.com/geometry/convex_hull_trick.html) [3](https://codeforces.me/blog/entry/63823)<br/>[p1](/contest/319/problem/C)</small></td>
</tr>
<tr>
<td><small>Convex Hull Optimization2</small></td>
<td nowrap><small>$dp[i][j] = min_{k<j}{dp[i-1][k]+b...
=%22Speed-Up+in+Dynamic+Programming%22) - _"The Least Weight Subsequence Problem
" by D. S. Hirschberg
24.
Codeforces Round #570 Solutions Since it will be a little while longer before the editorials for the recent Division 3 Round come out, I thought I'd post some solutions I wrote up. Please feel free to post below if you have any questions or notice any errors. If any of my solutions end up getting hacked, I'll replace the submission and solution text as soon as possible. Links to my submissions are at the bottom of this post.
---
**A:** We can easily prove that the answer will not be much bigger than A, so simply iterating through all the possible values until we find one that works will do fine. (As a trivial proof, note that 1003 is interesting, so we will have to test at most 1003 numbers.) Then, the only challenging part from here is finding the sum of the digits of a number, which can be implemented easily with modular arithmetic.
---
**B:** Start by sorting the prices. It turns out that only the greatest and least prices matter. We have two key facts to prove:
1. The answer is -1 if the ...
. Then, we can see based on this observation that if A[0] is in a set of two
problems, the otherproblem, Once we've found these values, we can easily solve the problem by prioritizing
the largest
25.
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 $[...
### [Permutation Subsequence](https://cses.fi/problemset/task/3404), $ in $a$. We can then replace the elements in $b$ with $p$ (i.e. set $b_i =
p_{b_i}$). Now theproblem, problem turns into finding the longest increasing subsequence in $b$.
https://cses.fi/paste
26.
Young Tableaus and the Hook Length Formula Boring backstory of this blog
-----------------------------
In 300IQ contest 3, there [was a problem](https://codeforces.me/gym/102538/problem/D) where you had to count the number of permutations with two disjoint longest increasing subsequences. We VCd this contest while practising for ICPC, and didn't solve this problem during the contest, so I was very interested to see how it could be solved. Turns out the solution uses something called Young diagrams, and unless you already know what they are, the editorial is impossible to understand.
I asked if someone knew about Young diagrams on the competitive programming discord, and got linked [a paper](https://github.com/enkerewpo/OI-Public-Library/blob/master/IOI%E4%B8%AD%E5%9B%BD%E5%9B%BD%E5%AE%B6%E5%80%99%E9%80%89%E9%98%9F%E8%AE%BA%E6%96%87/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F2019%E8%AE%BA%E6%96%87%E9%9B%86.pdf) from the Chinese IOI selection camp, written by [user:yfzcsc,2021-12-22]. If you can speak chinese, you shoul...
particular, there probably exists a problem where you have to find for every
$m$ the maximum total, In 300IQ contest 3, there [was a problem](https://codeforces.me/gym/102538/
problem/D) where you
27.
Codeforces round #649 editorial ### [problem:1364A]
Let's start with the whole array. If every element in it is divisible by $x$, the answer is $-1$; if its sum isn't divisible by $x$, the answer is $n$. Otherwise, we must remove some elements. The key idea is that removing an element that is divisible by $x$ doesn't do us any benefits, but once we remove an element that **isn't**, the sum won't be divisible by $x$. So let the first non-multiple of $x$ be at index $l$, and the last one be at index $r$. We must either remove the prefix all the way up to $l$ or the suffix all the way up to $r$, and we'll clearly remove whichever shorter.
Code link: https://pastebin.com/j2Y8AJBA
Alternatively, we can notice that this means the answer is either a prefix or a suffix, so we can simply bruteforce them all.
### [problem:1364B]
TL;DR the answer contains the first element, last element, and all the local minima and maxima, where a local minimum is an element less than its 2 adjacents, and a local maximum is an e...
Let's look at the expression in the problem for 3 numbers. If $a>b$ and $b>c$
or if $a
Tutorial of Codeforces Round 649 (Div. 2)
28.
Educational Codeforces Round 167 (Rated for Div. 2) — Video Tutorial Hi,
Here is the video editorial of all the problems of Educational Codeforces Round 167 (Rated for Div. 2). I hope it helps.
[1989A — Catch the Coin](https://codeforces.me/contest/1989/problem/A)
---------------------------------------------------------------
<iframe width="560" height="315" src="https://www.youtube.com/embed/85AjFqfSL3E?si=dHOPNz2AnT4xbUsG&start=128" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
[1989B — Substring and Subsequence](https://codeforces.me/contest/1989/problem/B)
-----------------------------------------------------------------------------
<iframe width="560" height="315" src="https://www.youtube.com/embed/85AjFqfSL3E?si=Tt6U4eMALoAafAXw&start=558" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-...
/problem/A) --------------------------------------------------------------- , [1989B — Substring and Subsequence](https://codeforces.me/contest/1989/problem
/B)
-----------------------------------------------------------------------------
29.
Every Technique and Algorithm I Used to Become Grandmaster Hi everyone, I became grandmaster today so I decided to go down memory lane and review every problem I have ever done in a CodeForces contest to look back and see every technique and algorithm I had to use to become a grandmaster. I am not sure how useful this is, I mostly think it's fun to look at all the old solutions I wrote and how different it was from how I write code now. The main takeaway is that, as many people have said before, you don't need to know or memorize a bunch of advanced algorithms to become grandmaster. As you will see, there are many problems where I just used "ad hoc reasoning," meaning there's not a standard technique I used to solve the problem and you just need to make some clever mathematical observations to solve the problem. Also, there are many popular algorithms that I have never needed in a CodeForces contest despite being a grandmaster:
- Sparse tables, Fenwick trees, and segment trees
- String algos, like rolling hashes, Knuth-Morris-Pratt, suffix...
- [Problem A](https://codeforces.me/contest/1183/submission/56080739): Basic
number theory, - [Problem A](https://codeforces.me/contest/1194/submission/57023277): Ad hoc
reasoning and math, problem I have ever done in a CodeForces contest to look back and see every
technique and algorithm I had
30.
Codeforces Round #320 [Bayan Thanks-Round] Editorial ## [Problm 1 : Raising Bacteria](http://codeforces.me/problemset/problem/579/A)
Write down $x$ into its binary form. If the $i^{th}$ least significant bit is $1$ and $x$ contains $n$ bits, we put one bacteria into this box in the morning of $(n+1-i)^{th}$ day. Then at the noon of the $n^{th}$ day, the box will contain $x$ bacteria. So the answer is the number of ones in the binary form of $x$.
[code of author's friend: this](http://codeforces.me/contest/579/submission/13053439)
## [Problem 2 : Finding Team Member](http://codeforces.me/problemset/problem/579/B)
Sort all possible combinations from high strength to low strength. Then iterator all combinations. If two people in a combination still are not contained in any team. then we make these two people as a team.
[author's code: this](http://codeforces.me/contest/579/submission/13053526)
## [Problem 3 : A Problem about Polyline](http://codeforces.me/problemset/problem/578/A)
If point ($a$,$b$) is located on t...
## [Problm 1 : Raising Bacteria](http://codeforces.me/problemset/problem
/579/A) Write down $x, . Then we have solved the problem. And this part can be done with greedy method.
31.
Problems that I authored so far Hi everyone! I wanted to write such a blog for a long time. I finally decided to do it after Codeforces Round $934$.
I would like to thank [user:Non-origination,2024-03-21], [user:GoatTamer,2024-03-21] and [user:KingRayuga,2024-03-21] for discussing the problems with me.
For each problem, I tried to include the some interesting stuff if I could remember.
I tried to avoid using spoilers for the problems. So you can look at the comments even if you have not tried the problem.
| # | Date | Problem | Difficulty | Contest | Comment
|----|-----------|---------------------------------|------------|--------------------------------------|--------------------------------------|
| 1 | Aug 2021 | [Tree Distance Sum](https://www.codechef.com/problems/TREEDIST) | Div 2 E | Codechef Starters 10 | My first problem which appeared in some contest. I noticed some nice properties about the dfs traversal and de...
-03-21] and [user:KingRayuga,2024-03-21] for discussing the problems with me.
For eachproblem, I, | # | Date | Problem | Difficulty | Contest
32.
[Tutorial] Counting subsequences in a regular language Hello everyone! In this blog I want to share a simple but powerful technique: **counting subsequences of a string that belong to a given regular language**, by adding a DFA state dimension to the DP.
The idea itself is not new, but I haven't seen it written down explicitly as a general technique. Once you see it, you'll start recognizing it in many problems.
Maybe this is well known in China, but I'm happy because I discovered it independently.
## Prerequisites
You should be comfortable with:
- Dynamic programming.
- Basic concepts from the theory of formal languages: alphabets, regular languages, and deterministic finite automata (DFA).
## A fun motivating problem
Let's start with something concrete. You have a string $s$ of length $n$ over the alphabet $\Sigma = \{\texttt{a}, \texttt{b}, \ldots, \texttt{z}, \texttt{@}, \texttt{.}\}$. You want to count how many subsequences of $s$ form a valid email address.
We define a "valid email" as any string in the lan...
technique becomes a useful tool in your problem-solving toolbox. The recipe is
always the same: spot, ## A fun motivating problem, But the problem doesn't just ask us to *count* these subsequences, it asks for
the *sum of their, Let's see this in action on a harder problem. Consider [B2. Sub-RBS (Hard
Version)](https, What if your problem has **two** constraints on the subsequence?, problem has **two** constraints on the subsequence? - If both are regular:
build the product automaton
33.
think-cell Round 1 Editorial Thank you for your participation! I hope you liked atleast one problem from the set (:
[problem:1930A]
Idea: [user:satyam_343,2024-02-18]
Editorial: [user:Non-origination,2024-02-18]
<spoiler summary="Hint 1">
Selecting the smallest two elements on the whiteboard is a good choice in the first move.
</spoiler>
<spoiler summary="Solution">
Let $b$ denote the sorted array $a$. Assume that $b$ contains only distinct elements for convenience. We prove by induction on $n$ that the maximum final score is $b_1 + b_3 + \ldots + b_{2n-1}$.
For the base case $n = 1$, the final and only possible score that can be achieved is $b_1$.
Now let $n > 1$.
**Claim**: It is optimal to choose $b_{1}$ with $b_{2}$ for some move.
<spoiler summary="Proof">
Suppose that in some move, $b_{1}$ is choosen with $b_i$ and $b_{2}$ is choosen with $b_j$, for some $2 < i,j < 2n, i \not = j$.
The contribution to the score according to these choices is $\min(b_{1}, b_{i}) + \min(b_{2...
$) such that the last element of $S$ is $i$. Note that the answer to our
originalproblem will be $dp[n]$.
Tutorial of think-cell Round 1
34.
Codeforces Round #815 (Div. 2) Editorial [A — Burenka Plays with Fractions](https://codeforces.me/contest/1720/problem/A)
------------------
Authors: [user:zer0brain,2022-08-18]
<spoiler summary="Solution">
Note that we always can make fractions equal in two operations:
Multiply first fraction's enumerator by $bc$, the first fraction is equal to $\frac{abc}{b} = ac$,
Multiply second fraction's enumerator by $ad$, the second fraction is equal to $\frac{acd}{d} = ac$.
That means that the answer does not exceed 2.
If fractions are equal from input, the answer is 0. Otherwise, it can't be 0.
Now we have to check if the answer is 1. Let's assume that for making fractions equal in 1 operation we have to multiply first fraction's enumerator by $x$. Then $\frac{ax}{b} = \frac{c}{d}$ must be true. From this we can see that $x = \frac{bc}{ad}$. $x$ must be integer, so $bc$ must be divisible by $ad$. If we assume that we multiplied first fraction's denumerator by $x$, we can do the same calculations and see that...
[D1 — Xor-Subsequence (easy version)](https://codeforces.me/contest/1720/
problem/D1, [D2 — Xor-Subsequence (hard version)](https://codeforces.me/contest/1720/
problem/D2
Tutorial of Codeforces Round 815 (Div. 2)
35.
[Tutorial] Problems about swapping adjacent elements Hello everyone,<br>
problems about swapping adjacent elements are quite frequent in CP, but they can be tedious. In this tutorial we will see some easy ideas and use them to solve some problems of increasing difficulty. I tried to put a lot of examples to make the understanding easier.<br>
The first part of the tutorial is quite basic, so feel free to skip it and jump to the problems if you already know the concepts.
Target: rating $[1400, 2100]$ on CF<br>
Prerequisites: greedy, Fenwick tree (or segment tree)
Counting inversions
------------------
Let's start from a simple problem.
_You are given a permutation $a$ of length $n$. In one move, you can swap two elements in adjacent positions. What's the minimum number of moves required to sort the array?_
#### Claim
The result $k$ is equal to the number of inversions, i.e. the pairs $(i, j)$ ($1 \leq i < j \leq n$) such that $a_i > a_j$.
#### Proof 1
Let $f(x)$ be the number of inversions after $x$ moves.<br>
In one...
tree (or segment tree) Counting inversions ------------------ Let's start from
a simpleproblem, '` separately. The relative order of a subsequence of equal characters doesn't
change in the optimal solution
36.
My sad story Today I participated in Facebook Hacker Cup Round 3. 100 people participated and top 25 will advance to the onsite round in California.
---
The contest has started. I glanced at titles of problems and samples, and decided to solve "Divisor Function Optimization" first. It was a number theory problem, so I was confident that I can solve this problem. However, after thinking for a while, I noticed that I need to calculate all primes <= 2^250000! (of course, it turned out to be wrong later.) It seemed to be impossible, so I read the other two problems.
"Trapezoids". My first implession was (I don't know whether it's correct or not): convert trapezoids to rectangles in 2D plane and do some sweep line algorithm. It looked hard to implement, so I decided to skip it.
"Unfriending". Try all local-maximal subsequences that can be removed? It's quite easy! I implemented and debugged... oh, I didn't read the problem correctly!
Meanwhile a few people solved "Trapezoids", but let's r...
implemented and debugged... oh, I didn't read the problem correctly!, problem, so I was confident that I can solve this problem. However, after
thinking for a while, I
37.
Codeforces Round 964 Video Editorial (with hints) [problem:1999A]
<spoiler summary="Idea">
$N/10$ will give you the digit at tenth place.
$N\%10$ will give you the digit at ones place.
</spoiler>
My submission — [submission:274717610]
<spoiler summary="Video editorial">
<iframe width="853" height="480" src="https://www.youtube.com/embed/9gxHLLYsfcg?start=305" title="Codeforces Round 964 Solution Discussion | ABCDEFG1G2 | All Problems" 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:1999B]
<spoiler summary="Idea">
We can bruteforce all the possible rounds.
The possible pairings are -
- $A_1 - B_1$ and $A_2 - B_2$
- $A_2 - B_2$ and $A_1 - B_1$
- $A_2 - B_1$ and $A_1 - B_2$
- $A_1 - B_2$ and $A_2 - B_1$
</spoiler>
My submission — [submission:274958241]
<spoiler summary="Video editorial">
<ifra...
`?`. [392. Is Subsequence](https://leetcode.com/problems/is-subsequence
/description, [problem:1999A] $N/10$ will give you the digit at tenth place
Statements of Codeforces Round 964 (Div. 4)
38.
Insomnia'25 Editorial Hope you enjoyed the contest!
Text editorials will be published soon. I've created video editorials for all problems, except for problem _M — Alternating Sum_).
[A \- XO-OR](https://codeforces.me/gym/590997/problem/A)
----------
[Link to video](https://youtu.be/wVtzgq1r8RU)
<spoiler summary="Code">
~~~~~
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e3 + 14, B = 60;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
ll x, y;
cin >> x >> y;
if (y > x) {
cout << "-1\n";
continue;
}
bool seen = false;
for (int i = B - 1; i >= 0; --i) {
if ((x >> i & 1) > (y >> i & 1))
seen = true;
if (seen && (x >> i & 1) == 0) {
x ^= (1ll << i + 1);
x |= (1ll << i + 1) - 1;
...
Tutorial of Insomnia 2025
39.
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...
Contest discussion <http://codeforces.me/blog/entry/447>
Problem A. Noldbach, Problem C. Balance
Consider the input string $A$ of length $n$. Let's perform some
Tutorial of Codeforces Beta Round 17
40.
Codeforces Month of Blog Posts Results One and a half months ago [I proposed a challenge](https://codeforces.me/blog/entry/110840) to every one of you to get something from your drafts or from your head and actually write a blog post about it. I got a bunch of submissions, and you can find the links to all of them throughout this blog post (I was actually surprised that all entries were meaningful and interesting, so I definitely recommend checking them out). If you submitted an entry and I didn't mention it here, it is not purposeful! Indicate it via a direct message and I will include it here. It was just a bit hard to keep track of all submissions.
I went through all the submissions. Some of them were very complicated, and I tried my best to get the overall idea but I will need to come back to dive deeper into some technical proofs. However, I believe that these technicalities that I glanced through do not affect my decisions. We are ready to present the winners!
Regarding the first place, there was no doubt in my...
increasing subsequence queries. It's based on a research paper (with the
author of which I actually, ) [of blog posts](https://codeforces.me/blog/entry/111807) on range longest
increasingsubsequence
41.
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://...
DP Tutorial and Problem List, ) * [Consecutive Subsequence](https://codeforces.me/problemset/problem/977/F)
* [substring](https, -293ac65c10d6) * [Subsequence related Problem
solution](https://medium.com/@harryjobz/subsequence-of-length-3, /spidernitt/problem-c-codeforces-round-455-293ac65c10d6) * [Subsequence related
Problem solution
42.
Topic Stream: Dynamic Programming #1 Hi,
Today, I had my first topic stream on Dynamic Programming. The stream lasted for two hours, and this was the plan for the first livestream:
1. Start with the basics of Dynamic Programming: the logic behind it and when to apply it.
2. [Boredom — difficulty 1500](https://codeforces.me/contest/455/problem/A)
3. [Consecutive Subsequence — difficulty 1700](https://codeforces.me/contest/977/problem/F)
4. [Red-Green Tower — difficulty 2000](https://codeforces.me/problemset/problem/478/D)
5. [Winter is here — difficulty 2200](https://codeforces.me/problemset/problem/839/D)
I will write the highlights of the livestream here, while embedding the specific parts of the videos so that you can easily watch the parts you want. You can ask questions about any part here, on YouTube, or in our Telegram Channel. The main discussion thread is in our Telegram Channel.
The Basics of Dynamic Programming
---------------------------------
In this part, I talk...
://codeforces.com/contest/455/problem/A) 3. [Consecutive Subsequence —
difficulty 1700](https, Subsequence — difficulty 1700](https://codeforces.me/contest/977/problem/F) 4.
[Red-Green Tower, This is another problem that helps with the idea of defining subproblems as the
different cases, [977F — Consecutive Subsequence](https://codeforces.me/contest/977/problem/F)
------------------------------------------------------------------------------------
43.
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),...
, I've mainly invented easy-ish problems. I wish to invent a very hard problem
sooner or later, Anyway, I still wanted to make a problem where the intended solution uses the
random shuffle
44.
Codeforces Round #402, Editorial ### [problem:779A]
Problem setter: [user:MikeMirzayanov,2017-02-28]
To solve this problem let's use array $cnt[]$. We need to iterate through first array with academic performances and for current performance $x$ let's increase $cnt[x]$ on one. In the same way we need to iterate through the second array and decrease $cnt[x]$ on one.
If after that at least one element of array $cnt[]$ is odd the answer is $-1$ (it means that there are odd number of student with such performance and it is impossible to divide them in two. If all elements are even the answer is the sum of absolute values of array $cnt$ divided by 2. In the end we need to divide the answer on 2 because each change will be counted twice with this way of finding the answer.
### [problem:779B]
Problem setter: [user:MikeMirzayanov,2017-02-28]
To solve this problem we need to make $k$ zeroes in the end of number $n$. Let's look on the given number as on the string and iterate through it beginning from the end...
In this problem we have to find the last moment of time, when $t$ has $p$ as a
subsequence., subsequence greedily. ### [problem:778B] Problem setter:
[user:burakov28,2017-02-28] Note
Tutorial of Codeforces Round 402 (Div. 1)
Tutorial of Codeforces Round 402 (Div. 2)
45.
A notorious coincidence (1854E) So one thing led to another and now I'm here to share my results.
[Codeforces Round 889 (Div. 1)](https://codeforces.me/contest/1854)
------------------
As of writting this blog that's the most recent codeforces round and there was some controversy about some problems in it. I'm here to talk about a funny thing that happened involving its div1E.
This story starts during the contest.
<spoiler summary="You can skip this, it's just me talking about what happened to me before reaching E">
I was taking the contest and thinking about going to sleep after 1 hour without mindsolving anything but A1 but then I ended up solving CBA1. Without being able to notice that my solution to A1 was actually the intended solution to A2 and not having the faith in the gods of AC to just take the minimum of both constructions, I turned into E as I'm notoriously bad at interactive problems.
</spoiler>
Revisiting E after solving the other problems, I thought "maybe using a bunch of ones and hi...
point. Then something clicked and I remembered a past problem that I deemed to
be similar and had, #### "Almost reducing" Problem 2 into Problem 1 If we're able to solve an
instance ofProblem 1
46.
Codeforces Round #283: editorial (with bonuses!) Each problem comes with a challenge — a bonus task somehow related to the problem; you may tackle at the challenges for fun and practice, also feel free to discuss them at the comments. =)
[problem:496A]
For every option of removing an element we run through the remaining elements and find the maximal difference between adjacent ones; print the smallest found answer. The solution has complexity $O(n^2)$. It can be noticed that after removing an element the difficulty either stays the same or becomes equal to the difference between the neighbours of the removed element (whatever is larger); thus, the difficulty for every option of removing an element can be found in $O(1)$, for the total complexity of $O(n)$. Any of these solutions (or even less efficient ones) could pass the tests.
**Challenge**: suppose we now have to remove exactly $k$ arbitrary elements (but the first and the last elements have to stay in their places). How small the maximal difference between adjacen...
Each problem comes with a challenge — a bonus task somehow related to the
problem; you may
Tutorial of Codeforces Round 283 (Div. 2)
47.
Codeforces Round #766 (Div. 2) Editorial Thank you for participating in our contest! We hope you enjoyed it.
[problem:1627A]
<spoiler summary="Hint 1">
When is the answer $-1$? When is the answer $0$? When is the answer $1$?
</spoiler>
<spoiler summary="Hint 2">
Can you do all remaining cases in $2$ steps?
</spoiler>
<spoiler summary="Solution">
[tutorial:1627A]
</spoiler>
<spoiler summary="Implementation (C++)">
[submission:142882991]
</spoiler>
<spoiler summary="Implementation (Java)">
[submission:142882684]
</spoiler>
<spoiler summary="Implementation (Python)">
[submission:142882963]
</spoiler>
<spoiler summary="Video Editorial">
https://www.youtube.com/watch?v=j_oe8DA4hhM
</spoiler>
[problem:1627B]
<spoiler summary="Hint">
If the classroom was one-dimensional, i.e. $n = 1$, where would the best place for Tina to sit be?
</spoiler>
<spoiler summary="Hint Solution">
The best place for Tina to sit a grid where $n = 1$ would be either $(1, 1)$, or $(1, m)$.
</spoiler>
<spo...
Sorry for the statement of the problem initially. It was correct throughout
testing, but during, Thank you for participating in our contest! We hope you enjoyed it. [problem
:1627A]
Tutorial of Codeforces Round 766 (Div. 2)
48.
Codeforces Round #326 (Editorial) ### Div.2 A (Author: [user:Haghani,2015-10-01])
Idea is a simple greedy, buy needed meat for $i-th$ day when it's cheapest among days $1, 2, ..., n$.
So, the pseudo code below will work:
~~~~~
ans = 0
price = infinity
for i = 1 to n
price = min(price, p[i])
ans += price * a[i]
~~~~~
Time complexity: $\mathcal O(n)$
[C++ Code](http://ideone.com/fa7rF5) by [user:amd,2016-03-05]
[Python Code](http://ideone.com/Sh0hPp) by [user:Haghani,2015-10-15]
[Python Code](http://ideone.com/5J6Rew) by [user:Zlobober,2015-10-15]
### Div.2 B (Author: [user:amd,2016-03-05])
Find all prime divisors of $n$. Assume they are $p_1, p_2, ..., p_k$ (in $\mathcal O(\sqrt n)$). If answer is $a$, then we know that for each $1 \leq i \leq k$, obviously $a$ is not divisible by $p_i^2$ (and all greater powers of $p_i$). So $a \leq p_1 \times p_2 \times ... \times p_k$. And we...
For the problem above, let $dp[i][j]$ be the number of valid subsequences of
$b$ where $x = j$ and
Tutorial of Codeforces Round 326 (Div. 1)
49.
[Tutorial] Rolling hash and 8 interesting problems [Editorial] **UPD**: while I was translating this post from Russian to English, [user:dacin21,2018-07-06] wrote his post, more advanced, [link](http://codeforces.me/blog/entry/60442). I hope that my post will help beginners, but in my post more rough estimates.
And in Russia we call **rolling hashes** as a **polynomial hashes**.
Hello, codeforces! This blogpost is written for all those who want to understand and use polynomial hashes and learn how to apply them in solving various problems. I will briefly write the theoretical material, consider the features of the implementation and consider some problems, among them:
1. Searching all occurrences of one string of length $n$ in another string length $m$ in $O(n + m)$ time
2. Searching for the largest common substring of two strings of lengths $ n $ and $ m $ $(n \ge m) $ in $O((n+m \cdot log(n)) \cdot log(m))$ and $O(n \cdot log(m))$ time
3. Finding the lexicographically minimal cyclic shift of a string of length $ n $ in $ O(n \cdo...
In this problem we need to use compare by great / less in `O, often do not need to think, you can immediately take and write a naive
algorithm to solve theproblem
50.
Codeforces Educational Round 171 — Video Tutorial **Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.**
### [2026A — Perpendicular Segments](https://codeforces.me/contest/2026/problem/A)
<spoiler summary="Video">
<iframe width="800" height="450" src="https://www.youtube.com/embed/UXdnEa14CbM?si=pEUHDEJmUWKlZoHl&start=289" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
</spoiler>
### [2026B — Black Cells](https://codeforces.me/contest/2026/problem/B)
<spoiler summary="Video">
<iframe width="800" height="450" src="https://www.youtube.com/embed/UXdnEa14CbM?si=GWFvyDEUaeeVbCqc&start=1190" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipbo...
### [2026E — Best Subsequence](https://codeforces.me/contest/2026/problem/E)
51.
TheForces Round #20 (7-Problem-Forces) Editorial [A](https://codeforces.me/gym/104471/problem/A)
<spoiler summary="code">
```
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t --> 0) {
int n;
cin >> n;
vector<int> a(n);
vector<int> b(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y) {
if (b[x] == b[y]) return a[x] > a[y];
return b[x] == 1;
});
int ans = a[0] * b[0];
int suma = 0, sumb = 0;
for (int i = 0; i <...
TheForces Round #20 (7-Problem-Forces) Editorial, number of non-empty subsequence of subarray [l,r] //with adding=sum if(
!(sum>=L and sum<=R, Firstly,we substract all $a_i$ by $x$.Then the problem is equivent to count the
number of, [A](https://codeforces.me/gym/104471/problem/A) ``` #include
Tutorial of TheForces Round #20 (7-Problems-Forces)
52.
Unofficial editorial for Codeforces Round #760 (Div.3) <spoiler summary="A small confession">
Hi, this is the first time I write such a blog like this. All is because of my excitement that for the first time I can solve all problems, not because I am worshiping myself or something. I know this is just a Div-3 contest, so there are many people who can solve it. But if you are stuck with some problems, feel free to read my solutions.
This is not an official editorial, so the solutions might not be the best of all solutions out there, so if you have something to discuss, feel free to leave something below. Thanks for all.
</spoiler>
[A. Polycarp and Sums of Subsequences](https://codeforces.cc/contest/1618/problem/A)
-------------------------------------------------------------------------------------
The first two numbers cannot be produced by a sum operation, so we have $2$ of $3$ numbers we must find. How to find the last one? Subtract these two from the largest one.
<spoiler summary="Implentation">
~~~~~
vector<ll> a(...
[A. Polycarp and Sums of Subsequences](https://codeforces.cc/contest/1618/
problem/A)
-------------------------------------------------------------------------------------
53.
Codeforces Round 1057 (Div. 2) Editorial ### [problem:2153a]
<spoiler summary="Hint 1">
You can't eat two apples of the same beauty value.
</spoiler>
<spoiler summary="Hint 2">
Is there a way to eat apples of all kinds of beauty values that appearred?
</spoiler>
<spoiler summary="Solution">
First of all, since the beauty values of the apples you eat are in strictly increasing order, any two of them have different beauty values.
So, for each beauty value, you can eat at most one apple.
In fact, it can be shown that it is always possible to eat exactly one apple of each beauty value. Let's say all the distinct beauty values are $v_1,v_2,\ldots,v_k\ (v_1\lt v_2\lt\ldots\lt v_k)$. You can eat one apple of beauty value $v_i$ during the $i$-th time you move along the full circle.
Therefore, the answer is the number of distinct numbers in beauty values. The time complexity is $\mathcal{O}(n)$.
</spoiler>
<spoiler summary="Code (C++, maomao90)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
i...
The strange condition given by the problem is that there are no
Tutorial of Codeforces Round 1057 (Div. 2)
54.
Codeforces Round 967 (Div. 2) — Video Tutorial **Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.**
### [2001A — Make All Equal](https://codeforces.me/contest/2001/problem/A)
<spoiler summary="Video">
<iframe width="800" height="450" src="https://www.youtube.com/embed/MqRyqCoi6Lc?si=ulDr7OFQVXzC5gH7&start=196" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
</spoiler>
### [2001B — Generate Permutation](https://codeforces.me/contest/2001/problem/B)
<spoiler summary="Video">
<iframe width="800" height="450" src="https://www.youtube.com/embed/MqRyqCoi6Lc?si=Y1kmFV6JXqula6UN&start=962" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboar...
editorial.** ### [2001A — Make All Equal](https://codeforces.me/contest/2001/
problem/A, ### [2001D — Longest Max Min Subsequence](https://codeforces.me/contest/2001/
problem/D)
Tutorial of Codeforces Round 967 (Div. 2)
55.
Codeforces Round #172 Editorial Overview ...
==================
In DIV 1, there are 3 normal tasks accompanied with 2 challenge tasks.
About 40 competitors solve first three tasks during the contest and I believe there will be more if we extended the duration a little bit.
Task D is a standard data-structure problem hidden behind a classical maximum cost flow model. This kind of problem are usually trick-less, but hard to implement especially under the pressure. Because of this, it becomes tonight's draw-breaker.
Task E is a extended version on a classical DP && Math problem. There are many solutions to the original problem, one is giving a global view under the state transition, and using a data structure to handle it carefully. However, this one is even more harder, few people have ever tried it except [user:Jacob,2013-03-11]. (Although is wrong.)
As a seasoned competitor, [user:Petr,2013-03-10] took the C-B-A order which proved to be the best choice through out the night. And after quickly solved C and...
/280/C) - [Problem D. k-Maximum Subsequence
Sum](http://codeforces.me/problemset/problem/280/D, /problemset/problem/280/C) - [Problem D. k-Maximum Subsequence
Sum](http://codeforces.me/problemset
Tutorial of Codeforces Round 172 (Div. 1)
Tutorial of Codeforces Round 172 (Div. 2)
56.
What are the things that you discovered independently? Hello CodeForces!
I know this happened to everyone — you made an interesting mathematical/algorithmic/whatever discovery and you were very proud of it and later you realized it's already well known. What's your story?
I'll start:
I discovered a variant of Mo's algorithm around 4 years ago. I was solving the following problem:
Given a static array $a_1, ..., a_n$ and $q = O(n)$ queries. You are allowed to solve them offline. Each query has the form $(l, r)$ and you're supposed to answer, if you were take all the numbers from $a_l, ..., a_r$, extract them into another array and then sort that array, what would be the sum of all elements at odd indexes?
This is how I was thinking:
If all the queries could be ordered such that both their left ends and right ends form an increasing sequence, you could answer all those queries by adding/removing elements from some augmented balanced binary tree or segment tree in $O(n log n)$. Then again, the same is true when all the que...
that, in an array of $n^2+1$ numbers, there is always an increasing subsequence
or a decreasing, years ago. I was solving the following problem: Given a static array $a_1,
..., a_n$ and $q = O(n
57.
On "PermutationForces" Disclaimer: This blog is entirely my own opinion, please do not get mad at the authors from round 779. If you did not enjoy that round, please do not blame the authors. Personally, I felt that the authors overall did a wonderful job ([user:SPyofgame,2022-04-02]'s div 2F was honestly one of my favourite problems in 2022 so far).
Last week round 779 was held, a common feedback that people seemed to be quite vocal about was that the round was "PermutationForces".
If we look at the actual contest, we do see that problems B, C, D, E all contain the word permutation inside, so it is natural to think that pr...
a subsequence, we have to paste some definition into the statement. Of course,
I feel it is kinda, problems, we only use the definitions of permutation at "face value". - [
problem:1658B] — a
58.
Segment Tree Problems I gathered up a lot of Segment problems :) -->
**upd1** : more segment :D
**upd2** : now there is e-olymp problems. thanks to [user:dmkozyrev,2019-12-06].
codeforces :
[Xenia and Bit Operations](http://codeforces.me/problemset/problem/339/D)
[Knight Tournament](https://codeforces.me/contest/356/problem/A)
[Bash and a Tough Math Puzzle](https://codeforces.me/problemset/problem/914/D)
[Pashmak and Parmida's problem](https://codeforces.me/contest/459/problem/D)
[Enemy is weak](https://codeforces.me/contest/61/problem/E)
[Circular RMQ](https://codeforces.me/contest/52/problem/C)
[REQ](https://codeforces.me/contest/594/problem/D)
[Lucky Queries](https://codeforces.me/contest/145/problem/E)
[XOR on Segment](http://codeforces.me/problemset/problem/242/E)
[Sereja and Brackets](http://codeforces.me/problemset/problem/380/C)
[Ant Colony](http://codeforces.me/problemset/problem/474/F)
[Babaei and Birthday Cake](https://codeforces...
) [Sasha and Array](https://codeforces.me/contest/718/problem/C) [New Year and
OldSubsequence, ://codeforces.com/contest/718/problem/C) [New Year and Old Subsequence
](https://codeforces.me/contest/750, ://codeforces.com/gym/101879/problem/G) [Subsequence Sum
Queries](https://codeforces.me/gym/101741
59.
Codeforces Round #361 (Div. 2) Editorial [A.Mike and Cellphone](http://codeforces.me/contest/689/problem/A)
Author:[user:dans,2016-07-06].
Developed:[user:reality,2016-07-06],[user:ThatMathGuy,2016-07-06]
We can try out all of the possible starting digits, seeing if we will go out of bounds by repeating the same movements. If it is valid and different from the correct one, we output "NO", otherwise we just output "YES".
<spoiler summary="C++ code">
~~~~~
pair < int , int > s[55][55];
int v[55][55];
pair < int , int > where[55];
int main(void)
{
for (int i = 1;i <= 10;++i)
for (int j = 1;j <= 10;++j)
v[i][j] = -1;
v[1][1] = 1;
v[1][2] = 2;
v[1][3] = 3;
v[2][1] = 4;
v[2][2] = 5;
v[2][3] = 6;
v[3][1] = 7;
v[3][2] = 8;
v[3][3] = 9;
v[4][2] = 0;
for (int k = 0;k <= 9;++k)
for (int i = 1;i <= 4;++i)
for (int j = 1;j <= 4;++j)
if (v[i][j] == k) where[k] = {i,j};
for (int i = 0;i <= 9;++i...
[D. Friends and Subsequences](http://codeforces.me/contest/689/problem/D)
Tutorial of Codeforces Round 361 (Div. 2)
60.
My Editorial of Problem E in Round 1055 [Problem E. Monotone Subsequence](https://codeforces.me/contest/2152/problem/E)
Suppose you made a query $[i_1, i_2, \ldots, i_k]$ and got a response $[j_1, j_2, \ldots, j_c]$. From the definition of visible skyscrapers, you can tell $i_1 = j_1$, and the following holds: $$\begin{align*}
p_{j_1} > p_{i_t} &\quad \text{for all} \; t \; \text{such that} \; j_1 < i_t < j_2, \\
p_{j_2} > p_{i_t} &\quad \text{for all} \; t \; \text{such that} \; j_2 < i_t < j_3, \\
& \quad \vdots \\
p_{j_{c-1}} > p_{i_t} &\quad \text{for all} \; t \; \text{such that} \; j_{c-1} < i_t < j_c, \\
p_{j_c} > p_{i_t} &\quad \text{for all} \; t \; \text{such that} \; j_c < i_t.
\end{align*}$$
Based on this, think about the following algorithm:
* Initially $S_0 = \\{ 1, 2, \ldots, n^2 + 1 \\}$.
* Do the following $n$ times. In the $r$-th round $(1 \le r \le n)$, make a query consisting of all indices in $S_{r-1}$. Suppose you get a response $[j_1, j_2, \ldots, j_c]$. If $c \ge n+1$, you tak...
My Editorial of Problem E in Round 1055, response $[j_1, j_2, \ldots, j_c]$. If $c \ge n+1$, you take any subsequence
of length $n+1$ out of the, [Problem E. Monotone Subsequence](https://codeforces.me/contest/2152/problem
/E) Suppose you, [Problem E. Monotone Subsequence](https://codeforces.me/contest/2152/problem/E)
61.
Beginner Friendly Series on Dynamic Programming This series of videos are focused on explaining dynamic programming by illustrating the application of DP through the use of selected problems from platforms like Codeforces, Codechef, SPOJ, CSES and Atcoder.
After going through this series, you should find yourself confident in approaching dynamic programming problems and also implementing them in a reasonable amount of time.
I will also live code and submit the solutions to the problem on the coding platform from where the problem comes.
Some Basic elements of Dynamic Programming
==================
Some general ideas and my thoughts about DP to help you get started:<br>
Part 1: [https://youtu.be/24hk2qW_BCU](https://youtu.be/24hk2qW_BCU)<br>
1. What is Divide and Conquer?<br>
2. What is Dynamic Programming?<br>
3. Types of DP problems.<br>
Part 2: [https://youtu.be/yfgKw6BUZUk](https://youtu.be/yfgKw6BUZUk)<br>
1. What is a DP-state?<br>
2. Characterizing a DP-state.<br>
3. What is a recurrence?<br>
4. T...
://youtu.be/QGJXQAaDs3I](https://youtu.be/QGJXQAaDs3I) Problem 13: Longest
IncreasingSubsequence O, Problem 13: Longest Increasing Subsequence O(NlogN) ------------------ Source:
CSES
Problem
62.
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...
, then we can just put all the elements in $1$ subsequence. Otherwise, we need
the partitioning, : https://pastebin.com/0D8yL5WW ### [problem:1514C] So first observe that the
subsequence can't
Tutorial of Codeforces Round 716 (Div. 2)
63.
Codeforces Round #201 Editorial 
Overview
========
In DIV 1, there are 4 interesting problems together with a normal one. We think it is reasonable because we can't have a round fullly with intelligence. Problem A, C have weak pretests while others intended to be strong. About more then 200 participants solve A in the early 45mins, then a few of them start from C while most of the other start from B.
Problem B is a rather standard problem, but if you're unfamiliar with the algorithm, it can be very hard. Problem C is a more intersting problem. As the name implies, there was [a similar version](http://codeforces.me/problemset/problem/251/C) in the previous round before, but this time it has a brand new constrains.(So here we have a psychology experiment: could different constrains make people thinking in a slightly different way?ww)
The standard solution of problem C is $O((b-a) + nlogn)$. The first expected correct solution was writt...
### [Problem B. Lucky Common Subsequence](http://codeforces.me/problemset/
problem/346/B
Tutorial of Codeforces Round 201 (Div. 1)
Tutorial of Codeforces Round 201 (Div. 2)
64.
Codeforces round #473 editorial #### [problem:959A]
It's easy to see that if $n=0$, the next player loses. If $n$ is even, Mahmoud will choose $a=n$ and win. Otherwise, Mahmoud will have to choose $a<n$. $n$ is odd and $a$ is even, so $n-a$ is odd. Ehab will then subtract it all and win. Therefore, if $n$ is even Mahmoud wins. Otherwise, Ehab wins. $n=1$ doesn't follow our proof, yet Ehab still wins at it because Mahmoud won't be even able to choose $a$.
Code link (me) : https://pastebin.com/X3D08tg9
Code link ([user:mahmoudbadawy,2018-04-02]) : https://pastebin.com/4u3RHE7n
Time complexity : $O(1)$.
**Bonus task :** If there were multiple integers, and each player can choose which integer to subtract from, who will win?
<spoiler summary="Solution">
Ehab can follow a good greedy strategy : make some number odd and leave it till the end of the game. Mahmoud won't be able to make it 0 so Ehab will win. If there's already an odd integer, or there are at least 2 even integers, Ehab can do that. Theref...
Let's solve a simpler version of the problem. Assume the queries only ask you
to see whether the, To solve our problem, let's see the naiive dynamic programming solution. Let
$dp[i][x]$ be the
Tutorial of Codeforces Round 473 (Div. 2)
65.
Proving Open Cup Problem. The problem D in the latest Open Cup involves function <i>f</i>(<i>n</i>) which is defined as the minimum sum of sequence <i>b</i><sub>1</sub>, ..., <i>b</i><sub><i>k</i></sub> such that any sequence <i>a</i><sub>1</sub>, ..., <i>a</i><sub><i>l</i></sub> with sum less than or equal to <i>n</i> can be dominated by some subsequence of <i>b</i>. One sequence dominates the other, if they have the same length any every element of the first sequence greater than or equal to corresponding element of the second sequence. It turns out that <i>f</i>(<i>n</i>) = <i>n</i> + <i>f</i>(<i>k</i>) + <i>f</i>(<i>n</i> − 1 − <i>k</i>) where <i>k</i> = [(<i>n</i> − 1) / 2]. But why? If this equation still keeps you up at night, you can finally sleep well now. I have found a wonderful proof of this statement which fits the bounds of this site.
<p>
[cut]
Two sides of the proof
==================
Let us construct the <i>b</i> sequence first.
For brevity, we will say that sequenc...
Proving Open Cup Problem., > can be dominated by some subsequence of B1. If t = s we don't need to, For brevity, we will say that sequence b covers sequence a, if some subsequence
of, The problem D in the latest Open Cup involves function f(n) which is defined as
the
66.
Codeforces Round 921 (Div. 1, Div. 2) Editorial I hope you enjoyed the round. Here is the editorial. Do provide your feedback on each problem so that we can improve upon them the next time.
#### [2A. We Got Everything Covered!](https://codeforces.me/contest/1925/problem/A)
Author: [user:JaySharma1048576,2024-01-27]
<spoiler summary="Hint 1">
The smallest length for such a string is $n\cdot k$.
</spoiler>
<spoiler summary="Tutorial">
The smallest length possible for such a string is $n\cdot k$.
<spoiler summary="Why?">
To have the string $\texttt{aaa}\ldots\texttt{a}$ as a subsequence, you need to have at least $n$ characters in the string as $\texttt{a}$. Similarly for all $k$ different characters. So, that gives a total length of at least $n\cdot k$.
</spoiler>
In fact, it is always possible to construct a string of length $n\cdot k$ that satisfies this property. One such string is $(a_1a_2a_3\ldots a_k)(a_1a_2a_3\ldots a_k)(a_1a_2a_3\ldots a_k)\ldots n$ times where $a_i$ is the $i^{th}$ letter of English alph...
#### [1D. Balanced Subsequences](https://codeforces.me/contest/1924/problem/D)
Author
Tutorial of Codeforces Round 921 (Div. 1)
Tutorial of Codeforces Round 921 (Div. 2)
67.
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...
### [C. Largest Palindromic Subsequence](https://codeforces.me/gym/104520/
problem/C)
Tutorial of Teamscode Summer 2023 Contest
68.
5th place curse in Turkish Team Selection Contest and my goodbye Hello, I want to talk about an ongoing curse in Turkey. I am the most recent victim of that curse at it's 9th year. Let's start with the beginning.
#### 2015-2016
Curse starts with [user:ErdemKirez,2023-05-10] taking 5th place in 2015. After that year, he tried his best and was in the team in 2016. But because of some reasons Turkey team wasn't able to participate IOI 2016. After that, the curse has started. You can look at this [blog](https://codeforces.me/blog/entry/54007) for details.
#### 2017
I don't know who was at 5th place that year. But probably curse was active.
#### 2018-2019
In 2018, [user:TahsinEnesKuru,2023-05-10] got 5th place. 3/4 of that team was at their last year so he had a high chance of being in the team at 2019. But he didn't know, he was already cursed. He missed the team with a difference of 3/700. He also has a [blog](https://codeforces.me/blog/entry/66811) about it.
#### 2020
At that year, [user:ExpertHunter,2023-05-10] got 5th place. He was at hi...
literally was at div3A level. I don't know the purpose of that problem. Most
of the participants, misreaded a simple thing about a problem (replace and swap is similar in
Turkish) so I wasn't able to solve
69.
Problem 629D (heaviest increasing subsequence) discussion Problem [problem:629D] asks for the heaviest strictly increasing subsequence of a set of volumes. When I saw this problem (in practice) I immediately recognized that this was probably a well-known problem, so I looked up code. I found some code from StackOverflow, but it occured to me that this code only found the heaviest nondecreasing subsequence. Not willing to change the code too much, I came up with the following idea. If taking the array one by one is like:
~~~~~
l = []
for r in range(n):
k = int(input())
l.append(k)
~~~~~
then in order to make the heaviest strictly increasing subsequence roughly equal to the heaviest nondecreasing subsequence, do something along these lines. This should work, because the epsilon is small enough such that the relative order should not be changed, but equal terms will have a difference: terms which come closer to the front will be ever so slightly larger than equal terms closer to the end.
~~~~~
l = []
for r in range(n):
...
Problem 629D (heaviest increasing subsequence) discussion, will become larger than k+1. Furthermore, the sum of all terms in the
subsequence will have a, Problem [problem:629D] asks for the heaviest strictly increasing subsequence of
a set of volumes, then in order to make the heaviest strictly increasing subsequence roughly
equal to the heaviest
70.
Codeforces Trainings Season 1 Episode 10: Editorial #### **Welcome to The Editorial!**
<img src="http://th04.deviantart.net/fs70/PRE/f/2013/078/b/f/mi_super_saiyan_god_remasterizado_by_salvamakoto-d5ymxyi.png" height="50%" width="50%" />
**Keep the upvotes piling up! muhehe**
IZ.COMPLETE.
### A. Rasheda And The Zeriba
[cut] $\ $
(difficulty: medium)
The first question is: When is it possible to construct a (convex) polygon from sticks of given lengths $L_i$?
This question is answered by what's sometimes known as Polygon inequality theorem, which states that the sufficient and necessary condition is for every $L_i$ to be strictly less than the sum of all other $L_i$. You can imagine that it works because for the endpoints of every side, the shortest path between them (equal to the length of that side) must be smaller than any other path, including the other one along the perimeter of the polygon; constructing such a polygon, even a convex one, is pretty easy, just imagine it as having sticks linked to each other that...
If we had $N=1$, the problem would be just about checking whether a string $T$
is a substring of
71.
VK Cup 2012 Round 2 — Разбор ** UPD: Formulas are already fixed. **
**[problem:163A]**
Solution summary: dynamic programming.
Sample jury solution: [submission:1415300] (author = [user:levlam,2012-03-25])
The problem could be solved with the following dynamic programming.
Let $f[i, j]$ be the number of distinct pairs ("substring starting at
position $i$" and "subsequence of the substring $t[j\ldots |t|]$")
Then:
~~~~~
f[i, j] = f[i, j + 1];
if (s[i] == t[j])
add(f[i, j], f[i + 1, j + 1] + 1)
~~~~~
Answer = $\sum$ f[i,0]
**[problem:163B]**
Solution summary: sorting + binary search.
Sample jury solution: [submission:1415306] (author: [user:Burunduk1,2012-03-25])
We need to find the minimal time $T$.
Let us find it using binary search.
Once the time is fixed, one can arrange lemmings using greedy approach
starting either from the top or from the bottom.
In this solution we consider the way to start from the bottom.
Among all lemmings, that can get on the first ledge, l...
The problem could be solved with the following dynamic programming. Let $f[i,
j]$ be the number of
Tutorial of VK Cup 2012 Round 2
Tutorial of VK Cup 2012 Round 2 (Unofficial Div. 2 Edition)
72.
Some Interval DP Problems and State Reduction Hi everyone! Recently I have been solving some classic interval DP problems, and came across some neat problems. Most of these problems have relatively simple recurrence relations, but the straightforward solutions will not pass in complexity, hence requires an observation to reduce the complexity (generally by reducing the number of states by some pre-computation). Most of the problems are from CF, and they already have editorials. But I will still write my own tutorials to illustrate my points.
Prerequisites : Introductory interval DP such as Longest Increasing Subsequence, Longest Common Subsequence.
[problem:1312E]
You are given an array of $a_1,a_2,\dots,a_n$ length $n \ (n \leq 500, 1 \leq a_i \leq 1000).$ You can perform the following operation any number of times:
- Choose a pair of two neighboring equal elements $a_i=a_{i+1}$ (if there is at least one such pair).
- Replace them by one element with value $a_i + 1$.
After each such operation, the length of the arra...
Common Subsequence. [problem:1312E] You are given an array of
$a_1,a_2,\dots,a_n$ length $n \ (n, The reduced problem given as a hint can be trivially solved with dp, the remaining suffix of $t$ as two disjoint subsequences from $s$. So the
problem reduces to, Prerequisites : Introductory interval DP such as Longest Increasing Subsequence
, Longest Common
73.
Rethink the Dijkstra algorithm -- Let's go deeper This is a blog for cp newbies (like me).
For a long time I think the [Dijkstra algorithm (dij)](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) only has two usages:
(1) Calculate the distance between vertices when the weights of edges are non-negative.
(2) (Minimax) Given a path $p = x_1x_2...x_n$, define $f(p) := \max_{i=1}^{n-1}d(x_i, x_{i+1})$. Given source vertex $s$ and target vertex $t$, dij is able to calculate $min \\{f(p)|p\,\text{is a s-t path}\\}$.
However, dij works for a function class, not only the sum/max functions. The sum/max functions are only the two most frequently used members of this function class, but the function class is far larger. Once the function $f$ satisfies several mandatory properties, you could use dij. The word "function class" is like an abstract class in C++:
~~~~~
struct f{
virtual bool induction_property() = 0; //bool: satisfy or not
virtual bool extension_property() = 0; //bool: satisfy or not
virtual bool dp...
during the contest. The problem is: You are given an integer array nums and a
positive integer k, /). I failed to solve it during the contest. The problem is: You are given an
integer array nums and, [ARC150C Path and Subsequence
](https://atcoder.jp/contests/arc150/tasks/arc150_c). Thisproblem is
74.
AI Tech Poorly Prepared Contest (Aritifical Intelligence Generated Problems) We got an AI to generate programming problems, after being trained for hundreds of hours on problem 4A.
(This is what we used to train it: https://colab.research.google.com/drive/1gWn1uN4cULoDnBJTSGqrUxxao5q3xHeI)
We omitted samples, time limits, and memory limits because they don't make much sense.
Here are the funniest results:
------------------
~~~~~
<|title|>
E. Back to the Future
<|time-limit|>
4 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
After escaping from the crashed time machine, Marty McFly was transported to present-time! He landed on the lawn where his damaged car was parked. He was given the coordinates of the car's location x y.
Marty quickly recognized that this car park is located at a distance of 1 meter from the starting position x, and its maximum speed is v. He also noticed that the car's navigation system is malfunctioning. For some inexplicable reason the system tells Marty that the distance between a pair of stationary objects is...
megabytes <|problem-text|> You are given a sequence of integers
a1, a2, ..., an. Your task is to, We got an AI to generate programming problems, after being trained for hundreds
of hours onproblem
75.
Teamscode Spring 2024 Contest Official Editorial Sorry for the long wait. These problems were brought to you by [user:esomer,2024-04-05], [user:danx,2024-04-05], [user:dutin,2024-04-05], [user:jay_jayjay,2024-04-05], [user:oursaco,2024-04-05], [user:superhelen,2024-04-05], [user:thehunterjames,2024-04-05], [user:willy108,2024-04-05], and [user:yash_9a3b,2024-04-05]. Also, massive thanks to [user:omeganot,2024-04-05] for his [unofficial editorial](https://codeforces.me/blog/omeganot) (which was posted a lot sooner than ours).
[Novice A/](https://codeforces.me/gym/105066/problem/A)[Advanced A: It's Time to Submit](https://codeforces.me/gym/105067/problem/A)
==================
<spoiler summary="Solution">
Both "YES" and "NO" are consistent answer (as long as exactly one of them is the answer).
If you print "YES" and get AC, you are getting AC by printing the sample output.
If you print "NO" and get AC, you are getting AC by not printing the sample output.
Never assume just because the carrot is big ... the sample out...
[Novice E/](https://codeforces.me/gym/105066/problem/F)[Advanced C: Unique
Subsequences](https
Tutorial of Teamscode Spring 2024 (Novice Division)
Announcement of Teamscode Spring 2024 (Advanced Division)
76.
Longest Common Subsequence using bit operations? Recently i did Leetcode [Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence/description/) problem. I used the basic dp approach and solved it in 18 ms using 12 mb space. After that i decided to check the fastest solutions for the problem and got this code
<spoiler summary="Fastest LCS code">
~~~~~
class Solution {
public:
int longestCommonSubsequence(string X, string Y) {
if ( X.size() < Y.size() ) swap(X,Y) ;
int m = X.size() , n = Y.size();
if (m == 0 || n == 0) return 0;
int w = (m + 31) >> 5;
std::uint32_t S[256][w];
std::memset(S, 0, sizeof(std::uint32_t) * 256 * w);
std::int32_t set = 1;
for (int i = 0, j = 0; i < m; ++i) {
S[X[i]][j] |= set;
set <<= 1;
if (!set) set++,j++;
}
std::uint32_t L[w];
std::memset(L, 0, sizeof(std::uint32_t) * w);
for (int i = 0; i < n; ++i) {
std::u...
Longest Common Subsequence using bit operations?, -subsequence/description/) problem. I used the basic dp approach and solved it
in 18 ms using 12 mb
77.
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 ...
programming problem: $D[x]$ is equal to the length of a longest suitable
increasingsubsequence
Tutorial of VK Cup 2015 - Finals
Tutorial of VK Cup 2015 - Finals, online mirror
78.
CSES Additional problems tutorial Many thanks to [user:miaowtin,2023-10-01] and [user:FBI,2023-10-01] for their invaluable help and support in the preperation of this blog. Unfortunately, this blog is not currently completed, but we encourage everybody to share their solutions to these and other problems of the section in comments. And last but not least thanks to [user:pllk,2023-10-01] for maintaining CSES.
[Shortest Subsequence](https://cses.fi/problemset/task/1087/)
<spoiler summary="Prerequisites">
Greedy
</spoiler>
<spoiler summary="Tutorial">
Consider the string $s=s_1,\dots,s_n$. Suppose $s_i$ is the first occurence of a letter $c$ (the string looks $s_1,\dots,s_i,\dots,s_n$). If we output $c$, the problem reduces to $s=s_{i+1},\dots,s_n$. The number of such outputs must be minimalized.
Observation: the largest $i$ we choose, the smallest string we obtain.
Greedy solution is always to take the largest $i$ such that $s_i$ is the first occurence. But after this traversal, the string we output is ...
this traversal, the string we output is still a subsequence of $s$, so we need
to output one more, Subsequence](https://cses.fi/problemset/task/1087/) Greedy , The solution to the problem is easy now if one notices that we can iterate over
the strings with, [Shortest Subsequence](https://cses.fi/problemset/task/1087/)
79.
Meet in the Middle (Topic Stream) **Meet in the Middle** lecture & problem-solving starts in an hour https://www.twitch.tv/errichto. See the problem list below. I will later update this blog with codes and written explanations.
UPD, video recording: https://youtu.be/18sJ3mK173s, some codes from the stream: https://ideone.com/1uScID
P1. Knapsack with $n \leq 40$ and values up to $10^9$ https://cses.fi/problemset/task/1628
P2. Given a sequence $a_1, a_2, \ldots, a_n$ ($n \leq 2000$), count increasing subsequences of length 3.
P3. 4-SUM, find four values that sum up to the target value https://cses.fi/problemset/task/1642
P4. Find a string with the standard polynomial hash equal to the target value $X$ modulo $10^9+7$. The hash is computed by converting characters a-z into 0-25 and multiplying every character by the next power of 26. Find a solution without just converting $X$ to base $26$.
P5. You're given a graph: $n \leq 300$, $m \leq n\cdot(n-1)/2$. Count paths made of 5 nodes. Nodes and edges can be...
**Meet in the Middle** lecture & problem-solving starts in an hour
https://www.twitch.tv/errichto
80.
Codeforces Round #162 Tutorial #### [Div2 A
Colorful Stones (Simplified Edition)](http://codeforces.me/problemset/problem/265/A) (Author: [user:rng_58,2013-01-21])
In this problem you just need to implement what is written in the statement. Make a variable that holds the position of Liss, and simulate the instructions one by one.
#### [Div2 B
Roadside Trees (Simplified Edition)](http://codeforces.me/problemset/problem/265/B) (Author: [user:snuke,2013-01-21])
The optimal path of Liss is as follows: First she starts from the root of tree 1. Walk up the tree to the top and eat a nut. Walk down to the height $min(h_1, h_2)$. Jump to the tree 2. Walk up the tree to the top and eat a nut. Walk down to the height $min(h_2, h_3)$, $\cdots$ and so on.
#### [Div1 A / Div2 C Escape from Stones](http://codeforces.me/problemset/problem/264/A) (Author: [user:DEGwer,2013-01-21])
In this problem, there are many simple algorithms which works in $O(n)$.
One of them (which I intended) is following:
You should...
#### [Div2 A Colorful Stones (Simplified
Edition)](http://codeforces.me/problemset/problem/265/A
Tutorial of Codeforces Round 162 (Div. 2)
81.
Topics Problems Good Day to you!
While a lot of us, when he begins to start competitive programming he found difficult to found problems on some topics in the beginning to practice of it, and same thing for a lot of ICPC Communites that they have started.
These are some topic not advanced and videos, problems and articles on them.
<br>
<spoiler summary="Prefix Sum & Frequency Array">
[Wonderful Coloring](https://codeforces.me/contest/1551/problem/B1)
[Do Not Be Distracted](https://codeforces.me/contest/1520/problem/A)
[Letter](https://codeforces.me/problemset/problem/43/B)
[Pangram](https://codeforces.me/problemset/problem/520/A)
[Andryusha and Socks](https://codeforces.me/contest/782/problem/A)
[Count Numbers](https://codeforces.me/group/c3FDl9EUi9/contest/262795/problem/A)
[Count Characters](https://codeforces.me/group/c3FDl9EUi9/contest/262795/problem/B)
[Range Sum Query](https://codeforces.me/group/c3FDl9EUi9/contest/262795/problem/E)
[Count a's](https...
://codeforces.com/problemset/problem/977/F">Consecutive Subsequence
* , [Is B a subsequence of A
?](https://codeforces.me/group/MWSDmqGsZm/contest/219774/problem/U), subsequence of A ?](https://codeforces.me/group/MWSDmqGsZm/contest/219774/
problem/U) [Blanced
82.
Unofficial Editorial — Dilhan's Computing Contest 1 [Partial, P1~4 + P5S1] Contest hosted on DMOJ [https://dmoj.ca/contest/dcc1](https://dmoj.ca/contest/dcc1)
### [P1 — The Cathedral of Learning](https://dmoj.ca/problem/dcc1p1)
<spoiler>
If $a > b$, the answer is `NO`, as Alice always goes up and Bob always goes down. Otherwise, $a \leq b$, and the answer is `YES` if and only if the parity (oddness or evenness) of $a$ and $b$ is equal (equivalently, that $b - a$ is even). This is because the difference between them reduces by $2$ each step, and if the difference is odd, they'll end up on neighboring floors and then pass and miss each other on the next step.
Time complexity: $O(1)$
</spoiler>
### [P2 — Square Sum](https://dmoj.ca/problem/dcc1p2)
<spoiler>
Assume that $A \leq B$ (otherwise, swap them). Now let's count the valid pairs $(a, b)$ where $a + b = c^2$ for some non-negative integer $c$.
Let's also define a useful function $\displaystyle P(n) = \sum_{i = 1}^{n} i^2 = \frac {n(n+1)(2n+1)} {6}$, representing the sum of th...
[longest increasing subsequence problem](https://cp-algorithms.com/sequences
83.
Codeforces Round 915 (Div. 2) Editorial [A — Constructive Problems](https://codeforces.me/contest/1905/problem/A)
=====
Author: [user:valeriu,2023-12-16]
<spoiler summary="Solution">
We can observe an invariant given by the problem is that every time we apply adjacent aid on any state of the matrix, the sets of rows that have at least one rebuilt city, respectively the sets of columns that appear that have at least one rebuilt city remain constant. Therefore, if we want to have a full matrix as consequence of applying adjacent aid multiple times, both of these sets must contain all rows/columns. As such, the answer is bounded by $max(n, m)$.
We can tighten this bound by finding an example which always satisfies the statement. If we take, without loss of generality, $n \le m$, the following initial setting will satisfy the statement: $(1, 1), (2, 2), (3, 3), ..., (n, n), (n, n + 1), (n, n + 2), .. (n, m)$
<spoiler summary="Author's Note">
I have proposed this div2A at 3 contests and after 1 year of waiti...
[C — Largest Subsequence](https://codeforces.me/contest/1905/problem/C) =====
Tutorial of Codeforces Round 915 (Div. 2)
84.
Topic Stream: Dynamic Programming #2 Hi,
As always, we have topic streams on Fridays from 12-14 GMT. Today was the second topic stream on Dynamic Programming. Here are the topics covered in this livestream:
1. The idea of updating dp in two directions ([Sending a Sequence Over the Network](https://codeforces.me/problemset/problem/1741/E))
2. Keeping our states for matching subsequences ([Easy Problem](https://codeforces.me/problemset/problem/1096/D))
3. Importance of ordering in updating DP ([Gargari and Permutations](https://codeforces.me/problemset/problem/463/D))
4. Keeping max values to optimize DP ([Choosing Balls](https://codeforces.me/problemset/problem/264/C))
5. Memory optimization and moving in two directions ([Pigs and Palindromes](https://codeforces.me/problemset/problem/570/E))
I will write the highlights of the livestream here, embedding specific parts of the videos so you can easily watch the sections you’re interested in. You can ask questions about any part here, on YouTube, or in our T...
/problem/1741/E)) 2. Keeping our states for matching subsequences ([Easy Problem
](https://codeforces.com, ://codeforces.com/problemset/problem/1741/E)) 2. Keeping our states for
matching subsequences ([EasyProblem, In this problem, we want to remove certain characters to ensure that the string
"hard" does not
85.
Alternative Solution to 2077C Using Probability Hello, Codeforces community! Today, I want to share my solution to a problem from recent contest: [Binary Subsequence Value Sum](https://codeforces.me/contest/2077/problem/C). Rather than using polynomials and FFT, I tried
to approach this problem from a different viewpoint — probability! Now, let's get started with the solution itself.
---
## 1. Deterministic definition of the score
Suppose you have a binary string $v$ of length $m$. Interpret each character as a “contribution”: assign $+1$ for a ‘1’ and $-1$ for a ‘0’. Define
$$
d = \text{(number of 1's)} - \text{(number of 0's)}
$$
so that $d$ is the overall “imbalance” of $v$.
The score of $v$ is defined as
$$
\text{score}(v) = \max_{1 \le i < m} \Bigl( F(v,1,i) \cdot F(v,i+1, m) \Bigr),
$$
where $F(v,1,i)$ is imbalance of prefix and $F(v,i+1,m)$ is imbalance of suffix; if the prefix imbalance is $S$, then the suffix is $d-S$, and the product is
$$
P(S) = S\cdot (d-S).
$$
For fixed $d$, th...
: [Binary Subsequence Value Sum](https://codeforces.me/contest/2077/problem
/C). Rather than using
86.
Codeforces Round #165 Tutorial ### [problem:270A,Div II A — Fancy Fence]
#### Problem
The problem is to tell whether there exists a regular polygon with angle equal to $a$.
#### Solution
Consider all supplementary angles of the regular $n$-polygon with angle $a$, which are equal to $180^\circ-a$. Their sum is equal to $360^\circ$, because the polygon is convex. Then the following equality holds: $n\cdot(180-a) = 360$, which means that there is an answer if and only if $360\mod(180-a) \equiv 0$.
Time: $O(t)$.
Memory: $O(1)$.
Implementation: [C++](http://ideone.com/xnq9Iu), [Java](http://ideone.com/D2hHEL)
#### Comments
The problem can be also solved by rotating vector $(1,0)$ by angle $180^\circ-a$ until it returns in this position (but at most 360 times), and checking that only one full turn has been made (implementation example: C++).
It is also a rare problem on Codeforces that contains just 1 sample test, 1 pretest and 1 full test.
### [proble...
In this problem it was enough to implement a quadratic solution. We count
$dp[i][j]$ — the
87.
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...
problem is known as the all-substrings longest common subsequence (ALCS) problem
.
88.
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 — 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 — 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 =...
### [663295B — Palindromic Subsequence](https://codeforces.com, ### [663295B — Palindromic Subsequence](https://codeforces.me/contests/663295/
problem/B)
89.
TheForces Rounds Editorials Here's the editorials of [TheForces Rounds](https://t.me/TheForcesOfficial):
<spoiler summary="Round 1">
<spoiler summary="Problem A">
For a number $x$, as long as $2\le x$, it can be squared to any large number. For $0$ and $1$, the square of both numbers is equal to themselves. So just compare $0$ and $1$.
<spoiler summary="Code">
~~~
void elysia() {
cin >> n;
bool flag=true;
for(int i=1;i<=n;++i) {
cin >> a[i];
a[i]=min(a[i],2ll);
if(i!=1&&a[i]<a[i-1]) flag=false;
}
if(flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
~~~
</spoiler>
</spoiler>
<spoiler summary="Problem B">
Consider the number of times each $a_i$ is XOR in the answer. for $a_i$, calculated $i(n-i+1)$ times in the answer. Two same XOR will disappear, so checking is this an odd number then done.
<spoiler summary="Code">
~~~
void elysia() {
int answer=0;
cin >> n;
for(int i=1;i<=n;++i) {
cin >> a[i];
...
For good subarrays, just use two-pointer to solve it, while for good
Tutorial of TheForces Round #10 (TEN-Forces)
Tutorial of TheForces Round #14 (Cool-Forces)
Tutorial of TheForces Round #17 (AOE-Forces)
90.
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...
A. Next Test <http://codeforces.me/contest/27/<B>problem</B>/A>
, C. Unordered <http://codeforces.me/contest/27/<B>problem</B>/C>
91.
Counting using symmetry of expectations Hello Codeforces! Today I want to share some thoughts on the magic of symmetry and linearity of expectation. We have all encountered counting problems that seem completely impossible to calculate directly. But there is a beautiful trick: if we use symmetry to convert a pure counting problem into an expected value problem, we unlock the ability to bypass massive formulas and solve the problem elegantly.
Before we begin, make sure you are familiar with the basics of:
**Expected values (Obviously)**
**Indicator variables:** An indicator variable is a simple binary variable that equals 1 if a specific event occurs, and 0 if it does not. The most useful property of an indicator variable is that its expected value is exactly equal to the probability of the event happening ($E[I] = P(I=1)$). This makes them the perfect atomic building blocks for counting complex occurrences.
**Linearity of expectation:** the expected value of a sum of random variables is always equal to the sum o...
#### [problem:1426F] In a nutshell, you are given a string $s$ of length $n$
consisting of
92.
Characteristics of the optimal solution, a technique for finding observations in a problem Introduction
------------------
Some of you smart people out there may find the contents of this blog so obvious, that it does not deserve to be called a "technique." It is just the totally normal thought process that comes across our minds when we try to solve a problem!
However, I often find it useful (and others may relate) to state my thoughts explicitly when trying to conquer a problem, whether I write it down on a sheet of paper, comment it in my code, or just talk out loud like a crazy guy :D.
I observe that one of the things that makes a problem-solver better than another (other than practice and knowledge about certain topics/algorithms, of course) is the way of thinking and approaching a problem. So, to make myself a better problem-solver, I sometimes go about thinking about how I think and try to improve this way of thinking generically and generally about any problem. It is, to many great problem-solvers, one of the byproducts of practicing problems a lot that develo...
Characteristics of the optimal solution, a technique for finding observations
in aproblem, the requirements (e.g. if a subsequence has a minimum * something *, can I
reduce the number of, thought process that comes across our minds when we try to solve a problem!
However, I often find, . find a subsequence that has minimum * something * or find a graph of an array
that satisfies some
93.
Problems that I authored so far Hi everyone!
Today I saw a discussion in AC Discord server about how many problems some people made for different competitions. It was sparkled by [this](https://codeforces.me/blog/entry/108595) CF entry. I haven't keep track of this before, so it made me curious to go through everything that I made and publish in a comprehensive list. I'm doing it mostly out of curiosity, but maybe it might be interesting for someone else too :)
[cut]<br>
| # | Date | Problem | Contest | Comment |
|-|-|-|-|
| 1 | Jan 2016 | [Sasha and Swaps](https://www.hackerrank.com/contests/infinitum14/challenges/sasha-and-swaps/problem) | Ad Infinitum 14 | Find a $T$-th root of a given permutation, while minimizing the number of swaps in which the root may be decomposed. |
| 2 | Aug 2015 | [Sasha and swag strings](https://acm.timus.ru/problem.aspx?space=1&num=1799) | Ptz Summer 2015. MIPT Contest | Compute the total number of distinct substrings on all edges of a given string's suffix tree. |
| 3 | ...
be interesting for someone else too :) [cut]
| # | Date | Problem | Contest | Comment, | # | Date | Problem | Contest | Comment | |-|-|-|-| | 1 | Jan 2016 | [Sasha
and Swaps](https
94.
Weekly Training Farm #14 Editorial Thanks [user:drazil,2016-12-03] to translate the [Chinese editorial](http://dreamoon4.blogspot.tw/2016/11/14.html) to English.
Two of the problems in this week are created by modifying input constraints of recent Atcoder problems. The other three are a series of problems. Thus, in this editorial we won't follow the order of the problems but begin with the problems which are modified from Atcoder problems and put the series problems to the last.
### [Problem B — Write a Special Judge!](http://codeforces.me/group/gRkn7bDfsN/contest/210166/problem/B)
This problem is modified from [AGC007 — Shik and Stone](http://agc007.contest.atcoder.jp/tasks/agc007_a), which is originally created by Dreamoon as well. The difference in the Atcoder version is that the input must be a valid path (starting at the top left corner and ending at the bottom right corner). In fact, this modified version is the very first version proposed. But the contest organizers at Atcoder think this (mo...
Atcoder problems and put the series problems to the last. ### [Problem B —
Write a Special Judge, At this point, the problem is identical to find the longest continuous good
subsequence. We can
95.
Codeforces Round #715 Editorial <strike>Note: I can't figure out how to place the tutorials inside spoilers. If someone is familiar with how CF spoilers work and can help I would really appreciate it. For now, be warned that the tutorials are visible by default (but everything else isn't)</strike>
**UPD:** I figured out how to use spoilers! Also added implementations for all problems.
Thanks for participating in our contest!
[problem:1509A]
Author: [user:Kuroni,2021-04-13]
<br>
First solve: [user:cfg0d,2021-04-16] at 00:01:02
<spoiler summary = "Hint">
How can you write the condition that $\frac{a_u + a_v}{2}$ is an integer in a more useful way? Think of the parities.
</spoiler>
<spoiler summary = "Tutorial">
[tutorial:1509A]
</spoiler>
<spoiler summary = "Comments from the authors">
</spoiler>
[Implementation](https://codeforces.me/contest/1509/submission/113263196)
[problem:1509B]
Author: [user:Ari,2021-04-13]
<br>
First solve: [user:bl...
contest! [problem:1509A] Author: [user:Kuroni,2021-04-13]
First solve: [user:cfg0d,2021-04
Tutorial of Codeforces Round 715 (Div. 1)
Tutorial of Codeforces Round 715 (Div. 2)
96.
Educational Codeforces Round 9 Challenge Overview. 632A — Grandma Laura and Apples
-------------------------------
There were no successful challenges for this problem. Thumbs up to everyone! I did find a couple of C/C++ solutions with uninitialized local variables though. Fortunately for them, the top of the stack is filled with zeros in the current testing system and compiler didn't decide to place uninitialized local variables in the register.
632B — Alice, Bob, Two Teams
----------------------------
There was quite a variety of off-by-one errors in this problem. My most successful test was
~~~~~
2
1 1
BB
~~~~~
Some solutions just have to flip something. The were also 2 challenges where solution got TL due to slow input.
The most crazy uninitialized variable prize for this problem goes to [submission:16447719]:
~~~~~
ll n;
v b(n);
cin >> n;
forn(i, n)
{
cin >> b[i];
}
~~~~~
What is the size of vector `b`? Definitely not `n`. Fortunately for the author, it can't be challenged. Und...
632D — Longest Subsequence -------------------------- Most challenges in this
problem used
97.
Another solution for Div.4 problem 1003H (Extended) Hello Сodeforces,
-----------------
Recently the [Div. 4 round](https://codeforces.me/contest/2065) was held with quite balanced and beautiful problems. I especially liked [Problem H](https://codeforces.me/contest/2065/problem/H), where I accidentally _overkilled_ the solution. I want to share with you a solution I came up with that supports **range queries** in $O(n + q \log n)$.
### 1. Some observations
Firstly, one should notice that value of $f(b)$ equals to ( number of $i$ : $b_{i} \neq b_{i+1}$ for $(1 \leq i < |b|)$ ) $+$ $1$. For **binary** strings, that means $f(b) = (\text{number of "10"}) + (\text{number of "01"}) + 1$.
Secondly, when there are update-queries mentioned in the problem, one should consider using some **data structures**.
### 2. Main idea
Suppose we have two binary strings $L$ and $R$ and we know the answer for each of them. Now our goal is to figure out how we can combine them to get the answer for the full string.
#### **All** subseque...
Another solution for Div.4 problem 1003H (Extended), #### **All** subsequences can be represented as follows: 1. Subsequence
**starts** with "0" and, /2065) was held with quite balanced and beautiful problems. I especially liked [
Problem H](https, The contribution of each subsequence from the $L$ is $S_{L} \cdot C_{R}$ and
vice versa. Note that
98.
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 ...
If all elements and $X$ are positive, we can use a greedy approach to solve the
problem optimally, Subsequence problem). Let $dp[i]$ denote the length of the longest **valid**
subsequence ending at, We can apply a dynamic programming solution (Similar to the Longest Increasing
Subsequence problem
99.
Weird sorts #1 — LIS sort I like sorting algorithms very much, and I usually come up with weird ideas for sorting. Sometimes I wonder would those work properly, and now when I finally have the time from social distancing, I decided to start a series on my eccentric ideas — Weird sorts.
As an introductory problem for Dynamic Programming, you all probably know about the Longest Increasing Subsequence problem (LIS). But what if we apply this… to sorting? Today in the first blog of the Weird sorts series, I introduce to you… the LIS sort.
#### **Basic idea**
The core idea is to extract the LIS from the current array and repeat it until the current array is empty. It can be shown that this process always terminates, because there will always be a LIS that have a size of at least 1, thus at each pass, we will always take at least 1 element away from the array. In the implementation, we will first find the LIS of the array and separate the LIS from the rest of the array. We will then recursively perfo...
Increasing Subsequence problem (LIS). But what if we apply this… to sorting?
Today in the first blog of the, for Dynamic Programming, you all probably know about the Longest Increasing
Subsequence problem (LIS
100.
Codeforces Round #127 — editorial #### Problem A(div 2) --- LLPS
It's assumed that this problem can be solved just looking at the samples and without reading the statement itself :)
Let's find the letter in the given string which comes last in the alphabet, denote this letter by $z$.
If this letter occurs $p$ times in the given string, then the answer is string $a$ consisting of letter $z$
repeated $p$ times.
Why is it so? Using the definition of lexicographical comparison and the fact that $z$ is the largest letter in
the string it's easy to understand that if some other subsequence $b$ of the given string is lexicographically larger
than $a$, then string $b$ should be longer than $a$ and, moreover, $a$ should be a prefix of $b$ (that is, $b$ should
start with $a$). But string $b$ must be a palindrome, therefore its last letter must be $z$. In this case string $b$
must contain more occurrences of letter $z$ than the original string $s$ does, which is impossible as $b$ is
a subsequence of $s$.
Beside...
of inversions to the moment if among the first $j$ words of the archive problem
we've found a, Besides that, the constraint on the length of the string was very low, so the
problem could be, The constraints in this problem were so low that a solution with complexity
$O(m\cdotk^n)$ was just
101.
[Tutorial] Divide and Conquer Offline Query — A Niche Way to solve Static Range Query <br> Hi guys, this is my first blog on Codeforces. So if there were any mistakes or suggestions, feel free to correct me down in the comment section. Anyway, I discovered a nice way to solve static range query problems using "Divide and conquer", and I'm eager to share it with you guys.
<p> Pre-requisites:
<br> • Prefix Sum.
<h2>Problem 1:</h2>
Given an array $A$ of $N (N \leq 10^{5})$ integers, your task is to answer $q (q \leq 10^{5})$ queries in the form: what is the minimum value in the range $[l, r]$?
<p>For now, let's forget about Segment Tree, Square Decomposition, Sparse Table and such. There's a simple way to solve this problem without any use of these fancy data structure.
<p> First, let's start with $L_{0} = 1$, $R_{0} = n$, and $M_{0} = \left\lfloor { \frac{L_{0} + R_{0}}{2} } \right\rfloor$. Let's just assume that every query satisfy $L_{0} \leq l \leq M_{0} < r \leq R_{0}$. We maintain two prefix sum arrays:
<br> • $X[i] = min(A[i], A[i+1], ..., A[M_{0...
Related problem:
Vietnamese problems:
• [MofK Cup Round 1 — E: Xor Shift
102.
[Tutorial] Using Complex Numbers for Grid Movement Problems Problems involving movement on a grid can be solved using tuples/pairs of the form (x, y). However, doing addition/subtraction of pairs/tuples is not supported by default. One alternative to this is using complex numbers.
Using complex numbers for geometry is not a new idea. You can read more about it in this [blog](https://codeforces.me/blog/entry/22175).
I will not go into the more "geometric" side of things. My aim here is to make you guys feel comfortable with using complex numbers instead of pair/tuples in grid-related problems.
I code in Python and for the better understanding of readers, I used AI to convert those codes to C++. We have to keep few things in mind when using std::complex in C++. Certain methods such as std::polar() and std::abs() don't work when you use complex with integral data types (int, long long etc.). They only work with FP datatypes (float, double, long double etc.). You can still use std::complex with integral datatypes if the use case is limited...
— Robot Sequence](https://codeforces.me/contest/626/problem/A) This problem
asks how many, This problem asks how many contiguous command subsequences bring the robot back
to its starting
103.
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...
[Problem'] Given a string $s$ and an integer $n$, find the number of the
palindromes of length $|s
104.
Unofficial Editorial for Educational Codeforces Round 97 [中文题解](https://cp-wiki.vercel.app/tutorial/codeforces/1437/)
### [problem:1437A]
<spoiler summary="Hint">
What will happen if $r\geq2l$?
</spoiler>
<spoiler summary="Solution">
Suppose that $r\geq2l$, then at least we need to cover $[l,2l]$. Obviously, we must have $a>l$, since the length of the segment is already longer than $l$. Now if $l<a\leq2l$, there are at most $l$ modules of $a$ which are no less than $\frac{a}{2}$, which cannot cover the segment whose length is $l+1$. But if $a>2l$, then $l$ cannot be a good value.
On the contrary, if $r<2l$, we can always choose $a=2l$ which will be a valid answer.
So this problem can be simplified to judging whether $r<2l$ holds.
Time complexity is $O(1)$.
</spoiler>
<spoiler summary="Code (Python 3)">
~~~~~
def read_int():
return int(input())
def read_ints():
return map(int, input().split(' '))
t = read_int()
for case_num in range(t):
l, r = read_ints()
print('YES' if l * 2 > r els...
the original problem will be split into several subtasks. 2. For each subtask,
we actually need to, , we need to find the longest increasing subsequence. However, there are two
differences compared to
105.
Codeforces Round 1108 (Div. 2) Editorial We hope you enjoyed the contest as much as we enjoyed writing it! Thank you especially to [user:PCTprobability,2026-07-12] [for](https://codeforces.me/contest/2246/submission/382271865) [your](https://codeforces.me/contest/2246/submission/382275385) [very](https://codeforces.me/contest/2246/submission/382277166) [entertaining](https://codeforces.me/contest/2246/submission/382278076) [submissions](https://codeforces.me/contest/2246/submission/382279367) [to](https://codeforces.me/contest/2246/submission/382283699) [problem](https://codeforces.me/contest/2246/submission/382285777) [E](https://codeforces.me/contest/2246/submission/382287709).
<spoiler summary="Rating predictions">
</spoiler>
[problem:2246A]
<spoiler summary="Hint 1">
Try to eliminate a large class of possible sums.
</spoiler>
<spoiler summary="Hint 2">
Think about parity. Is it possible to eliminate all odd numbers?
</spo...
/2246/submission/382283699) [problem
](https://codeforces.me/contest/2246/submission/382285777) [E, First, let's solve the problem for only positive integers (i.e. $1 \leq a_i
\leq 10^9$). For a, Now we consider the full problem, with $a_i$ possibly equal to $-1.$ In this
case there exist
Tutorial of Codeforces Round 1108 (Div. 2)
106.
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...
The problem then becomes iterating through the subsequences of the vector in
lexicographical order
Tutorial of VII UnBalloon Contest Mirror
107.
Thanks for participating in JUST ACM HALF EXTREME The [contest](https://codeforces.me/group/CDy0my6omC/contests) is over! Everyone did a great job!! <br/>
We want to thank the first 5 places for their more than wonderful efforts:
1- [user:Hosen_ba,2024-10-5], [user:EyadBT,2024-10-5], and [user:JaberSH1,2024-10-5].
2- [user:BluoCaroot,2024-10-5], [user:M0N,2024-10-5], and [user:Moataz_Muhammed,2024-10-5].
3- [user:Islam_Imad,2024-10-5], [user:Mr_Turtle_,2024-10-5], and [user:7oSkaaa,2024-10-5].
4- [user:ahmedalaa22,2024-10-5], [user:MUZAN,2024-10-5], and [user:detective...dots,2024-10-5].
5- [user:Eslam_Saleh,2024-10-5], [user:Mohamed_M.M.R,2024-10-5], and [user:EslamSamy2002,2024-10-5].
And for everyone who participated in the contest, please vote in the Feedback box for every problem, Thank you.
---------
[A. Nuclear Experiment] (https://codeforces.me/group/CDy0my6omC/contest/553288/problem/A)
Problem setter: [user:hmsh,2024-10-5] <br/>
<spoiler summary="Feedback">
- Very good [likes:A,option1...
[O. Subsequence Construction]
(https://codeforces.me/group/CDy0my6omC/contest/553288/problem/O)
108.
CSES Construction Problems Editorial As of Feb 26, 2026. I am not aware of an editorial on this section. So I decided to write it here.
If you see any mistake or have an alternative solution, I'd be glad if you tell me in the comments.
Notes (2026-02-26):
1. The codes given are my AC codes on CSES. They are written at very different times. Therefore, you might expect some jumps in coding style among the solutions.
2. I am not good at implementing. Sometimes I make solutions harder to understand in exchange for them being easier to implement. If you can't understand the solution, feel free to ask.
3. I haven't been able to AC Grid Path Construction yet. I do have a solution in mind though. (Therefore the solution is not checked by AC, if you find any mistake please tell me).
[Inverse Inversions](https://cses.fi/problemset/task/2214/)
------------------
<spoiler summary="Hint 1">
How do you construct an array with one inversions? How about three? How about six?
</spoiler>
<spoiler summary="Hint 2"...
109.
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.**
**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 ...
Consider another problem: given two words, find the length of their longest
commonsubsequence. For, For example, longest increasing subsequence problem DP solution can be
accelerated to O(N log(N, The second example is longest common subsequence problem. It is of
maximization-type, so we have to, To solve the problem we introduce the set of subproblems: given a prefix of the
first word and a
110.
Problems involving Bracket Sequences. Please suggest some. I've a fear of bracket sequence. Whenever I face one, It scares me. So, I'm gonna solve as many as possible.
I was trying to make a list of problems which contains dealing with "Bracket Sequences".
Here are some. Please suggest some if you've solved any.
It'll be so kind if you comment the topic with the problem.
Thank You in advance.
Happy Coding O_o.
[Reading Material CP-Algorithm ](https://cp-algorithms.com/combinatorics/bracket_sequences.html)
[Online Judge — Parentheses Balance ](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=614) ( Stack )
[Codechef — Convert the Expression ](https://www.codechef.com/problems/CDM01)( Infix / Postfix / Prefix conversion )
[Online Judge — Equation ](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=668) ( Infix / Postfix / Prefix conversion )
[Codeforces — Sereja and Brackets](https://codeforces....
/problemset/problem/1023/C) [Codeforces — Bracket Subsequence
](https://codeforces.com, [Codeforces — Bracket Subsequence ](https://codeforces.me/problemset/problem
/1023/C)
111.
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
=...
To solve this problem, we sort the pairs by the first value, then we only need
thesubsequence to
112.
Editorial of ICPC de Tryst 2026 I hope you enjoyed the contest!
[Contest link](https://codeforces.me/contestInvitation/f8ab858a73f3627f85787c828e7ba84d12495ce9)
<spoiler summary="Rating Predictions and Tags for the Problem">
| Problem | Expected Rating | Tags|
| :---: | :---: | :---: |
| [A. Game is Game](https://codeforces.me/gym/675631/problem/A) | 1500 | games, math |
| [B. Hakurei Shrine's Purification Ritual](https://codeforces.me/gym/675631/problem/B)| 1600 |number theory, binary search|
| [C. Permutation Game](https://codeforces.me/gym/675631/problem/C) | 2600 | dp, greedy, implementation,brute force |
| [D. Path Blow-up?](https://codeforces.me/gym/675631/problem/D) | 2400|bitmasks, trees, dp, combinatorics, implementation|
| [E. Coffee Date of MEX](https://codeforces.me/gym/675631/problem/E)|2100|constructive algorithms, brute force|
| [F. Wordleforces](https://codeforces.me/gym/675631/problem/F) |1800 |math, combinatorics|
| [G. Adaptive Guessing](https://codeforces.me/gym/675631/probl...
Instead of evaluating each transmission individually, we can reframe the problem
using **double
113.
Invitation to CodeChef October Lunchtime 2020 We invite you to participate in the [CodeChef October Lunchtime](http://bit.ly/LTIME89-Codeforces) — the 3-hour contest which offers 5 challenging problems to be solved, next Saturday, October 31st, [19:30 to 22:30 IST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=October+Lunchtime+2020&iso=20201031T1930&p1=44&ah=3).
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's
contests, you can share them [here](https://www.codechef.com/problemsetting/new-ideas).
The members of the problem setting panel are:
- Setter: Mohammed [user:mohammedehab2002,2020-10-23] Ehab
- Tester: Ramazan [user:Kamfucius,2020-10-23] Rakhmatullin
- Statement Verifier: Jakub [user:Xellos,2020-10-23] Safin
- Editorialist: Ishmeet Singh [user:Psychik,2020-10-23] Saggu
- Video Editorialists: Chirayu [user:chirayu,2020-10-23] Jain, Prachi [user:agarwal19,2020-10-23] Agarwal, Darshan [user:darshancool25,2020-10-23] Lokhande,...
The problem asks for the number of distinct subsequence sums of $[l,l+1, problem asks for the number of distinct subsequence sums of $[l,l+1,\ldots,r]$.
Let's fix the number
114.
All-Ukrainian School Olympiad in Informatics: editorial (A,B,C,D,E,F) <p></p><div>The editorial is now completed.</div><div><br></div><div><div><b>Problem A: Gift (Roman Iedemskyi)</b></div><div><br></div><div>Suppose that the pair $(A,B)$ is an optimal solution, where $A$ is the number of gold coins in a gift and $B$ is a number of silver coins. It is easy to see that there exist two (probably equal) indexes $i$ and $j$ such that $g_i=A$ and $s_j=B$. It is true, because in the other case we could decrease either $A$ or $B$ without changing connectivity of the graph.</div><div><br></div><div>Let $R(A,B)$ be the graph in which for all $i$ the following statement holds: $g_i \leq A \wedge s_i \leq B$.</div><div><br></div><div>Let $T(A)$ be the weighted graph in which for all edges $g_i \leq A$. For each edge $i$ we will assign a weight equal to $s_i$. Let's find a spanning tree of this graph, which has the property that its maximal edge is minimal possible. It can be shown that for the fixed $A$ the minimal value of $B$ for which graph $R(A,B)$ is st...
$q$. The second subproblem of our problem can be solved by finding a longest
increasingsubsequence
Tutorial of All-Ukrainian School Olympiad in Informatics
115.
The solution to the problem #172-div1-D Sorry for my poor English :) This is the online version.
Problem D. k-Maximum Subsequence Sum
**Brief Description**
Giving a number sequence ${A_i}$, in this sequence you need to implement the following two operations:
1. **0 x v**: Change $A_x$ to $v$.
2. **1 l r k**: Query the **k-MSS** in $[l,\,r]$.
**Analysis**
Consider the static problem, Apparently, we can use a dynamic programming to solve it.
1. $f_0[i][j]$: the **j-MSS** in [0, i].
2. $f_1[i][j]$: the **quasi-j-MSS** in [0, i], which the item ${A_i}$ must be selected.
The state transition is enumerating whether the $i$th element is selected or not. That's easy for a clever guy such as you. So the \textit{brute-force} method is doing a dynamic programming for each query. The operation **Modify** takes $O(1)$ time, and **Query** takes $O(nk)$ . It's too slow to get Accepted.
A simple optimization is using a data structure to speed up **Query**. The segment tree can be OK. In every node, we store su...
The solution to the problem #172-div1-D, Problem D. k-Maximum Subsequence Sum
116.
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...
that perfect square, and the problem won't change. Let's define normalizing a
number as dividing it, ### [problem:1325A] $a=1$ and $b=x-1$ always work. Code link:
https://pastebin.com/ddHKD09B
Tutorial of Codeforces Round 628 (Div. 2)
117.
Codeforces Round #187 tutorial [problem:315A]
Just check for each bottle, can I open it with another. In this task can pass absolutely any solutions.
[problem:315B]
We will support all of the elements in the array, but also we will supprt additionally variable add: how much to add to all the elements. Then to add some value to every element we simply increase the add. In the derivation we deduce the value of the array element + add. When you update the item we put to a value, value that you need to put minus the current value of add.
[problem:314A]
Note that if we remove some of the participants, we never remove the participants with lower numbers as theirs amount will only increase. So just consider the sequence of all the participants, and if the participant does not fit we delete him.
[problem:314B]
It is clear that we can use greedy algorithm to look for the number of occurrences of the 2nd string in the first string, but it works too slow. To speed up the process, you can look at the ...
[problem:314C] It is clear that we need to calculate the sum of the products of
elements of all, [problem:315A] Just check for each bottle, can I open it with another. In this
task can pass
Tutorial of Codeforces Round 187 (Div. 1)
Tutorial of Codeforces Round 187 (Div. 2)
118.
Editorial of TheForces Round #13 Hello Codeforces!
Thanks for participating in [the round](https://codeforces.me/contestInvitation/6f589939fd095f0f82a175a52d83611a2ddd49d0), We hope you liked the problems!
Also huge thanks to [user:Endlessdreams,2023-05-07] for preparing the editorial.
<spoiler summary="Round 13">
<spoiler summary="Problem A">
Calculate the units first, and then calculate the value according to the units
<spoiler summary="Code">
~~~
void elysia() {
int n;cin >> n;
if(n<1024ll) cout << n << "B" << endl; else
if(n<1024ll*1024ll) cout << n/1024ll << "KiB" << endl; else
if(n<1024ll*1024ll*1024ll) cout << n/1024ll/1024ll << "MiB" << endl; else
if(n<1024ll*1024ll*1024ll*1024ll) cout << n/1024ll/1024ll/1024ll << "GiB" << endl;
}
~~~
</spoiler>
</spoiler>
<spoiler summary="Problem B">
You can compute this with fast powers, or you can compute whether n is odd or even.
<spoiler summary="Code">
~~~
void elysia() {
int n,m;
cin >> n >> m;
cout << power...
Obviously, the answer is equal to the longest common subsequence of
Tutorial of TheForces Round #13 (Boombastic-Forces)
119.
An intuitive alternative solution to a hard problem I recently came across a beautiful problem from the Romanian national olympiad from 2005. It has a beautiful intended solution but i will provide another you might have tried if you couldn't find it.
A sequence is called circular if its elements consist of only 'A' and 'B', it has size n (n >= 1) and the element next to the last is considered to be the first. A consequence of such a sequence is that there are precisely n contiguous subsequences (from now on whenever we mention subsequence we mean a contigous one) of any size, for example for "ABBA" the 4 subsequences of size 3 are in order "ABB", "BBA", "BAA", "AAB".
A sequence is called special if it satisfies the property of the circular sequence defined above and furthermore ANY two subsequences of equal size differ in the number of characters 'A' by at most 1. For example "AABB" is not special because there exist "AA" and "BB", "ABABAABAAB" is not special either because of "AABAA" and "BABAB", but "ABA" and "AABABAAB" satis...
An intuitive alternative solution to a hard problem, across the subsequence, meaning the spaces between consecutive 'B's must not
differ by much. Thus, that there are precisely n contiguous subsequences (from now on whenever we
mentionsubsequence we, I recently came across a beautiful problem from the Romanian national olympiad
from 2005. It has a
120.
Help Needed with Problem D — Longest Max Min Subsequence (Codeforces Round 967 Div. 2) Hi everyone,
I'm currently working on Problem D : Longest Max Min Subsequence from Codeforces Round 967 (Div. 2). You can find the problem here (https://codeforces.me/contest/2001/problem/D?mobile=true ).
I've been stuck with a "Wrong Answer" on test 5. You can check out my submission here (https://codeforces.me/contest/2001/submission/277865632).
The checker log says that the 18714th number is different than expected, with my code outputting '95' instead of the expected '140'.
My approach :-
The solution to this problem involves several steps:
Unique Element Collection:
The first step is to identify unique elements in the array. This is done using a set sty and a stack st. The stack st is used to store indices of unique elements in reverse order (from the end of the array to the beginning). The stack is used because when constructing the subsequence, we need to process elements in reverse to preserve the lexicographical order when needed.
Two-Pointer Tec...
Help Needed with Problem D — Longest Max Min Subsequence (Codeforces Round 967
Div. 2), array to the beginning). The stack is used because when constructing the
subsequence, we need to, faced a similar problem or could provide insight into what I might be missing?, Hi everyone, I'm currently working on Problem D : Longest Max Min Subsequence
from Codeforces, I'm currently working on Problem D : Longest Max Min Subsequence from
Codeforces Round 967 (Div. 2, My approach :- The solution to this problem involves several steps:
121.
Mastering Subsequences with Recursion: A Step-by-Step Guide 
Subsequences: they’re like the wardrobe combinations of coding—every possible way to arrange your elements without messing up the order. A subsequence is any sequence derived by deleting some (or no) elements of the array without changing the order of the remaining elements.
This is my first blog on Codeforces ^-^
In this blog, I’ll guide you through the process of generating all subsequences of a given array using recursion. Along the way, we’ll explore the logic, implementation, and common pitfalls, with just the right mix of fun and formality.
---
#### **What Are Subsequences?**
A subsequence is any sequence derived from an array by deleting some (or no) elements, without changing the order of the remaining elements.
For example, given the array `[1, 2, 3]`, the subsequences are:
```
[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]
```
Notice how the order is preserved, and...
smaller parts of the problem to itself. For subsequences, here’s the plan:, without messing up the order. A subsequence is any sequence derived by
deleting some (or no) elements
122.
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...
solving the opposite problem: given $n$, build a permutation such that no
subsequence of length 3 forms
Tutorial of MemSQL Start[c]UP 2.0 - Round 1
Tutorial of MemSQL Start[c]UP 2.0 - Round 2
Tutorial of MemSQL Start[c]UP 2.0 - Round 2 - Online Round
123.
Codeforces Round #104 - Editorial <p</p><p><b>DIV2-A Lucky Ticket:</b></p><p>In this problem everything is obvious: if all digits are lucky and sum of the digits of the first half equals to the sum of the digits of the second half, then answer is YES, in other case - NO. All this can be checked by single loop through all the digits. </p><p><br /></p><p><b>DIV2-B Lucky Mask:</b></p><p>You can see that, in worst case, the answer will be equal to $177777$. It can't be greater. So, only thing you need is to write some function $F(x)$ which will return mask of the $x$. After that you need to write such kind of code: </p><p><br /></p><p>$x$ = $a+1$;</p><p>while ($F(x)$ is not equal to $b$)</p><p>increase $x$;</p><p><br /></p><p>and $x$ will contain the answer.</p><p><br /></p><p><b>DIV2-C DIV1-A Lucky Transformation:</b></p><p>You need to find two numbers: $c47$ (number of such positions $i$, that $a_i = 4$ and $b_i = 7$) and $c74$ (number of such positions that $a_i = 7$ and $b_i = 4$). After that the result will be $max(c4...
DIV2-A Lucky Ticket:
In this problem everything is obvious: if all digits are
, fact to solve problem. Let $C[i]$ - number of occurrences of $i$-th lucky
number in array $a$. Now we
Tutorial of Codeforces Round 104 (Div. 1)
Tutorial of Codeforces Round 104 (Div. 2)
124.
Problems that I authored so far Hi everyone! I have been inspired [by](https://codeforces.me/blog/entry/108940) [recent](https://codeforces.me/blog/entry/108595) [events](https://codeforces.me/blog/entry/113093) to write this blog post. This list is not comprehensive, but mostly because I do not keep detailed logs of problems I have written.
There are a few things you will notice after reading through these problems. In no particular order:
1. Most of these problems are not "high-quality" — they would never see the light of day on a CF round for example. This is mostly due to my lack of skill in generating "high-quality" problems. You'll see that a lot of my problems are generated from observing real-life events and then constructing problems out of those scenarios. There are many ideas that have been proposed and thrown into the void because they were worse. I think there are a couple problems in this list that are actually good problems, but most of them I am not particularly proud of.
2. The diffic...
APIO problem? I no longer recall. | | 52 | March 2021 | [Longest Common
Subsequence](https, problem? I no longer recall. | | 52 | March 2021 | [Longest Common Subsequence
](https
125.
OPC March 2026 Editorial Thank you for participating in $\mathbf{OPC\ March\ 2026}$!
This editorial outlines the key ideas and solution approaches for each problem. We hope it helps you gain deeper insights and further strengthen your problem-solving skills in competitive programming.
We would greatly appreciate your feedback. Please share your thoughts through this [Google Form](https://docs.google.com/forms/d/e/1FAIpQLSf2jvScUIwpxy16neU-CKQj7wIFx9diAO7vFY7TJSERR_PFwQ/viewform)
Contest Link: [Link](https://codeforces.me/group/hUywLYmr80/contest/678537)
### [A. Find Sum](https://codeforces.me/group/hUywLYmr80/contest/678537/problem/A)
<spoiler summary="Hint 1">
To make a sum of differences as large as possible, you want to subtract the smallest available numbers and add the largest available numbers.
</spoiler>
<spoiler summary="Solution">
The cost function is $Cost = |a_n - a_1| + \sum_{i=2}^{n} |a_i - a_{i-1}|$. This is equivalent to the total distance traveled if you start...
### [E. Cyclic Non-Decreasing Subsequence
](https://codeforces.me/group/hUywLYmr80/contest/678537
126.
Codeforces Round #223 — Tutorial ### [problem:381A]
Simply do the process described in the statment.
### [problem:381B]
Calculate the amount of each number. For all the different numbers — maximum possible times of use isn't more than 2 times.
For the maximum is is only — 1.
### [problem:380A]
Generate the first number 100000.
Will in turn handle the requests, if the request gets to the point of adding one number, just print it.
Otherwise see what element will meet our and just print it from precalculated array.
### [problem:380B]
Lets generate a tree as described in the statment.
For each request to add items we just add a segment for a certain level.
At the request of the number of items we just go through all the lower levels, considering the leftmost
and the rightmost vertex in the subtree. To each level will take all intervals that it owns
and for each check — whether it intersects with the interval that we have generated in the current stage. If so, simply add items ...
### [problem:380C] We will support the segments tree. At each vertex will be
stored: $a_v, ### [problem:381A] Simply do the process described in the statment. ### [problem
:381B
Tutorial of Codeforces Round 223 (Div. 1)
Tutorial of Codeforces Round 223 (Div. 2)
127.
CodeGuerra Editorial Greetings everyone! We hope you enjoyed the problems. Here is the editorial of the [contest]((https://codeforces.me/contestInvitation/fbbb2bf3110f360b249aaa9225bd8348ba2e9d26)):
###[A — PAS C3](https://codeforces.me/gym/493827/problem/A)
Idea: [user:agrim07,2023-12-22]
<spoiler summary="Hint">
Be careful of precision errors!
</spoiler>
<spoiler summary="Tutorial">
For rajat to pass it should answer should be max(marks to get 4CG, marks to pass C3). which is max(marks to score 4CG,12). Let marks required to pass C3 is $c$ so following conditions should be satisfied
$$\displaystyle\frac{{c_1 + c_2 + c_3}}{h} \times 10 \geq 4$$
which can be re-written as
$$c_3 \geq \displaystyle\frac{2h}{5} - c_1 - c_2 $$
The above inequality can be modified to the following form to remove fractional values:
$$c_3 \geq \displaystyle\left\lceil\frac{2h}{5}\right\rceil - c_1 - c_2$$
We will use the following property to avoid dealing with float values as they are p...
For each delete query in this problem, deleting a substring from a, ###[ D — Subsequence Query](https://codeforces.me/gym/493827/problem/D)
128.
Google Intern OA Problems ~~~~~
Problem 1.
Given an array find no. of non-empty subsequences which does not have three consecutive odd or three consecutive even numbers in subsequence. Since answer is large print it modulo 1e9+7.
Expected time complexity is O(N) or (ONlogN).
~~~~~
<spoiler summary="hint">
DP... dp[k][i][j]: number of subsequences using first k elements, where the last two parities are (i, j), with
</spoiler>
<spoiler summary="code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
static const long long MOD = 1000000007;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
// dp[k][i][j]: number of subsequences using first k elements
// where the last two parities are (i, j), with:
// 0 = none, 1 = even, 2 = odd
vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(3, vector<long long>(3, 0))...
subsequence
129.
CodeDrills — A new online judge We are going through an unprecedented situation currently. There are lockdowns and quarantines in many parts of the world. We feel the best way to cope with everything that is going on is to keep ourselves occupied.
To help with that, we at CodeDrills have something for all the competitive coders out there. On 25th March, we launched our own online judge and also launched the CodeDrills covid 21 days challenge. Every day, for the 21 days starting from 25th March, we will upload 1 problem. Just visit [codedrills.io](https://codedrills.io), login and start solving! The launch coincided with the start of a full lockdown in India.
Since the situation was unexpected, we rushed to put up the site as soon as possible, so there might be issues. If you find any bugs or want to request a feature, please write to us at [email protected] with as much details as possible.
Here is our mascot Ufu wearing a mask (if you are unable to see him here, head over to [our page](https://codedrills...
21 days challenge. Every day, for the 21 days starting from 25th March, we
will upload 1problem, |Day | Problem link | |----|--------------| |1|[Beating Shell
sort](https://codedrills.io
130.
Could anyone give me some suggestions in learning please? Hello everyone, I'm [user:Cuber-26,2025-08-30].
Two years ago I don't even know how to write a program in programming language like C++. I started to learn programming and some very basic algorithms when I was a Freshman. Now it has been a year since I first come to Codeforces, currently my contest rating is $1815$.
Since I'm actually a student learning Mathematics, the part I do the best is Number Theory. I'm also good at solving some constructive problems and math problems. Problems like interactive or bitmask are OK for me too.
However some parts are my shortcomings:
1. Data Structures: Now I only learned BIT, Segment Tree, DSU, Trie, Sparse Table, and could only accomplish some simple applications.
2. Graphs(especially problems related to paths): I've never finished any problem about shortest paths and weighted graphs. I've learned Dijkstra and Floyd in Data Structure Course. However I had never written them into code, and I've completely forget them after final ex...
131.
Crafting Farmer John — My USACO Problemsetting Experience Hello Codeforces!
If you've somehow been living under a barn, [USACO](https://usaco.org/) is the largest online competitive programming contest for the USA high school students. As I myself am a USA high school student about to graduate, I'd like to reflect on my experience with contributing problems to USACO. By the way, I don't select problems that end up on each contest — I just contribute possible candidates. Also, I guess this is inspired by [user:xiaowuc1,2025-01-30]'s [blog](https://codeforces.me/blog/entry/113687), who also used to be a pretty active USACO problemsetter.
The difficulty column is purely based on **my own opinion**.
<table>
<thead>
<tr>
<th> # </th>
<th> Problem </th>
<th> Contest </th>
<th> Difficulty </th>
<th> Comments </th>
</tr>
</thead>
<tr>
<td> 1 </td>
<td> <a href="https://usaco.org/index.php?page=viewproblem2&cpid=1255">Circular Barn</a> </td>
<td> Silver, 2022 December<...
Best Subsequence Gold, February 2025 2300 I, > # Problem Contest Difficulty
132.
New Year, New Content! [](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 — 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...
1. I started with a dynamic programming problem from CodeForces: [problem:587B]
. You are given a
133.
Codeforces Round #832 (Div. 2) Editorial I hope you all liked the round. Please share your feedback in the comments section.
[1747A — Two Groups](https://codeforces.me/contest/1747/problem/A)
===============================
<spoiler summary = "Hint">
How about putting all positive numbers in one group and negative in second group
</spoiler>
<spoiler summary = "Tutorial">
Let $S$ denotes sum of element of array $a$.
**Claim**: Answer is $|S|$.
**Proof**: Let sum of all positive elements is $S_{pos}$ and sum of all negative elements $S_{neg}$. Put all positive numbers in first group and negative numbers in second group. We get $||S_{pos}| - |S_{neg}|| = |S|$.
Let's prove that we can not do better than that. Let $S_1$ denotes sum of elements of first group and $S_2$ denotes sum of elements of second group. We have $|S_1| - |S_2| \leq |S_1 + S_2| = |S|$. Hence $|S|$ is the upperbound for the answer.
</spoiler>
<spoiler summary = "Solution">
```cpp
// Jai Shree Ram
#include<bits/stdc++....
Now if you see clearly, after performing above operations, there does not exist
anysubsequence of
Tutorial of Codeforces Round 832 (Div. 2)
134.
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, ...
Problem Setter Team](https://sua.ac), so most of the problems I authored are
for the onsite contests, | # | Problem | Contest | Rating (Est.) | Tags | Comments
135.
[Analysis] Yandex.Algorithm 2016 Warm-up round Thanks to all the participants for [successful submissions](https://contest.yandex.com/algorithm2016/contest/2497/standings/)!
This set has been prepared by [user:snarknews,2016-05-11], [user:Chmel_Tolstiy,2016-05-11], [user:Gassa,2016-05-11] and [user:Zlobober,2016-05-11]. The analysis was prepared by [user:snarknews,2016-05-11] and [user:Gassa,2016-05-11].
Problem А. Alphabetical E-mail
------------------
Note that sets of vowels and consonants does not intersect,
which means that, when comparing two subsequences
lexicographically, first goes the one with the lesser first letter.
So read the characters one by one and remember
first consonant and first vowel.
When we meet both of them, immediately compare and print the answer. One of the subsequences can be empty.
Problem B. Bytaler
------------------
Read the first exchange rate and set $\mathrm{max}$ and $\mathrm{min}$
to its value.
Then read all other exchange rates; if the next rate
is greater than $\mat...
Problem А. Alphabetical E-mail ------------------ Note that sets of vowels and
consonants does
136.
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...
After filtering points on each side, the problem becomes finding a
137.
Problems that I authored so far UPD after one year!
Only a periodic summary. It will be updated continuously.
I'll be glad if someone gets inspired/gives feedback :)
| # | Date | Problem | Contest | Comment |
| -------- | -------- | -------- | -------- | -------- |
| 1 | Aug 2022 | [Ring Game](https://www.codechef.com/problems/RING_GAME) |[Codechef Starters 53](https://www.codechef.com/START53) | One of the simplest |
| 2 | Aug 2022 | [Rocket Pack](https://www.codechef.com/problems/ROCKET_PACK) | [Codechef Starters 53](https://www.codechef.com/START53) | |
| 3 | Sep 2022 | [Energetic Node](https://www.codechef.com/problems/ENODE_HARD) | [Codechef Starters 56](https://www.codechef.com/START56) | |
| 4 | Oct 2022 | [Collinear Points](https://www.codechef.com/problems/COLLINEAR) | [Codechef Starters 59](https://www.codechef.com/START59) | Highly recommend :)|
| 5 | Oct 2022 | [Maximun Sum](https://www.codechef.com/problems/MAXIMUM_SUM) | [Codechef Starters 60](https://www.codechef.com/...
Subsequence ](https://codeforces.me/gym/104542/problem/A) | [TheForces Round
#22](https://codeforces.com, | # | Date | Problem | Contest | Comment
138.
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...
The problem asks us to select a subsequence of raw materials to
139.
A2SV Contest #23 editorial [Here](https://codeforces.me/contestInvitation/5c44dfeff15ca6fb6c46bc1ed0a660996f7d0d76) is the link to the contest. All problems are from Codeforces' problemset.
#### [A. Balanced Subsequence](https://codeforces.me/gym/532814/problem/A)
<spoiler summary="Solution">
<p>
First we need to find the frequencies of the first $k$ alphabets in the string. Let the minimum frequency among these frequencies be $m$. Then we cannot select $m + 1$ characters of one kind, and we can definitely select $m$ characters of each kind, hence the answer is given by min(frequency of first k characters) * $k$.
</p>
</spoiler>
<spoiler summary="Code">
```python
import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()
n, k = map(int, input().split())
s = input()
count = Counter(s)
ans = float("inf")
for i in range(k):
char = chr(i + ord('A'))
ans = min(ans, count[char])
ans *= k
print(ans)
```
</spoiler>
#### [B. Tz...
#### [A. Balanced Subsequence](https://codeforces.me/gym/532814/problem/A)
140.
Codeforces Round #358 (Div. 2) Editorial [682A — Alyona and Numbers](http://codeforces.me/contest/682/problem/A)
Let's iterate over the first number of the pair, let it be $x$. Then we need to count numbers from $ 1 $ to $ m $ with the remainder of dividing $ 5 $ equal to $ (5 - x mod 5) mod $ 5. For example, you can precalc how many numbers from $ 1 $ to $ m $ with every remainder between $ 0 $ and $ 4 $.
[682B — Alyona and Mex](http://codeforces.me/contest/682/problem/B)
Let's sort the array. Let $ cur = $ 1. Then walk through the array. Let's look at current number. If it is greater or equal to $cur$, then let's increase $cur$ by $1$. Answer is $ cur $.
[682C — Alyona and the Tree](http://codeforces.me/contest/682/problem/C)
Let's do dfs. Suppose that we now stand at the vertex $u$. Let $v$ be some ancestor of vertex $u$. Then $ dist (v, u) = dist (1, u) - dist (1, v) $. If $ dist (v, u)> a_u $, then the vertex $ u $ makes $v$ sad. So you must remove the whole subtree of vertex $ u $. A...
Let's use the method of dynamic programming. Let d[i][j][cnt][end] be answer to
theproblem for the, [682A — Alyona and Numbers](http://codeforces.me/contest/682/problem/A) Let's
iterate
Tutorial of Codeforces Round 358 (Div. 2)
141.
A2SV G5 — Contest #10 Editorial [Here](https://codeforces.me/contestInvitation/f9a3ec3d30cb15397ba1c3cd0a4a744bd3f8a2c5) is the link to the contest.
#### [A. Longest Non-Palindromic Subsequence](https://codeforces.me/gym/514644/problem/A)
<spoiler summary = "Solution">
Consider the substring of $s$ from the second character to the last, or $s_2s_3⋯s_n$. If it's not palindrome, then the answer must be $n−1$. What if it's palindrome? This implies that $s_2=s_n, s_3=s_{n−1}$, and so on. Meanwhile, the fact that $s$ is palindrome implies $s_1=s_n, s_2=s_{n−1}$, etc. So we get $s_1=s_n=s_2=s_{n−1}=⋯$ or that all characters in $s$ is the same. In this situation, every subsequence of $s$ is palindrome of course, so the answer should be $−1$.
</spoiler>
<spoiler summary="Code">
```python3
import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
s = sys.stdin.readline().strip()
if len(set(list(s))) == 1:
print(- 1)
else:
print(len(s) - 1)
```
</spoiler>
###...
#### [A. Longest Non-Palindromic Subsequence](https://codeforces.me/gym/514644/
problem/A)
142.
Editorial of Educational Codeforces Round 11 ### [problem:660A]
The problem was suggested by Ali Ibrahim [user:New_Horizons,2016-04-09].
Note that we should insert some number between any adjacent not co-prime elements. On other hand we always
can insert the number $1$.
<spoiler summary="С++ solution">
~~~~~
const int N = 1010;
int n, a[N];
bool read() {
if (!(cin >> n)) return false;
forn(i, n) assert(scanf("%d", &a[i]) == 1);
return true;
}
void solve() {
function<int(int, int)> gcd = [&](int a, int b) { return !a ? b : gcd(b % a, a); };
vector<int> ans;
forn(i, n) {
ans.pb(a[i]);
if (i + 1 < n && gcd(a[i], a[i + 1]) > 1)
ans.pb(1);
}
cout << sz(ans) - n << endl;
forn(i, sz(ans)) {
if (i) putchar(' ');
printf("%d", ans[i]);
}
puts("");
}
~~~~~
</spoiler>
Complexity: $O(nlogn)$.
### [problem:660B]
The problem was suggested by Srikanth Bhat [user:srikkbhat,2016-04-09].
In this problem you should simply do what was written in the problem sta...
Let's consider some subsequence with the length $k>0$ (the empty subsequences
we will count
Tutorial of Educational Codeforces Round 11
143.
More detailed explanation: Hello 2019, Problem E You are given a permutation of size $n$, i.e. a sequence of $n$ distinct numbers. The task is to partition this permutation into monotonic subsequences. The number of subsequences (syn.: partition) does not need to be minimum, but it has to be smaller than $f(n)$, which denotes the minimum $k$ such that any permutation of size $n$ can be split into at most $k$ subsequences.
[Egor and an RPG game](https://codeforces.me/contest/1097/problem/E)
They did provide a [solution](https://codeforces.me/blog/entry/64310), but since I had a hard time understanding it, and I love proving things, I want to note down some of my insights and findings. Please let me know if you find any mistakes.
<!--more-->
## Observations
Let $t$ be the greatest $\tau$ such that $\frac{\tau(\tau+1)}{2} \leq n $. Consider the permutation (size $n$) in which the first $\frac{t(t+1)}{2}$ terms are 1, 3, 2, 6, 5, 4, 10, 9, 8, 7, ... ([OEIS A038722](http://oeis.org/A038722)), followed by the rest of $n...
More detailed explanation: Hello 2019, Problem E, distinct increasing subsequence, hence $a=t$., game](https://codeforces.me/contest/1097/problem/E) They did provide a
[solution](https, guaranteed that $t\leq f(n)$. Such a solution will be immediately valid. We're
near to solving theproblem., $ elements from the LIS, use them as a subsequence, leaving $n-t$ elements, and
$t-1$ is the largest $\tau, 2. $b\neq 0$. If we have a decreasing subsequence $d$, we have to expand it to
the whole
144.
Solution to REAL Codeforces Round #815 (Div. 2) D1 As known, [problem:1720D1] has an ambiguous descriptioin. I'm the one of those who got misled during the contest. However, the misunderstood problem is solutable. Let's have a look.
**It is the misunderstood version of the problem. The only difference is that in this version** $b_i$ do be the subsequence of $a$, where any $b_i$ is an element of $a$. Note that $a_i<200$ remains true.
<spoiler summary="Hint 1">
How to use the property of $a_i<200$?
</spoiler>
<spoiler summary="Hint 2">
Consider pair $(b_p, a_{b_p})$. Many of them are the same.
</spoiler>
<spoiler summary="Hint 3">
How to efficiently find the next possible $b_j$ after the current $b_i$?
</spoiler>
<spoiler summary="solution">
It's noticed that the number of distinct pair $(b_p, a_{b_p})$ is limited. What's more, such number is $200$ instead of $200^2$.
Therefore, we can compute whether placing $j$ after $i$ is valid by checking if $j \oplus a_i < i \oplus a_j$. The complexity of this part is...
**It is the misunderstood version of the problem. The only difference is that
in this version
145.
A2SV G6 — Round #6 (Editorial) [Here](https://codeforces.me/contestInvitation/c9f73b6b05a07d2c184e732ba6641fa16c328e13) is the contest link.
#### [A. The Ticket Booth](https://codeforces.me/gym/594077/problem/A)
<spoiler summary = "Solution">
Simply put, the problem is asking us to represent $S$, as a summation of numbers from the set ${1, 2, 3, … ,n }$.
Obviously there are many ways to do that, for example one might use $1$ $S$ times, but in this problem we are asked to use the minimum number of elements and output how many we used.
Since we have all the numbers from $1$ to $n$ and we can use each element repeatedly, we can afford to be greedy and always use the largest value less or equal to $S$, until we get the sum of the selected elements equal to $S$. This ensures that we use the fewest possible numbers.
This process can easily be represented by a ceil division of $S$ by $n$.
because $⌈S/n⌉$ tells us how many times we would need to add the largest possible number (which is $n$) to reach o...
The problem requires dividing the binary string into the **minimum, contest link. #### [A. The Ticket Booth](https://codeforces.me/gym/594077/
problem/A) , #### [E. Minimum Subsequence](https://codeforces.me/gym/594077/problem/E)
146.
What I've learnt from Pinely Round 4 ## Abstract
After I participated in Pinely Round 4 yesterday, my rating dropped down a lot.
BUT, I learnt something useful.
## 1. Check your initialization — AND Reconstruction
After I solved A in a minute and saw the statement of B, I quickly realized that there's an efficient construction which is simply set $a_i=b_i|b_{i-1}$. The code is below.
<spoiler summary="code">
```c++
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], b[N];
void run()
{
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
scanf("%d", b + i);
}
for (int i = 1; i <= n; i++)
{
a[i] = (b[i] | b[i - 1]);
}
for (int i = 1; i < n; i++)
{
// printf("%d %d\n", (a[i] & a[i + 1]), b[i]);
if ((a[i] & a[i + 1]) != b[i])
return puts("-1"), void();
}
for (int i = 1; i <= n; i++)
{
printf("%d%c", a[i], " \n"[i == n]);
}
}
int main()
{
int T = 1;
...
When I took my first look at this problem, I thought about segment tree.
However, it's unnecessary
147.
Codeforces round #396 editorial [problem:766A]
If the strings are the same, Any subsequence of $a$ is indeed a subsequence of $b$ so the answer is "-1", Otherwise the longer string can't be a subsequence of the other (If they are equal in length and aren't the same, No one can be a subsequence of the other) so the answer is maximum of their lengths.
Code : http://pastebin.com/aJbeTTjw
Time complexity : $O(|a|+|b|)$.
Problem author : me.
Solution author : me.
Testers : me and [user:mahmoudbadawy,2017-02-07].
[problem:766B]
#### First solution :-
Let $x$, $y$ and $z$ be the lengths of 3 line segments such that $x \le y \le z$, If they can't form a non-degenerate triangle, Line segments of lengths $x-1$, $y$ and $z$ or $x$, $y$ and $z+1$ can't form a non-degenerate triangle, So we don't need to try all the combinations, If we try $y$ as the middle one, We need to try the maximum $x$ that is less than or equal to $y$ and the minimum $z$ that is greater than or equal to $y$, The easiest way to do so...
[problem:766A] If the strings are the same, Any subsequence of $a$ is indeed a
subsequence of $b
Tutorial of Codeforces Round 396 (Div. 2)
148.
Good Observations: I will account for good observations and ideas while solving problems in codeforces/CodeChef/atcoder . The proofs of the below statements will not be mentioned here; It's advised to do such proofs on your own for exercise.
- Lets say I have a set $S$ consisting of integers, denote its $lcm(S) = L$, I add a new element $x$ to this set $S$ ,
Lets deonte the new set as $S'$,where $S' = union(S , x)$ and its $lcm(S') = L'$. Can we deduce a relation between $L$ and $L'$? We can observe $L = L'$ or $L' >= 2*L$.
<hr>
- We want to find two numbers in an array $A[]$ with maximum common prefix bits in binary representation. It's easy to show that those two numbers always occur as adjacent numbers in $sorted(A[])$
<hr>
- The number of distinct gcd prefixed/suffixed at an index in an array will never exceed $log(A_{max})$
<hr>
- Let's say I have a number $X$, And I apply modulo operation as many times as I wish, i.e $X = X \% {m_i}$ for some different values of ${m...
appears at any problem, maybe bruteforcing all $2^N$ combinations of $+/-$ may
give way to the, /contest/1553/problem/F - Lets take an array $A$ and let $f(x)$ be number of
subsequence
149.
Unofficial Editorial for Codeforces Round 964 - Upsolved a Whole Problem Set **This is the first contest where I solved the full problem set. That's why, to celebrate this achievement, I am writing an editorial about my implementations. If I made any mistakes or typos, please let me know.**
[1999A — A+B Again?](https://codeforces.me/contest/1999/problem/A)
<spoiler summary="Hint">
Since $n$ is a two-digit number, you can access each digit by simple arithmetic operations.
</spoiler>
<spoiler summary="Tutorial">
To find the sum of digits of a two-digit number $n$, divide $n$ by 10 to get the first digit and take $n$ modulo 10 to get the second digit. Adding these gives the desired result.
**Time Complexity:** $O(1)$ per test case
**Space Complexity:** $O(1)$
</spoiler>
<spoiler summary="Implementation">
```
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
cout << (n / 10) + (n % 10) << endl;
return 0;
}
```
</spoiler>
[B — Card Game](https://codeforces.me/conte...
Unofficial Editorial for Codeforces Round 964 - Upsolved a Whole Problem Set, Check if the string $t$ can appear as a subsequence in string $s, so that $t$ becomes a subsequence of $s$., - For a subsequence of odd length $k$, the median is the $(\frac{k +
1}{2})^{th}$ element when, - Use combinatorics to calculate how many times each element can be the median
in asubsequence of, 3. If $t$ becomes a subsequence of $s$, fill remaining '?' with any valid
letter (e.g., 'a') and, 4. If it is not possible to make $t$ a subsequence of $s$, print "NO".
150.
Number of partitions of n into at least two distinct parts ### About the problem
The problem is to calculate the number of such subsequence $\{a_1, a_2, \dots a_n\}$ that ($a_1 + a_2 + \dots + a_k = n$) where ($k \geq 2$) and ($a_i \in \{1, 2, \dots, n}$)
It is the sequence [OEIS A111133](https://oeis.org/A111133)
----
----
### My approach for small n
Lets $magic(left, last)$ is the number of valid subsequences whose sum equal $left$ which next selected element is such $next$ in range $(last, left]$ ($next$ is strictly greater then last selected number $last$ and not greater than current sum $left$). The recursive stop when $left = 0$ then we found one valid subsequence
<spoiler summary="Recursive dp - O(n^3) - small n">
```cpp
vector<vector<ll> > f; /// init as -1
ll magic(int left = n, int last = 0)
{
if (left == 0) return 1;
ll &res = f[left][last];
if (res != -1) return res;
res = 0;
for (int next = last + 1; next <= left; ++next)
res += magic(left - cur, next);
return r...
The problem is to calculate the number of such subsequence $\{a_1, a_2, \dots
a_n\}$ that ($a_1
151.
Editorial For CodeRed 2024 Greetings everyone! We hope you enjoyed the problems. Here is the editorial of the [contest](https://codeforces.me/contests/514183). Sorry for delay!.
###[A — Construct a subsequence](https://codeforces.me/gym/514183/problem/A)
<spoiler summary="Hint">
Check if $i$-th bit of the cost can be $0$?
</spoiler>
<spoiler summary="Tutorial">
Let's say the cost $2^{30} - 1$, we will try to set the $i$-th bit of the cost to $0$ while iterating $i$ from $29$ to $0$.
<spoiler summary="Why iterating in reverse? ">
We are iterating in reverse because if we can construct a subsequence with cost that has $i$-th bit $0$, then even if all bits $j$, $j < i$ are $1$ it would still have less cost.
</spoiler>
You can pick an index $i$ in your subsequence if $a_i$ is a sub-mask of the cost you are currently constructing.
Now greedily club indices that have distance $\leq k$ between them. Note that if you can make a subsequence we length $l'$, $(l' \gt l)$, you also ma...
Lets solve this problem when there are no queries In that case we can, ://codeforces.com/contests/514183). Sorry for delay!. ###[A — Construct a
subsequence](https
152.
SPOJ SUPPER WA Hello
I'm trying to solve problem SUPPER from SPOJ.
I think a number x[n] is defined to be super if length of LIS[n] (longest increasing subsequence ending at x[n]) plus LDC[n] (length of longest decreasing subsequence ending at x[n] , when reading the input permutation in reverse) equals the length of longest increasing subsequence of the entire input permutation .
Solution Complexity is O(N log N).
I'm using Segment Tree , suppose node n covers interval [i .. j] ,
then tree[n] = max { LIS [ x [ i ] ] , LIS [ x [ i + 1 ] ] , ... , LIS [ x [ j ] ] }
I used an O(N^2) solution to compare my answers against.
Thanks a lot in advance for any help.
~~~~~
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 100001;
int N;
int x[MAXN];
int LIS[MAXN];
int LDS[MAXN];
int lis[MAXN];
int lds[MAXN];
int tree[4 * MAXN];
int best;
int query(int node , int s , int e , int qs , int qe)...
Hello I'm trying to solve problem SUPPER from SPOJ. I think a number x[n] is
defined to be super
153.
A painful implementation problem WARNING: DISGUSTING PROBLEM ALERT
At the start of the year, I wrote a very painful implementation problem. My official solution was over 200 lines long and I was wondering if anyone could come up with a more elegant solution.
The problem is as follows:
<spoiler summary="Problem">
The S value of an array is the sum of maximum values across all continuous subsequences length at least one. In the array $(4,5,1)$, the value is $4+5+1+5+5+5=25$.
You are given an array $A$ of length $N$. There are $N$ updates, where the $I$th update increases the $i$th value of the array by a value $B_i$. It is guaranteed that all $2N$ values, before and after updates, are **unique**.
Output $N+1$ integers, the initial S value and the S value after every update.
$N \leq 5 \cdot 10^5$
</spoiler>
Given some subtasks, the highest score was 72 by [user:A_Wallaby,2020-11-08]. Majority of participants scored 27 points, where $B_i = 0$ for all $i$.
<spoiler summary="Solution">
Clearly, ...
A painful implementation problem, The S value of an array is the sum of maximum values across all, WARNING: DISGUSTING PROBLEM ALERT At the start of the year, I wrote a very
painful
154.
Problems with UVa 103? Hello, I was trying to solve [UVa 103](https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=39) using $O(N^2)$ Longest Increasing Subsequence. Here is my code:
~~~~~
#include <bits/stdc++.h>
using namespace std;
int K, N, dp[31];
pair<vector<int>, int> A[31];
string hist[31];
bool canFit(int i, int j) {
for (int k = 0; k < N; ++k)
if (A[i].first[k] >= A[j].first[k])
return false;
return true;
}
int main() {
while (cin >> K >> N) {
for (int i = 0; i < K; ++i) {
A[i].first.resize(N, 0);
for (int j = 0; j < N; ++j)
cin >> A[i].first[j];
A[i].second = i;
sort(A[i].first.begin(), A[i].first.end());
}
sort(A, A+K);
fill_n(dp, 31, 1);
for (int i = 0; i < K; ++i)
hist[i] = to_string(A[i].second+1);
int ans = 1;
string best = "1";
for (int i = 1; i < K...
&Itemid=8&page=show_problem&problem=39) using $O(N^2)$ Longest Increasing
Subsequence. Here is my code:
155.
[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 — CodeForces 57C](https://www.youtube.com/watch?v=eU9_C7DKiys&list=PLPSFnlxEu99HgAEayVzwxfLo0jwUU3rQD&index=4)
Part 5 | [Problem Bad Subsequenc...
Part 5 | [Problem Bad Subsequences — PSUT Qualification Round
2017](https://www.youtube.com
156.
Codeforces Round #279 (Div. 2) Editorial ### [problem:490A]
The teams could be formed using greedy algorithm. We can choose any three children with different skills who are not participants of any team yet and form a new team using them. After some time we could not form any team, so the answer to the problem is minimum of the number of ones, twos and threes in given array. We can get $O(N)$ solution if we add children with different skills into three different arrays. Also the problem could be solved in $O(N^2)$ — every iteration find new three children for new team.
### [problem:490B]
This problem can be solved constructively. Find the first student — it is a student with such number which can be found among $a_i$ and could not be found among $b_i$ (because he doesn’t stand behind for anybody). Find the second student — it is a student standing behind the first, number $a_i$ of the first student equals $0$, so his number is a number in pair $[0, b_i]$.
After that we will find numbers of all oth...
The problem is generalization of finding maximal increasing subsequence in
array, so it probably
Tutorial of Codeforces Round 279 (Div. 2)
157.
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...
The first step is to realize the solution to a well known dp problem
Tutorial of Insomnia 2025
158.
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 – ...
immediately recognize it as a classical problem “subsequence of maximal sum”.
If you never heard about it
Tutorial of Codeforces Round 191 (Div. 2)
159.
Cursed (unproven) solution to 1944B found during testing During testing of Codeforces Round 934, I found a very cursed (albeit unproven) solution to [problem:1944B] and I thought it would be worth a separate blog, so here it is.
Before I explain the solution, I must give you a quick disclaimer; It is much harder than the intended solution and is very likely useless. If you would appreciate understanding it despite it being very useless, please do read further.
First, let us use an assumption which will be under the very basis of the solution. I will **not** prove it to you, but you will see that it is likely true.
- Let $X$ be an uniform random subsequence of $a$ with size $k$. Then, $X_1 \oplus X_2 \oplus \cdots \oplus X_k$ is **almost** uniformly distributed across all possible values.
If this assumption is true, then we can get to a solution with $\mathcal{O}(n \sqrt{n})$ expected time complexity and $\mathcal{O}(n \sqrt{n}/w)$ expected space complexity.
Let us sample one random subsequence of length $2k$ from $a_1,a_2,\cdo...
[problem:1944B] and I thought it would be worth a separate blog, so here it
is. Before I explain the, situation is very close to the birthday problem where we need an expected
number of $O(\sqrt{n})$ people
160.
A2SV Contest #17 editorial [Here](https://codeforces.me/contestInvitation/d7abc8565f76749806ef38279c69014f99ad4952) is the link to the contest (the problems are from Codeforces problemset).
#### [A. Distribute](https://codeforces.me/gym/524965/problem/A)
<spoiler summary = "Solution">
Because of it is guaranteed, that the answer always exists, we need to sort all cards in non-descending order of the numbers, which are written on them. Then we need to give to the first player the first and the last card from the sorted array, give to the second player the second and the penultimate cards and so on.
</spoiler>
<spoiler summary="Code">
```python3
from sys import stdin
def input(): return stdin.readline().strip()
N = int(input())
a = list(map(int, input().split()))
nums_idx = [(a[i], i) for i in range(N)]
nums_idx.sort()
for i in range(N//2):
i1 = nums_idx[i][1] + 1
i2 = nums_idx[N - 1 - i][1] + 1
print(i1, i2)
```
</spoiler>
#### [B. Grid Path](https://codeforces...
Let's rephrase the problem a bit. Instead of counting the number of arrays,
let's count the number
161.
Online Assesment problems(Amazon Hackon) Few days ago Amazon Hackon 1st round was conducted, i would like to discuss some of the problems(i have written what i have done in some the problems) which were given to us in our team .
Problem 1: You work at a company that has 5 offices, each with a distinct salary level and a priority ranking from lowest to highest as follows:
Office A ($ 1)< Office B ($ 10)< Office C ($ 100)< Office D ($ 1,000)< Office E($ 10,000).
Your work schedule is represented by a string, where each character corresponds to an office (e.g., 'D' for Office D) you work on the ith day. Your salary is calculated based on the following rule:
Salary Calculation Rules:
- If you work in an office and no higher-priority office appears after it in the sequence, you add its salary to your total salary
- If you work in an office and a higher-priority office appears later in the sequence, you subtract its salary from your total salary
The company allows you to change the office you work in, on any one day...
Problem 3: Given a array A and two values x ,M . We can choose a subsequence
such that sum of
162.
UTPC April Fools' Contest 2024 Editorial Hello everyone! Hope you enjoyed our contest, this was our first time making a contest in this fashion. Hopefully we will have many more years :)
[A – Are you a Robot?](https://codeforces.me/gym/105071/problem/A)
Author: [user:blueberryJam,2024-04-02]
<spoiler summary="Solution">
The answer is `No`. We would also accept the full CAPTCHA,
$$JR5JNYNJSABN03BIELLEQ9PA9REEUXO5DXSA4C5S$$
$$U6A9SXD2A2VR00B5SUWPX38ONBR9THZ8Y80Q18Z$$
$$JI4ESKAWMU7MX5K33EAFXPR7323LP4DMTI3YSZL2$$
$$4EIUYBZJBHD7OVF6GEIE28JUQVILEIWWDM8RHKZ8$$
for those who have the patience to type it out.
</spoiler>
<spoiler summary="Feedback">
-
Good problem
-
Amazing problem
-
Best problem ever
</spoiler>
[B – Working Out](https://codeforces.me/gym/105071/problem/B)
Author: [user:sg2themax,2024-04-02]
<spoiler summary="Solution">
Simple dad joke: anything containing "codeforces gym" works as a valid output (including the URL, or just the ph...
The problem hints at an off-by-one error. Indeed, it turns out the, /105071/problem/A) Author: [user:blueberryJam,2024-04-02] The
Tutorial of UTPC April Fools Contest 2024
163.
EPIC Institute of Technology Round Summer 2025 (Codeforces Round 1036, Div. 1 + Div. 2) Editorial Thanks for participation! We hope you loved the contest.
#### [problem:2124A]
Problem Credits: [user:Lilypad,2025-07-01] <br>
<spoiler summary="Hint">
When is there definitely *not* a solution?
</spoiler>
<spoiler summary="Solution">
First, note that since relative order is preserved no matter which elements are deleted, if $a$ is originally sorted in nondecreasing order, the array cannot be a derangement no matter which elements are deleted.
If $a$ is not sorted, we can note that any two elements that form an inversion pair satisfies the requirements. The total runtime is $O(n)$.
</spoiler>
<spoiler summary="Code">
```
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
vector<int> arr(n);
for(auto &x : arr) cin >> x;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(arr[i] > arr[j]){
cout << "YES\n2\n";
cout << arr[i] << " " << a...
Thanks for participation! We hope you loved the contest. #### [problem:2124A]
Problem Credits
164.
Notes on Codeforces Beta Round #107, Div2- A, B, C, D (union-find), E (segment tree and maximum subsequence sum) [problem:151A]
Simply calculate the answer as the sample indicates.
[problem:151B]
A straightforward implementation problem. Take care of the output format.
[problem:151C]
Note that the player who can not move wins! Therefore, for the initially given integer $q$, if it is a prime number, the first player wins.
Otherwise, we decompose $q=(p_1)^{a_1}(p_2)^{a_2}...$, where $p_i$ is a prime divisor. If $q$ only has two prime divisors, it is obvious that the second player wins. If $q$ has more than two prime divisors, the first player definitely wins, since he can find any two prime divisors $p_i$ and $p_j$ and write down integer $p_i\times p_j$, and then the second player has to face an integer that has only two prime divisors.
As a general method, we can find a divisor of $q$, denoted as $d$, which falls into interval [2, \srqt{q}]. If such $d$ can not be found, the first player wins. Otherwise, we have found two divisors of $q$, i.e., $d$ and $q/d$. Then, we test w...
subsequence sum), that asks to find a consecutive subsequence which gives the maximum sum (a
classicalproblem)., A straightforward implementation problem. Take care of the output format., To solve the reduced problem, we should adopt segment tree since the number of
queries is large, [problem:151A], [problem:151B], [problem:151C], [problem:151D], [problem:151E], problem can be reduced to such one that asks to find a consecutive subsequence
which gives the
165.
Dyanamic Programming # Dynamic Programming
There were huge number of sources on the internet on this topic but still we (me and my friend) couldn't understand any of it for a very long time until we fiddled with code and tracked the output for every change in the input. So this repository is exactly created for people like us to make the transition from [greedy](https://en.wikipedia.org/wiki/Greedy_algorithm) to dynamic programming easier. This will just be an introduction to dynamic programming, so that one can pick it up from there. I have added additional sources for practice and other online tutorials that I found a little helpful at the end and will continue to do so as I find something new. It is for programmers who are comfortable with brute-force and might not the serve the purpose for absolute beginners. Contributions or suggestions are welcome.
## Definition
So what's dynamic programming? Let's first look at a more formal definition.
Dynamic programming (also known as dynamic optimiz...
## Longest increasing subsequence <>, - [Minimum cost problem](#problem-1) - [Longest increasing subsequence](#problem
-2), The Longest Increasing Subsequence (LIS) problem is to find the length of the
longestsubsequence
166.
Codeforces Round 1007 (Div. 2) Editorial We hope you enjoyed the problems! Thank you for participating in the contest! We would love to hear your feedback in the comments.
<br>
<spoiler summary="How did you find the contest?">
- Great:
- Good:
- Average:
- Bad:
- Trash:
</spoiler>
<spoiler summary="Which problem was your favorite?">
- A:
- B:
- C:
- D1:
- D2:
- E:
- F:
</spoiler>
<spoiler summary="Which problem did you find the least enjoyable?">
- A:
- B:
- C:
- D1:
- D2:
- E:
- F:
</spoiler>
<br>
[problem:2071A]
<spoiler summary="Hints">
<spoiler summary="Hint 1">
When Fofo is the spectator of the first match, what is the earl...
Tutorial of Codeforces Round 1007 (Div. 2)
167.
'Compatible Subsequences' Problem of CodeRushX 2023 ~~~~~
The problem statement is:-
Two sequences A and B are said to be compatible if A can be converted to B in any number of moves of the following type:
- Replace any element of the sequence with -1*(S) where S is equal to the sum of all elements in the current sequence.
Now, given two sequences X and Y. Count the number of subsequences of X that are compatible with Y . Print the answer modulo 109+7
Input
Each test contains multiple test cases. The first line contains the number of test cases, T. The description of the test cases follows.
The first line of each test case contains two integers n, m where n and m are the sizes of the sequence X and Y respectively.
The second line of each test case contains n integers X1, X2,. , Xn
The third line of each test case contains m integers Y1, Y2,. , Ym.
Constraints:
1 <= T <= 500
1 <= m <= n <= 2*105
-109 <= Xi, Yi <= 109
The sum of n over all test cases is less than or equal to 2*105
Output
For each test cas...
'Compatible Subsequences' Problem of CodeRushX 2023, the first time, we have as 'sum of the subsequence' -(the element replaced)
and it can be exchanged, will this compatible subsequence be counted. 7 4 2, Ex:- 7 4 2 sum of subsequence is 13 2 7 4 replacing 7 with -13 , -13 4 2 (new
sum is, The problem statement is:-
168.
Need a link to "count different subsequences with interval queries" problem If you've already seen this task somewhere, I'd be grateful for the link.
You are given a string of length about $10^5$. There are many queries about intervals of this string and for each interval, you have to calculate the number of distinct subsequences (not necessarily contiguous) of this interval.
The solution builds a segment tree and keeps matrices in each node. Have you seen this problem?
Need a link to "count different subsequences with interval queries" problem, problem?
169.
[Tutorial] Recursion This tutorial will cover explicit use of recursion and its implementation in problems. This topic is not used directly to solve problems in contests but rather is an essential tool in Dynamic Programming, Tree algorithms, Graph Traversal, etc. Topics like time complexity and space complexity of recursive function are not discussed in this tutorial.
# What is recursion?
When a function calls itself, then its called recursion. That is the most basic definition. This definition is enough when you need to solve basic problems like fibonacci series, factorial, etc. This is the implicit use of recursion.
Problems like printing all permutations, combination or subsets uses explicit use of recursion also known as "Complete Search".
# Approach to solve a problem recursively
When solving a problem through recursion one must think of breaking the current problem into sub-problem. Sub-problem is chosen such that we can keep on breaking the sub-problems until we reach a sub-proble...
Another approach is possible for this problem using a boolean vector and
subsequences but that idea
170.
Another solution to 2241F _I used AI to fix my grammar, so this blog might look like it was written by AI. You can read the Chinese version of this blog [here](https://www.luogu.com.cn/article/3v6yitu4)._
Upd 2026.08.30: Replaced with a cleaner proof. Thanks to [user:PhirainEX,2026-08-30] for the inspiration!
This is an alternative solution to [problem:2241F], which differs from the editorial.
Obviously, if the remaining sequence length is $\le 1$, the number of inversions is $0$, making it a P-state (a losing state for the current player). Now, let's consider the following three states:
- If the initial number of inversions is odd, Alice can simply remove the entire sequence, leaving an empty sequence. Thus, this is an N-state (a winning state for the current player), and Alice wins.
- If the initial number of inversions is even, and there exists an index $i$ such that the number of inversions becomes odd after removing $s_i$ (which is equivalent to saying $s_i$ contributes an odd number of invers...
$1$ in the chosen subsequence. Since $s$ is in state three, each $s_i$
contributes an even number of
171.
Rerooting dynamic Euler tour trees Dear wise-and-all-knowing people of Codeforces, I have come to call on you for aid.
I'm trying to wrap my head around rerooting an Euler tour tree. In particular, I want to be able to still do link/cut operations. I can find some bits information about rerooting on the internet (which I understand), but I don't understand how I can continue using my Euler tour tree afterwards. Thus my question is: how, _if possible at all_, can I use Euler tour trees to support the operations `cut(u)`, `link(u, v)` (assuming u has no parent), `findroot(u)` and `makeroot(u)`, each in $O(\log n)$ time? (or optionally with some extra $\log$-factors) In particular, `makeroot(u)` would preserve the general shape of the tree, i.e. you can't do `attach(findroot(u), v))`, instead all edges on the path from $u$ to the root would be reversed.
Throughout this post let me use the left tree in [this](http://wcipeg.com/problem/images/noi13p2/noi13p2.png) image as an example, with Euler tour 124252131. (these a...
Now, the problem comes from the fact that if you want to do e.g. a `cut(u)`
operation, you need to
172.
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...
1. [Kanade's Perfect Multiples](https://codeforces.me/problemset/problem
/2173/C), 2. [Game on
173.
Codeforces Round 1046 (Div. 1, Div. 2) Editorial <spoiler summary="Rate the Contest!">
- Amazing round:
- Good round:
- Average round:
- Bad round:
- Horrible round:
</spoiler>
[problem:2136A]
Idea: [user:Alan_dong,2025-08-25]
Preparation: [user:Register,2025-08-25]
<spoiler summary="Hint">
If one team got a score of $x$ in the first half, what is the maximum score the other team could get?
</spoiler>
<spoiler summary="Solution">
We can consider the first half and the second half separately. The dream might come true if and only if the scores in both halves are possible. In the second half, the RiOI team scored $(c - a)$ goals, while the KDOI team scored $(d - b)$ goals.
Suppose the RiOI team scored $x$ goals in some half. Denoting the score of the KDOI team as $y$, one can see that the maximal value of $y$ is $2\cdot x + 2$, under the goal order $\tt{\color{red}K\color{red}K\color{black}RK\color{red}K\color{black}R...RK\color{red}K\color...
] [problem:2136A] Idea: [user:Alan_dong,2025-08-25] Preparation:
[user:Register,2025
Tutorial of Codeforces Round 1046 (Div. 1)
Tutorial of Codeforces Round 1046 (Div. 2)
174.
Editorial for Codeforces Round #148 Hi :)
Here is the editorial for round #148. I just tried to explain the ideas rather than detailed implementation explanation. I'm sorry for my bad English, so please tell me if something is not clear in the descriptions.
### Two Bags of Potatoes
The author of this problem is ~Gerald,2012-11-05. The total number of potatoes is a multiple of $k$ and constraint $\frac{n}{k} \leq 10^5$ there will be at most $10^5$ multiples of $k$ in range $1$ to $n$. So you can iterate on multiples of $k$ and print the ones that satisfy the problem.
### Easy Tape Programming
In this problem you just need to simulate every thing which is written in the statement step by step. You can see a simple implementation of this here: http://www.codeforces.com/contest/239/submission/2512422
### Not Wool Sequences
Let $a_1, \dots, a_n$ be a not-wool-sequence. We define another sequence called $b$ in which $b_i$ is xor of the first $i$ elements of $a$, $b_i = a_i \oplus b_{i-1}$ and $b_0 = 0$.
...
Now xor of elements of a consecutive subsequence like $a_i, \dots, a_j$ will be
equal to $b_j
Tutorial of Codeforces Round 148 (Div. 1)
Tutorial of Codeforces Round 148 (Div. 2)
175.
My not impractical solution to 2037E with smaller number of queries. The problem [E. Kachina's Favorite Binary String](https://codeforces.me/problemset/problem/2037/E) is saying that we have a binary sequence $s$ that we don't know and we can ask queries. In each query we can choose a subarray and ask about the number of subsequences of $01$ in this subarray. Your task is to determine the string $s$ or say that it's impossible.
It might be helpful to read an editorial or solve the problem yourself before reading this blog.
First let's solve the problem using $\frac{1}{2}\cdot n + \mathcal{O}(\log{n})$ queries(it is possible to do a bit better, but it would be helpful later). To do this we would like to know where is the last occurrence of $1$. Our first query will be the whole string. If the answer is $0$ we can just print IMPOSSIBLE, else we can binary search on a prefix. If some prefix gives the same result as a whole string, we know that each element not in this prefix must be $0$. Now we ignore all elements after this $1$(they are all $0$s). ...
The problem [E. Kachina's Favorite Binary
String](https://codeforces.me/problemset/problem/2037/E
176.
Longest Common Subsequence Problem Link : https://www.interviewbit.com/problems/longest-common-subsequence/
Can anyone help me out.
why this code is giving time limit error(tle):
~~~~~
int fun(vector<vector<int> > &dp,int i,int j,string s1,string s2)
{
if(i==s1.length()|| j==s2.length()) return 0;
int &ans=dp[i][j];
if(ans!=-1) return ans;
ans=max(fun(dp,i,j+1,s1,s2),fun(dp,i+1,j,s1,s2));
if(s1[i]==s2[j])
ans=max(ans,1+fun(dp,i+1,j+1,s1,s2));
return ans;
}
int Solution::solve(string s1, string s2) {
if(!s1.length() || !s2.length()) return 0;
int n=s1.size(),m=s2.size();
vector<vector<int> > dp(n,vector<int> (m,-1));
return fun(dp,0,0,s1,s2);
}
~~~~~
and why this code get accepted:
×
~~~~~
int Solution::solve(string s1, string s2) {
if(!s1.length() || !s2.length()) return 0;
int n=s1.size(),m=s2.size(),i,j;
vector<vector<int> > dp(n+1,vector<int> (m+1,0));
fo...
Longest Common Subsequence, Problem Link : https://www.interviewbit.com/problems/longest-common-subsequence/
177.
"Merging treaps" -- or how to merge sorted sets in good complexity... ... without doing much of anything.
I've been obsessed for the last two days about problem [Data Centers](https://ubilo.tubitak.gov.tr/egoi2022/assets/tasks/DataCenters.pdf) from EGOI 2022. In particular, it has a subtask where $1 \leq N \leq 10^5$ and $1 \leq S \leq 5000$, where it seems $O(NS)$ wouldn't fit TL. I've been conjecturing that using treaps would amortize to good complexity, and after two days of burning grey matter, I've finally found a proof, and it's pretty cool to make a blog out of it.
The problem basically starts with an array $[v_1, v_2, ..., v_N]$, where $1 \leq v_i \leq V$ for all $i$. It then asks us to iteratively simulate the operation: "Subtact $x_i$ from the biggest $m_i$ elements.". All this while keeping the array sorted.
We'll show that just using treaps (or any BBST for that matter) yields a good amortized complexity. More exactly, we'll prove $O((N + Q) \log V \log N)$, and it should actually be better in practice.
### Naive solution with tr...
... without doing much of anything. I've been obsessed for the last two days
aboutproblem [Data
178.
Codeforces Round #745 Editorial I'm very sorry about all the inconvenience, and I would like to bear the blame. Much thanks to those who help me prepare this round. It's not their fault. And much thanks to your participation.
[problem:1581A]
------------------
idea: [user:interlude,2021-09-30]
preparation: [user:CQXYM,2021-09-30]
tutorial: [user:CQXYM,2021-09-30]
Assume a permutation $p$, and $\sum_{i=2}^{2n}[p_{i-1}<p_i]=k$. Assume a permutaion $q$, satisfying $\forall 1 \leqslant i \leqslant 2n, q_i=2n-p_i$. We can know that $\forall 2 \leqslant i \leqslant 2n,[p_{i-1}<p_i]+[q_{i-1}<q_i]=1$. Thus,$\sum_{i=2}^{2n}[q_{i-1}<q_i]=2n-1-k$, and either $p$ should be counted or $q$ should be counted. All in all, the half of all the permutaions would be counted in the answer. Thus, the answer is $\frac{1}{2}(2n)!$.
The time complexity is $O(\sum n)$. If you precalulate the factors, then the complexity will be $O(t+n)$.
-----
<spoiler summary="solution">
~~~~~
#include<stdio.h>
int f[100001];
int m...
. [problem:1581A] ------------------ idea: [user:interlude,2021-09-30]
preparation: [user:CQXYM
Tutorial of Codeforces Round 745 (Div. 1)
Tutorial of Codeforces Round 745 (Div. 2)
179.
Codeforces Round 313 — Short editoral [problem:560A]
Just check is the 1 in the set.
[problem:560B]
One can snuggle pictures to each other and to edge of stand.
[problem:559A] & [problem:560C]
Let's join regular triangles to three edges of hexagon (to 1st, 3rd and 5th edges).
[problem:559B] & [problem:560D]
One can check if lexicographically smallest string wich is equals to first string in statement the same as second.
[problem:559C] & [problem:560E]
Let's paint bottom-right cell to black color. Then let's calculate number of ways to came to each black cell avoiding previous black cells via dp.
[problem:559D]
Let's remember Pick's theorem and let's consider all potencial sides of polygon separately. Do we really need to consider them all?
[problem:559E]
Lightened part of path is union of disjoint segments. Hence if we know what segments of path each continious subsequence of spotlights can lighten then we can solve the problem with simple (for such problem munber) dp.
How one can ...
continious subsequence of spotlights can lighten then we can solve the problem
with simple (for such
180.
Mastering Binary Search with Codeforces Problems (Rating Wise) # Mastering Binary Search with Codeforces Problems (Rating Wise)
Binary Search is one of the most fundamental and powerful techniques in competitive programming. Many beginners only use it to find an element in a sorted array, but in contests, Binary Search is used in much more creative ways.
This post lists problems ordered by rating (800 → 2000) so you can practice progressively.
## Easy (800 – 1200)
**[706B — Interesting Drink](https://codeforces.me/problemset/problem/706/B)**
— Simple use of binary search with arrays.
**[1352C — K-th Not Divisible by n](https://codeforces.me/problemset/problem/1352/C)**
— Binary search on the answer.
**[812C — Sagheer and Nubian Market](https://codeforces.me/problemset/problem/812/C)**
— Binary search to maximize affordable items.
## Medium (1300 – 1600)
**[371C — Hamburgers](https://codeforces.me/problemset/problem/371/C)**
— Binary search on the maximum number of burgers.
**[1181B —...
**[1157C2 — Increasing Subsequence (Hard)](https://codeforces.me/problemset/
problem/1157/C2
181.
[Unofficial] Educational Codeforces Round 161 Editorial Since the editorial is still unpublished yet as I was writing this blog, I decided to write an editorial for the problems that were given at yesterday's contest. For tasks A-E I also published video editorials ([A-C](https://www.youtube.com/watch?v=WPueAdG03Po), [D-E](https://www.youtube.com/watch?v=aTI-CLjoRCU))
[problem:1922A]
In order to solve this problem, we must observe that each position is independent from each other and it is enough for us to fix only one position in order to see if we can get both $a$ and $b$ match the template while $c$ doesn't. Thus, it will be enough to check if $a_i \neq c_i$ and $b_i \neq c_i$ for that to work, as we could then put an uppercase letter and discard $c$ right away.
Solution code: [submission:242416975]
Video editorial: [Link](https://www.youtube.com/watch?v=WPueAdG03Po)
Alternatively, this can also be done in a much more complicated fashion with bitmask dp where $dp_{(i, j)}$ is $1$ if we can get a configuration up to positio...
?v=aTI-CLjoRCU)) [problem:1922A] In order to solve this problem, we must
observe that each
182.
Codeforces Beta Round #25 Solution Analysis <h3>Problem A - IQ Test</h3>We can store two values, $count_{odd}$ and $count_{even}$, as the number of odd or even elements in the series. We can also store $last_{odd}$ and $last_{even}$ as the index of the last odd/even item encountered. If only one odd number appears --- output $last_{odd}$; otherwise only one even number appears, so output $last_{even}$.<br><br><br><h3>Problem B - Telephone Numbers<br></h3>There are many ways of separating the string into clusters of 2 or 3 characters. One easy way is to output 2 characters at a time, until you have only 2 or 3 characters remaining. Here is a possible C++ solution:<br><br><code><br>for( i=0; i<n; i++ )<br>{<br> putchar(buf[i]);<br> if( i%2 && i<n-(n%2)-2 ) putchar('-');<br>}<br></code><br>
<br><br>
<h3>Problem C - Roads in Berland<br>
</h3>
If you are familiar with the <a href="http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm">Floyd-Warshall algorithm</a>, then this...
,...,x_n)=x_0+ax_1+a^{2}x_2+...+a^{n}x_n$. This polynomial is a good hash
function in thisproblem
Tutorial of Codeforces Beta Round 25 (Div. 2 Only)
183.
Strictly Increasing Array / Sequence I am posting this just for **beginners** like me so that we can use such tricks in future and as both the problems are almost similar I just posted them together not to get confused in case.
Q1.
===
You are given an array of N integers. Suppose you are allowed to change an element into any integer with one operation. Find the minimum number of operations to make the array strictly increasing. (Note that the elements can become <1). The given array contains N positive integers.
- 1 ≤ N ≤ 10^5
- 1 ≤ ai ≤ 10^9 for 1 <= i <= N
#### Example:
1) N = 5
1 2 2 3 6
Sol: 1 2 3 5 6. So the answer is 2
2) N = 3
1 1 1
Sol: −1 1 2. So the answer is 2
3) N = 6
4 2 4 4 6 8
Sol: 1 2 4 5 6 8. So the answer is 2
4) N = 7
1 2 2 2 3 4 5
Sol: -1 0 1 2 3 4 5. So the answer is 3.
#### Here is how we can solve this problem:
Suppose the problem was simply named Non-decreasing Array. Obviously, you want to keep ...
#### Here is how we can solve this problem: Suppose the problem was simply
named Non-decreasing
184.
TheForces Round #26 Editorial [problem:104802A] Writer: [user:wuhudsm,2023-11-14]
<spoiler summary="Editorial">
We use two pointers to solve this problem.
Set $l=1$ and $r=n$ initially.
- If $a_l=a_r$, <code>l++,r--;</code>
- If $a_l<a_r$,split $a_r$ into $a_r-a_l$ and $a_l$, <code>r--;</code>
- If $a_l>a_r$,split $a_l$ into $a_r$ and $a_l-a_r$, <code>l++;</code>
When $l \geq r$,the process ends.
</spoiler>
<spoiler summary="Rate the problem">
Good problem! :
Average problem :
Bad problem... :
</spoiler>
[problem:104802B] Writer: [user:pavlekn,2023-11-14]
<spoiler summary="Editorial">
Let $M$ be the initial mass of the bus with all passengers: $M = w + \sum_{i = 1}^{n}{m_i}$. Let $F$ be the total force of the pushers, initially, $F=0$.
Imagine getting out the $i$-th passenger out of the bus, then $M$ is decreased by $m_i$, while $F$ is increased by $f_i$. Hence, $M - F$ is decreased by $m_i + f_i$. Clearly, we want to make ...
[problem:104802A] Writer: [user:wuhudsm,2023-11-14] We use two
Tutorial of TheForces Round #26 (Readall-Forces)
185.
Spectral::Cup 2026 Round 2 (Codeforces Round 1100, Div. 1 + Div. 2) Editorial Thank you for participating in our round! We hope you enjoyed the problems as much as we enjoyed preparing them.
<spoiler summary="Rate the contest!">
<spoiler summary="Quality">
-
Absolute Cinema contest
-
Excellent contest
-
Good contest
-
Average contest
-
Bad contest
-
Horrible contest
</spoiler>
<spoiler summary="Difficulty">
-
Trivial contest
-
Easy contest
-
Average contest
-
Hard contest
-
Impossible contest
</spoiler>
</spoiler>
[problem:2229A]
Idea by: [user:Intellegent,2026-05-23]
Prepared by: [user:Intellegent,2026-05-23]
Editorial by: [user:reirugan,2026-05-23]
<spoiler summary="Hint 1">
Let $y$ denote the final position of all of the slimes. Then it is optimal to choose $x = y$ for every operation.
</spoiler>
<spoiler summary="Hint 2">
Let $\mathrm{mn}$ denote the minimum value in $a$, a...
> [problem:2229A] Idea by: [user:Intellegent,2026-05-23] Prepared by
186.
Request for Solutions to few problems stated Below! Hello community,
Recently I cam across 4 questions(A hiring challenge from Hacker Earth which is over now!) to which I could not find solutions. I tried my best during contest to come with solutions but I was unable to do so. It would be great if you guys could help me provide a solution for these problems(also a generic solution for similar kind of problems) Would really help me a lot. I dont remember the exact problem but I would try to provide the best description to my knowledge.
Problem 1:
` We have to distribute N coins to S students such that each gets distinct number of coins while maximizing S. We have to find S. For eg. if N is 5 then S is 2 because (2,3). Its not mandatory to distribute all N coins. `
<spoiler summary="My Idea">
I was able to think of it as a pattern but I'm not sure if its right or wrong.
0=>0
1=>1 2
2=>3 4 5
3=>6 7 8 9
4=>10 11 12 13 14
and so on
I was trying to preprocess it but ended up with TLE anybody could tell me h...
`Given a string s we need to find two subsequence s1=s2 and maximize |s1+s2|.
For eg: aabababb the
187.
Codeforces Round 979 Editorial Below is a timeline of the changes made to the round from start to finish. I hope this can depict what setting a contest is actually like for aspiring problemsetters. Please give me feedback about this in the comments. What else about the round would you like to know? Was this helpful?
<spoiler summary="Round Timeline">
To denote problems, I will use quotes to denote the number of problems proposed for that postion so far (e.g. A' represents the first A proposed for the round, A'' represents second A proposed, etc). If the problem is in the final set, then it will be **bolded**. For dates, I will use the american standard notation (mm/dd).
Also, I will not go in detail about why problems were rejected/unused because they might appear in the future.
8/11: [contest:1998] has just concluded and [user:sum,2024-10-18] has shipped himself off to college and won't have time due to <s>attending frat parties</s> his studies. I invite [user:vgoofficial,2024-10-18] to problemset with m...
'' represents second A proposed, etc). If the problem is in the final set, then
it will be **bolded**. For dates
Tutorial of Codeforces Round 979 (Div. 2)
188.
USACO - Dynamic Programming - Maximum Decreasing Subsequence I've confused with the code that is written in the TEXT Dynamic Programming section of USACO Training about a classical problem (Finding Maximum Decreasing Subsequence). This is <a href="http://www.dcc.fc.up.pt/~pribeiro/estagio2008/usaco/2_2_Dynamic_Programming.htm">Article Link</a>. Please help me to get it!
Here's the code:
~~~~~
1 #include <stdio.h>
2 #define MAXN 200000
3 main () {
4 FILE *in, *out;
5 long num[MAXN], bestrun[MAXN];
6 long n, i, j, highestrun = 0;
7 in = fopen ("input.txt", "r");
8 out = fopen ("output.txt", "w");
9 fscanf(in, "%ld", &n);
10 for (i = 0; i < n; i++) fscanf(in, "%ld", &num[i]);
11 bestrun[0] = num[n-1];
12 highestrun = 1;
13 for (i = n-1-1; i >= 0; i--) {
14 if (num[i] < bestrun[0]) {
15 bestrun[0] = num[i];
16 continue;
17 }
18 for (j = highestrun - 1; j >= 0; j--) {
19 if (num[i] > bestrun[j]) {
20 ...
USACO - Dynamic Programming - Maximum Decreasing Subsequence, Training about a classical problem (Finding Maximum Decreasing Subsequence).
This is
189.
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...
Common Subsequence Problem](https://www.techiedelight.com/longest-common-
subsequence/) 3. [Maximum, . [Longest Common Subsequence Problem
](https://www.techiedelight.com/longest-common-subsequence/) 3
190.
Editorial PLC TOC 16 Stage II I made this draft 7 months ago and I haven't published it. I went into some form of depression (cuz of the my stupidity in the final) so I got embarrassed to publish anything about it. But I spent a lot of time in this and since I don't care that much anymore, I'll publish this anyway. Hope you enjoy!
A couple of MHT students in Indonesia decided to hold a contest for local Competitive Programming students. It is called PLC TOC 16 and it is inspired by PLC TOC 12. We have prepared original problems for this contest. For people who want to see the problems, it can be seen through links in the editorial. Here is the editorial.
[Problems](https://codeforces.me/contestInvitation/dc0ff68270b387e43fb62f61d05ae4a90556e213)
[A. PLC Maximum GCD Subarray](https://codeforces.me/gym/670273/problem/A)
<spoiler summary="Subtask 1">
<spoiler summary="Hint 1">
How many possible subarrays are there in an array sized $n$?
<spoiler summary="Answer">
There is a maximum amount of $n^2...
handle. However, the problem doesn't ask for the chosen subsequence but the
score itself. Can we
191.
Theoretical grounds of lambda optimization Hi everyone!
This time I'd like to write about what's widely known as "Aliens trick" (as it got popularized after 2016 IOI problem called [Aliens](https://ioinformatics.org/files/ioi2016problem6.pdf)). There are already some articles about it here and there, and I'd like to summarize them, while also adding insights into the connection between this trick and generic Lagrange multipliers and Lagrangian duality which often occurs in e.g. linear programming problems.
Familiarity with a [previous blog](https://codeforces.me/blog/entry/98524) about ternary search or, at the very least, definitions and propositions from it is expected.
Great thanks to [user:mango_lassi,2022-01-01] and [user:300iq,2022-01-01] for useful discussions and some key insights on this.
Note that although explanation here might be quite verbose and hard to comprehend at first, the algorithm itself is stunningly simple.
Another point that I'd like to highlight for those already familiar with "Aliens tr...
popularized after 2016 IOI problem called
[Aliens](https://ioinformatics.org/files/ioi2016problem6
192.
Editorial for CodeHurdle Athlos 02 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/c9482c2d71d0b5cdc04841221671e06b827c1e07)
### [A — Costly Divisibility](https://codeforces.me/gym/670769/problem/A)
Writer: [user:amartya110,2026-01-19]
<spoiler summary="Editorial">
In this case any $a[i]>=b[i]$ for all $(1<=i<=n)$, you can easily make a[i]%b[i]==0 by decreasing the value of a[i] or increase the value of b[i] with cost 0, and otherwise the cost is the absolute difference between a[i] and b[i].
</spoiler>
<spoiler summary="Solution">
```c++
#include <bits/stdc++.h>
using namespace std;
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define testcase int t; cin>>t; for(int i=0;i<t;i++)
#define ll long long int
ll lcm(ll a, ll b) {
return (a / __gcd(a, b)) * b;
}
void solved(){
/*start*/
ll n;
cin>>n;
vecto...
largest possible subsequence we can form consists of all integers $x \in [l,
r]$ such that $x \text
193.
[Solution] Problem 1418C Mortal Combat Tower ## CF: Mortal Combat Tower
[problem:1418C]
[Problem — 1418C — Codeforces](https://codeforces.me/problemset/problem/1418/C)
Simple problem.... but solution 1 took me a long time to debug, mainly because there was a sneaky hidden bug
### Solution 1: DP
Simple brute force memoization search of all cases:
State: $dp[i][j]$ means at position $j$ when switched to player $i\in[0,1]$ (0=my friend, 1=me), the minimum skip points used. So the answer is $min(dp[0][n],dp[1][n])$, checking at the end which player's side has the minimum skip points.
Initial state: $dp[1][0]=0$ means if switched to me at position 0 (although impossible since friend starts first), then 0 skip points were used.
Code:
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int test_case_num;
cin >> test_case_num;
for (int t = 0; t < test_case_num; t++) {
int n;
cin >> n;
vector<int> bosses(n);
for (int j = 0; j < n;...
[Solution] Problem 1418C Mortal Combat Tower, subsequence of $k$ consecutive 1s, minimum skip points needed is $\lfloor
\frac{k}{3} \rfloor$. So, just count
194.
UVA problem seemingly above the State of the Art I stumbled upon [UVA Summing the Lengths of the Longest Increasing Subsequence of Permutations](https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2247), that basically asks for the first three digits of the sum of the LIS lengths over all permutations of length $n$. After trying it or a few days, I gave up and searched for information. It is easy to see that:
$$\sum_{w\in permutations(1,2,..,n)} LIS(w)= \mathbb E(LIS(w))\times n!$$
Where $\mathbb{E}$ denotes the expected value. It is easy to manage the logarithm of that number with Stirling's approximation, get the fractional part of the logarithm and exponentiate to get the first digits. Nevertheless the core of the problem lies in computing $\mathbb{E}(w)$ for a random permutation $w$ of length $n$. I have been reading about the topic, and [this paper](http://stanford.edu/~mikep15/mike_math310_report.pdf) gives the estimate
$$\mathbb{E}(w)=2\sqrt{n}+cn^{1/6}+o(n^{1/6})$$
Where $c\approx -1.77108$ ...
UVA problem seemingly above the State of the Art, I stumbled upon [UVA Summing the Lengths of the Longest Increasing Subsequence
of Permutations
195.
Editorial for Codeforces Round #910 (Div. 2) ## [1898A *-* Milica and String](https://codeforces.me/contest/1898/problem/A)
Author: [user:n0sk1ll,2023-10-01]
<spoiler summary="Hint">
In one move, Milica can replace the whole string with $\texttt{AA} \ldots \texttt{A}$. In her second move, she can replace a prefix of length $k$ with $\texttt{BB} \ldots \texttt{B}$. The process takes no more than $2$ operations. The question remains — when can we do better?
</spoiler>
<spoiler summary="Solution">
In the *hint* section, we showed that the minimum number of operations is $0$, $1$, or $2$. We have $3$ cases:
0. No operations are needed if $s$ already contains $k$ characters $\texttt{B}$.
1. Else, we can use brute force to check if changing some prefix leads to $s$ having $k$ $\texttt{B}$s. If we find such a prefix, we print it as the answer, and use only one operation. There are $O(n)$ possibilities. Implementing them takes $O(n)$ or $O(n^2)$ time.
2. Else, we use the two operations described in the hint se...
## [1898A *-* Milica and String](https://codeforces.me/contest/1898/problem/A)
Author
Tutorial of Codeforces Round 910 (Div. 2)
196.
Exploring Dynamic Programming: A Comprehensive Guide Hey Codeforces community! Today, let's dive deep into the fascinating world of Dynamic Programming (DP). Whether you're a beginner looking to grasp the basics or an experienced coder seeking advanced techniques, this guide aims to provide a comprehensive overview of DP concepts and applications.
**What is Dynamic Programming?**
Dynamic Programming is a powerful algorithmic technique used to solve problems by breaking them down into simpler subproblems and storing the solutions to these subproblems to avoid redundant calculations. It's particularly useful for optimization problems where we seek to maximize or minimize certain criteria.
**Basic Concepts**
1. Memoization vs. Tabulation: Discuss the two main approaches to implementing DP — memoization (top-down) and tabulation (bottom-up)
2.State Definition: Explain what a "state" means in DP and how to define it based on the problem's constraints.
3. Transition Function: Illustrate how to derive the transition fu...
- Longest Common Subsequence - Knapsack Problem 2. **Optimization vs. Decision
Problems:** Differentiate
197.
How do you personally approach dynamic programming problems? I've always found pure dynamic programming problems to be easier than pure greedy problems (at the same rating) and I don't really understand why. I wonder if other people feel the same.
When I have a solution for a DP problem, it just... makes sense. I don't really understand how the states and the recurrences come up in my mind, but it feels really intuitive. When I try to explain my solution to a student, for example, I just get stumped. I can't find an easy, step-to-step approach for explaining it (I'm a tutor and it really annoys me).
It was just an "Eureka!" moment for me (I solved a couple of problems by myself a long time ago, and from then on, it became easy) and I didn't overthink it until now.
For context, I've never watched tutorials / been taught by someone, I just knew the solution for the maximum non-increasing subsequence problem and that's it.
When explaining, I always try to answer myself this questions:
* Why are there $n$ states? Why do we need all of...
the maximum non-increasing subsequence problem and that's it.
198.
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...
Problem Insight The values in the array are small, specifically in
199.
Editorial For Code-X-Culture 24 We want to extend our heartfelt gratitude to each and every one of you for participating in Code-X-Culture, our online coding event. Your enthusiasm, dedication, and creativity have made this event a remarkable success. We hope you enjoyed solving the questions as much as we enjoyed creating them for you.
A: RRR (Robbery Edition)
----------------------
Idea:[user:rachitkansal,2024-06-21]
<spoiler summary="Solution">
Since there is a difference of 3 coins generated every day, the answer can be calculated using the formula
$(a−b+2)/3$.
</spoiler>
<spoiler summary="Author's Code (C++)">
~~~~~
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int x,y;
cin>>x>>y;
cout<<(y-x+2)/3<<endl;
}
}
~~~~~
</spoiler>
B: Hridyansh's Dilemma
----------------------
Idea:[user:warmachineg,2024-06-21]
<spoiler summary="Hint 1">
Think about maintaining a running total of the money accumulate...
Lets just reverse the problem and length of longest palindromic
200.
Tutorial — codeforces problem 597C Subsequences http://codeforces.me/problemset/problem/597/C [Codeforces contest](http://codeforces.me/contest/597)[user:uditgupta][submission:27884973][problem:http://codeforces.me/problemset/problem/597/C]-Consider for index ith
-Now at each index we want to find number of subsequences ending at index i
of length 1 , 2 , 3 ... k+1 ;
How we can compute this ?
say arr[i] == 5
if know number of subsequences which end at value either 1 or 2 or 3 or 4
from index 1 to index i+1
pls read above lines again if not clear.
so now wat the equation becomes
no of subsequences of length k+1 which end at index i=
number of subsequences of length k which end at [value 1] from index range 1 to (i-1) of given array
+ number of subsequences of length k which end at [value 2] from index range 1 to (i-1) of given array
+ number of subsequences of length k which end at [value 3] from index range 1 to (i-1) of given array
+ number of subsequences of length k which end at [value 4] from index range...
Tutorial — codeforces problem 597C Subsequences
http://codeforces.me/problemset/problem/597/C, ][problem:http://codeforces.me/problemset/problem/597/C]-Consider for index
ith -Now at each index we
201.
DE Shaw Online Assessment (OA) – IIT Bhubaneswar (2026) (Technology Developer Intern) This is a write-up of the DE Shaw Online Assessment for the SDE Intern 2026 role. The assessment consisted of 3 DSA problems with separate timers.
FORMAT
------------------
- 3 programming questions
- Separate timers for each question:
- Q1: 15 minutes
- Q2: 35 minutes
- Q3: 40 minutes
Questions had to be attempted in order.
No ability to return to a previous question.
Any unused time from one question could not be carried forward.
Problem 1: Good Trace(15 min)
==================
A string is called a good trace if it can be generated using the following rules:-
- The empty string is a good trace.
- If t is a good trace and c is any lowercase English letter, then adding c to both the beginning and the end of t also produces a good trace.
- Example:
— "" → "aa"
— "bb" → "cbbc"
- The concatenation of two good traces is also a good trace.
You are given m strings (m ≤ 10, total length up to 10^5). For each string, determine whether it is ...
Problem 2: Number of Subsequences (35 mins) ------------------ Given:
202.
Codeforces Round 1064 (Div. 1, Div. 2) Editorial [2166A — Same Difference](https://codeforces.me/contest/2166/problem/A)
idea & solution: [user:le0n,2025-11-17]
<spoiler summary="Tutorial">
It can be observed that $s_n$ will not change throughout the operations, therefore, for the final string to have every character the same, every character must be equal to $s_n$.
To change every character to $s_n$, we can iterate over all characters from right to left, repeatedly setting $s_{i-1}\leftarrow s_i$ if $s_{i-1}\neq s_n$. Through this, we can need one operation for every character not equal to $s_n$, which is also obvious as a lower bound.
Time complexity: $O(n)$.
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
char s[100005];
int main()
{
int n, t, i, m;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
scanf("%s", s + 1);
m = 0;
for(i = 1; i < n; i++)
m += (s[i] != s[n]);
printf("%d\n", m);
}
return 0;
}
~~~~~
</spoiler>
...
[2166A — Same Difference](https://codeforces.me/contest/2166/problem/A) idea &
solution
Tutorial of Codeforces Round 1064 (Div. 1)
Tutorial of Codeforces Round 1064 (Div. 2)
203.
Codeforces Round #777 Editorial Task A. Idea [user:FairyWinx,2022-03-11]
<spoiler summary="Hint 1">
The optimal answer has the maximum number of digits, so you only need to use the digits $1,2$.
</spoiler>
<spoiler summary="Hint 2">
Alternate these numbers so that there are no adjacent identical numbers.
</spoiler>
<spoiler summary="Solution">
Since we want to maximize the number we need, we will first find the longest suitable number. Obviously, it is better to use only the numbers $1$ and $2$ for this. Therefore, the answer always looks like $2121\ldots$ or $1212\ldots$. The first option is optimal when $n$ has a remainder of $2$ or $0$ modulo $3$, otherwise the second option is optimal.
Below is an example of a neat implementation.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
int type;
if (n % 3 == 1)
type = 1;
else
type = 2;
int sum = 0;
while (sum != n) ...
if the answer to the problem is "YES". Think about a
Tutorial of Codeforces Round 777 (Div. 2)
204.
Problemsetting Goal Since goals are very important in any individual's life, I decided to **set** a goal for myself. The target is to **set** 100 problems until I quit cp.
Current progress: **40**
| # | Date | <center>Problem</center> | <center>Contest</center> | <center>Difficulty</center> | Comments | Feedback |
|----|---------------|----------------------------------------------------------------------------------------------|-----------------------------------------------------------------|-----------------------------------------------...
| [**Largest Subsequence**](https://codeforces.me/contest/1905/problem/C, >[**Largest Subsequence**](https://codeforces.me/contest/1905/problem/C) |
Codeforces
205.
DP Examples — Full Explanation ## 1. Fibonacci
**Idea:** Each number is the sum of the two before it.
```
0, 1, 1, 2, 3, 5, 8, 13, ...
```
```cpp
fib[1] = 0, fib[2] = 1;
for (int i = 3; i <= n; i++) fib[i] = fib[i-1] + fib[i-2];
```
**Trace for n=6:**
```
fib[1] = 0
fib[2] = 1
fib[3] = fib[2] + fib[1] = 1+0 = 1
fib[4] = fib[3] + fib[2] = 1+1 = 2
fib[5] = fib[4] + fib[3] = 2+1 = 3
fib[6] = fib[5] + fib[4] = 3+2 = 5
```
**Why DP?** You reuse previously computed values instead of recalculating recursively every time.
---
## 2. Number of Ways (Staircase)
**Problem:** You're on step `s`, want to reach step `e`. Each move you can jump +1, +2, or +3 steps. How many ways?
```cpp
dp[s] = 1; // one way to be at start
for (int i = s+1; i <= e; i++) {
if (i-1 >= s) dp[i] += dp[i-1]; // came from 1 step back
if (i-2 >= s) dp[i] += dp[i-2]; // came from 2 steps back
if (i-3 >= s) dp[i] += dp[i-3]; // came from 3 steps back
}
```
**Trace for s=0, e=4:**
...
**Problem:** Given an array, find the length of the longest subsequence where
each element is
206.
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...
. DNA sequencing in bioinformatics uses the same longest common subsequence
(LCS) and sequence
207.
Preparing For Olympiads Contest 2 Editorial [A-Luck](https://codeforces.me/gym/279477/problem/A)(author [user:Halit,2020-05-15]):
<spoiler summary="Solution">
Simply we should select maximum number and we should print:
value (number_of_value / n). If we select all (values) we can reach maximum possibility
</spoiler>
code by [user:Halit,2020-05-15]
<spoiler summary="code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d", &n);
int arr[n+1];
for(int i = 1;i <= n;i++)
scanf("%d", arr + i);
map<int, int> h;
int maxim = -1;
for(int i = 1;i <= n;i++){
maxim = max(arr[i], maxim);
h[arr[i]]++;
}
printf("%d %.2f", maxim , (double)h[maxim]/n);
}
~~~~~
</spoiler>
[B-)Find the missed number](https://codeforces.me/gym/279477/problem/B)(author [user:Halit,2020-05-15])
<spoiler summary="Solution">
So, Simply we should assign leaf nodes to 2 and multiply it with other children, do it step by step, because lea...
In this problem you will erase some letters. So when you found a
208.
Codeforces Round 1008 (Div. 1, Div. 2) Editorial I hope everyone enjoyed the tasks, and thank you for participating.
Thank you to the coordinators and testers for suggesting solutions and modifications to the tasks, as I alone wouldn't be able to solve my own tasks or make it to how it is right now. Also thank you to them for dealing with me since July.
Please tell me in the comments if the editorial is written incorrectly or unintelligibly somewhere. I'm not the best at phrasing some things, and would appreciate amendments to the editorial.
[problem:2078A]
<spoiler summary="Hint">
Something doesn't change after each operation.
</spoiler>
<spoiler summary="Solution">
The average of the entire array doesn't change after each operation. Simply check whether the average value of $a$ is $x$ or not.
Time complexity: $\mathcal{O}(n)$ per test case.
Submission: [submission:310297520]
</spoiler>
[problem:2078B]
<spoiler summary="Hint 1">
Try to put as many people in cell $n$ as possible.
</spoiler>
<spoile...
editorial. [problem:2078A] Something doesn't change after each operation
Tutorial of Codeforces Round 1008 (Div. 1)
Tutorial of Codeforces Round 1008 (Div. 2)
209.
Codeforces Round #757 (Div. 2) Editorial [A. Divan and a Store](https://codeforces.me/contest/1614/problem/A)
<spoiler summary="Solution">
To solve this problem, let's use the following greedy algorithm.
Let's sort the prices of chocolate bars in increasing order, after which we will go from left to right and take chocolates that have a price not less than $l$, but not more than $r$ until we run out of money.
The number of chocolate bars that we took will be the answer to the problem.
The resulting asymptotics in time: $\mathcal{O}(n\log{}n)$.
</spoiler>
[B. Divan and a New Project](https://codeforces.me/contest/1614/problem/B)
<spoiler summary="Solution">
Obviously, the more often we have to go to the $ i $ building, the closer it should be to the main office.
This implies a greedy algorithm. Let's put the main office at $0$ and sort the rest by $a_i$. Then we put the most visited building at a point with a coordinate of $1$, the second at $-1$, the third at $2$, etc.
The resulting asymptotics ...
[A. Divan and a Store](https://codeforces.me/contest/1614/problem/A)
Tutorial of Codeforces Round 757 (Div. 2)
210.
Codeforces Round #321 Editorial [problem:580A]
Note, that if the array has two intersecting continuous non-decreasing subsequence, they can be combined into one. Therefore, you can just pass the array from left to right. If the current subsequence can be continued using the $i$-th element, then we do it, otherwise we start a new one. The answer is the maximum subsequence of all the found ones.
Asymptotics — $O(n)$.
[Solution](http://ideone.com/dIGhiB)
[problem:580B]
At first we sort all friends in money ascending order. Now the answer is some array subsegment. Next, we use the method of two pointers for finding the required subsegment.
Asymptotics — $O(n$ $log$ $n)$.
[Solution](http://ideone.com/k4Hlxv)
[problem:580C]
Let's go down the tree from the root, supporting additional parameter $k$ — the number of vertices in a row met with cats. If $k$ exceeds $m$, then leave. Then the answer is the number of leaves, which we were able to reach.
Asymptotics — $O(n)$.
...
[problem:580A] Note, that if the array has two intersecting continuous
non-decreasing
Tutorial of Codeforces Round 321 (Div. 2)
211.
Codeforces Round #271 (Div. 2) Editorial [problem:474A]
This is an implementation problem, therefore most of the solution fit in the time limit. We can even save the keyboard in $3$ strings and make a brute force search for each character to find its position and then print the left/right neighbour.
[problem:474B]
There are two solutions:
1. We can make partial sums ($sum_i = a_1 + a_2 + \dots + a_i$) and then make a binary search for each query $q_i$ to find the result $j$ with the properties $sum_{j-1} < q_i$ and $sum_j \geq q_i$. This solution has the complexity $O(n + m \cdot log(n))$
2. We can precalculate the index of the pile for each worm and then answer for each query in $O(1)$. This solution has the complexity $O(n + m)$
[problem:474C]
For each $4$ points we want to see if we can rotate them with $90$ degrees such that we obtain a square. We can make a backtracking where we rotate each point $0, 1, 2$ or $3$ times and verify the figure obtained. If it's a square we update the minimal solution. S...
))$. [problem:474F] For each subsequence $[L, R]$ we must find how many queens
we have. A value is
Tutorial of Codeforces Round 271 (Div. 2)
212.
Editorial of Codeforces Round 975 (Div. 1, Div. 2) All the Polygon materials (including the official implementations of all the problems) are [here](https://drive.google.com/file/d/1zWk5N_iF3TWbzzab5IAIza78_FohSZtP/view?usp=sharing).
[problem:2019A]
Author: [user:TheScrasse,2024-09-27]<br>
Preparation: [user:TheScrasse,2024-09-27]
<spoiler summary="Hint 1">
Can you reach the score $\max(a) + \lceil n/2 \rceil$?
</spoiler>
<spoiler summary="Hint 2">
Can you reach the score $\max(a) + \lceil n/2 \rceil - 1$?
</spoiler>
<spoiler summary="Solution">
The maximum red element is $\leq \max(a)$, and the maximum number of red elements is $\lceil n/2 \rceil$. Can you reach the score $\max(a) + \lceil n/2 \rceil$?
- If $n$ is even, you always can, by either choosing all the elements in even positions or all the elements in odd positions (at least one of these choices contains $\max(a)$).
- If $n$ is odd, you can if and only if there is one occurrence of $\max(a)$ in an odd position. Otherwise, you can choose even position...
](https://drive.google.com/file/d/1zWk5N_iF3TWbzzab5IAIza78_FohSZtP/view?usp=sharing).
[problem
Tutorial of Codeforces Round 975 (Div. 1)
Tutorial of Codeforces Round 975 (Div. 2)
213.
Codeforces Round #256 — Editorial [problem:448A]
Solution:[submission:7139559]
Because rewards of one type can be on one shelf, lets calculate number of cups — $a$ and number of medals — $b$. Minimum number of shelves that will be required for all cups can be found by formula $(a + 5 - 1) / 5$. The same with shelves with medals: $(b + 10 - 1) / 10$. If sum of this two values more than $n$ then answer is "NO" and "YES" otherwise.
[problem:448B]
Solution:[submission:7139584]
Consider each case separately. If we use only suffix automaton then $s$ transform to some of its subsequence. Checking that $t$ is a subsequence of $s$ can be performed in different ways. Easiest and fastest — well-known two pointers method. In case of using suffix array we can get every permutation of $s$. If it is not obvious for you, try to think. Thus, $s$ and $t$ must be anagrams. If we count number of each letter in each string, we can check this. If every letter appears in $s$ the same times as in $t$ then word...
[problem:448A] Solution:[submission:7139559] Because rewards of one type can be
on one shelf
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/03/2026 19:33:07 (g2).
Desktop version, switch to mobile version.
Supported by
