implementation"> ```cpp std::pair find_pivot() { if(pivot == size_t(-1, () { if(pivot == size_t(-1)) { pivot = 0; while(pivot < size(*this) &&
normalize(pivot
→ 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 | 157 |
| 2 | maspy | 150 |
| 3 | Um_nik | 145 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | DNR | 133 |
| 8 | nik_exists | 132 |
| 9 | AmShZ | 130 |
| 10 | Dominater069 | 129 |
→ 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.
Efficient linear algebra for dummies Hi everyone!
Some time ago I started developing a linear algebra library for Library Checker, and it turned out to be much fun. I'd like to write this blog to outline how one can implement a linalg library with a very good Library Checker performance, while also avoiding highly technical low-level details that are common in other similar blogs. Instead, we will learn a few high level ideas that will let us write a code that the compiler will then optimize using all these fancy techniques _in our stead_.
Huge thanks to ~ToxicPie9,2024-05-08 and [user:magnus.hegdahl,2024-05-08] for explaining me some of the optimizations used here! You may also look into ~sslotin,2024-05-08's [entry](https://codeforces.me/blog/entry/101655) about how it can be sped up even further with more advanced and low-level techniques.
### Tl'dr.
In this blog, I present my [matrix library](https://cp-algorithms.github.io/cp-algorithms-aux/cp-algo/linalg/matrix.hpp), which maintains a simple and elegant...
2.
[Tutorial] Network simplex Hello!
If you've learned the simplex algorithm and a minimum cost flow algorithm, perhaps you've also heard about this fancy thing called [network simplex](https://en.wikipedia.org/wiki/Network_simplex_algorithm) which is supposed to be a specialization/optimization of the simplex algorithm for computing a [minimum cost circulation](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem). If your google search didn't turn up any interesting results or your interest faded, you might have moved on to other subjects.
Well I didn't! So this is a tutorial on network simplex (NS) for the **minimum cost circulation** problem. I'll describe and formulate the problem, show how it relates to the usual minimum cost flow problem, explain the theory behind the algorithm in-depth, and then derive the implementation details.
## Introduction
The algorithm commonly used in competitive programming for this sort of task is a minimum cost flow algorithm based on finding augmenting paths in a *f...
handcrafted graph algorithms in $O(V)$ time per pivot (or better)., simplex algorithm has a complexity of $O(VE)$ per pivot, and a similar memory
requirement to, simplex pivot. I think approaching the problem this way grants more motivation
for the decisions, solution: Perform a pivot for as long as there are variables that can enter
the basis., , ### How to prevent cycling — choosing exiting arc When we try to pivot on an
edge $e$ and, (V+E)$ time, which is just fine for the simplex algorithm, but a bit
sub-optimal if we plan topivot, )$ per pivot, and a similar memory requirement to represent the tableau. By
analyzing the linear, Another option would be to simply pivot on the first edge found, called the
*first-candidate, We target a complexity of $O(V)$ per pivot in the worst-case, and for pivot
selection we will, What we have just done here is find a way to **pivot** from one spanning tree
solution to another, pivot on, so we want a decent **pivoting strategy**, i.e. some clever way to
select good edges quickly
3.
Codeforces Round 955 (Div. 2, with prizes from NEAR!) Hello, Codeforces!
It's been a long journey, and I'm finally pleased to invite you to participate in our [contest:1982], which will take place on [contest_time:1982].
This round will be <b>rated</b> for all participants with a rating is <b>below 2100</b>. Participants with higher ratings can participate out of competition.
During the round, you will need to solve <b>6 problems</b>. You will have <b>2 hours</b> to solve them.
The problems for the round were prepared by [user:nik1998,2024-06-21], [user:egor4444ik,2024-06-21], [user:iamdimonis,2024-06-21] and me.
We sincerely thank everyone who provided invaluable assistance in preparing this round:
<ul style="list-style-type:square">
<li>Our insightful coordinator [user:74TrAkToR,2024-06-21] for excellent communication, helpful advice and assistance in problem preparation!</li>
<li>[user:Kolychestiy,2024-06-21] for improving one of the problems.</li>
<li>[user:EJIC_B_KEDAX,2024-06-21], [user:A_G,2024-06-21], [user:zw...
Announcement of Codeforces Round 955 (Div. 2, with prizes from NEAR!)
4.
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 ...
$s$ (call it the 'pivot'), and then $k$ elements smaller than $x$ and $k$
elements larger than $x, **Case 1** : $x \ge 2 \cdot k$ : Choose subsequence = pivot $i$ + arbitrary $k$
elements of $X, , let's assume that a possible pivot of the last operation is $i$ and there are
$x$ larger elements to be, - There must exist at least one element part of $s$ which can act as a "pivot"
for at least one, Because $i$ can act as a pivot $x, y \ge k$. Note that $(x + y)$ is a multiple
of $2 \cdot k$., If $x + y = 2 \cdot k$, we are done, because $x = y = k$, and we can choose
subsequence =pivot $i, In each operation, we choose an element $x$ in $s$ (call it the 'pivot'), and
then $k$ elements
5.
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...
to do a slightly different solution where we first merge the cycles and choose
thepivot afterwards, where we first merge the cycles and choose the pivot afterwards by choosing a
point unaffected by
Tutorial of Codeforces Round 715 (Div. 1)
Tutorial of Codeforces Round 715 (Div. 2)
6.
Geometry: 2D points and lines [Tutorial] I get an impression that a lot of coders struggle with geometric problems and prefer to avoid them. That's not much of a surprise, considering that I couldn't find a good writing explaining the basics and giving useful advice how to proceed. Moreover, some resources obfuscate this beautiful area to the point it's despised by the readers. I'll try to change that, but first I'll mention some of the better resources:
[geomalgorithms.com](http://geomalgorithms.com/points_and_vectors.html) This is where you can start if you don't have a basic notion of a vector. Also there are more detailed explanations for some examples I'll list, but I dislike the implementations.
[This post in Russian](http://codeforces.me/blog/entry/6642) has a link to the code that's most similar to mine, with some comments (unfortunately, also is Russian)[cut].
### Point structure and operations
Without further ado, I'll start with my code for the `Point` structure. Explanations are below, so don't rush t...
== origin; }); auto pivot = partition(first, last, [&origin](const
decltype(*first)& point) { return, point == origin; }); auto pivot = partition(first, last, [&origin](const
decltype(*first)& point
7.
Editorial for Codeforces Round 920 (Div. 3) [problem:1921A]
Idea: [user:goncharovmike,2024-01-16], prepared: [user:pashka,2024-01-16]
<spoiler summary="Tutorial">
[tutorial:1921A]
</spoiler>
<spoiler summary="Solution">
~~~~~
t = int(input())
for _ in range(t):
a = [[int(x) for x in input().split()] for i in range(4)]
x = [p[0] for p in a]
dx = max(x) - min(x)
print(dx * dx)
~~~~~
</spoiler>
[problem:1921B]
Idea: [user:pashka,2024-01-16], prepared: [user:ikrpprppp,2024-01-16]
<spoiler summary="Tutorial">
[tutorial:1921B]
</spoiler>
<spoiler summary="Solution">
~~~~~
t = int(input())
for _ in range(t):
n = int(input())
start = [int(x) for x in input()]
finish = [int(x) for x in input()]
pairs = list(zip(start, finish))
add_amnt = sum(int(a < b) for a, b in pairs)
rmv_amnt = sum(int(a > b) for a, b in pairs)
print(max(add_amnt, rmv_amnt))
~~~~~
</spoiler>
[problem:1921C]
Idea: [user:step_by_step,2024-01-16], prepared: [user:step_by_st...
a(n); int pivot = 1; while (pivot * pivot < n) { pivot, void solve() { int n, q; cin >> n >> q; vector a(n); int pivot = 1
Tutorial of Codeforces Round 920 (Div. 3)
8.
How I understand Floor Sum Hi everyone,
Today we are going to compute
$$\begin{gather}\sum_{x=0}^{n-1} \left\lfloor \frac{ax + b}{m} \right\rfloor\end{gather}$$
in $\mathcal{O}(\log(m))$.
This topic has been discussed elsewhere, but I find the proofs that are currently available online to be too artificial for me.
So here is my attempt to describe how I understand this topic using illustrations, albeit in a less rigorous manner.
[cut]
<br />
## 1. Floor Sum
Let us define
$$\begin{gather}S(a, b, m, n) = \sum_{x=0}^{n-1} \left\lfloor \frac{ax + b}{m} \right\rfloor\end{gather}$$
Here, we are going to assume that $a < m$ and $b < m$. If they are not, it is not hard to reduce them into $a \rightarrow a \bmod m$ and $b \rightarrow b \bmod m$, which I am not going to discuss here.
The sum above is equivalent to counting the number of lattice points below the curve $y = \frac{ax + b}{m}$ bounded by $0 \le x < n$. As an instance, the sum for $(a, b, m, n) = (3, 2, 5, 10)$ can be illustra...
9.
Codeforces Round 960 (Div. 2) Editorial Thank you for participation and we hope you enjoy this round :)
Additionally, we sincerely invite you to join the unofficial round of TheForces Community tomorrow. Compete alongside many high-rated participants and earn your own rating in a our own rating system([TheForces Rating System](https://theforces.netlify.app/ratings))!
For more details, pls read https://codeforces.me/blog/entry/131733.
#### [A — Submission Bait](https://codeforces.me/contest/1990/problem/A)
<spoiler summary="hint1">
For Alice, what if choosing the maximum value doesn't work?
</spoiler>
<spoiler summary="hint2">
Consider parity.
</spoiler>
<spoiler summary="solution 1">
Case $1$: When all values appear an even number of times, Alice will lose. This is because no matter which number Alice chooses, Bob can mimic Alice's move.
Case $2$: When at least one value appears an odd number of times, Alice will win. Alice only needs to choose the maximum value that appears an odd number ...
[sm, mx, pivot] = seg.query(L, R); insert(insert, 0, L, R); if (mx < sm, ; } else { int ret = self(self, L, pivot, auto [sm, mx, pivot] = seg.query(L, R);
Tutorial of Codeforces Round 960 (Div. 2)
10.
How to get started with solving Ad-Hoc tasks on codeforces Disclaimer : I just want to highlight some simple techniques used to solve Ad-Hoc tasks.
In my opinion, these are all simple techniques, but a lot of these are used even in much harder problems. I hope these will be helpful to some people.
1: Eliminate obvious cases, and see if you can simplify the problem.
<spoiler summary="Question">
https://codeforces.me/problemset/problem/1446/A
</spoiler>
<spoiler summary="Solution">
How do we get to the solution here.
We eliminate any weight >w, as that is useless. We can use any weight s that is w/2 < s < w. Therefore, we essentially need to solve only for small weights. Now it is easy to see you wont "jump" over the range.
</spoiler>
2: Ignore unnecessary information, and use it to draw the problem in new ways.
<spoiler summary="Question">
https://codeforces.me/problemset/problem/1442/B
</spoiler>
<spoiler summary="Solution">
Firstly notice, numbers we will not remove are really not different at all.
So we ...
with a pivot element. Clearly this will work only in an odd length array. This
proves we can, /2) moves. Making equal pairs is also really easy. Just do operations with all
pairs with apivot
11.
Easy geometry using std::complex It's always a hassle to define our 2D Geometry library during a contest. Is there a way to make our computational geometry lives easier in any way? Fortunately for us, there is, at least in C++, using complex numbers.
**Complex numbers** are of the form a + bi, where a is the real part and b imaginary. Thus, we can let a be the x-coordinate and b be the y-coordinate. Whelp, complex numbers can be represented as 2D vectors! Therefore, we can use complex numbers to define a point instead of defining the class ourselves. You can look at std::complex reference [here](http://www.cplusplus.com/reference/complex/).
<hr>
#### Defining our point class
We can define our point class by typing `typedef complex<double> point;` at the start of our program. To access our x- and y-coordinates, we can macro the `real()` and `imag()` functions by using `#define`. Of course, don't forget to `#include <complex>` before anything.
~~~~~
#include <iostream>
#include <complex>
using namespac...
12. Rotation about pivot p: `(a-p) * polar(1.0, theta) + p`
12.
[Tuωutoωoial] Convex Polygon Counting Hi everyone, today I'm back with another blog that sadly, [user:nor,2023-10-19] won't have to spend 45 minutes GPT-ing my anime and kaomoji propaganda to read it. ૮₍ ˃ ⤙ ˂ ₎ა 👅
---
Not sure whether there is another blog explaining this technique in a "so many visualizations" manner.
There are so many paper about these problems in particular. So please put your opinions and any other similar techniques you know in the comment section 📃📃📜. I think this is a "very known technique" for <span class="rated-user user-red">GM</span>s, so you guys might want to skip reading this blog.
I also do expect this is a "very common geometry problem" in China or something but, here is my attempt on explaining it.
Here is a cute quote by me oωo
> When it comes to polygon problems, sometimes you have to see 🐦 🎀 𝓈𝑒𝑔𝓂𝑒𝓃𝓉 🎀 🐦 in...
consider one point as a pivot, and count how many convex polygon if we use
this point as our left, ```c++ for (int i = 0; i < n; i++) { // i is the pivot memset(dp, 0, sizeof
13.
Codeforces Global Round 29 Editorial Thanks everybody for participating in the round!
### [A. Shortest Increasing Path](https://codeforces.me/contest/2147/problem/A)
Author: [user:BernatP,2025-09-20] Preparation: [user:BernatP,2025-09-20]
<spoiler summary="Hint1">
How big can the answer be?
</spoiler>
<spoiler summary="Hint2">
Which coordinates can you reach in $2$ or $3$ moves?
</spoiler>
<spoiler summary="Solution">
[tutorial:2147A]
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
#define int long long
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--){
int x,y;
cin>>x>>y;
if(x==y || x==y+1 || y==1)cout<<-1<<endl;
else if(x<y)cout<<2<<endl;
else cout<<3<<endl;
}
}
~~~~~
</spoiler>
### [B. Multiple Construction](https://codeforces.me/contest/2147/problem/B)
Author: [user:danx,2025-09-20] Preparation: [user:danx,2025-09-20]
<spoiler summary="Hint1">
Don't over comp...
Tutorial of Codeforces Global Round 29 (Div. 1 + Div. 2)
14.
Codeforces Round #763 (Div. 2) Editorial In my opinion, all of the problems have a very simple solution and actually require no special data structure at all. To demonstrate the point, I will also use EvErYoNe'S fAvOrItE lAnGuAgE: **Pascal**.
I will also include some notes, which are not related to the solution at all, but I find them interesting, so I will also include them in.
## [A. Robot Cleaner](https://codeforces.me/contest/1623/problem/A)
Obviously, the problem is solvable using simulation. But it is solvable in $O(1)$ time as well, and I will discuss it.
<spoiler summary="Tutorial">[tutorial:1623A]</spoiler>
<spoiler summary="Problem note">
- Yes, I purposely make the constraint small. Firstly, the simulation solution is straightforward to think of, and I think everyone should be able to do it. But secondly, I wanted to see high-rated people suffering from going too fast :).
- I hope that you like the animation! If you didn't know it yet, I use the library called [Manim](https://www.manim.community/), ...
range, picked by Alice, is the sorting range, and the number, picked by Bob,
is thepivot. - Testers, the sorting range, and the number, picked by Bob, is the pivot. - Testers
really like sorting. Some
Tutorial of Codeforces Round 763 (Div. 2)
15.
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...
for any $n$, by simply finding one "pivot" element to act as $a_2$, then
letting $a_1$ be the sum of, It turns out we can generalize the $n=3$ case for any $n$, by simply finding
one "pivot" element to
16.
TJIOI 2024 Editorial Thanks to the $20$+ teams who participated in the [TJIOI 2024](https://activities.tjhsst.edu/tjioi/) contest in-person and others who competed virtually in the [mirror](https://codeforces.me/contestInvitation/b55e39f0fa8decc6c57bb7fd133488fe299e2436). We hope you enjoyed the problems! Please let us know in the comments if you have any questions or feedback.
[problem:523552A]
Idea: [user:DanielQiu,2024-05-13], Preparation: [user:DanielQiu,2024-05-13]
<spoiler summary="Solution">
Rewrite $c$ in its binary representation. Let's call $c$ good if it has an even number of trailing zeros, possibly none.
**Claim:** Assume $c > 1$. If $c$ is good, then the current player can always make $c$ not good after their turn. On the flip side, if $c$ is not good, no matter what the current player does, it will always be good after their turn.
**Proof:** For the first part, if $c$ has $2$ or more trailing zeros, we can divide by $2$ to leave an odd number of trailing zeros. If $c$ doesn...
never cross the inner hull. At some moment, call the current pivot $P$. The new
pivot must be one of, 1. Solve the general case! (pivot is any point to begin) 2. Generate test data!
Specifically, At some moment, call the current pivot $P$. The new pivot must be one of three
points:
17.
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...
We can prove that no matter how the pivot is selected, each possible, matter how the pivot is selected, each possible permutation for the deeper
level appears with equal
18.
2 Special cases of Gaussian [Tutorial] Hello Codeforces. Today I'm writing about a Math topic that is really simple, but resources are limited.
SLAE stands for system of linear algebraic equations. Basically, consider we have a set of equations of the form :
$ a_0 \cdot x_0 + a_1 \cdot x_1 + a_2 \cdot x_2 + ... + a_{n-1} \cdot x_{n-1} = val_0 $
$ b_0 \cdot x_0 + b_1 \cdot x_1 + b_2 \cdot x_2 + ....+ b_{n-1} \cdot x_{n-1} = val_1 $
$ c_0 \cdot x_0 + c_1 \cdot x_1 + c_2 \cdot x_2 + ....+ c_{n-1} \cdot x_{n-1} = val_2 $
$ ..... $
Note that all $ a,b,c ... $ are real-valued arrays and all $ val_i , x_i $ are arbitrary reals. Realize how $ x_0, x_1 , ... x_{n-1} $ appear in each of the equations. In the post below, it is assumed we are dealing with reals, and not only integers.
Now, we want to find values of $ [ x_0 , x_1 ... x_{n-1} ] $ that satisfy each of the given equations listed, **given** all $ a,b,c...$ and $ val_i$. The simplest method to find such solutions is to use **Gaussian Eliminat...
. Basically, we can also prove the basis elements are those columns that have a
pivot row in RREF, pivot row in RREF. Hence, the number of pivoted variables is the size of the
basis.
19.
Codeforces Round #1091 and CodeCraft '26 (Div. 2) Editorial [problem:2217A]
===============
**Idea:** [user:shakr,2026-04-06] <br>
**Problem Setting:** [user:AS23,2026-04-06], [user:shakr,2026-04-06]
<spoiler summary="Hint 1">
What if Shaunak never uses the special move?
</spoiler>
<spoiler summary="Hint 2">
If Shaunak uses the special move, is using it on the first turn any different from using it later?
</spoiler>
<spoiler summary="Hint 3">
The above two cases are independent, and give you two conditions for Shaunak to win. What are they?
</spoiler>
<spoiler summary="Solution">
In a game without special moves, every turn reduces the total sum of the array, $\sum a_i$, by exactly $1$. Thus, the game lasts exactly $\sum a_i$ turns. The first player (Shaunak) wins if $\sum a_i$ is odd, and the second player (Yash) wins if $\sum a_i$ is even.
<ul>
<li><b>If $\sum a_i$ is odd:</b> Shaunak plays normally and wins. He doesn't need the special move.</li>
<li><b>If $\sum a_i$ is even:</b> Shaunak is guaranteed to lose ...
<= n; i++) { cin >> arr[i]; } int pivot; cin >> pivot;, boundaries at $l-1$ and $r$.
* The pivot constraint $l \le p_1 \le r$ means one toggled boundary, The constraint that $[l, r]$ must contain at least one pivot $p_i$ means we can
only pair two, arr[0] = arr[n+1] = arr[pivot];, int countL = 0, countR = 0; for (int i = 0; i < pivot; i++) { if (arr[i] !=
arr[i+1, pivot constraint $l \le p_1 \le r$ means one toggled boundary must be $< p_1$
and the other $\ge p_1
Tutorial of Codeforces Round 1091 (Div. 2) and CodeCraft 26
20.
Quicksort and chill I began holding some weekly student workshop at Imperial College London and I find some of the material presented useful for Codeforces community, so I will also post it here. So, enjoy!
Quicksort
---------
We already discussed some cool sorts such as mergesort that work in O(N log N). We want you to learn not “a sort algorithm”, but the ideas behind some of them.
A technique that works many times is finding redundancies in problems. We will illustrate this by trying to build quicksort out of insertion sort. Insertion sort takes each element and puts it in the right place. Take the next example: ( first array is the sorted one that is being constructed and the second is the remainings from the initial array ) [cut]
~~~~~
[] [ 2 , 3 , 1 , 2 , 5 ] →
[ 2 ] [ 3 , 1 , 2 , 5 ] →
[ 2 , 3 ] [ 1 , 2 , 5 ] →
[ 1 , 2 , 3 ] [ 2 , 5 ] →
[ 1 , 2 , 2 , 3 ] [ 5 ] →
[ 1 , 2 , 2 , 3 , 5 ] [ ]
~~~~~
This seems to work fine, but the array `[ 5 , 4 , 3 , 2 ...
only one segment. We take a random pivot and count the smaller elements. If
the number of smaller, quicksort algorithm with pivot on the leftmost position. ~~~~~ quicksort ::
(Ord a) => [a, this case. We have to take different elements at each step, therefore we will
choose thepivot, . And that gives us the standard quicksort algorithm with pivot on the leftmost
position., Each pivot has the same probability to appear. Therefore, the lengths of the
two arrays might be, The algorithm works as follows: - take the first element in the array (call it
pivot – “x” in the, The complexity we expect with a random pivot is `O(N)` because we expect a cut
at `N/2` at first
21.
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...
\dots a_{k-2}$ with unique values: $2^{25} \mid (i+1)$. Let their XOR sum be
$S$. Set thepivot $a_{k, ### D — The Equilibrium Pivot
22.
The Fear of Gaussian Elimination Recently, I was asked to help flesh out a problem for the [NAIPC 2019](http://naipc19.kattis.com) contest whose problems are also used every year as the "Grand Prix of America." Although I didn't create or invent the problem, I helped write a solution and created some of the test data for [Problem C, Cost Of Living](https://naipc19.kattis.com/problems/costofliving).
From the problem setter's perspective, this was intended to be an easy, A-level problem: suppose you have a table of values $a_{y,c}$ that meet the condition that: $a_{y, c} = b_c m_c^y \prod_{k<y} i_k$ for some $m_c > 0$.
If you are given a subset of the values in this table, and a subset of the values for $i_k$, determine whether a set of queried values $a_{y', c'}$ is uniquely determined or not. Note that $a_{0, c} = b_c$.
Most contestants immediately realized that above product can be written as a linear combination/sum by taking the logarithm on both sides:
$\log{a_{y, c}} = \log{b_c} + y \log{m_c} + \...
Calm and (Partially) Pivot
On](/predownloaded/ed/d2/edd2c36c94ac20839d904bb68e7c4350a051e7d0.png), 
* Pivot to a, ?)
* Pivot to a trading or HFT firm (matches CP-style thinking, but a steep
learning
24.
TheForces Round #39 (1000-Forces) Editorial [A](https://codeforces.me/gym/105672/problem/A)
Idea:[user:FP7317,2025-01-23]
<spoiler summary="solution">
### Problem Description
Since the constraints are small, you only need to simulate this process.
You are tasked with finding the minimum number of bandages required to defeat a dragon using a sword. The sword deals:
- **1 damage** if the i-th attack is **not divisible by 3**.
- **2 damage** if the i-th attack is **divisible by 3**.
If your health will becomes less than $0$ when the dragon attack you (in other words, your hp is less than $k$) , you must use a bandage.
</spoiler>
<spoiler summary="code(C++)">
```cpp
void solve(){
int h,k,n;cin>>h>>k>>n;
int ans = 0, l = k, r = 1;
while(h > 1){
r++;
k -= n;
if(k <= 0){
k = l - n;
ans++;
}
if(r % 3 == 0){
h-=2;
}else{
h--;
}
}
cout<<ans<<endl;
}
```
</spoiler>
...
of $y$; otherwise, $z$ and $x$ are on different sides of $y$. Thus, we use $y$
as thepivot and, Thus, we use $y$ as the pivot and partition the elements into the left and
right halves. To
Tutorial of TheForces Round #39 (1000-Forces)
25.
Hacker Cup 2019 Round 2 "Seafood" Solution I participated in this year's Facebook Hacker Cup and have enjoyed all the problems so far. The only problem I couldn't solve during the contest was the last problem of Round 2 named "Seafood" ([link](https://www.facebook.com/hackercup/problem/404425766835121/)). Facebook always uploads solutions right after the contest, which I'm thankful for, so I checked the [solution](https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2019-round-2-solutions/2860037857345430/) for that problem. However, I couldn't see why the solution works just from their description. Maybe I'm not thinking through it enough, but I found it hard to justify their approach in mathematical rigor. So I picked up key ideas from their description and filled out the details. I'm writing this for myself, and it turns out to be more complicated than I thought but I hope this helps some folks out there. If you have any simpler solution/description I'm happy to know.
Here is a short synopsis of the problem. You...
26.
Would this be a good div. 2 B-C? I thought of this problem a while back, but I'm not sure if it has been created before. Anyway, I think that it is a pretty fun (possibly easier) problem, but I might be a bit biased. I'd appreciate it if you could give it a try and rate it. Also, maybe someone can find a simpler proof for it.
Problem statement:
A derangement of length $n$ is a permutation $p$ where $p_i \ne i$ for all $1 \le i \le n$.
You are given an integer $n$. You have to count the number of permutations $p$ of length $n$ that can be converted into a derangement using the following operation some (possibly $0$) number of times:
- Choose any two integers $l, r$ such that $1 \le l < r \le n$ and sort the subarray $p_{l...r}$ in descending order.
For example, $p = [1, 2]$ would be counted for $n = 2$ as you can pick $l = 1,\,r = 2$ and transform the permutation into $[2, 1]$.
Constraints: $10$ testcases per test, each consisting of a single integer $n$ $(1 \le n \le 2 \cdot 10^5)$.
Examples:
$...
corresponding index. Call this pivot value $v$. Notice that if $p_v = v$ and
we can't move $v$ out of, fall into its corresponding index. Call this pivot value $v$. Notice that if
$p_v = v$ and we can't
27.
A2SV G5 — Contest 2 Editorial [Here](https://codeforces.me/contestInvitation/da039344b0dc2ce9e75d667164b7b6a98caba345) is the mashup link (the problems are from Codeforces' problem set).
#### [A. Anti-codeforces](https://codeforces.me/gym/491508/problem/A)
<spoiler summary = "Solution">
<p>Given that the length of the provided string is 10, the approach involves iterating through the string and comparing each character at position i with the corresponding character at position i in "codeforces."</p>
</spoiler>
<spoiler summary="Code">
```python3
t = int(input())
c = "codeforces"
for _ in range(t):
s = input()
res = 0
for i in range(10):
if s[i] != c[i]:
res += 1
print(res)
```
</spoiler>
#### [B. Alice and Bob Again] (https://codeforces.me/gym/491508/problem/B)
<spoiler summary = "Hint">
<p>
Consider the first character in each pair.
</p>
</spoiler>
<spoiler summary = "Solution">
<p>
Take every other character starting from the first...
print(pair_count) ``` #### [E. Pivot Sorting]
(https://codeforces.me/gym/491508, #### [E. Pivot Sorting] (https://codeforces.me/gym/491508/problem/E)
28.
[Tutorial]:Gauss-Jordan Elimination — Part 1: The Theory **Gauss-Jordan Elimination — Introduction**
Given a system of $n$ linear algebraic equations (SLAE) with $m$ variables, we are asked to solve it (i.e., determine whether it has no solution, a unique solution, or infinitely many solutions). In the case of at least one solution, return any one of them.
In short, we are given the following system of equations:
$$
\begin{cases}
a_{11}x_1 + a_{12}x_2 + \cdots + a_{1m}x_m = b_1 \\
a_{21}x_1 + a_{22}x_2 + \cdots + a_{2m}x_m = b_2 \\
\vdots \\
a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nm}x_m = b_n
\end{cases}
$$
where $a_{ij}$ ($1 \le i \le n,\ 1 \le j \le m$) and $b_i$ ($1 \le i \le n$) are known constants, and $x_i$ ($1 \le i \le m$) are the unknowns.
Alternatively, the system can be represented in matrix form as:
$Ax = b$
where $A$ is an $n \times m$ matrix of coefficients $a_{ij}$, and $b$ is an $n$-dimensional vector of constants.
This method can also be applied when the system has modular co...
equation $r$, subtract $a_{ri}$ times the pivot row (equation $e$). This sets
all other $a_{ri} = 0, 2. For each remaining equation $r$, subtract $a_{ri}$ times the pivot row
(equation $e$). This sets
29.
Coding Track NITSHACKS 8.0 Editorial Thank you everyone for participating!<br>
Here's the <a href="https://codeforces.me/blog/entry/148539">Blog Link</a> and <a href="https://codeforces.me/contestInvitation/bf7862176fe66f9655deac0d350e142a848b624a">Contest Link</a>
<br>
<h3><a href="https://codeforces.me/gym/652259/problem/A">A. AntiDitto Arrays! </a></h3>
<p>Idea and Prepared by: [user:itsiftikar02,2025-11-23]</p>
<spoiler summary="Hint 1">
The final array will be the form of either $1010101...$ or $0101010...$
</spoiler>
<spoiler summary="Hint 2">
$x^1 + x^2 + x^3 + ... + x^{n - 1} < x^n$ $\forall$ $x \ge 2$
</spoiler>
<spoiler summary="Solution">
**Case $x = 1$:** we will calculate the cost for both $101010...$ and $010101...$. Then minimum of this cost will be the answer.
**Case $x \ge 2$:** For other value of $x$, it will always optimal not to change the value of $a_n$.
if $a_n = 1$ then the final array will be $.....0101$ and
if $a_n = 0$ then the final array will be $.....1010$
</...
every possible $X$ (meeting point or pivot) takes $O(n)$ per query, resulting
in $O(n^2)$ overall, A direct way to solve the equation for every possible $X$ (meeting point or
pivot) takes $O(n)$ per
30.
SWERC Documentation ~~~~~
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=99824LL;
vector<ll> fat,ifat;
ll Mo_bucket; //sqrt(arr.size())
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
temp...
det; vector pivot; Matrix() {N=0LL; M=0LL; Red=nullptr; Inv=nullptr; Trans, ++; } if(line==N) {continue;} pivot[ind]=true; double, ,N) {val+=B.a[i][j]*b[j];} while(!pivot[piv] && piv, ; Matrix *Red, *Inv, *Trans; double det; vector pivot;, ]); dummy.pb(a[y]); dummy.pb(a[z]); sort(whole(dummy),cmp); T pivot=dummy[1LL];
vector rel
31.
Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2) Hello, Codeforces!
I am pleased to invite you to participate in [contest:1994], which will be held at [contest_time:1994]. You will be given **8 problems** and **2 hours** to solve them. It will be rated for **all participants**.
The theme of the round is computer games!
Tasks for the round were prepared by [user:EJIC_B_KEDAX,2024-07-16], [user:zwezdinv,2024-07-16], [user:green_gold_dog,2024-07-16], [user:molney,2024-07-16], [user:azureglow,2024-07-16] and [user:Sokol080808,2024-07-16].
We would like to thank everyone who assisted in the preparation of this round:
1. Our coordinator [user:74TrAkToR,2024-07-16] for his useful advices and help in preparing the tasks!
2. [user:Qwerty1232,2024-07-16] for red interest in testing the round.
3. [user:turmax,2024-07-16] for the red-black testing.
4. [user:makrav,2024-07-16], [user:arbuzick,2024-07-16], [user:Anonymous_Noob,2024-07-16], [user:Hyperbolic,2024-07-16] for red testing.
5. [user:ivan.alexeev,2024-07-17], [...
Announcement of Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
32.
[Tutorial] Quick Sort Hi codeforces!
Quick Sort is a sorting algorithm (duh).<br>
### History:<br>
A bit about its history, It was developed by a British computer scientist Tony Hoare (Not that it helps in understanding the algorithm)<br>
#### Application / Where to use Quick Sort:<br>
There are many sorting algorithms then why do we need to learn/ use quick-sort? Quick sort is used in places where we need to efficiently sort the elements. It is also used when there are restrictions in space availability.<br>
#### What is the time complexity of quick sort:<br>
Quick sort has an average time complexity of O(n log n) but if we don't chose the pivot correctly, the worst case time complexity is O(n^2).
#### How Quick Sort works:<br>
Quick sort can be related in the real life like this. Suppose a student comes to a teacher and asks her to tell the student s who are better than him and the ones who are weaker than him. Now the teacher looks at the class in the order they are sitting, and for each stude...
O(n log n) but if we don't chose the pivot correctly, the worst case time
complexity is O(n^2, we don't chose the pivot correctly, the worst case time complexity is O(n^2).
#### How Quick Sort, > 
Now we chose a pivot element. Lets say, Now lets move to quick sort, in quick sort we chose an element as a pivot
element which is similar, pivot){ while(l<=r){ while(arr[l]<pivot){ l++; } while
33.
Know Some Sorting Techniques Introduction:
-------------
Sorting is a fundamental operation in computer science, playing a crucial role in various applications and algorithms. Sorting involves arranging elements in a specific order, making it easier to search, retrieve, and analyze data. There are numerous sorting algorithms, each with its own unique approach and time complexity. In this blog, we'll explore some commonly used sorting techniques and see their code.
### 1) Selection Sort
Introduction:
Selection Sort is a simple sorting algorithm that repeatedly selects the minimum element from an unsorted portion of the array and places it at the beginning. This process continues until the entire array is sorted.
Time Complexity:
- Best: O(N^2)
- Average: O(N^2)
- Worst: O(N^2)
Code:
~~~~~
int main()
{
int n = 5;
int arr[] = { 9, 1, 5, 6, 3 };
for (int i = 0; i < 5; i++) {
int position = 0, minimum = 1e5;
for (int j = i; j < n; j++) {
if (a...
low, int high) { int pivot = arr[low]; int p1 = low; int p2 = high; while (p1, ~~~~~ int partition(vector& arr, int low, int high) { int pivot = arr[low]; int
p1
34.
Exploring std::sort Recently, I was solving this problem : [problem:2219C]
While writing the solution, I encountered a runtime error with my submission [submission:377542151].
After trying to find out the bug for 30 mins I finally got the error.
I have written a decent amount of C++ but this is the first time I have encountered a runtime error caused by `std::sort`
The exact problem lies in this part of the code :
~~~~~
sort (tree[u].adj.begin(), tree[u].adj.end(), [&tree](int a, int b) {
return ((tree[a].exp0 - tree[a].exp1) <= (tree[b].exp0 - tree[b].exp1));
});
~~~~~
while it looks pretty normal the bug is caused by the use of `<=` in `std::sort`
while investigating I found out that there are some properties that must be satisfied while using `std::sort`
- The comparator must obey strict weak ordering **i.e** `compare(A, A)` **must return false**
- If `compare(A, B)` returns true, `compare(B, A)` must return false.
- If `compare(A, B)` returns true, `compare(B...
element equal to the pivot, allowing the algorithm to swap them. This happens
because a valid, moving when they hit an element equal to the pivot, allowing the algorithm to
swap them. This happens, By using `<=`, my comparator returned `true` when it hit elements equal to the
pivot. The pointer
35.
Why Arrays.sort() Got TLE but Collections.sort() Got Accepted on Codeforces Recently, I encountered an interesting issue while solving a problem on Codeforces. Initially, I submitted a solution using Arrays.sort() to sort my array. Unfortunately, it resulted in a Time Limit Exceeded (TLE) error. After some experimentation, I replaced Arrays.sort() with Collections.sort() for the same logic, and to my surprise, the solution was accepted. Curious about this behavior? Let’s dive into the details!
Understanding the Sorting Mechanisms
Both Arrays.sort() and Collections.sort() are Java utilities designed to sort data, but they differ in terms of implementation and behavior:
1. Arrays.sort()
Algorithm Used:
For primitive types (int[], long[], etc.), Arrays.sort() uses Dual-Pivot QuickSort, which has an average time complexity of O(n log n) but can degrade to O(n²) in the worst case.
For objects (Integer[], String[], etc.), Arrays.sort() uses TimSort, which has a guaranteed time complexity of O(n log n) in all cases.
Edge Cases:
Dual-Pivot Quic...
hit the worst-case performance of QuickSort, it can degrade to O(n²). This
happens because Dual-Pivot, .), Arrays.sort() uses Dual-Pivot QuickSort, which has an average time
complexity of O(n log n) but can, Dual-Pivot QuickSort, used for primitive arrays, may perform poorly if the data
is highly, For primitive types (int[], long[], etc.), Arrays.sort() uses Dual-Pivot
QuickSort, which has an
36.
Learning Roadmap for a Data Analyst **The very first question to hit our mind is who is a data analyst? What do they do?.**
In simple words, a data analyst is responsible for collecting data, processing it, and analyzing it to find sensible insights for decision making.
In most cases, an analyst will work on the raw data, grind it to produce action-oriented insights. Most of the analysts won’t work on the core machine learning or the deep learning models.
A data analyst will make use of multiple tools to process the data and work with it. Having experience in working with different tools and statistics is most important for them.
In the next blocks, we will be discussing each skill and related certifications as well.
**1. Statistics**
For every data professional, stats and math are the must-haves. Because, without the knowledge of stats and probability, one cannot able to interpret the data effectively.
Some of the major topics include descriptive and inferential stats. If you are a pure beginner, you ...
charts, analysis, VBA, Macros, Filters, and Formulas. The Pivot table and
VLOOKUP functions are the, Pivot table and VLOOKUP functions are the most commonly used functions on excel
by analysts.
37.
Weak tests for Hello 2020 D Tests for problem D are too ill-conceived: [user:kiimak,2020-01-04]'s told his submission fails on a simple case with n = 5 and here is my dumb solution.
As it was mentioned, we need to check if there is a pair of indices $(i, j)$ such that $a_i$ and $a_j$ intersect but not $b_i$ and $b_j$(or vice versa). That is what we do to find those indices:
Perform the following operation 5000 times.
Take a randomly generated pivot index not chosen before. This index might be $i$ in our assumption. Then iterate through $[1\dots n]$ looking for $j$. If there is one suitable for us then the answer is NO, we can stop our algorithm. Else try taking another $i$. This runs in $\mathcal{O}(5000 \times n)$. Now I'm going to tell why it's a terrible solution and why it mustn't pass the tests(thanks to [user:lemelisk,2020-01-04], it's already hacked).
Imagine a test where $n = 100000$ and there are only two segments intersecting in $a$ (let their indices be $i$ and $j$) and no segments intersect...
of picking $i$ or $j$ as the pivot index. We pick only $\frac{5000}{10^5} =
\frac{1}{20} = 0.05$ of, . Take a randomly generated pivot index not chosen before. This index might be
$i$ in our assumption, Perform the following operation 5000 times. Take a randomly generated pivot
index not chosen
38.
Gauss Jordan Elimination I am trying to solve http://www.spoj.com/problems/GS . Here is my approach.
Let u, v denote the start and end vertices. [0 based index]
Let E[i] = expected number of roads to cross while going from vertex i to vertex v [0 <= i <= N-1]
Let preferred value of an edge (i, j) be P(i, j).
Now, from vertex i (other than vertex v), there are degree(i) possibilities.
Let the neighbors of i be i1, i2, ..., ik.
Thus, E[i] = [(1+E[i1])*P(i, i1) + ... + (1+E[ik])*P(i, ik)] / [P(i, i1) + ... + P(i, ik)]
For vertex v, E[v] = 0
So, we get a linear equation for each vertex. Overall, we get N equations with N unknowns, which can be solved by elimination.
However, I am getting Wrong Answer. I think there is a bug in my implementation of Gauss Jordan Elimination (this is the first time I am coding that). Can somebody help me?
Here is my code.
~~~~~
typedef long double db;
typedef vector<db> vd;
typedef vector<vd> vvd;
#define EPS 1e-9
db GaussJordan(vvd...
; } assert(fabs(A[i][i]) >= EPS); db pivot = A[i][i]; det *= pivot; for (int k
= 0; k < N; k, ]) >= EPS); db pivot = A[i][i]; det *= pivot; for (int k = 0; k < N; k++)
A[i][k] /=pivot
39.
Please make some functions that makes problem proposals private again! Hello.
I am interested in making contest and I have bunch of problem proposals. My problems are classified as below:
- Used for past(already approved) contests like [Round 566](https://codeforces.me/contest/1182)
- Used for future contest proposals
- Excluded from contest proposals due to pivoting or something else
- Abandoned
I want to make some problems to private, but for now I can make my contest proposals to private only.
Please make some functions that users can make problem proposals to private again!
Thank you for reading this.
40.
Problem: Array Stabilization Hello guys, for all those who message me here on codeforces, i cant reply since i have reached my daily message quota...
### Now to the Hack for todys Div. 3 B. [problem:1095B]
-------------------------------------------------------
For those who tried to solve this problem in java and Arrays.sort() and got hacked, you need to know that this method implements a deterministic dual pivot quicksort for primitive types like int. This maybe doesn't sounds bad, but it is! A deterministic quicksort is only on random input data in $\mathcal{O}(n\log n)$, but its worst case behaviour is still $\mathcal{O}(n^2)$. Therefore it is possible to find inputs where you will get TLE (like in my hack).
There is a generator for this from [user:dalex,2018-12-27] [generator](https://codeforces.me/blog/entry/4827), and many problem setters know about this an can build such testcases.
There are however many ways to fix this here i will list some examples:
- use Integer[] instead of int[]
- u...
Arrays.sort() and got hacked, you need to know that this method implements a
deterministic dualpivot, know that this method implements a deterministic dual pivot quicksort for
primitive types like int
41.
B. Pasha and String Pasha got a very beautiful string s for his birthday, the string consists of lowercase Latin letters. The letters in the string are numbered from 1 to |s| from left to right, where |s| is the length of the given string.
Pasha didn't like his present very much so he decided to change it. After his birthday Pasha spent m days performing the following transformations on his string — each day he chose integer ai and reversed a piece of string (a segment) from position ai to position |s| - ai + 1. It is guaranteed that 2·ai ≤ |s|.
You face the following task: determine what Pasha's string will look like after m days.
Input
The first line of the input contains Pasha's string s of length from 2 to 2·105 characters, consisting of lowercase Latin letters.
The second line contains a single integer m (1 ≤ m ≤ 105) — the number of days when Pasha changed his string.
The third line contains m space-separated elements ai (1 ≤ ai; 2·ai ≤ |s|) — the position from which Pasha started t...
pivot = a[(s+e)/2]; while(i <= j){ while(a[i] < pivot){ i++; } while(a[j] >
pivot, public static void sort(int a[], int s, int e){ int i = s, j = e; int pivot =
a[(s+e)/2
42.
How to solve "Pivoting point" from 19-20 Pacific Northwest regional? Original comment:
https://codeforces.me/blog/entry/72252?#comment-587046
How to solve "2019-2020 ACM-ICPC Pacific Northwest Regional Contest" problem H pivoting point?
Particularly, there's a "p-dk.cc" in the official solution package [1]. Its logic looks much simpler than the editorial, but I don't understand why it works. Meanwhile, a bunch of submissions seem to follow the same logic. Could somebody explain it to me? In particular, what does [left] and [rep] mean?
[1] http://www.acmicpc-pacnw.org/ProblemSet/2019/editorial.zip
43.
Seeking Efficient Approach to Find Pivot in Rotated Sorted Array with Duplicates Problem Statement:
Given a rotated sorted array that may contain duplicate elements, the task is to find the pivot index. The pivot is defined as the index where the sorted array was rotated, and it is the smallest element in the array.
~~~~~
Input : [2,5,6,0,0,1,2]
Output : 3
Input : [2,1]
Output : 1
Input : [2,2,2,3,2,2,2]
Output : 4
Input : [1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1]
Output : 14
~~~~~
I'm facing challenge: In a rotated sorted array with unique elements, identifying the pivot index is straightforward using binary search in O(log n) time. However, when the array contains duplicates, this approach becomes less effective due to the inability to determine which half is sorted. Any insights would be greatly appreciated.
Seeking Efficient Approach to Find Pivot in Rotated Sorted Array with Duplicates, to find the pivot index. The pivot is defined as the index where the sorted
array was rotated, and it, I'm facing challenge: In a rotated sorted array with unique elements,
identifying thepivot index
44.
To the several people who got TLE14 on yesterday's problem D... [user:Manoj_mk,2025-06-04] [user:phoenix_beast117,2025-06-04] [user:sukhbir0609,2025-06-04] [user:1091857051,2025-06-04] [user:cai_lian_2023,2025-06-04] [user:HARSHdeep1234,2025-06-04] (I think that's all of you)
That was me. Hi, I guess.
Or rather, it was you, submitting in an old version of Java, and using Arrays.sort(), that caused you to get hacked.
Unfortunately, it's possible to make Arrays.sort() take O(n^2) time when sorting primitive data types — and that's because it ends up defaulting to quicksort, and if I use a certain script that I don't even understand properly, I can create an array specifically to cause quicksort to use the worst possible pivot at each iteration. That's why you all got hacked.
If you don't want to be hacked or FST, use Collections.sort(). But also, why don't you just use the newer Java version?
can create an array specifically to cause quicksort to use the worst possible
pivot at each, quicksort to use the worst possible pivot at each iteration. That's why you
all got hacked.
45.
[Video]: How to flip subarrays, subtrees and downward paths ft. 2217G Problem [G. Down the Pivot](https://codeforces.me/contest/2217/problem/G) had an interesting subproblem, given a tree where nodes contain 0 or 1, in one operation, you are allowed to select one downward path and flip it. What is the minimum number of operations required to set all nodes to 0?
So I created a video discussing 3 techniques:
* Minimum operations when you are allowed to flip a subarray.
* Minimum operations when you are allowed to flip a subtree.
* Minimum operations when you are allowed to flip a downward path.
https://youtu.be/ekhPwtSgY_g
Problem [G. Down the Pivot](https://codeforces.me/contest/2217/problem/G) had
an interesting
46.
How to O(n*n) online convex hull constructrion By Graham Scan O(n*n*logn) would be possible for online construction of convex hull. Can you help me with O(n*n) algorithm.
Also what is the difference between 2D CH construction and 3D CH construction
And in graham scan there is a function to sort according to polar order which i did not understand. Please help.
~~~~~
bool polar_order(Point a, Point b){
//ccw is a function that returns 0 if collinear -1 if counter-clockwise and 1 if clockwise
//pivot is the lowest y-coordinate point(tie broken by lowest x-coordinate)
int order = ccw(pivot,a,b);
if(order==0)
return sqrdist(pivot,a) < sqrdist(pivot,b);
return (order==-1);
}
~~~~~
Also if there are some problems you know of convex hull, please share them. Thank you.
-1 if counter-clockwise and 1 if clockwise //pivot is the lowest y-coordinate
point(tie, that returns 0 if collinear -1 if counter-clockwise and 1 if clockwise //pivot
is the lowest y
47.
Java Arrays.sort() is safe now? I saw many articles saying that Java Arrays.sort() on int[] has worst case complexity O(n^2) but according to the Java docs:
"
public static void sort(int[] a,
int fromIndex,
int toIndex)
Sorts the specified range of the array into ascending order. The range to be sorted extends from the index fromIndex, inclusive, to the index toIndex, exclusive. If fromIndex == toIndex, the range to be sorted is empty.
Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.
"
Does this mean that Arrays.sort() is safe to use now in Java? Does it also hold for Kotlin, or does Kotlin use a lower version of Java that still has the hack-vulnerable quick-sort?
empty. Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by
Vladimir Yaroslavskiy, , the range to be sorted is empty. Implementation note: The sorting algorithm
is a Dual-Pivot
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/03/2026 23:41:01 (h1).
Desktop version, switch to mobile version.
Supported by
