Catching the Mole (Psychotic_D cheating accusation) Hello codeforces! You guys must have seen the recent blog accusing international master [user:Psychotic_D,2024-07-23] of cheating in the most recent div2 round: [Codeforces Round 960 (Div. 2)](https://codeforces.me/contest/1990). This is due to the fact that the author, [user:wuhudsm,2024-07-23] is [user:Psychotic_D,2024-07-23]'s friend and that [user:Psychotic_D,2024-07-23] had a ridiculous performance, winning the amongst official participants.  They are both big members of [TheForces](https://theforces.netlify.app/), raising suspicions of whether there was some collusions between the two. At first i thought it was nonsense since the evidence was lacking, but after a bit of my own investigation I've compiled the most interesting pieces of evidence of why i believe [user:Psychotic_D,2024-07-23] (along with some accomplices from TheForces) is in fact a cheater. Case #1: Introduction ------------------ I first learned about the sub...

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

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

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

Meet IT Codeforces Round Editorial Thank you very much for taking part in the contest! <spoiler summary="Contest timeline"> - -0:05. Starting the chat with the Questions Answering team: [user:tnowak,2020-11-15] and our beloved coordinator [user:antontrygubO_o,2020-11-15]. We hope that there won't be that many questions :) - -0:01. One minute to go! I hope that everything goes smoothly. I'm so afraid of posting the editorial accidentally that I moved this timeline into another blog... - 0:01. First blood in Div2! Congratulations to [user:majorro,2020-11-15]!. - 0:03. First blood in Div1 as well! Congratulations to [user:Errichto,2020-11-15], your knapsack is ready for a journey to win! - 0:04. [user:Sho10,2020-11-15] first to solve Div2B. Well done! - 0:05. We also have the first question. So far so good... - 0:06. [user:Um_nik,2020-11-15] gets the first pretests pass in Div1B. The cheaters are caught! - 0:09. [user:bandiaoz,2020-11-15] packs the first Knapsack in Div2! A difficulty spike is coming... - 0:12....

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

Unofficial Editorial for Educational Round 95 (Div. 2) Here are my approaches to the problems today: #### [problem:1418A] Since the second trade is the only way to get coal, we clearly need to perform the second trade $k$ times. So how many times do we need to do the first trade? We can see that in order to end up with enough sticks and coal by the end, we need to obtain $ky + k$ sticks ($ky$ to convert to coal and $k$ to save as sticks). Since the first trade really just gives us $x - 1$ new sticks each time, we'll need to make $\displaystyle \left \lceil \frac{ky + k - 1}{x - 1} \right \rceil$ first trades ([reference to floor and ceiling functions](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) for anyone unfamiliar). For implementation details, note that for positive integers $a$ and $b$, $\displaystyle \left \lceil \frac{a}{b} \right \rceil = \left \lfloor \frac{a + b - 1}{b} \right \rfloor$. Code: [submission:92851684] #### [problem:1418B] We can think about the problem as follows: we want to order the $a_i$ to...

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

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

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

Mo's Algorithm on Trees [Tutorial] Introduction ------------ Mo's Algorithm has become pretty popular in the past few years and is now considered as a pretty standard technique in the world of Competitive Programming. This blog will describe a method to generalize Mo's algorithm to maintain information about paths between nodes in a tree. Prerequisites ------------- Mo's Algorithm &mdash; If you do not know this yet, read this amazing [article](http://blog.anudeep2011.com/mos-algorithm/) before continuing with this blog. Preorder Traversal or DFS Order of the Tree. Problem 1 &mdash; Handling Subtree Queries ------------------------------------------ Consider the following problem. You will be given a rooted Tree $T$ of $N$ nodes where each node is associated with a value $A[node]$. You need to handle $Q$ queries, each comprising one integer $u$. In each query you must report the number of distinct values in the subtree rooted at $u$. In other words, if you store all the values in the subtree rooted...

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

Editorial of DeepInfra Round 1 (Codeforces Round 1126, Div. 1 + Div. 2) thanks to [user:nifeshe,2026-10-10] for making my life easier with templates [problem:2271A] <spoiler summary = "Hints"> <spoiler summary = "Hint 1"> After performing $z$ operations, the robot's $x$-coordinate is exactly $z$. </spoiler> <spoiler summary = "Hint 2"> After completing any operation, the $x$-coordinate and $y$-coordinate always have the same parity. </spoiler> <spoiler summary = "Hint 3"> Try to find a construction to reach any point $(x,y)$ where $y\le x$ and $x$ and $y$ have the same parity. </spoiler> </spoiler> <spoiler summary = "Solution"> Notice that after performing $z$ operations, the robot's $x$-coordinate will be exactly $z$, while its $y$-coordinate cannot exceed $z$. We will first consider the case $b\le a$, then handle the special case $b=a+1$. Notice that the robot can reach any point $(x,y)$ where $0\le y\le x$ and $x$ and $y$ have the same parity in exactly $x$ operations. To do so, we can first move up until reaching $y$...

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

Unofficial Editorial for Round 532 (Div. 2) Just finished this contest in virtual mode and noticed the editorial is missing, so I thought I would share my approaches. #### [problem:1100A] Loop over all values of $b$ and take the sum of all indices that are not equivalent to $b \bmod k$. Remember to take the absolute value at the end. Runtime is $\mathcal{O}(n^2)$. Code: [submission:48374675] #### [problem:1100B] Maintain a frequency array of size $n$ and track the number of distinct values seen so far as we loop through the array. Once the number of distinct values reaches $n$, we hold a round and decrement each index of the frequency array. Note that this takes $n$ time, but this is fine since we can only hold at most $\displaystyle \frac{m}{n}$ rounds. Runtime is $\mathcal{O}(m)$. Code: [submission:48374608]. Note that `x++` means use the value of `x` and then increment, whereas `++x` means increment and then use. Similar for `x--` and `--x`. #### [problem:1100C] Draw the line segments between the center of the inn...

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

Gale-Ryser Theorem _This blog is a submission for the [Third Codeforces Month of Blog Posts](https://codeforces.me/blog/entry/149422), thanks to [user:cadmiumky,2026-02-10] for the initiative!_ _Thanks to [user:TeaTime,2026-02-10] and [user:k1r1t0,2026-02-10] for giving feedback on the post._ --- Hi everyone! I want to talk about Gale-Ryser Theorem and some of its applications. I've provided proofs for each fact in the blog, they're hidden under the spoilers. --- Gale-Ryser Theorem ================== We have an array of $n$ non-negative integers $a_1, a_2, \ldots, a_n$ and an array of $m$ positive integers $b_1, b_2, \ldots, b_m$, $b_i \le n$. The array $b$ describes a sequence of operations, in the $i$-th operation we need to decrease the values at $b_i$ positions by $1$, formally pick $b_i$ unique indices $j_1, j_2, \ldots, j_{b_i}$ and decrease $a_{j_p}$ by $1$ for $1 \le p \le b_i$. We want to know if it's possible to have all $a_i \ge 0$ after the operations. Without loss o...

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

Codeforces Round #934 (Div1, Div2) Editorial Sorry for the delay in publishing the editorial. If anything is unclear or missing, please let me know in the comments. In all the problems, reading the hints is a must as the solution continues from there. [problem:1944A] Idea: [user:Dominater069,2024-03-17] Preparation: [user:Dominater069,2024-03-17] Editorial: [user:Dominater069,2024-03-17] <spoiler summary="Hint 1"> What is the minimum number of bridges to burn if we want to make exactly $i$ islands visitable from $1$? </spoiler> <spoiler summary="O(n) Solution"> Atleast $i \cdot (n - i)$ bridges need to burnt (the bridges connecting the $i$ reachable islands and the $n - i$ non-reachable islands). A simple $O(n)$ solution is for every $i$ from $1$ to $n$, check if $i \cdot (n - i) \le k$, in which case print $i$ and break. </spoiler> <spoiler summary="Hint 2"> What is the answer when $k \ge n - 1$. </spoiler> <spoiler summary="Hint 3"> When $k < n - 1$, is it possible to make any island non-...

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

Codeforces Round 987 (Div. 2) Editorial <spoiler summary="A little backstory about the round (ACGN)">The Highschool CPers (HSCP) Discord server was created in April 2022 by [user:pwned,2024-11-14], which over time grew into a close-knit community of highschool competitive programmers. I joined in the same month of its creation, and in the next month I approached [user:pwned,2024-11-14] about the possibility of setting a contest. Thus the HSCP round concept was born. Over the next month or so, the initial problems were born; the current problems A and F were produced in June-July 2022. We had several problem ideas by then, enough to set a div.2 round. However, as I was going to be busy in my 5th year of high school, and may not be that responsive to coordinators, the contest was in the ownership of [user:pwned,2024-11-14], who needed to wait until he reached master in order to propose the set on Codeforces. However, this step took almost 1.5 years as he would stay at candidate master for 57 consecutive contests, eve...

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

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

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

Codeforces Round #372 Editorial We hope everyone enjoyed the problems. Here is the editorial for the problems. I tried to make it more detailed but there might be some parts that might not be explained clearly. [Div. 2 A &mdash; Crazy Computer](http://codeforces.me/contest/716/problem/A) ------------------ Prerequisites : None This is a straightforward implementation problem. Iterate through the times in order, keeping track of when is the last time a word is typed, keeping a counter for the number of words appearing on the screen. Increment the counter by $1$ whenever you process a new time. Whenever the difference between the time for two consecutive words is greater than $c$, reset the counter to $0$. After that, increment it by $1$. Time Complexity : $O(n)$, since the times are already sorted. <spoiler summary="Code (O(n))"> ~~~~~ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #def...

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

Codeforces Round 1081 (Div. 2) Editorial [2192A &mdash; String Rotation Game](https://codeforces.me/contest/2192/problem/A) <spoiler summary="Hint 1"> By performing the operation, try to break a block into $2$ blocks. </spoiler> <spoiler summary="Solution"> The only way to increase the count of blocks is to break a block into $2$ blocks by performing an operation such that some characters of a block are present at the start of the string and some characters at the end of the string. For us to be able to achieve this, there must exist at least one block with a size greater than or equal to $2$. But, if in the original string, the first and the last character are already equal, this means a block is already broken into $2$ block (in some other rotation, it will be one block). Hence in this case the answer will be the score of the original string. Inshort, if first and the last character of the string are equal, or no $2$ adjacent characters are equal, then the answer will be score of the original string. Else the...

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

CSES Range Queries section editorial **UPD:** some video editorials on range query data structures: [youtubePlaylist](https://www.youtube.com/playlist?list=PLb3g_Z8nEv1isaHPaXL1j-pSo60812JtY) Hello Codeforces, In this blog I will try to write a well detailed editorial for the CSES Range Queries section. The motivation for this editorial comes from https://codeforces.me/blog/entry/70018. Quoting [user:icecuber,2020-05-09] "I think [CSES](https://cses.fi/problemset/) 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." So here I am writing an editorial for the range queries section. If you find any error or maybe have a better solution to some problem please do share. Range Sum Queries I =...

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

Codeforces Round 1066 (Div. 1 + Div. 2) Editorial [problem:2157A] Author: [user:TheScrasse,2025-11-22]<br> Preparation: [user:TheScrasse,2025-11-22] <spoiler summary="Hint 1"> Each value $x$ is independent of the others; only its own frequency matters. </spoiler> <spoiler summary="Hint 2"> In a balanced array, value $x$ must appear either $0$ times or **exactly** $x$ times. </spoiler> <spoiler summary="Solution"> - Each value $x$ is independent of the others; only its own frequency matters. In particular, for each value, find its frequency $f[x]$. - In a balanced array, value $x$ must appear either $0$ times or **exactly** $x$ times. Specifically, if it appears $< x$ times at the beginning, you have to delete all its occurrences, otherwise you should keep $x$ occurrences. Specifically, for each $x$, add $f[x]$ to the answer if $f[x] < x$, else add $f[x] - x$. Complexity: $O(n)$ time. Slower solutions (e.g., $O(n^2)$) are allowed. </spoiler> <spoiler summary = "Code"> [submission:350380351] </spoiler> [...

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

Editorial of Codeforces Round #768 ### [problem:1631A] Author: [user:humbertoyusta,2022-01-27] <spoiler summary="Hint 1"> Think about how $max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$ will contribute to the answer. </spoiler> <spoiler summary="Hint 2"> The maximum of one array is always $max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$. How should you minimize then? </spoiler> <spoiler summary="Solution"> Let $m_1 = \max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$. The answer will always be $m_1 \cdot m_2$ where $m_2$ is the maximum of the array that does not contain $m_1$. Since $m_1$ is fixed, the problem can be reduced to minimize $m_2$, that is, minimize the maximum of the array that does not contain the global maximum. WLOG assume that the global maximum will be in the array $b$, we can swap elements at each index $x$ such that $a_x > b_x$, ending with $a_i \leq b_i$ for all $i$. It can be shown that the maximum of array $a$ is minimized in this way. Time complexity: $O(n)$ <spoiler ...

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

Codeforces Round #662 (Div 2) Problems A-D Unofficial Editorial Hello everyone! At the time I am writing this, there is still no editorial for Round #662. I did very well on this contest and I think my solutions are interesting, so hopefully this can help some people. [problem:1393A]: <spoiler summary="Problem A"> Consider the center column (or column closest to the center if $n$ is even). For that column, you get closer to the center from the edge each time. For even columns, the first turn gets one block, while every turn after that gets two blocks, until the last turn, which fills in the last block, so that takes $\frac{n}{2}+1$ turns. For odd columns, every turn fills two blocks, except for the last turn, which fills in the last block, so that takes $\lfloor \frac{n}{2} \rfloor +1$ turns. The other columns are filled at least as fast. The answer is thus $\lfloor \frac{n}{2} \rfloor+1$. </spoiler> Code (Java): [submission:89214023] [problem:1393B]: <spoiler summary="Problem B"> There are a few different cases that would a...

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

[Tutorial] "1354D — Multiset" + A Gentle Introduction to Fenwick Trees (For the tutorial, skip to the second paragraph) The recently held [Educational Codeforces Round 87](https://codeforces.me/contest/1354) was full of controversies. The delay in its start, the overlap with Google Code Jam and then the many complaints that problems B, C1, C2 and D were all google-able! In particular, problem D was heavily criticised due to its strict memory limit which didn't help non-C++ users. The authors have given their reasons for this &mdash; to discourage the use of memory heavy data structures such as policy-based data structures (gnu pbds) and treaps. I personally found the contest to be "educational" indeed and I'm sure the same authors will now deliver even better contests in the future. Here I discuss the problem [D &mdash; Multiset](https://codeforces.me/contest/1354/problem/D) and some of the ways in which it could be solved. This blog is aimed at beginners. I hope to provide you with a gentle introduction to this fast and easy-to-implement data st...

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

Codeforces Round 1061 (Div. 2) Editorial ### Thank you for participating ! Special Thanks to [user:hxu10,2025-10-24] for giving me the chance to write the editorial and for [user:maomao90,2025-10-24] for enhancing the editorial !. Editorial of Problems E and F are written by hxu10, and the rest are written by me. I hope they're insightful and concise, please let me hear your opinion about it or any feedback in general &#128153;. #### [problem:2156A] <spoiler summary="Hints"> <spoiler summary="Hint 1"> Since $m_1 \le m_2$, the total number of slices Alice ate is always at least as much as the total number of slices Bob ate. What's optimal construction ? </spoiler> <spoiler summary="Hint 2"> We want to try to minimize the difference between the total number of slices Alice ate and the total number of slices Bob ate. </spoiler> <spoiler summary="Hint 3"> The optimal construction is to let both $m_1$ and $m_2$ to be equals to one. The sequence of operations, denoted by $(m_1, m...

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

Unofficial Div 4 Round #2 Editorial This is the editorial for the [contest:102873]. We hope everyone had fun and enjoyed the contest! [Video Editorial](https://youtu.be/FRWYFwSoiZw) by [user:demoralizer,2020-11-26] Problem A &mdash; Catching the Impostor. <spoiler summary="Tutorial"> Solution using frequency array: Initialize an array of length $n$ with all the elements 0. This will be our frequency array. For every element we have in our list, we increase its frequency by one in the frequency array, $freq[arr[i]]+=1$. After we do this, we iterate through the frequency array and see how many elements have a frequency higher than 0 (it means they were mentioned in the list), let this number be $cnt$. Now if $cnt = n-1$ them we know for sure that who is the impostor, because all the other people are mentioned in the list. If $cnt ≠ n-1$ then we can't for sure know who is the impostor, so the answer is no. Solution using set: We introduce all the elements of the list in a set. A property of a set is th...

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

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

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

Codeforces Round 988 (Div. 3) Editorial #### [problem:2037A] Problem Credits: [user:cry,2024-10-25] <br> Analysis: [user:cry,2024-10-25] <spoiler summary="Solution "> We want to count how many times we can choose $i$ and $j$ such that $a_i = a_j$. Suppose $f_x$ stores the frequency of $x$ in $a$. Once we choose $a_i = a_j = x$, $f_x$ is subtracted by $2$. Thus, the answer is the sum of $\lfloor \frac{f_x}{2} \rfloor$ over all $x$. </spoiler> <spoiler summary="Code (Python) "> ```py t = int(input()) for _ in range(t): n = int(input()) a = list(map(int, input().split())) print(sum([a.count(x) // 2 for x in range(n + 1)])) ``` </spoiler> #### [problem:2037B] Problem Credits: [user:cry,2024-10-25] <br> Analysis: [user:chromate00,2024-11-17] <spoiler summary="Are you a python user and failing test 4?"> It is worth noting that test $4$ is especially made to blow up python dictionaries, sets, and Collections.counter. If you are time limit exceeding, consider using a frequency array of le...

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

Codeforces Round 1050 (Div. 4) Editorial #### [problem:2148A] <spoiler summary="Solution (written by cry)"> Notice that if we pair each odd-indexed element with an even-indexed element, it sums to $0$. Therefore, our strategy is to pair the $2i$'th element with the $(2i+1)$th element until there are no more elements to pair. Note that if $n$ is odd, then there exists an unpaired odd element at the end. In this case, the answer will just be that ending element, which will be $x$. Otherwise, when $n$ is even, we paired every element perfectly and the sum will be $0$. Time complexity: $\mathcal{O}(1)$ per test case. </spoiler> <spoiler summary="Code (C++) (MikeMirzayanov)"> ```cpp #include <bits/stdc++.h> using namespace std; #define forn(i, n) for (int i = 0; i < int(n); i++) int main() { int t; cin >> t; forn(tt, t) { int x, n; cin >> x >> n; if (n % 2 == 0) cout << 0; else cout << x; cout << endl; } } ``` </...

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

Fast Walsh Hadamard Transforms and it's inner workings One of my favorite algorithms out there is FWHT, but sadly there are not many tutorials about it. So here's a simple attempt by me (feedback is appreciate). **Note:** I will be explaining FWHT via DFT/FFT and as such good understanding of theory behind DFT/FFT is **required**. Also, I won't be going into Hadamard matrices, since I don't know much about them myself. What is FWHT? Suppose you have two sets $ (1, 2, 2) $ and $(3, 4, 5)$ and want to perform all possible xor operations between these two sets, the resulting set being $(1, 1, 2, 4, 5, 6, 6, 7, 7)$. This is commonly called xor convolution. Naively you'd do this in $O(n^2)$ time, where $n=2^k$, $k$ = maximum number of bits (you maintain a frequency count for each possible value and loop on all possible pair). FWHT let's you do this in $O(n\log n)$ time via some <strike>black magic</strike> FFT tricks. We first build the frequency arrays upto $n=2^k$, apply FWHT to turn them into some mysterious point-value form, perform ...

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

Codeforces Round #804 (Div. 2) Editorial Reupload The [original blog](https://web.archive.org/web/20220705073720/https://codeforces.me/blog/entry/104088) was deleted yesterday by one of the other authors. We are very sorry about this. [A — The Third Three Number Problem](https://codeforces.me/contest/1699/problem/A) ===== Authors: [user:antontrygubO_o,2022-10-31], [user:Gheal,2022-10-31] <spoiler summary="Hints"> <spoiler summary="Hint 1"> An answer exists only when $n$ is even. </spoiler> <spoiler summary="Hint 2"> $a \oplus a = 0$ $a \oplus 0 = a$ </spoiler> </spoiler> <spoiler summary="Solution"> First and foremost, it can be proven that $(a \oplus b) + (b \oplus c) + (a \oplus c)$ is always even, for all possible non-negative values of $a$, $b$ and $c$. <spoiler summary="Proof"> Firstly, $a \oplus b$ and $a+b$ have the same parity, since $a + b = a \oplus b + 2 \cdot (a \text{&amp;} b) $. Therefore, $(a \oplus b) + (b \oplus c) + (a \oplus c)$ has the same parity as $(a+b)+(b+c)+(a+c...

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

Derangement Generation of an Array [Tutorial] I would like to explain the concept of derangement of a permutation. Definition: Derangement of a permutation is another ordering where each and every element of the permutation is not in its original position. Examples: A derangement of 1 2 3 can be 3 1 2, but 3 2 1 is not a derangement of 1 2 3 because 2 is still in its correct position. Sometimes for an array, a derangement is not possible. Let us take an example. Consider the array of numbers 1 2 1. Try writing the remaining permutations of this array, at least 1 element will retain its position. Statement: If an element occurs more than 'half the size' number of times in an array then the derangement of that array is not possible. Proof: Consider, an array of n elements. If there exists an element with a frequency that is greater than n / 2(take it as real division). Then the given array cannot be deranged because if we pick that particular element and try filling the remaining numbers into its original position...

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

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

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

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

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

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

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

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

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

Unofficial Editorial for SEATST 2026 # Introduction On 23 and 24 May, 7 countries participated in the **S**outh **E**ast **A**sia **T**eam **S**election **T**est. As the only contestant who AKed both days, I decided to write an editorial for the bugaboos. (The bugaboos are [here](https://tlx.toki.id/bugaboos/seatst-2026).) # 1A (Two Exams) <spoiler summary="Solution"> My solution was the same as [user:blackscreen1,2026-05-27]'s [solution](https://codeforces.me/blog/entry/154034), but I found it in a different way. First, I tried binary searching on the answer, so it reduces to checking if $P[i] - i \leq K$. Rather than setting $P^{-1}[0], P^{-1}[1], \cdots$, giving each index $i$ a deadline of $i + K$, I decided to use the reverse order; first set $P^{-1}[N-1]$, then $P^{-1}[N-2]$, and so on. This means that each index $i$ is only "usable" from "time" $i+K$ onwards. Then, $P^{-1}[i]$ must be the remaining student with highest $A$ or highest $B$. Now, the key observation is that the only way we can "die...

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

Codeforces Round #940 and CodeCraft-23 (Div. 2) Editorial [problem:1957A] ================== **Idea:** [user:keyurchd_11,2024-04-21] **Problem Setting:** [user:shakr,2024-04-21] [user:lezirtin,2024-04-21] **Editorial**: [user:shakr,2024-04-21] [user:TheRaja,2024-04-21] There were a few solutions which passes pre-tests with the assumption that $a_i \leq n$. We apologize for the pre-tests on A not including this case. <spoiler summary="Hint 1"> To create the most polygons, you should use as few sticks as possible per polygon. What polygon has the least number of sides? </spoiler> <spoiler summary="Solution"> [tutorial:1957A] </spoiler> <spoiler summary="Rate this problem"> - Great Problem - Ok Problem - Bad Problem - Didn't solve </spoiler> <spoiler summary="C++ Code"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main(){ int t; cin >> t; while(t--) { int n; cin >> n; vector<int> a(101, 0);...

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

[Tutorial] Subset Sum Square Root Optimisation Problem ================== Let's look at the following two problems:<br> 1. _Given an array $A$ of $N$ elements where $0 \le A_i \le X$ for some positive integer $X$, find all possible subset sums._ <br> 2. _Given an array $A$ of $N$ elements where $0 \le A_i \le X$ for some positive integer $X$, for all possible subset sums, calculate the minimum number of elements required to achieve that sum._ Thanks to [user:socho,2021-12-02] for improving the tutorial! Solution ================== This is a [classical dynamic programming problem](https://en.wikipedia.org/wiki/Subset_sum_problem) which can be solved in $O(N^2 \times X)$ (the sum of elements is bounded by $N \times X$) and hence that solution won't be discussed in much detail here. We can create an array $\it{dp}$ of size $X + 1$ and say that $\it{dp}_a$ is $1$ if it's possible to form a sum of $a$ using some elements from the array and $0$ otherwise. Then, we try to include every element $A_i$ and set all $\it{dp}_a$ for...

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

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

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

Zaglol FCDS Contest Solutions **[Zaglol Contest &mdash; FCDS level 1:](https://codeforces.me/gym/106350)** Problem [A. Zaglol welcoming](https://codeforces.me/gym/106350/problem/A): <spoiler summary="Solution"> Print **FCDS** </spoiler> <spoiler summary="Code"> ~~~~~ #include <iostream> using namespace std; int main() { cout << "FCDS" << endl; } ~~~~~ </spoiler> Problem [B. Baby Baraa in ALBAIK](https://codeforces.me/gym/106350/problem/B): <spoiler summary="Hint"> Notice that the values of $a_i$ are bounded: $(1 \le a_i \le 100)$. </spoiler> <spoiler summary="Solution"> It is easy to see that the $O(N^2)$ brute-force approach will be too slow for the given constraints. Therefore, we need a faster way to count, for each $i$, how many indices $j > i$ satisfy $(a_i > a_j)$. Since that the values of $a_i$ are bounded: $(1 \le a_i \le 100)$, we can use a frequency array to count how many numbers smaller than a given value appear to its right. We process the array fro...

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

Editorial of Newton's Coding Challenge January 2022 ### [A. Equal Distribution]() <hr> <spoiler summary = "Solution"> The answer is $YES$ if and only if the number of red balls and the number of blue balls are both divisible by $2$. </spoiler> ### [B. Smallest String]() <hr> <spoiler summary = "Solution"> The solution will not exist if $n < k$ because each letter must be used at least once. Further, if $k = 1$ and $n > 1$, the solution will not exist because each pair of adjacent characters must be different. In all other cases, we can greedily construct the solution from left to right by maintaining number of characters not yet used, $r$; and the previous character, $prev$.To decide for the $i$-th position we do the following: <ul> <li> If $r < n+1-i$, we can place the lexicographically smallest letter which is not equal to $prev$. (This will always be either "a" or "b".) <li> Otherwise, we can place the smallest unused letter and decrease $r$ by $1$. </ul> Time Complexity: $O(|A|*n)$ where $|A| = 26$ denotes ...

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

[Training] [Arabic] ACM JCPC Summer Training 2017 Hello Codeforces, On Septemper 2017 the JCPC Summer Training 2017 was held in the University of Jordan, covers varied topics consists of 2 main levels 1 & 2 each consists of 8 Lectures and one additional lecture in level 3. The training is recorded and published on youtube on [user:SolverToBe,2018-09-14] channel *note: language of training is Arabic. **Level 1** ----------- **Lecture 1** &mdash; Presented By Ibraheem Tuffaha [user:Vendetta.,2017-09-02] <spoiler summary="ACM and Problem Solving"> Part 1 | [ACM and Problem Solving](https://www.youtube.com/watch?v=7pdNV-8BwIk) Part 2 | [Complexity](https://www.youtube.com/watch?v=adTPPwU0w-w) Part 3 | [Implementation 1](https://www.youtube.com/watch?v=ftZGTQxaNzQ) Part 4 | [Implementation 2](https://www.youtube.com/watch?v=e4-m2uHOsds) </spoiler> **Lecture 2** &mdash; Presented By Mohammad Zuhair [user:zuhair,2018-09-14] <spoiler summary="STL"> Part 1 | [STL Pair](https://www.youtube.com/watch?v=fR7GcvxCA...

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

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

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

Codeforces Round 1056 (Div. 2) Editorial Hello, Codeforces! Sorry for the late editorial. Our national olympiad just finished and we were sorting everything out. We also apologize for weak tests on D that made an incorrect solution pass. Many testers submitted the same solution and we mistakenly thought that it was correct given the low bound on the number of batteries. Still, we hope that the contest was a fun and valuable experience for all contestants. The editorial was prepared by [user:efishel,2025-10-08] and me. If you have any questions about the problems or the solutions, please ask in the comments. ### [problem:2155A] <spoiler summary="Hint 1"> When two teams in the same group face off against each other, exactly one of them stays in the group. </spoiler> <spoiler summary="Solution 1"> The answer for all $n$ is $2n-2$. Let's consider the winners' group first. Note that exactly one team drops to the losers' bracket for every match in this group. Only one team is left in the winners' group...

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

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

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

Unofficial editorial Codeforces Round #640 (Div. 4) This is unofficial editorial to first Div4 contest [contest:1352]. Please be lenient, this is my first editorial of a real contest. In [problem:1352A] there is a definition of a number to be "round". To create the set of round numbers we need to observe that every single digit of the initial number can be used to create a round number. Just add the numbers of zeros according to the position of the digit. ie "123" becomes "100 20 3". [submission:79585673] [problem:1352B] ask us to create a set of numbers where the sum equals a given n. The summands are limited to be all odd or all even, and the number of summands is given as k. So it turns out it is a case work of n and k being odd or even. If n is odd and k is even there is no solution, since an even number of summands of same parity will allways result in an even sum. If n is odd and k is odd we can construct a solution by using 1s and a last, bigger number as $n-k+1$. But we need to check if $k{\geq}n$ since if it is n...

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

Code Collection Covering Bubble Sort, Binary Search, Lower Bound, Frequency, and Prefix Sum Recently, I was explaining fundamental algorithms like Bubble Sort, Binary Search, Lower Bound, Frequency, and Prefix Sum to my friends. It occurred to me that sharing these algorithms on Codeforces could be beneficial to others as well. So, I decided to share the code, as it might serve as a useful resource for anyone interested in learning these concepts. Bubble Sort: compares adjacent elements and swaps them if in the wrong order until the list is sorted. ~~~~~ #include <iostream> using namespace std; int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); // Bubble Sort for (int i = 0; i < n; i++) { // --> O(N^2) for (int j = 0; j < n - 1; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } } cout << "Sorted array using Bubble Sort: "; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } return 0; }...

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

Suffix Array — CP Algorithms A friendly explanation of the implementation of [Sufix Array](https://cp-algorithms.com/string/suffix-array.html) CP-alg. Constructive comments are welcome ^-^ #### Recap The algorithm will sort the cycle shifts of a string. For this purpose, we'll maintain arrays p and c on each iteration, where p[i] is the index of the i-th substring and c[i] is the class of the i-th substring, meaning that a substring with a lower class will be lexicographically smaller. The algorithm will perform $log(n) + 1$ iterations $n$ times => $O(nlogn)$ #### 0-th iteration _Probably this is not so complicated but just in case._ The main idea of counting sort here is array cnt. Once you have the frequencies of every character in the string, do a prefix sum with cnt. Then, $p[--cnt[s[i]]] = i$ will just mean that the characters with higher frequency will be placed later p. ~~~~~ vector<int> p(n), c(n), cnt(max(alphabet, n), 0); for (int i = 0; i < n; i++) cnt[s[i]]++; f...

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

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

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

Codeforces Round #336 Editorial #### [problem:608A] **Author:** [user:tonynater,2015-12-23] **Code:** [https://ideone.com/HiZd9g](https://ideone.com/HiZd9g) The minimum amount of time required is the maximum value of $t_i + f_i$ and $s$, where t_i and f_i are the time and the floor of the passenger respectively. The initial observation that should be made for this problem is that only the latest passenger on each floor matters. So, we can ignore all passengers that aren't the latest passenger on each floor. Now, assume there is only a passenger on floor $s$. Call this passenger $a$. The time taken for this passenger is clearly $t_a + f_a$ (the time taken to wait for the passenger summed to the time taken for the elevator to reach the bottom). Now, add in one passenger on a floor lower than $s$. Call this new passenger $b$. There are 2 possibilities for this passenger. Either the elevator reaches the passenger's floor after the passenger's time of arrival or the elevator reaches the passenger's floor...

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

The Quarantine Contest — Editorial Link to the contest: [The Quarantine Contest](https://codeforces.me/contests/360591) #### [A. Aditya and Monkeys](https://codeforces.me/group/gcVZzr4igt/contest/360591/problem/A) Problem Author: [user:Mantra7,2021-12-20] <spoiler summary="Hint"> What is minimum number of chocolates Kikazaru and Iwazaru can get? </spoiler> <spoiler summary="Tutorial"> The minimum amount of chocolates that Kikazaru can get is $2$. And Iwazaru can get minimum $1$ chocolates. Which leaves Mizaru with $n-3$ chocolates at maximum. Which should be greater than both Kikazaru(2) and Iwazaru(1). So, $n-3>2$ which gives $n>5$ to divide such that all conditions are met. </spoiler> <spoiler summary="Solution Code"> ~~~~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; void solve() { ll n; cin>>n; if(n>=6) cout<<"YES"<<endl; else cout<<"NO"<<endl; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0);cout...

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

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

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

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

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

2015 ِACM AmmanCPC Editorial #### **[A. Who Is The Winner](http://codeforces.me/gym/100712/problem/A)** We can keep the name of the winner team while reading the input, if the current team solved more problems than the current winner, or solved the same number of problems but with less penalty, we set the current team as the winner: ~~~~~ cin >> curTeam >> curSolved >> curPenalty; if (curSolved > winSolved || curSolved == winSolved && curPenalty < winPenalty){ winTeam = curTeam; winSolved = curSolved; winPenalty = curPenalty; } ~~~~~ Complexity: $O(N)$ #### **[B. Rock-Paper-Scissors](http://codeforces.me/gym/100712/problem/B)** Let's start with the brute force solution, we can try all possible pairs $(X, Y)$, if we know $X$ and $Y$, then $Z = N - X - Y$. The number of times Bahosain wins depends on the number of Scissors in the first $X$ rounds, the number of Rocks in the next $Y$ rounds, and the number of Papers in the last $Z$ rounds. We can find the number of times he will lose in a...

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

Invitation to ICM Technex 2019 — IIT(BHU) Varanasi I would like to invite you all to the **International Coding Marathon 2019**, under the banner of Technex'19, IIT (BHU) Varanasi. [Technex](https://www.technex.in/) is the annual techno-management fest of Indian Institute of Technology (BHU), Varanasi organized from March 8 &mdash; 10, 2019. International Coding Marathon is the flagship event of [Byte The Bits](https://www.technex.in/events/), the set of programming events organized under Technex. ICM is brought to you by [Mentor Graphics](https://www.mentor.com/india). It will take place on [Friday, 8th March 2019, 21:00 IST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=ICM+Technex+2019+by+IIT+%28BHU%29&iso=20190308T1530&ah=2). The contest will be held on [Codechef](https://www.codechef.com/ICMT2019?utm_source=contest_listing&utm_medium=link&utm_campaign=ICMT2019). The problemset has been prepared by [user:hitman623,2019-03-06], [user:dhirajfx3,2019-03-06], [user:_shanky,2019-03-06], [user:drastogi21,2019-03-08...

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

2018 CMUT BeihangU Contest, Editorial This editorial corresponds to [contest:102114] (stage 5), which was held on Aug 6th, 2018. Moreover, this problem set was also used as Jingzhe Tang Contest 1 in Petrozavodsk Winter Camp on Jan 30th, 2019. **This post is now finished**, in which I try to elaborate on notes, solutions and maybe some data generating. Alternatively, you can refer to [an old published material](https://drive.google.com/file/d/1CFumWbNLTUEywkVDNF-LKT3SzYd1r15L/view), though I think the old English version did not explain something clearly. --- [problem:102114A] This problem requires to calculate $s$-$t$ min cut between any two vertices on a weighted cactus graph having $n$ vertices, denoted by $\mathrm{flow}(s, t)$. You need to report $\sum_{s < t}{(s \oplus t \oplus \mathrm{flow}(s, t))}$. $n \leq 10^5$, $\sum{n} \leq 10^6$, weights are $\leq 10^9$. Try to find some features of this graph. <spoiler summary="solution"> By contradiction, we can prove that for an undirected graph, each ed...

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

Infoleague Spring 2022 Round Editorial <spoiler summary="Vote your favourite problem"> <spoiler summary="Div 2"> Div 2A &mdash; The Hatchet Div 2B &mdash; Floor Or Xor Div 2C &mdash; Yet Another Constructive Problem Didn't participate, idc </spoiler> <spoiler summary="Div 1"> Div 1A &mdash; Bamboo Coloring Div 1B &mdash; Xor Or Floor Div 1C &mdash; Jump Didn't participate, idc </spoiler> </spoiler> [103633A &mdash; The Hatchet](https://codeforces.me/gym/103633/problem/A) ------------------ Author: [user:tibinyte,2022-03-30] <spoiler summary="Rate Problem"> 1700 or less 1800 1900 2000 2100 or more Didn't solve it, idk </spoiler> <spoiler summary="Solution"> ### Subtask 1 : $N \le 10^2$ This subta...

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

[Gym] 2018 ACM Amman Collegiate Programming Contest — editorial The tutorials for problems B & E were written by [user:1am,2018-06-03], D by [user:The-Legend,2018-06-03], F by [user:Qumair,2018-06-03], J & K by [user:Motarack,2018-06-03] and M by [user:abo_od303,2018-06-03]. Thank you guys for also reviewing the rest of the tutorial! #### [A. Careful Thief](http://codeforces.me/gym/101810/problem/A) It’s enough to try all segments of size $K$ that either starts with the start of a range or ends with the end of a range, suppose that the optimal solution is somewhere that starts in some range and ends in some other range (possibly ranges of zeroes), then shifting the segment to one direction will increase the answer, and shifting it in the other direction will decrease it until you reach the boundary of the range, or if both ranges have the same amount of money then shifting will not affect the answer. This can be done using a sorted array of the ranges and for each range that starts with $l_i$ we can binary search for $l_i + k - 1$ and to get...

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

[Tutorial] Binomial Coefficient mod Non‑Prime m (Easy Method) When I was making a problem, I needed to calculate $C_r^n$ modulo a non-prime big number. So, I found a simpler method I haven't seen shared, and I'm excited to explain it. **Prerequisites:** - Modular arithmetic - Factorization - Binary exponentiation - Knowing $\binom{n}{r}$ and Euler's totient function The problem is the modular inverse. We can get it for a number $x$ **if and only if** $x$ is **coprime** with the modulus. But in a lot of problems, we just need to undo a previous operation, $C_3^5 = \frac{5!}{3! \cdot 2!}$. We delete one $3$ and two $2$s from $5!$. **So why have we never thought to store it in a frequency array?** My idea is that when multiplying, we use the modular arithmetic formulas, and when dividing, we will **count the frequency** of each prime number in the modulus and delete it from $n!$, So we need to first calculate $n!$ **without the primes in the modulus** and **count the frequency for each prime**. Then, when you need to know ...

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

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

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

Codeforces Round 1124 (Div. 1, Div. 2) Editorial ### ⭐ **Hope you enjoyed the problems!** ⭐ <span style="font-size: 20px;">[problem:2269A]</span><br> **Idea:** [user:Hamed_Ghaffari,2026-09-26]<br> **Preparation:** [user:Hamed_Ghaffari,2026-09-26] <spoiler summary="Hints"> <spoiler summary="Hint 1"> If Hamed waits $d$ days before withdrawing, the amount of money in his card increases by exactly $2^d$. </spoiler> <spoiler summary="Hint 2"> For fixed $a+b$, is $2^a+2^b$ larger when $a,b$ are close together, or when one is as large as possible? </spoiler> </spoiler> <spoiler summary="Solution"> If Hamed waits $d$ days before withdrawing, the amount of money in his card increases by exactly $2^d$. Therefore the problem becomes: Split $n$ into exactly $k$ positive integers $a_1,\dots,a_k$, and maximize $$2^{a_1}+2^{a_2}+...+2^{a_k}$$ For fixed $a+b$, $2^a+2^b$ is larger when one of them is as large as possible. <spoiler summary="Proof"> Suppose two segment lengths are $a\le b$, with $a>1$. Move one day...

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

HU JCPC Qualification 2026 Tutorial Hints are mostly related, so you have to think and get some observations before understanding the next, make sure to understand the code before you submit it as well, "The world is full of obvious things which nobody by any chance ever observes" ~the,2026-08-02 poet. Big thank you to the testers for improving this problem set beyond what it was, [user:JwanaAlghonmien,2026-08-20] , [user:halakreishan7,2026-08-20], [user:Mohammad-Najjar,2026-08-20], [user:samuelster,2026-08-20], [user:moath_mohammed,2026-08-20], [user:real_MBS,2026-08-20], [user:SaDOS.exe,2026-08-20] and Thank you to the organizers in HU especially [user:hyasat,2026-08-21] and of course judges and writers, [user:DarkVoidd,2026-08-21] and [user:Aziz_05,2026-08-21] and [user:babushkaguy,2026-08-21] and others that are mentioned down in the blog. The contest exist in the group so make sure to join https://codeforces.me/group/ppRciMeJFg/contests A video tutorial by the one and only [user:hyasat,2026-08-22] [YouT...

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

Codeforces Round #697 (Div. 3) [Alternative editorial + Screencast with commentary] [my solutions on github](https://github.com/Sky-Nik/Codeforces/tree/main/697-3), variable names are mostly reasonable so that you can read it alongside explanations. The screencast with video editorial is coming soon on my [YT channel](https://www.youtube.com/watch?v=Z4dfNNjYnpY&feature=youtu.be&ab_channel=NikitaSkybytskyi) ### A. Odd Divisor A number has an odd divisor iff it is not a power of two. ### B. New Year's Number $2020 x + 2021 y = n$. Mod out by $2020$, you get $y = n \% 2020$. Then simply check that $x = (n - 2021 y) / 2020$ is nonnegative. ### C. Ball in Berland We have a bipartite graph. All pairs of pairs are good except for the pairs that share a common vertex. There are $\binom{k}{2}$ pairs in total and $\binom{\deg v}{2}$ pairs that share a vertex $v$, hence the answer is $\binom{k}{2} - \sum_v \binom{\deg v}{2}$. ### D. Cleaning the Phone Among the applications of equal importance we want to delete the heaviest ones first, hence it makes sens...

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

Rewriting blogs that aren't well written part 1: Inversion count using mergesort/fenwick tree <i>This blog's target audience is for newbies who don't know this (like me!). So, if you knew this before, it would be great if you read this blog and give me some valuable feedbacks. Thanks ^^!</i> Now for the intro: A while ago, I met a problem where it requires me to count the number of inversion of an array. Having 2 braincells, I knew nothing about this. So, I decided to ask my friends [user:ballss,2026-10-24] and [user:quanhoangbla,2026-10-24]. <strike>Of course, they are good friends so they taught me everything about that.</strike> NO. [user:ballss,2026-10-24] just called me dumb, so I decided to learn it myself. That's when I stumbled across [this](https://codeforces.me/blog/entry/86294) blog. This blog, in my opinion, is a great blog, but it was not really well written. As a result, it got heavily downvoted (I recommend you upvote that blog, although it's most likely that the author have stopped doing CP, since the last time he/she visited was 9 months ago). Although I...

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

[Gym] 2018 JUST Programming Contest 1.0 — editorial ### A. Will he Die? <spoiler summary="Hint 1"> Due to symmetry, the answer of `n m` is equal to the answer of `-n m`, so work with the absolute value of $n$. </spoiler> <spoiler summary="Hint 2"> We are looking for the probability of starting at position $0$ and ending at $n$ positions to the right, using $m$ moves. </spoiler> <spoiler summary="Hint 3"> A move goes to Right with probability $\frac{1}{2}$ and Left with probability $\frac{1}{2}$, we can imagine we have a binary string of instructions of length $m$ (executed one by one), where $0$ means go left and $1$ means go right. because of this discrete uniform distribution, every unique binary string of length $m$ will have a probability of $\frac{1}{2^m}$ as we have $2^m$ different strings. </spoiler> <spoiler summary="Hint 4"> So the answer will be the number of such strings that $x-y=n$ where $x$ is the number of $1$'s and $y$ is the number of $0$'s, with some work on paper you can find that $x=n+\frac{m...

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

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

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

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

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

My Editorial for Google Kick Start 2020 Round F [中文版 | Chinese version](https://cp-wiki.vercel.app/tutorial/kick-start/2020F/) ## Problem A &mdash; [ATM Queue](https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff48/00000000003f4ed8) It takes a person $\left\lceil\frac{A_i}{X}\right\rceil$ rounds to withdraw $A_i$. So we can turn $A_i$ into pairs $(\left\lceil\frac{A_i}{X}\right\rceil, i)$, then sort the pairs to get the final sequence. Total time complexity is $O(N\log N)$ since we need to sort. <spoiler summary="Code (C++)"> ~~~~~ #include <algorithm> #include <cstdio> #include <iostream> #include <vector> using namespace std; template <typename T> void read(T &x) { x = 0; char c = getchar(); T sig = 1; for (; !isdigit(c); c = getchar()) if (c == '-') sig = -1; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= sig; } class Solution { public: void solve(int case_num) { printf("Case #%d: ", case_num); int n, x; ...

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

Editorial Divide by Zero and Codeforces Round #399 (Div. 1+2, combined) [768A. Oath of the Night's Watch](http://codeforces.me/contest/768/problem/A) ------------------------------------------------------------------------------ Set and Editorial by: [user:vntshh,2017-02-15] You just have to find the number of elements greater than the minimum number occurring in the array and less than the maximum number occurring in the array. This can be done in $O(n)$ by traversing the array once and finding the minimum and maximum of the array, and then in another traversal, find the good numbers. **Complexity**: $O(n)$ <spoiler summary="Code"> ~~~~~ #include<bits/stdc++.h> using namespace std; int a[100005]; int main() { int n,c1=0,c2=0,mx=0,mn=1000000007; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; mx=max(mx,a[i]),mn=min(mn,a[i]); } for(int i=0;i<n;i++) { if(a[i]==mx) c1++; if(a[i]==mn) c2++; } if(mx==mn) cout<<0; else cout<<(n-c1-c2); return 0; } ~~~~~ </spoiler> [768B. Code For 1](http://codeforces.me/...

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

Mo online and how to solve problem from a recent Educational Round Hello everyone! In contests, problems involving range queries appear quite often. Most problems provide queries offline, which allows for greater flexibility in solving them, but often they reduce to using a segment tree or Mo's algorithm. However, sometimes a problem that is easily solvable offline with Mo's algorithm becomes interesting in the online version. In such cases, some people try to maintain something like $500$ different states of Mo's algorithm &mdash; I never really understood what was meant by that. Today, I managed to come up with an online version of Mo's algorithm that works in $O(n^{\frac{5}{3}})$ time and memory for usual problems (where moving the pointers is done in $O(1)$). For asymptotic analysis, I'll assume $n = q$. I'm not the first to come up with this idea. As it turns out, [here](https://codeforces.me/blog/entry/44711?) и [here](https://codeforces.me/blog/entry/135134) was a discussion where this idea was proposed, but I also want to do this as I'...

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

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

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

Looksery Cup 2015 Editorial **UPD** Editorial of problem E was added, I apologize for the delay. Hope you found it interesting. **A. Face Detection** Author: [user:Monyura,2015-06-06] One should iterate through each 2x2 square and check if it is possible to rearrange letters in such way they they form the word "face". It could be done i.e. by sorting all letters from the square in alphabetic order and comparing the result with the word "acef"(sorted letters of word "face"). **B. Looksery Party** Author: [user:Igor_Kudryashov,2015-06-06] In any cases there is such set of people that if they come on party and send messages to their contacts then each employee receives the number of messages that is different from what Igor pointed. Let's show how to build such set. There are 2 cases. There are no zeros among Igor's numbers. So if nobody comes on party then each employee receives 0 messages and, therefore, the desired set is empty. There is at least one zero. Suppose Igor thinks that i-th emp...

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

Editorial for CodeRed Prelims 2026 On behalf of the organizing team, we extend our deepest gratitude to everyone who participated in CodeRed Prelims 2026. Witnessing your dedication and fierce competitive spirit on the leaderboard validated the immense effort our team invested behind the scenes. Our problem-setters spent countless hours crafting and balancing these challenges. We sincerely hope the problemset provided a rewarding and engaging experience for the IIIT Allahabad community and our global participants. Below, you will find the official hints, detailed editorials, and author solutions. Happy upsolving! A: Ashutosh's Triad ---------------------- Author: [user:sigma__1,2026-04-16] <spoiler summary="Hint 1"> The phrase "minimize the maximum salary" is a classic indicator that we should use Binary Search on the answer. </spoiler> <spoiler summary="Hint 2"> Since $X$ is square-free, the maximum number of distinct prime factors $m$ is very small ($m \le 15$). Think about representing each wizard's ...

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

Contest Without tests :)) #### We would like to thank everyone who contributed to this contest, whether by providing ideas or participating in solving the problems. - [user:MUZAN,2025-02-08] - [user:TANJIR0U,2024-12-10] - [user:detective...dots,2024-01-31] - [user:ZAYAN,2024-01-31] - [user:Uchiha_Ouda,2024-01-31] - [user:jimy_26,2024-01-31] - [user:gom3a_,2025-02-08] #### And we also want to thank those who tested the problems. - [user:Ali_Azzam,2024-01-31] - [user:ahmedalaa22,2024-02-03] - [user:opop1omar,2024-01-31] - [user:Ahmed_JS,2024-01-31] [A &mdash; Free Palestine](http://codeforces.me/group/rjUbMTacuS/contest/500816/problem/A) ------------------ Idea: [user:gom3a_,2025-02-08] <spoiler summary="Hint"> How many numbers are there from $1$ to $3$? </spoiler> <spoiler summary="Tutorial"> You simply calculate $end - start + 1$. </spoiler> <spoiler summary="Solution (gom3a_)"> ~~~~~ /* " أَمْ حَسِبْتُمْ أَن تَدْخُلُوا الْجَنَّةَ وَلَمَّا يَأْتِكُم مَّثَلُ الّ...

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

A2SV G6 — Round #2 Editorial [Here](https://codeforces.me/contestInvitation/cccd31bebeb08638cc7f11e41ebbd2d9d0a60025) is the link to the contest. All problems are from Codeforces' problemset. #### [A. Make the Product Zero](https://codeforces.me/gym/586960/problem/A) <spoiler summary="Hint"> To make the product of all elements zero, we need at least one element in the array to be zero. </spoiler> <spoiler summary="Solution"> <p> There are three cases to consider: <ul> <li>If there is already a zero in the array, no operations are needed.</li> <li>If there are negative numbers, we can turn one of them into zero, requiring at most |A[i]| operations.</li> <li>If all numbers are positive, the minimum number of operations required is to turn the smallest positive number into zero.</li> </ul> The solution involves iterating through the array and determining the minimum number of operations needed. </p> </spoiler> <spoiler summary="Code1"> ```python3 n = int(input()) ...

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

Editorial for Summer programming olympiad #1 [contest:329695] Editorial in PDF: https://drive.google.com/file/d/1KL723lzYE8tVlgIUveMt2lSWDbd4nccv/view?usp=sharing [problem:329695A] Task author: [user:Jugo,2021-06-09] Translate author: [user:MatesV13,2021-06-09] Solution author: [user:Jugo,2021-06-09] <spoiler summary="tutorial"> Let's just go through all the numbers on the segment $[l; r]$ and, by dividing the numbers by 2, 3, 5 while we can, check whether the resulting number is one (in other words, there are no dividers larger than 5). The asymptotics of this solution will be $n \cdot \sigma(n)$, where $\sigma(n)$ is the number of twos, triples and fives in the factorization of the number. Since this number is fairly small (around 3, so there will be no problem with time limit. </spoiler> <spoiler summary="code"> ~~~~~ #include <bits/stdc++.h> #define int int64_t using namespace std; bool f(int n){ while((n & 1) == 0) n >>= 1; while(n % 3 == 0) n /= 3; ...

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

CSES — Sliding Window Editorial Some of the most powerful techniques are also the simplest yet identifying when and how to apply them effectively can be challenging. Sliding window is one such method. Sliding window helps solve problems involving sequences, subarrays, or continuous segments by efficiently tracking changes as the window moves forward. While tackling the CSES Sliding window problems, I noticed that many seemingly complex tasks like tracking the sum of elements in a dynamic segment, finding a subarray's minimum or maximum, or counting distinct elements can be simplified and optimized with this technique. Initially, one might consider brute-force methods iterating over every possible subarray or recomputing values from scratch. However, the core idea behind sliding window is smartly updating the state of the window rather than recalculating everything each time. In my experience, the primary challenge while solving these problems came down to accurately managing the data structures supporting the w...

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

A2SV G5 ASTU — Contest #2 Editorial [Here](https://codeforces.me/gym/495407) is the mashup link (the problems are from Codeforces' problem set). #### [A. The Lone Element Quest](https://codeforces.me/gym/495407/problem/A) <spoiler summary="Solution"> To identify the unique element, this solution counts the occurrences of each number in the array. Then, it locates its index in the array. </spoiler> <spoiler summary="Code"> ```python from collections import Counter t = int(input()) for _ in range(t): n = int(input()) nums = list(map(int, input().split())) count = Counter(nums) for key in count: if count[key] == 1: mynum = key for i in range(len(nums)): if nums[i] == mynum: print(i + 1) break ``` </spoiler> #### [B. YetnotherrokenKeoard](https://codeforces.me/gym/495407/problem/B) <spoiler summary="Solution"> To solve the problem quickly, we can maintain two stacks: one for uppercase letters and one for low...

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

Editorial of IPC — 2 (2025-26) #### Welcome to the Editorial of [IPC-2](http://tinyurl.com/IPC2-25-26). [A. Binary Cleanup ](https://codeforces.me/gym/641544/problem/A) ------------------ Author:[user : Kp_s33,2025-10-28] <spoiler summary="Problem Tags"> greedy </spoiler> <spoiler summary="Hint 1"> Each operation removes one '1' and one '0' where the '1' is to the left of the '0'. So, every '1' needs a '0' somewhere to its right to be removed. </spoiler> <spoiler summary="Hint 2"> Think from the end of the string — the rightmost '1' can only be removed if there is at least one '0' after it. </spoiler> <spoiler summary="Hint 3"> Try scanning from the end while counting '0's. If at any moment the number of '1's exceeds the number of '0's to their right, it’s impossible to remove all '1's. </spoiler> <spoiler summary="Solution"> We iterate from the end of the string toward the beginning. Let’s maintain how many '0's are available to remove '1's. When we see '0', it becomes available for ...

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

CodePlus Long 2024 Editorial [contest:540279] ================== [problem: 540279A] <spoiler summary="Tutorial"> The problem boils down to finding the number of coordinates between $A_i$ and $A_{i+1}$ which are divisible by $k$ .Where $i$ is even considering $0$ based indexing. </spoiler> <spoiler summary="Code"> ```c++ #include<bits/stdc++.h> using namespace std; #define ll long long ll floor(ll x, ll m) { ll r = (x % m + m) % m; return (x - r) / m; } int main() { int t; cin >> t; while (t--) { ll n, k, ans = 0; cin >> n >> k; vector<ll>a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i += 2) { ans += floor(a[i + 1] - 1, k) - floor(a[i] - 1, k); } cout << ans << endl; } } ``` </spoiler> [problem:540279B] <spoiler summary="Hint "> This is a modified version of a popular problem $Dungeon$ $Game$.Try to solve...

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

Time Complexity Reduction Hello, I'm working on Audio Algorithm: Pitch-Shifter, unfortunately I can't find Text material about it design, But I found one of the code, implemented on c#: [pastebin link](https://pastebin.com/gsvBunqX). I would post code here as well, and if you have any idea how I can reduce time or implement new one, please share it, Thanks in advance. ~~~~~ /**************************************************************************** * * NAME: PitchShift.cs * VERSION: 1.2 * HOME URL: http://www.dspdimension.com * KNOWN BUGS: none * * SYNOPSIS: Routine for doing pitch shifting while maintaining * duration using the Short Time Fourier Transform. * * DESCRIPTION: The routine takes a pitchShift factor value which is between 0.5 * (one octave down) and 2. (one octave up). A value of exactly 1 does not change * the pitch. numSampsToProcess tells the routine how many samples in indata[0... * numSampsToProcess-1] should be pitch shifted and moved to outdata[0 ... * numSampsToProc...

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

[GYM] 100 Easy Problems (Bootcamp) Target audience: newbies and pupils (rating up to 1400). Group link: https://codeforces.me/group/yg7WhsFsAp/contests (hit "join" on the right). Hi. Enjoy a series of 8 problem lists for beginners. The example topics are strings, arrays, math, and binary search. You are allowed to discuss anything with others, or just look up solutions online. There are also 3 exams, each recommended for a 2-hour individual virtual participation. Use the displayed order, e.g. take exam 1 after day 3. It all should take you 2 weeks of intense bootcamp-like work (or a few months if you take your time). The problems were originally used two years ago in a Saudi Arabia camp. It's a mix of around 70 existing CF problems and 30 new original problems, mainly prepared by [user:kostka,2021-11-18], with some help from me and [user:mustafabar,2021-11-18]. I asked them for permission to publish everything. I will put hints to some problems in this blog (or in the group? not sure). Expect a few v...

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

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

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

International Coding League Round 1 Editorial ### [problem:681359A] **Problem Idea:** [user:kkapoor,2026-03-31] <spoiler summary="Solution"> We are given an array $a$ and need to find the maximum length subsequence $b$ such that for every adjacent pair: $$b_i \ \&\ b_{i+1} \ne 0$$ This means that every pair of consecutive elements in the subsequence must share at least one common set bit. #### Key Observation Two elements can be adjacent in the subsequence if and only if their bitwise AND is non-zero, i.e., they share at least one common bit. Instead of working with values directly, we can think in terms of bits (from $0$ to $32$). #### Approach Define a DP array: $$dp[b] = \text{maximum length of a valid subsequence ending with an element having bit } b$$ We process the array from left to right. For each element $a_i$: 1. Find all bits that are set in $a_i$ 2. Compute: $$best = 1 + \max(dp[b]) \quad \text{over all bits } b \text{ set in } a_i$$ If no such bit exists (i.e., all correspon...

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

Robocontest Round 103 Editorial ### Thank you for Participating ! #### [A.Hasan and Binary Function](https://robocontest.uz/olympiads/2619/tasks/A) <spoiler summary="Solution"> We can obtain $n$ from the binary representation as following $$\displaystyle n=\sum_{i=0}^{|s|-1}2^i \times (s_i=\mathtt{'1'})$$ We know that the fact $$\displaystyle \sum_{i=0}^n 2^i=2^{n+1}-1$$ Let’s consider the last active bit i.e. $\mathtt{1}$ is $i$ then $n$ as integer is $$\displaystyle \sum_{i=0}^n 2^i=2^{n+1}-1 \implies \lfloor \log_2(2^{i+1}-1) \rfloor = i$$ thus the answer is the index of last occurrence of $\mathtt{1}$ , Complexity $O(n)$. </spoiler> <spoiler summary="Code"> ```python for _ in range(int(input())): n=int(input()) s=input() ans=0 for i in range(n): if(s[i]=='1'): ans=n-i-1 break print(ans) ``` </spoiler> #### [B.Hasan and Beautiful !](https://robocontest.uz/olympiads/2619/tasks/B) <spoiler summary="Solution"> Maintain two array...

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

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

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

Sorting array element by frequency in O(nlgn) time I am trying to solve a problem where i have to sort an array based on the frequency of the elements(in case of a tie the one that comes first in the input array should be present first that is i have to maintain the initial order of elements) in O(nlgn) time. I came up with the following logic - Make an array of objects and initialize its index and value at that index using the given array. - Now sort the array of objects, using the value. - Fill their frequencies in the object's frequency field. - Sort according to frequency and index My implementation gives an error of **error: must use '.*' or '->*' to call pointer-to-member function** moreover the error occurs at the 1st instance of stable_sort(). C++ compiler details are g++ 4.9.2 ~~~~~ #include<iostream> #include<algorithm> using namespace std; class Element { int index, value, frequency; public: Element(); void setIndex(int); void setValue(int); void setFrequency(int); int getIn...

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

An alternate approach for 646E using Euler Tour and Fenwick Welcome to my first blog! I recently came across [problem E](https://codeforces.me/contest/1363/problem/E) of Round #646, and solved it using an approach that didn't seem to be mentioned in the tags. And I felt it would be good idea to share it! Let's just jump straight into the solution. I'll refer to nodes which are initially marked 1 and need to become 0 as of type $OZ$, and the nodes which need to change to 1 from 0 as of type $ZO$. An intuitive idea that is guaranteed to work is to greedily select the node which has the lowest cost, and make all possible exchanges in its subtree first. So, we sort the nodes in a non-decreasing sequence of their costs, and process them in that order. To achieve that, we need to efficiently query on the number of nodes of types $ZO$ and $OZ$ in a subtree, and update the counts every time we shuffle. We can use a Euler tour to flatten the tree down to an array. To keep track of the subtree of any node, we store the _in_ and _out_ times o...

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

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

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

Solution D. Array and Operations Codeforces Round 760 (Div. 3) I Tried to Write A Solution for this Problem. ================== ### [problem:1618D] #### Observation <br> 1. When performing an operation where $a_i = a_j$, the score will increase by `1`, because if $a_i \equiv x$, then: $$ \left\lfloor \frac{a_i}{a_j} \right\rfloor \Leftrightarrow \left\lfloor \frac{x}{x} \right\rfloor \Leftrightarrow \lfloor 1 \rfloor \Leftrightarrow 1 $$ On the other hand, when performing an operation where $a_i \neq a_j$, the score will minimally increase by `0`, because if $a_i < a_j$, then: $$ \left\lfloor \frac{a_i}{a_j} \right\rfloor = 0, $$ and vice versa. 2. Exactly $k$ operations will be performed on an array of $n$ integers, where each operation increases the score according to the rule in point 1. Additionally, there are $n - (2 \cdot k)$ integers that will be added to the score without any special operation. Thus, $\boxed{2 \cdot k}$ numbers undergo operations, and $\boxed{n - (2...

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

[Gym] 2017 JUST Programming Contest 4.0 — editorial ### A. Subarrays Beauty <spoiler summary="Hint 1"> Consider each bit on its own since the AND operation is bit-wise. </spoiler> <spoiler summary="Hint 2"> For each bit, notice that any sub-array that has a zero bit will add nothing to the answer. </spoiler> <spoiler summary="Hint 3"> For each bit, A sub-array of only ones of length $X$ has $\frac{X \times (X+1)}{2}$ sub-array of only ones, and each of them will add $2^{W}$ where $W$ is the Weight of the bit to the answer. </spoiler> [user:justHusam,2017-09-29] solution: https://ideone.com/PL7s1U <br/> [user:Vendetta.,2017-09-29] solution: https://ideone.com/23iukT <br/> **Complexity:** $O(N log(Max(A_i)))$. ### B. Array Reconstructing <spoiler summary="Hint 1"> You can construct the array from only one known element. </spoiler> [user:justHusam,2017-09-29] solution: https://ideone.com/IDqwCe <br/> **Complexity:** $O(N)$. ### C. Large Summation <spoiler summary="Hint 1"> All numbers are less tha...

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

LaTeX tips in Editorials and Statements: Make Your Equations Pretty Can you spot any difference between $max$ and $\text{max}$ or $dp$ and $\text{dp}$? How about $\lfloor \frac{max(a, b, c)}{b} \rfloor$ and $\left \lfloor \frac{\max(a, b, c)}{b} \right \rfloor$? Or even $\displaystyle \left \lfloor \frac{\max(a, b, c)}{b} \right \rfloor$! While appreciating the efforts and the careful elaborate writing of the authors, I have faced many issues with latex writing in editorials that have frustrated me while reading over the years, so I thought of writing this blog to settle many of such issues and making our equations in editorials the prettiest possible. I'm going to use [this editorial](https://codeforces.me/blog/entry/127195) in problem F div 1 an example and refer to it in things that can be improved. Of course, that doesn't mean any offence to [user:satyam343,2024-07-22]'s beautiful and careful writing of the editorial nor his/her LaTeX writing/skills, he/she has done it beautifully. Also, note that any code that is quoted in this blog `...

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

[Tutorial/Parody] How to practice basic topic in CP (Episode 1) Not long ago [user:ToxicPie9,2023-01-11] posted a <a href = "https://codeforces.cc/blog/entry/111254">blog</a> explaining common mistakes in competitive programming and how to avoid them. I was greatly inspired by that post so I decided to write an episode on my own. Today I will mention four topics that I learned why practicing Competitive Programming and I will also mention how to build them. Also, in most cases, I will give you a chance to find out what the hard part is before I reveal the culprit as I tried to make this blog interactive. The codes that I have used in this blog have been written in Python as it is the most **powerful** language for CP. #### Segment trees Definition: <spoiler summary="Click me"> A Segment Tree is a data structure that stores information about array intervals as a tree. This allows answering range queries over an array efficiently, while still being flexible enough to allow quick modification of the array. This includes finding the sum of...

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