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 ^^!

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 ballss and quanhoangbla. Of course, they are good friends so they taught me everything about that. NO. ballss just called me dumb, so I decided to learn it myself. That's when I stumbled across this 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 understand the main idea, I think that it might be confusing for other newbies too. So, I decided to rewrite that blog, to understand about this topic more and to contribute to the community :D.

Also, as you can notice from the title, this is the first part of this series. If I'm not lazy, I may write some more parts. If you want me to rewrite a blog, you can DM me for that topic.

NOTE THAT ALL OF THE IDEAS IN THIS BLOG WERE FROM THIS BLOG. WHAT I DO IS JUST REWRITE THAT BLOG SO THAT IT'S EASIER TO UNDERSTAND

Now, for the main part of the blog:

Counting inversion using mergesort/fenwick tree

Problem statement:

You were given an array $$$a$$$ of size $$$n$$$ $$$(1 ≤ n ≤ 10^5,$$$ $$$a_i ≤ 10^5$$$ $$$\forall$$$ $$$1 ≤ i ≤ n)$$$. Count the number of inversion in this array.

Naive approach: Brute force

Since the constraint of $$$n$$$ is up to $$$10^5$$$, so this approach will certainly get TLE. Tho, I think it's good to have this part so that you can understand the correct solution better.

The main idea of this method is to use 2 for loops to iterate through all of the possible pair of index. Then, you check if they sastify the condition. If yes, increase the count by 1.

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 69;
int a[N]; //the given array
long long cnt; //The number of inversions. Use long long to avoid overflow

int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i <= n; i ++) {
	    for (int j = i + 1; j <= n; j ++) {
	        //by writing the for loop like this, the first condition (i < j) is already satisfied. Now, we 
	        //just need to check the second condtion (a_i > a_j)
	        if (a[i] > a[j]) {
	            cnt ++;
	        }
	    }
	}
	cout << cnt;
}

Time complexity: $$$O(n^2)$$$
Space complexity: $$$O(n)$$$

Solution 1: Using Mergesort

It is recommended to read this blog to know more about merge sort

For the main idea of this method:

You need to count the number of inversions in the array $$$a$$$. You split them into 2 halves: array $$$b$$$ and $$$c$$$ (array $$$b$$$ contains the first half of array $$$a$$$, and array $$$c$$$ contains the second half). Assume that you have the inversion count for array $$$b$$$ and $$$c$$$. So, to get the inversion count of array $$$a$$$, you need to add the number of inversions in array $$$b$$$, array $$$c$$$, and the cross inversions (the number of index $$$i$$$ and $$$j$$$ so that, $$$i$$$ is in array $$$b$$$, $$$j$$$ is in array $$$c$$$ and $$$a_i \gt a_j$$$. This is an inversion since $$$i \lt j$$$). Think how to count this.

#include <bits/stdc++.h>
using namespace std;

//this code is made by a human, not AI. The comments and long function name is to make the code easier to understand
//sometimes I regret making long function name -_-

const int N = 1e5 + 69;
vector <long long> a; //the given array
int n;

long long count_cross_inversion(vector <long long> &a, int l, int mid, int r) {
    vector <long long> b, c; //array b and c
    b.push_back(0);
    c.push_back(0); //push_back to make them 1-index
    for (int i = l; i <= mid; i ++) {
        b.push_back(a[i]);
    }
    for (int i = mid + 1; i <= r; i ++) {
        c.push_back(a[i]);
    }
    //making array b and c
    int l1 = mid - l + 1;
    int l2 = r - mid; //the length of array b and c
    int i = 1;
    int j = 1; //the two pointers
    int idx = l; //the current index of array a
    long long ans = 0;
    while (i <= l1 && j <= l2) {
        if (b[i] <= c[j]) { //normal case
            a[idx] = b[i];
            i ++;
        } else if (b[i] > c[j]) {
            //this is the case where b[i] > c[j] and i < j; aka the case where there's an inversion
            a[idx] = c[j];
            ans += (l1 - i + 1); //we add l1 - i + 1, because if b[i] > c[j] then b[i + 1] > c[j], ..., b[l1] > c[j] (since the array b is sorted)
            j ++;
        }
        idx ++;
    }
    //add remaining numbers, as usual
    while (i <= l1) {
        a[idx] = b[i];
        idx ++;
        i ++;
    }
    while (j <= l2) {
        a[idx] = c[j];
        idx ++;
        j ++;
    }
    return ans;
}

long long count_inversion(vector <long long> &a, int l, int r) { //count the number of inversions of array a in the range l and r
    if (l == r) { //base case, where the length of a is 1. The answer for this case is 0
        return 0;
    }
    int mid = (l + r) / 2; //mid is the midpoint of the array, to split the array a into array b and c.
    long long res = 0;
    res += count_inversion(a, l, mid); //count the number of inversions in range l and mid (aka in array b, as well as sort the array b)
    res += count_inversion(a, mid + 1, r); //same thing for array c
    res += count_cross_inversion(a, l, mid, r);
    return res;
}

int main() {
	cin >> n;
	a.push_back(0); //push back to make the vector 1-index
	for (int i = 1; i <= n; i ++) {
	    int x; cin >> x;
	    a.push_back(x);
	}
	cout << count_inversion(a, 1, n);
}

Time complexity: $$$O(n$$$ $$$log$$$ $$$n)$$$
Space complexity: $$$O(n)$$$

Solution 2: Using Fenwick tree

It is recommended to read this blog to understand what is Fenwick tree. Explaining this is quite long so, for the sake of simplicity, assume that you know how fenwick tree works (by reading the blog I recommended) ^^

The main idea of this algorithm is, you build a frequency array, let's call it $$$freq$$$. Then, $$$freq_i$$$ will be the number of times that $$$i$$$ appeared. So, the number of indexes that are less than are equal to $$$i$$$ would be

Where $$$prefix_i$$$ is the prefix sum of the first $$$i$$$ elements in array $$$freq$$$. You can get this value in $$$log$$$ $$$n$$$ time using fenwick tree.

So, to count the number of inversions in an array $$$a$$$, initially, we set the array $$$freq$$$ to $$$0$$$. Then, you would need to iterate $$$x$$$ in array $$$a$$$ from back to front. After that, you add the numbers of indexes that are less than $$$a_x$$$ to the answer, which is the $$$prefix_{a_x - 1}$$$ to the array. This can be done in $$$log$$$ $$$n$$$ time. Note that you add $$$prefix_{a_x - 1}$$$, not $$$prefix_{a_x}$$$ since you need to count the number of elements that are less than $$$a_x$$$, not less than or equal to $$$a_x$$$.

Finally, you update the $$$freq_{a_x}$$$ by one. This mean that, you need to update the $$$prefix$$$ array as well. This can also be done in $$$log$$$ $$$n$$$ time using fenwick tree.

#include <bits/stdc++.h>
using namespace std;

//this code is made by a human, not AI. The comments and long function name is to make the code easier to understand
//sometimes I regret making long function name -_-

const int N = 1e6 + 69;
long long fenwick_tree[N];
int n;
 
long long get(int i) {
    int idx = i;
    long long ans = 0;
    while (idx) {
        ans += fenwick_tree[idx];
        idx -= idx & (-idx);
    }
    return ans;
}
 
void update(int u) { //increase the element of freq[u] by 1
    int idx = u;
    while (idx <= N) {
        fenwick_tree[idx] ++;
        idx += idx & (-idx);
    }
}

//the whole thing above is the template for fenwick tree

int main() {
	cin >> n;
    vector <long long> a;
	a.push_back(0); //push back to make the vector 1-index
	for (int i = 1; i <= n; i ++) {
	    int x; cin >> x;
	    a.push_back(x);
	}
    long long count_inversion = 0;
	for (int i = n; i >= 1; i--) { //iterate i from back to front
        count_inversion += get(a[i] - 1); //add the answer by prefix[a[i] - 1]
        update(a[i]); //update the fenwick tree
    }
    cout << count_inversion;
}

Time complexity: $$$O(n$$$ $$$log$$$ $$$n)$$$
Space complexity: $$$O(n)$$$

Bonus (this isn't in the original blog):

As you can see, the fenwick tree can only store elements that are less than are equal to $$$10^7$$$ (since that's the memory limit for an array in C++, I don't know for other languages). So, if the problem gives you $$$a_i$$$ up to $$$10^{18}$$$, what would you do? Of course, you can still use merge sort, but fenwick tree is way easier to implement.

#include <bits/stdc++.h>
using namespace std;

//this code is made by a human, not AI. The comments and long function name is to make the code easier to understand
//sometimes I regret making long function name -_-

const int N = 1e6 + 69;
long long fenwick_tree[N];
map <long long, int> m;
int n;
 
long long get(int i) {
    int idx = i;
    long long ans = 0;
    while (idx) {
        ans += fenwick_tree[idx];
        idx -= idx & (-idx);
    }
    return ans;
}
 
void update(int u) { //increase the element of freq[u] by 1
    int idx = u;
    while (idx <= N) {
        fenwick_tree[idx] ++;
        idx += idx & (-idx);
    }
}

//the whole thing above is the template for fenwick tree

int main() {
	cin >> n;
    vector <long long> a;
    set <long long> s; //add to a set to sort the numbers, as well as only store elements that aren't the same
	a.push_back(0); //push back to make the vector 1-index
	for (int i = 1; i <= n; i ++) {
	    int x; cin >> x;
	    a.push_back(x);
        s.insert(x);
	}
    int idx = 1; // the current number
    for (long long i : s) {
        m[i] = idx; //use map to remember what is the compressed number of an elements
        idx ++;
    }
    for (int i = 1; i <= n; i ++) {
        a[i] = m[a[i]]; //compress the numbers
    }
    //the rest is exactly the same
    long long count_inversion = 0;
	for (int i = n; i >= 1; i--) { //iterate i from back to front
        count_inversion += get(a[i] - 1); //add the answer by prefix[a[i] - 1]
        update(a[i]); //update the fenwick tree
    }
    cout << count_inversion;
}

So, that's the end of the blog! This is my first time posting something useful (as the others are mostly shitposts -_-), so I hope that you like this. Also, if you want me to rewrite any blog, message me. (Of course, please send me a blog that I can understand, not a FFT blog...).

Thank you for reading, and have a nice day ;)

...for what I've done in the past few days.

Firstly, I want to apologize cry and other users who I DMed. I'm sorry for disturbing all of you in the recent days. Yes, I know that what I did is stupid, but to be honest, I don't know what to do in that situation.

Secondly, I want to apologize the users who are intending to make a div3/4 but now can't do it because of the limit. I, myself, am one of them so I understand how angry you are, and how much hate you are having on me ;). "hi my name is duy mince 3434 and today im gonnan propose actual shit in a kettle to cry" — someone said that about me lol. So, I sincerely apologize to all of you, because of this dumb mistake.

Thirdly, and finally, I want to apologize my friend dinhhuubaonam123, who had spent sooo much time on making the contest. Yes, I'm dumb, sorry ;).

So it's the end for this blog, I hope that I can be forgived for what I've done. Bye, and good luck participating in the upcoming round 1128!

Happy birthday tourist :D

P.S.: I can only fit 7 candles on the cake ;)

No, clearly not.

TL,DR: We (me and my friends) found a cheater in CF after he flexed his performance at round 1113 in LQDOJ's chat (an Online Judge's chat). We found some evidence, and he admitted that he used AI during the contest. However, he didn't even sorry, he just started to normalzize cheating, saying that cheating is crucial for the future. In this blog, I won't go deep into the evidence, but his attitude toward cheating.

This all started when he posted this:

Translation:
pvhung (him): maybe it's D
pvhung: C used DP so it's quite hard.
pvhung: *started to flex*

At this point, we are quite sure that he cheated, because his performance has never been this good.

So we asked for his account. He didn't reply. That's when my friend realized that, if you calculate the total points that he got, combining with the timing that he sent. The result is, this is his account: auracpp

The timing is exact the same. His submissions also got skipped. So, we concluded that he is a cheater.

He admitted it.

However, instead of sorry for what he did, he said this:

Translation:
pvhung: everyone cheats.
pvhung: Are you sure that you don't cheat when you go to school?

The rest is not related.

After that, he said:

Translation:
pvhung: Instead of learning, you could just cheat to get high grades easily.
quanhoangbla: If everyone cheat, the competitions were for students to compete who is better at using AI?
pvhung: bro, no one would care if you really do it yourself at high school
krekupg: so cool T-T (he is joking btw)
quanhoangbla: getting a good grade is nonsense if it is not your work.
pvhung: =))

Please note that, kreukpg did cheat on CF, however, he admitted it, and now, he is participating seriously with a new account.

Moreover, he said:

Translation:
pvhung: Cheating during exam is normal
pvhung: Every exam has a cheater
The rest are not relevant

In the next morning:

Translation:
pvhung: It seems that people don't understand my opinion last night
pvhung: I did't say that cheating is good
pvhung: but
kyanh: What happened?
pvhung: you need to cheat to have good grades
pvhung: if everyone cheat but you don't
pvhung: That's your problem

Translation:
pvhung: I'm grinding CF rating, which doesn't affect anybody
pvhung: *Not relevant
kyanh: bruh, I mean, not cheating is better, since CF rating is not that important, you can practice your logic if you don't cheat
pvhung: No, being honest is not always good.

After that, he started to yap nonsense stuff:

Translation:
pvhung: You guys keep saying that help me understand that the problem is your parents didn't teach you.
pvhung: You guys just think that it is col
pvhung: *cool

Translation:
dinhhuubaonam123: If you cheat now, how could you live in the future
pvhung: For regular exam, cheating is a method to get a better grade, if you can do the exam easily, you don't need to cheat
pvhung: So what if you couldn't?
The rest are not relevant (because I'm too lazy to translate lol)

Finally,

Translation:
pvhung: You should cheat to get good grade
pvhung: J*b employers would look at those grade
pvhung: And you would get into good company and university
pvhung: Getting a good j*b is more important than being honest now.

The conversation ended here (but it might continue in the future, since I posted this blog so it's likely that he would DM me)

Why I posted this blog?

I can't understand how could there be a person like these. He insisted that he is right, so I want to listen to some opinion from the CF community. And I also want auracpp to express his opinion for everyone to listen. BTW, he participated R1114 yesterday and got fully skipped.

Also, I am not a native speaker (my IELTS is around 4.0 lol), so I not that confident about grammar. So, I decided to use AI to check my grammar. As a result, this blog might look like it was generated by ChatGPT, but the core idea is mine.. NVM, my ChatGPT is dumb (it couldn't understand what I want lol), if you found any grammar mistake, please let me know.

btw, if you are greateric, click here please.

This blog can't be done without the help of ballss, dinhhuubaonam123, panhkiet63, and quanhoangbla.

This blog focuses more on the functions (which help you format a blog), not the tips and tricks.

Since many recent blogs are hurting my eyes (I'm talking to you, MEGATRON_HACKER...), I decided to write a blog to share some tips and tricks about how to format a blog.

This post has been written with my best knowledge. If something is incorrect please let me know! I copied this sentence from this blog...

Here's a table of contents if you guys need it:

Table of Contents:

1. Codeforces specific features
2. Math
3. Emoji
4. Change font, font size, color, background color of text, and text's alignment
5. Tables
6. YouTube videos

This blog was written by DuyMinh3005

1. Codeforces specific features:

---

I think that everyone knows how these things work, but I will write this anyway. Here is a picture of the taskbar:
In the taskbar, you can see a few options to format your blog:

• Headings: Different levels of headings, with $$$H1$$$ being the largest, and $$$H4$$$ being the smallest.
• Bold: Make your text bold.
• Italic: Make your text italic.
• Bulleted and numbered lists: Create a bulleted or numeric list. As you can see, I'm using the bulleted list now.
• Picture and link: Insert a picture or a link (with a text to link if you want). To insert a picture, you could use this website to convert your image into a URL and insert it like this: ![ ](http://yourimagelink.jpg). Please note that, the website I said above only stored images for 30 days before it gets deleted
• Source code: This includes block and inline. Block code helps your code render correctly, inline code lets you see the raw code. And PLEASE use <spoiler> if your code is long.

 ```c++
#include 
using namespace std;
int main () {
   cout << "Hello world!\n";
   return 0;
}
``` 

And it would render like this:

#include <iostream>
using namespace std;
int main () {
   cout << "Hello world!\n";
   return 0;
}

Likes widgets: Codeforces supports likes in posts and comments. To add like buttons, use the syntax (likes:key,groups) (use square brackets instead of round). The same key means the same likes widget. The same key with different groups can be used for exclusive choices. For example:

Quote: You can quote a sentence from another comment or blog using the syntax > Your text here for a quote, or <blockquote>Your text here</blockquote> for a block quote. The only difference is that a block quote can span multiple lines, whereas a regular quote is typically limited to a single line.

2. Math:

---

Basically, Codeforces uses LaTeX for us to type math. You can write math symbols by simply "activating" the math mode ($$) and add a backslash (\) followed by the command. For example, \frac{1}{2} will be rendered as $$$\frac{1}{2}$$$. If you want your fraction to be larger, use dfrac instead of frac.
For more information about math symbol syntax, you can have a look here.

3. Emoji:

---

If you didn't know, Codeforces supports emojis. To display an emoji that you want, you just write the corresponding decimal code and the browser will render it for you.

For example, this is Santa Claus: 🎅. Decimal code: 🎅.

For more information about the emoji syntax, you could have a look at this website.

4. Change font, font size, color, background color of text, and text's alignment:

---

As Codeforces uses Markdown to render text, and Markdown includes HTML, so you can change how your text looks.

For example, to change the color of your text, do this: <p style="color:red">This text is red</p>, which will be rendered like this:

This text is red

Now, here is a table with the functions:

Now, if you know how to use these functions, you can actually do something fun:

For example, this is me: DuyMinh3005

This behaves exactly like a real profile link: when you click it, it redirects to my profile (which is still a pupil), and when you hover the link, it says "Legendary Grandmaster DuyMinh3005"

Another trick, which is more useful, is that you can make an anti-AI prompt just like this:

So you did what I said correctly

...and paste it into Notepad, you will find something interesting.

To do this, you need to set the font-size to 0.

5. Tables:

---

Basically, Codeforces uses Markdown to render tables. Markdown tables use pipes (|) to separate columns and hyphens (-) to define the header row. The structure includes a header row, a divider line, and data rows.

For example:

| No. | Name | Revenue |
|-------|-----|-----------|
| 1. | Clash Royale | $452.0 million |
| 2. | Brawl Stars | $272.6 million |
| 3. | Clash Of Clans | $253.9 million |
| 4. | Hay Day | $119.1 million |
| 5. | Boom Beach | $13.2 million |
| 6. | Squad Buster | $9.5 million |

Which will be rendered as:

Supercell's game revenue in 2025

You can control the alignment of text in each column too. I don't know why, but it seems that Codeforces doesn't support text alignment inside tables. If you still want to align text (for tables), you could use text-align as I said above.

6. Youtube videos

---

Well, you can add a Youtube video into Codeforces using HTML.

<iframe width="640" height="360"
src="https://www.youtube.com/embed/dQw4w9WgXcQ?autoplay=1">
</iframe>

To do this, you first need to get the ID of the video you want to play. For example, dQw4w9WgXcQ is the ID of the Rickroll above. Then, use this syntax:

<iframe width="640" height="360"
src="https://www.youtube.com/embed/ID goes here">
</iframe>

You can change the width and height, but as far as I know, 640×360 is a good size for embedded videos.

If you want your video to be autoplayed, use autoplay=1 like this:

<iframe width="640" height="360"
src="https://www.youtube.com/embed/ID goes here?autoplay=1">
</iframe>

If you want your video to be muted, use mute=1 like this:

<iframe width="640" height="360"
src="https://www.youtube.com/embed/ID goes here?mute=1">
</iframe>

If you want both at once (greedy approach?), use autoplay=1&mute=1 like this:

<iframe width="640" height="360"
src="https://www.youtube.com/embed/ID goes here?autoplay=1&mute=1">
</iframe>

Hello CodeForces community!

Because I'm too lazy to write an intro, let's just get straight to the point.

1. moh-kaz333: AI alike variables and functions names in F, G; like Path Result, BuildModPath, etc. Submission: F, G.

2. Mostafafied: He got skipped at least once in every problems (except for F).

3. dugu_qiubai: Got AI comments in F and G.

4. v.s.golovanov: His code looks like it was written by AI, with long variable names. Also, he got an AC on D just after 39 seconds from his C's AC

5. PKsilent: His B and D code got comments in French. He also cheated before in Educational Codeforces Round 188.

6. ayushmaan1092: He got an AC on E just after his AC on G 1 minute. And, if you argue that you found a small typo in your E's code which then lead to an AC, you can do a compare to see a big difference.

7. JC_Zhang: He got skipped at least once in every problems (except for E).

8. risk_master: He got skipped at least once in every problems.

9. sadwqdqEF213: He got comments in B, D, and E.

And more cheaters... (TBA)

NOTE: THIS IS MY OWN OPINION, I CAN MAKE MISTAKES.

Thank you!

Of course, the fastest way to become red is cheating. To be specific, use Gemini Pro. And, thanks to this method, I think Thanmai_19, jnccyyyq, ashgrove, nihaaleee, Terminator12, iammeteor, and phucngo2512010 will become a LGM soon.

1. Thanmai_19: He/she got AI comments in A and B, switched to Java in C and D.

2. jnccyyyq: Got TLE once in E, and then do it again with a totally different idea in just 7 minutes.

3. ashgrove, nihaaleee, harshxdsa: Many comments in their code.

4. Terminator12: Changed from Python 3 to C++ in just 3 minutes.

5. iammeteor: He/she got comments in E, and Vietnamese one in F.

6. phucngo2512010: His/her code for sure is made by an AI. Also, look at the time he got C and D correct...

Other suspects: undefined_Ryan, qwertyuiojhygtfdfg: I can't find any proof for these guys, I even looked at undefined_Ryan's past contest, but there are still no clue. Please tell me if I am missing something.

NOTE: THIS IS MY OWN OPINION, I CAN MAKE MISTAKES. ALSO, THE METHOD ABOVE IS JUST A JOKE, PLEASE DON'T CHEAT ;))

Hello Codeforces community!

After the previous Educational Codeforces Round 188 ended, I have noticed that there are so many cheaters who are maintaining their position at the top of the ranking. So, in this blog, I will list out some of them. Although my only method to expose cheaters is to look at their comments, I have found out quite a few of them.

Note: This is my own opinion, I can make mistakes.

1. The top 1 on the leaderboard, sonsimpmiku.

This one is quite obvious. He (or she?) got every problems accepted in 35 minutes, outstanding LGM like maspy, kotatsugame, etc.

2. Arthur_uncle

He got a big difference between his A — F submissions and G submission. Also, his submission for G has many comments

3. imakshat

Similar to Arthur_uncle, his F and G code got comments that look suspicious.

4. PKsilent

EVERY submissions of him have got comments in French.

5. ILoveNgocLinh

His comments aren't really suspicious, however, he changed his comments' language from English (in F) to Vietnamese (in G). Quite interesting, isn't it?

6. Last but not least, AshutoshSaugan.

This is the funniest case I've ever seen. In his submissions, none of them are suspicious. However, if you take a closer look, he submitted G TWICE, as he forgot to clear his AI's comments in the first one. This is the first one, and this is the second one.

Once again, this is my own point of view; I can make mistakes. If I missed anything important, please feel free to share your opinions

Thank you.