Sorting

Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. Estimated time of maintenance: from 2 Aug, 16:00 (UTC) to 2 Aug, 20:00 (UTC).
×

# | User | Rating |
---|---|---|

1 | tourist | 3819 |

2 | Benq | 3745 |

3 | ksun48 | 3560 |

4 | Radewoosh | 3511 |

5 | Um_nik | 3489 |

6 | peehs_moorhsum | 3460 |

7 | Petr | 3414 |

8 | Miracle03 | 3410 |

9 | maroonrk | 3400 |

10 | sunset | 3338 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 207 |

2 | awoo | 182 |

3 | Errichto | 180 |

4 | Um_nik | 179 |

5 | -is-this-fft- | 174 |

5 | maroonrk | 174 |

7 | Radewoosh | 172 |

7 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

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

`305`

— search for 305, most probably it will find blogs about the Round 305`andrew stankevich contests`

— search for words "andrew", "stankevich" and "contests" at the same time`user:mikemirzayanov title:testlib`

— search containing "testlib" in title by MikeMirzayanov`"vk cup"`

— use quotes to find phrase as is`title:educational`

— search in title

2.

Country statistics Hi guys!
I have prepared for you some statistics on how countries are performing against each other in Codeforces which I hope you will find interesting!
## Top 5 countries with the most users with certain rank:
![ ](/predownloaded/15/0d/150df04ac1d17beab569ac076e50fc114f7c5f83.png)
## Top 5 countries with highest percentage of their users in a certain rank:
(Here I don't count countries that have less than 10 Codeforces users)
![ ](/predownloaded/3b/f0/3bf088e64b43df38721a048501e8b85c2ed81241.png)
#### Newbie:
![ ](/predownloaded/0d/44/0d446aaa1317d5b095bf4591643da55edbf965c9.png)
#### Pupil:
![ ](/predownloaded/ad/23/ad2304a7f229e8d2a5e7b99055f9d8eaeb909911.png)
#### Specialist:
![ ](/predownloaded/78/a9/78a93ca3b698de2b72b0b600cbb73561bff49386.png)
#### Expert:
![ ](/predownloaded/e6/d5/e6d52596fab286b83c02d5ebe894a0af3c1650dc.png)
#### Candidate Master:
![ ](/predownloaded/9a/88/9a88461e5859c0ae7d5c7f9c972fbcf2e6b7192b.png)
#### Master:
![ ](/pre...

Sorting

3.

An alternative sorting order for Mo's algorithm Hello, Codeforces!
I think many of you know about Mo's algorithm. For those, who don't know, please read this [blog](https://codeforces.com/blog/entry/7383).
Here, I consider an alternative (and faster) approach of sorting queries in Mo's algorithm.
# Table of contents
* [Canonical version of the algorithm](#s1)
* [Achieving a better time complexity](#s2)
* [Relation to TSP](#s2-1)
* [Hilbert curve](#s2-2)
* [Benchmarks](#s3)
* [Applicability](#s4)
<div style="font-size: 1pt">
[cut]
</div>
<a name="s1"></a>
# Canonical version of the algorithm
The canonical version of this algorithm has $O((n + q)\cdot\sqrt{n})$ time complexity if insertions and deletions work in $O(1)$.
Usually, the two comparators for query sorting are used. The slowest one:
~~~~~
struct Query {
int l, r, idx;
inline pair<int, int> toPair() const {
return make_pair(l / block, r);
}
};
inline bool operator<(const Query &a, const Query &b) {
re...

An alternative sorting order for Mo's algorithm, (and faster) approach of sorting queries in Mo's algorithm. # Table of
contents * [Canonical, . Then sort the queries according to their $o_i$., As you can see, such sorting order doesn't make Mo's algorithm work slower, and
when $q, But TSP is NP-complete, so it cannot help us to find the optimal query sorting
order. Instead, we, Here, I consider an alternative (and faster) approach of sorting queries in
Mo's algorithm., Usually, the two comparators for query sorting are used. The slowest one:

4.

Lecture #3 — Exchange arguments (sorting with dp) Hi. I'm back from USA!
I will do a new lecture tomorrow (Thursday) at 2pm CEST on my Youtube channel: [https://www.youtube.com/watch?v=7hFWrKa6yRM](https://www.youtube.com/watch?v=7hFWrKa6yRM).
Watch me live (and ask questions), or just watch the video later.
This will be part 1, and I will do part 2 in a few days (maybe Tuesday).
**UPDATE** — part 2 is coming on Thursday, same time. Link: [https://www.youtube.com/watch?v=gXxu-Cr4b4c](https://www.youtube.com/watch?v=gXxu-Cr4b4c).
There are no prerequisites this time.
I recommend reading the materials below in advance, and trying to solve problems 1 and 5.
If you are strong, just read problems and see if you can't solve something (maybe problem 8?).
### Technique "Exchange Arguments"
If we're given $n$ items and we should choose some of them and choose their order, we should sort them with some strange/tricky comparator, and then do $O(N^2)$ dynamic programming.
The dp should be $dp[pref][used]$ — best po...

Lecture #3 — Exchange arguments (sorting with dp), should choose some of them and choose their order, we should sort them with
some strange/tricky, If we're given $n$ items and we should choose some of them and choose their
order, we shouldsort

5.

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

Algorithm](https://codeforces.com/blog/entry/88494) - [An alternative sorting
order for Mo's algorithm, arguments (sorting with dp)](https://codeforces.com/blog/entry/63533) -
[Matrix Exponentiation, useful](https://codeforces.com/blog/entry/63823) - [Lecture #3 — Exchange
arguments (sorting with dp, ://codeforces.com/blog/entry/20528) - [Sort before insert — A small, yet
powerful extension to Mergesort

6.

C++ tips and tricks Hello, codeforces.
I would like to tell you about some tricks and constructions I use in C++. They are not hidden or anything, moreover, most of them are from stl or maybe well known among software engineers, but I often see codes where something is done by hand in, say, 5 lines, while in stl there is a function which does the same.
The things below are filtered by my personal sense of non-popularity (so no `__builtin` functions) and usage frequency (so there almost surely are similar things I don't know about) and are not really sorted in any reasonable order. Let's begin. [cut]
<hr>
- ### `all(x)`
This may be an exception to the rule of non-popularity -- this is quite widely used, but some next items will depend on `all(x)`, so I define it here. So, I talk about
```[c++]
#define all(x) (x).begin(), (x).end()
```
Now sorting a vector looks like `sort(all(vec))` instead of `sort(vec.begin(), vec.end())`.
However, it's not all about this define. Imagine you nee...

Now sorting a vector looks like `sort(all(vec))` instead of `sort(vec.begin(),
vec.end())`.

7.

[Tutorial] Sorting with lambda Hello, Codeforces!
Today I want to share with you something that often gets brushed off because it's a very basic concept — sorting. I think that this topic is often overlooked even though it can be very useful. This blog (my first on Codeforces, yaay) is thus rather intended for beginners in C++. I'll describe a technique that makes sorting fast to implement — lambdas. For simplicity, arrays will always mean `vector` in this blog.
There are two main usages of sorting I want to describe:
#### 1. Sorting an auxiliary array to keep the original array unchanged.
This is often the case when our data is splitted into several separate arrays, that are somehow connected together. This may occur when each type of data is given in separate rows. For example, one array could contain a value of a cell and the other one — it's color. Say that we want to simultaneously sort both those arrays by value (increasing).
In order to do that, we may rather introduce a new a...

[Tutorial] Sorting with lambda, accepted. It only differs in the usage of the sorting technique described
before., concept — sorting. I think that this topic is often overlooked even though it
can be very useful, it's a very basic concept — sorting. I think that this topic is often
overlooked even though, numbers from `0` to `n - 1`. We now simply sort according to the following
lambda: `sort(order.begin, of sorting you prefer: lambdas, `operator<` overloading, comparator function
or comparator object?, to simultaneously sort both those arrays by value (increasing)., #### 1. Sorting an auxiliary array to keep the original array unchanged., #### 2. We want to sort complex objects or we need more comparators than one., Even though we all know and love sorting, in advanced uses writing comparator
objects, functions, Sometimes we need to sort objects that are more complex than basic integers /
floats etc. Those use, There are two main usages of sorting I want to describe:, ``` sort(queries.begin(), queries.end(), [](query& a, query& b) { return
a.right - a.left, b. round brakets containing `parameters` — for sorting purposes those are
always two elements

8.

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

9.

Day 1/60: Div.2 632 and easy sorting/binary search problems Today I participated in the Div.2 Round 632 and solved all the 1200 level problems of sorting and binary search from my list. I will write the main takeaways for self reference.
**Div. 2 Round 632:**
<spoiler summary="Contest experience">
I got confused and thought that a solution was only possible in A when both sides were odd, so I first submitted a chessboard coloring, this evidently failed the first test. I realized that I could just change the lower right corner to black when one of the sides was even, but this failed once more because it is already black when both sides are even. Finally realized this and sent a fixed solution after 14 minutes.
For the first couple minutes I didn't recall that the elements of $A$ were just ${-1,0,1}$. After realizing this for each position I just need to know whether I need to make $a[i]$ it bigger or smaller, and for that we only need to check if there is a $1,-1$ before it (respectively). This one took 11 minutes total.
Finall...

Day 1/60: Div.2 632 and easy sorting/binary search problems, This is sorting the three list and comparing consecutive ones to find, **Sorting:**, Today I participated in the Div.2 Round 632 and solved all the 1200 level
problems ofsorting

10.

Sorting in Python 3 for Competitive Programming ### Introduction
Today, we will discuss many cases for sorting in Python 3. It’s a must-have skill in competitive programming.
### Explaining the Sort Function, and its Different Arguments.
By default, the sorting function, sorts in ascending order.
The sort function can take two optional arguments:
A- The **reverse** attribute: It takes a boolean value. True if the sorting is descending, false if ascending.
```python
L = [3, 5, 1, 8, 5, 9]
L = sorted (L, reverse = True)
print (L) # [9, 8, 5, 5, 3, 1]
```
B- The **key** attribute: It takes a comparison function (I will call it: **key function** throughout this article) for custom sorting.
The key function is applied to each element of the list, to create a pseudo list of the new values returned from that function. Then, the sorting is done based on the values of this pseudo list.
> Note: We assign a function to the key attribute, not the return of a function.
Example:
```python
L = ['g', 'a', 'n', 'A'...

Sorting in Python 3 for Competitive Programming, returned from that function. Then, the sorting is done based on the values of
this pseudo list., ### Introduction Today, we will discuss many cases for sorting in Python 3.
It’s a must-have skill, ### Secondary Sorting., ### Sorting Based on the i-th Element in a List of Tuples. Suppose that we have
a list of tuples, ** throughout this article) for custom sorting., **How to write a sorting key function?**, , then it will have the opposite sorting effect that was set for it., . By default, the sorting function, sorts in ascending order. The sort function
can take two optional, A- The **reverse** attribute: It takes a boolean value. True if the sorting is
descending, false, If we have a dictionary, and the keys are strings, values are integers, and we
want tosort, The function will compute a value of each element, that we will sort upon., The sort function can take two optional arguments:, We will return the second element from that tuple, to sort based on it., What if we want to sort a dictionary based on ascending values, then by
descending keys., ]), reverse = True) # sorting based on ascending values, then by descending
keys print (d) # [('f, ```python d = {'f' : 8, 'd' : 8, 'b': 9} # we want to sort based on ascending
values, ```python def keyFunc (element) : return element[1], element[0] # sorting based
on values, sorting in descending order.

11.

Interactive sorting problem in atcoder I am trying to solve an interactive problem from atcoder's practice contest. The abridged problem statement is as follows:
~~~~~
Given the value of N where N ranges from [1,26] and Q where Q is the maximum number of queries that one can make, sort a list of distinct uppercase alphabets in ascending order. N indicates that there are N characters starting from 'A'. Hence, N = 5 means that our final list must contain 'A', 'B', 'C', 'D' and 'E'.
A single query is defined as printing out a string "? x y" where x and y represent the characters we want to check the relation between (e.g. "? A B"). The problem restricts the number of such queries to Q. Hence, we must determine the final order of the characters using at most Q queries.
For each query, we get a binary answer '<' or '>' from stdin. '<' indicates that x comes before y in the final list. '>' means otherwise.
~~~~~
Problem link: [here](http://practice.contest.atcoder.jp/tasks/practice_2)
(Do note that atcoder accoun...

Interactive sorting problem in atcoder, a separate comparison-efficient function to handle this. Otherwise, just use
merge-sort., couldn't find a better sorting algorithm that would solve the problem — I even
tried STLsort, of queries that one can make, sort a list of distinct uppercase alphabets in
ascending order. N indicates, ) — 2^(ceil(logn)) + 1 which gives 8 in this case. I couldn't find a better
sorting algorithm, I tried using merge sort to solve the problem — I changed the comparison at the
merging step

12.

Codeforces: Results of 2017 <img src="/predownloaded/e4/09/e40915ee54c5991b91098756a90270d94be893b3.jpg"/>
Happy New Year, Codeforces!
I hasten to wish the whole community (and including me) correct programs, sudden insights, beautiful ideas and interesting problems!
I hope that you have met the new year at least as fun as I am. Have you had enough sleep after New Year's Eve? This year, the traditional post summarizing the past year, I sat down to write only on January 1, 2018. I hope that I will not have to sum up the whole year.
This post is important to me, since it draws a line to all the work done by the Codeforces team and the entire community in 2017. Many thanks to the team: all of the achievements listed below are the result of joint efforts. We did an excellent job! The community must know its heroes. In 2017, [user:MikeMirzayanov,2018-01-02], [user:KAN,2018-01-02] (problem coordinator), ~gritukan,2018-01-02 (second problem coordinator), ~netman,2018-01-02 (ex-second problem coordinator), ~k...

by name, sorting by them. 1. List of the contests to which a problem belongs,
accessible from

13.

Sorting Algorithm (C++ general implementation) In Algorithm Design, Sorting is an important part. Different algorithm use the sorting algorithm. Some Interesting sorting algorithm are include here: Bubble Sort, Heap Sort, Quick Sort, Counting Sort, Selection Sort, Insertion Sort etc.<br /><br />In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output.<br />Bubble Sort:<br /><br />Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass throu...

Sorting Algorithm (C++ general implementation), ) algorithms such as selection sort or bubble sort; the best case (nearly
sorted input) is O(n), . Some Interesting sorting algorithm are include here: Bubble Sort, Heap Sort,
QuickSort, Counting, Bubble sort is a simple sorting algorithm that works by repeatedly stepping
through the list, Counting sort (sometimes referred to as ultra sort or math sort) is a sorting
algorithm which (like, Heapsort is a comparison-based sorting algorithm, and is part of the , In computer science and mathematics, a sorting algorithm is an algorithm that
puts elements, Insertion sort is a simple sorting algorithm, a comparison sort in which the
sorted, Quicksort is a sorting algorithm developed by C. A. R. Hoare that, on
average, makes O, Selection sort is a sorting algorithm, specifically an in-place comparison
sort, {/codecitation}
Counting Sort, {/codecitation}
Heap Sort:, {/codecitation}
Insertion Sort:, {/codecitation}
Quick Sort, {/codecitation}
Selection Sort

14.

C++ Tricks I see lots of programmers write code like this one:
~~~~~
pair<int, int> p;
vector<int> v;
// ...
p = make_pair(3, 4);
v.push_back(4); v.push_back(5);
~~~~~
while you can just do this:
~~~~~
pair<int, int> p;
vector<int> v;
// ...
p = {3, 4};
v = {4, 5};
~~~~~
[cut]
[This](http://codeforces.com/blog/entry/10124) is a great C++11 tutorial for those who want to know more about C++11.
#### 1. Assign value by a pair of {} to a container
I see lots of programmers write code like this one:
~~~~~
pair<int, int> p;
// ...
p = make_pair(3, 4);
~~~~~
while you can just do this:
~~~~~
pair<int, int> p;
// ...
p = {3, 4};
~~~~~
even a more complex `pair`
~~~~~
pair<int, pair<char, long long> > p;
// ...
p = {3, {'a', 8ll}};
~~~~~
What about `vector`, `deque`, `set` and other containers?
~~~~~
vector<int> v;
v = {1, 2, 5, 2};
for (auto i: v)
cout << i << ' ';
cout << '\n';
// prints "1 2 5 2"
deque<vector<pair<in...

You can use lambdas in `for_each`, `sort` and many more STL functions:

15.

CSES Sorting and Searching section editorials I just completed CSES Sorting and Searching section problems. And I didn't find any editorials for this. So I am writing my own approach for the problems.Please do correct me if I made any mistakes and do share your approach for the problems.
My solutions are [here](https://github.com/Perdente/CSES/tree/main/Sorting%20and%20Searching)
complete editorial for [CSES](https://cses.fi/problemset/) coding platform of all 27 problems in Sorting and Searching section.
--------------------------------------------------------------------------------------------------------------------------------------
**1.Distinct Numbers**
<spoiler summary="Editorial">
Just use set to store the elements and answer is the size of set.
</spoiler>
<spoiler summary="idea">
~~~~~
int n,x;cin>>n;
set<int>s;
for(int i=0;i<n;++i)
{
cin>>x;
s.insert(x);
}
cout<<s.size()<<endl;
~~~~~
</spoiler>
**2.Apartments**
<spoiler summary="Editorial">
...

CSES Sorting and Searching section editorials, First sort the pair in non decreasing order. Then each time get, First we have to sort the array. The total distance between, Here,we sort the pair according to the ending time.Now, Two pointer technique-First sort the array. Then we have to minimize, i=0;i>xx; a[i]=xx; v[i]={xx,i+1}; } sort, i=0;i>xx; a[i]=xx; v[i]={xx,i}; } sort, in Sorting and Searching section.
--------------------------------------------------------------------------------------------------------------------------------------, the pointer increase along with counter. NB.Don't forget to sort both the
arrays., ) { cin>>i; } sort(v.begin(),v.end()); ll mid=v[n/2],ans=0; for(ll &i:v) { ans, ) { int x,y;cin>>x>>y; v[i]={y,x}; } sort(v.begin(),v.end()); multiset, ++) { ll x,y; cin>>x>>y; arr.push_back({x,y}); } sort(arr.begin(),arr.end, I just completed CSES Sorting and Searching section problems. And I didn't find
any editorials, My solutions are [here](https://github.com/Perdente/CSES/tree/main/Sorting
%20and%20Searching), sorting to find the maximum amount of arrival times of the customers. , ~~~~~ cin>>n; VP vp; lp(i,n) { cin>>x>>y; vp.pb({x,y}); } sort(vp.begin

16.

O(n) Sorting Algorithm — Counting Sort There are many sorting algorithms like [merge sort](https://pencilprogrammer.com/algorithms/merge-sort/), [quick sort](https://pencilprogrammer.com/algorithms/quicksort-code-using-recursion/), etc to sort a linear data structure.
Of all the sort algorithms **Counting sort** is better, because time complexity is approx **O(n)**.
But counting sort is **only viable** when
- values of element lie in the small range.
- the values are non-negative.
Counting sort make use of an extra array also known as **counting array**.
Consider the following array `[5, 9, 11, 10, 15, 12, 2, 8 ,10]` — Min = 2 and Max = 15.
Counting array will store the frequency of each element of the original array at the relative index position. For example in our case, the frequency of 2 will be stored at index 0, frequency of 3 at 1, frequency of 4 at 2 and so on.
Finally, after storing the frequency of each element in the counting array, we will rewrite the original array on the basis of ...

O(n) Sorting Algorithm — Counting Sort, But counting sort is **only viable** when, Counting sort make use of an extra array also known as **counting array**., Counting sort should only be used when the input lies in the specific range and
space, Implementation of Counting Sort in C++ --------------------------------------, Of all the sort algorithms **Counting sort** is better, because time complexity
is approx **O(n)**., There are many sorting algorithms like [merge sort
](https://pencilprogrammer.com/algorithms/merge

17.

How to sweep like a Sir ### Cutting to the chase
Clearly you don't need a PhD in Computing to sweep in the yard , but one might be useful in order to know linear and radial sweep algorithms. So , what's all about ? It's just what it sounds it is , sweeping linear ( up to down , for example ) or radial ( making a 360 degrees loop ).
How this can help? [cut] Well...
### Linear sweep
Suppose you a set of objects in an Euclidean plane. We need to extract information about some objects. The method of linear sweeping takes a line and moves it on a fixed direction. Usually the line taken would be vertical and the direction would be left to right or up to down.
![ ](https://upload.wikimedia.org/wikipedia/commons/2/25/Fortunes-algorithm.gif)
Quite abstract for the moment , huh ? Let's go to a more specific example.
#### Rectangle union area
This example is well known. You have a set of rectangles with edges parallel to the OX and OY axes. What is their union area.
Well , first of all , let'...

1. [Line sweep and line segment sorting
](https://uva.onlinejudge.org/index.php?option=onlinejudge, The only remaining question is how we move the imaginary line ? Sorting , of
course.

18.

Good Blog Post Resources about Algorithm and Data Structures There are many good blogs in **Codeforces Blog** where people describes about different **Algorithm and Data Structures** .
Lets gather all the resources about **Algorithm and Data Structures** Explanations. You can comment bellow the link and about it . I will always update that post gather new resources.Hope ,its help all and inspire all to write new blog post in future :)
Last added blogs link will have a tag **(New)**
Resources:
**C++ STL**
[C++ STL: Policy based data structures]( /blog/entry/11080)
[C++ STL: Policy based data structures. Part 2]( /blog/entry/13279)
**String Processing**
[Suffix tree. Basics. Building in O(nlogn)]( /blog/entry/11337)
[Z Algorithm]( /blog/entry/3107)
[Great resource for string algorithms]( /blog/entry/8008)
[Aho-Corasick algorithm. Construction]( /blog/entry/14854)
[Suffix tree. Ukkonen's algorithm](/blog/entry/16780)
[On suffix automaton (and tree)](/blog/entry/22420) **New**
**Data Structur...

**Sorting & Searching**

19.

How to solve IOI 2015 'Sorting' [IOI 2015 — Sorting](http://wcipeg.com/problem/ioi1522)
#### Statement
If we **resume**, then it says: "We've got an **array $S$ of length $N$** (with **distinct** values) and two arrays **$Jx$ , $Jy$ of length $M$** (all arrays filled with values **from 0 to N-1**). Then the game starts and it consist of **M turns**, each turn $i$ goes this way:
- A: We **swap** $S[ Jx[i] ]$ with $S[ Jy[i] ]$ (Jx[i] **can be equal** to Jy[i])
- B: Then we're allowed to do **any swap** (we can swap a value with **itself**). I will call this **custom moves**
The objective of the game is to make the **array $S$ sorted** with the **lower amount of turns**. We're **guaranteed** that there is a solution with an amount of turns **lower or equal than $M$**.
**Limits:**
- $N \leqslant 200000$
- $M \leqslant 600000$
- $M = 3N$, so $M>N$
#### First Procedure
We'll first to solve the problem without trying to get the lower amount of turns. This solution (that is pretty) hard, will ...

How to solve IOI 2015 'Sorting', [IOI 2015 — Sorting](http://wcipeg.com/problem/ioi1522)

20.

[Not tutorial] Sort before insert — A small extension to Merge sort tree Hello Codeforces!
This is my first ever blog on Codeforces, and today I wanted to <s>gain contributions</s> share my small invention during my upsolving. I don't know if there existed a similar idea yet, but as far as I can tell, the editorial for the problem that I have solved does not use my idea. I think it would be nice to share with you guys and have your opinions on this idea.
<h1>Prerequisite</h1>
You should understand what is a segment and what is a merge-sort tree first.
All the code in this blog is in <a href="https://codeforces.com/blog/entry/18051">efficient style</a>, therefore you should at least recognize part of it before reading the code.
<h1>Idea explanation</h1>
<h2>How do we build Merge-sort tree again?</h2>
Merge sort tree is a Segment tree, each node of which contains a sorted set/vector of every element in its range. We build it in a bottom-up manner. To build the parent nodes, we merge 2 sets/vectors of the children the same as we do in the merge-...

[Not tutorial] Sort before insert — A small extension to Merge sort tree,
Can we do with ranges?
As we can see, each node in the merge-sort tree contains only,
Idea explanation
How do we build Merge-sort tree again?
Merge sort tree,
Prerequisite
You should understand what is a segment and what is a merge-sort tree first., of the merge-sort tree then do something like 2 pointer technique. But what is
thesort order? Well, ((n + q) \log n)$. But if the merge-sort tree is used instead, the complexity
is $O(n \log n + q, ); } sort(b.begin(), b.end()); for (auto [val, p]: b) { for (p +=
(int)a.size(); p > 0; p >>= 1, Let `A` be the array we are building the merge-sort tree on, `it[i]` be the
vector that contains, So we can call merge-sort tree — quick-sort tree from now on. :)), Some advantages of "sort before insert" over the classical way
* We can handle, We can see that I sort the array before inserting, so I decided to call this
trick `sort before

21.

Line segment sorting Notice: this is a piece of a bigger problem I'm trying to solve, but I could figure the rest out, and I think this part would be a good resource for the community in general, as I couldn't find anywhere.
The problem: I have an origin point O and a set of several line segments that never crosses each other. I know the line segments have a common angle interval in which they all appear. This angle is measured according to a line parallel to X axis and that contains point O. I need to sort this set of line segments according to the distance from the origin point, meaning that in the angle interval that the line segments appear, if line A is always closer to the point O, A comes first in the set. This comparison must be made without floating point operations!
Here is a tiny (horribly made) pic to illustrate the problem:
![http://imageshack.com/f/p9yxEGG8j](http://imagizer.imageshack.us/v2/150x100q90/909/yxEGG8.jpg)
The section between the dashed line is the region of interest. ...

Line segment sorting, is measured according to a line parallel to X axis and that contains point O.
I need tosort this set, . This angle is measured according to a line parallel to X axis and that
contains point O. I need tosort, If anyone is interested in the full problem, here is a link to it (though i UVa
thissorting isn't

22.

[Tutorial] Getting a sorted subsegment of size k in O(log(n)+k) using Merge sort tree Statement
==================
We are given an array $a$ of length $n$.
For some reason, we need answer $q$ queries. For the $i$-th, we need to return the contiguous subarray $a[l_i, r_i]$ of size $k_i=r_i-l_i+1$ in **_sorted order_**.
Solutions
==================
#### Naive solution: $O(1)$ preparation, $O(klog(k))$ per query
We can just copy the subarray and sort it using various sorting algorithms. Using comparison sorting algorithms (quick sort, merge sort, std::sort, ...) will get us $O(klog(k))$. Using distribution sorts (radix sort, counting sort, ...) will get us $O(k\times constant)$ but these are generally not much better than comparison sorts due to high constants.
#### Merge sort tree: $O(nlog(n))$ preparation, $O(log(n)+klog(k))$ or $O(log(n)+klog(log(k)))$ or $O(log(n)+k)$ per query
_To make the math easier to work with, we will assume that the segment tree is a Perfect Binary Tree._
Recall that when querying a range of size $k$, we need at most $2log_2(k...

[Tutorial] Getting a sorted subsegment of size k in O(log(n)+k) using Merge sort
tree, We can just copy the subarray and sort it using various sorting algorithms.
Using comparison

23.

Game sort numbers Hello codeforces.
Today I have a very interesting exercise, which is a number sorting game. First of all, let's understand this game.
The interface will consist of a rectangle of m rows and n columns, containing **m * n** squares of size **1*1**. The squares will get a value from **1** to **m*n-1** where no **2** cells have the same value, and **1** empty cell is numbered **-1**.
For each step, the player is allowed to change the position of the empty cell (_containing the number **-1**_) for the adjacent cells.
The game will be over if the tiles are in place, an empty cell (bearing number **-1**) is at the bottom right corner, the remaining numbers are arranged in ascending order from left to right, top to bottom.
The figure below is an example of the ending game:
![ ](https://www.upsieutoc.com/images/2021/02/08/a.png)
Given before starting game state check if you can end the game, output "YES" if possible, otherwise return "NO".
### Input
- The first is two integers ...

Game sort numbers, Hello codeforces. Today I have a very interesting exercise, which is a number
sorting game. First

24.

std::stable_sort vs std::sort This is my first blog post, so it probably will end up being scuffed.
==============================
The problem
==============================
So I was working on [CF 472D, Design Tutorial: Inverse the Problem](https://codeforces.com/contest/472/problem/D) and it requires an MST (sorry for spoiling) and I chose to use Kruskals MST to do this (just note that I could've avoided this issue by using any other MST alg, but that's not the point here). So I just coded vanilla Kruskals where I [std::sort](http://www.cplusplus.com/reference/algorithm/sort/)'ed the edges and used a DSU with path compression and union by size. And I submitted the code and lo and behold, [it was TLE on tc 39](https://codeforces.com/contest/472/submission/109422457)! I entered into a state of depression and decided to change my std::sort to [std::stable_sort](http://www.cplusplus.com/reference/algorithm/stable_sort/) and wow, it ac'ed ([with 1934ms on a 2 second TL](https://codeforces.com/contest/472/subm...

std::stable_sort vs std::sort, - 1466ms, c++17 with sort

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/03/2021 01:16:27 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|