tourist may reach the historic mark of 4000 rating in tomorrow's contest! Good luck tourist!

Edit: He did not participate :(

Thank mike. Polygon and Codenforces orz

It has been one exciting year since I gave my most sincere thanks to the legendary tourist after reading about his story. Remembering what he has done for me and my motivation in this last year, my apreciation for him has grown even further, so I am here to thank him again! To show my love for his existance, here is another drawing in his honor. Now in red and black to represent his awsome rank!

What happened with china this year in IOI? Why did they underperform? Why did they perform so badly this year? Is the chinese level falling? No one ik'ed ioi.

With the broad availability of quick and efficient sorting algorithms, that can sort arrays in $$$O(N*logN)$$$ complexity, little attention has been given to the vast and interesting world of the bad sorting algorithms. Because of this, I will, in this blog, explore this area. To make this list more interesting, we are only going to consider the algorithms in which play a role in the sorting process. That is, there won't be algorithms that use a wait function or an infinite loop.

Bogosort

-This may be the most famous bad sorting algorithm. Its legendary strategy consists of randomly shuffling and array until it is sorted.

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

vector<int> v = {10,9,8,7,6,5,4,3,2,1};
bool sorted()
{
    bool unsorted = false;

    for(int i = 1; i < v.size(); i++) if(v[i] < v[i-1])
        unsorted = true;

    return !unsorted;
}
int main()
{
    bool unsorted = false;
    while(!is_sorted(v.begin(),v.end()))
        random_shuffle(v.begin(),v.end());

    for(int x : v) cout << x << " ";
}

*It is also worth mentioning that there is a variant of this algorithms that eliminates the randomness issue: Create all $$$N!$$$ possible permutations of a given array. Go through each one checking if they are ordered or not.

Complexity

• In average, $$$(N-1)*N!$$$ swaps are made.

Bozosort

-This is another sorting algorithm that relies on randomness to be bad and the strategy it uses to sort is quite simple: If the array is not ordered, randomly select two elements of an array, swap them. The expected time complexity is a bit more complex, but on average $$$N!$$$ swaps are made.

#include<bits/stdc++.h>
using namespace std;
vector<int> v = {10,9,8,7,6,5,4,3,2,1};

int main()
{
    srand(time(0));

    int iteration = 0;
    while(!is_sorted(v.begin(),v.end()))
    {
        int i = rand() % v.size();
        int j = rand() % v.size();
        swap(v[i],v[j]);
    }

    for(int x : v) cout << x << " ";
}

Slowsort

-This algorithm is a very interesting one. It utilizes the infamous technique of multiply and surrender in order to sort its elements. The recursion it utilizes is very "efficient" and interesting:

function slowsort(begin,end)

   mid = floor((begin + end)/2)
   slowsort(begin,mid)
   slowsort(mid + 1, end)
   if(array[mid] > array[end]) swap(array[mid],array[end]) //we compare the greatest element of each half
   //now, the greatest element of the array is in the end, so we call recursively without including the last element

   slowsort(begin,end - 1)

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

vector<int> v = {10,9,8,7,6,5,4,3,2,1};

void slowsort(int st, int ed)
{
    if(st >= ed) return;

    int mid = (st + ed)/2;

    slowsort(st,mid);
    slowsort(mid + 1, ed);

    if(v[mid] > v[ed]) swap(v[mid],v[ed]);

    slowsort(st,ed - 1);
}

int main()
{
    slowsort(0,v.size() - 1);

    for(int x : v) cout << x << " ";
}

Complexity

• The complexity of this method is kinda sketchy, so I will just say it is very very bad (not polynomial, not by far).

To finish this amazing list, I will present a sorting algorithm that becomes faster the more faith one has. I present to you the unmatched, the most amazing:

Miracle Sort

This niche method relies solely on the faith the programmer has on whatever it is that he believes. The method to sort consists of 3 simple steps:

1. Check if the array is sorted
2. Have faith
3. Check if, by some miracle, the array is sorted again

#include<bits/stdc++.h>
using namespace std;
vector<int> v = {10,9,8,7,6,5,4,3,2,1};

void pray()
{
    //put whatever you use to pray here, I will put my prayer
    /*
	ヴァスコ・ダ・ガマ賛歌
	ヴァスコ・ダ・ガマ

	心から歌おう
	マルタ十字は我が旗
	英雄ポルトガル人の名を冠する
	ヴァスコ・ダ・ガマ、あなたの名声はこうして築かれた

	あなたの絶大なファンは大喜び
	ブラジルの南北
	地上に輝く君の星
	海を照らす

	陸上競技では、あなたは腕だ
	ボート競技は不滅だ
	フットボール界では
	ブラジルとポルトガルの結束

	陸上競技は腕だ
	ボート競技では、あなたは不滅です。
	サッカーでは
	ブラジルとポルトガルの団結

	みんなで心を込めて歌おう
	マルタ十字は私の旗！
	英雄ポルトガル人の名を冠する
	ヴァスコ・ダ・ガマ、それが君が有名になった理由だ

	あなたの膨大なファンはとても幸せです
	この国の南北、南北
	地上に輝く君の星
	海を照らす

	陸上競技では、あなたは腕だ
	ボート競技は不滅だ
	フットボール界では、君は不滅だ
	ブラジルとポルトガルの結束

	陸上競技は腕だ
	ボート競技では、あなたは不滅です。
	サッカーでは
	ブラジルとポルトガルの結束
	*/
    return;
}
int main()
{
    while(!is_sorted(v.begin(),v.end()))
    {
        pray();
    }

    for(int x : v) cout << x << " ";
}

With this quite reliable method, one can hope that the array will be sorted in $$$O(Faith^{-1})$$$ time complexity.

Conclusion

I hope you enjoyed this trip through the bad sorting algorithms. This is merely an introduction and I have yet to see everything bad algorithms have to offer. I find them interesting because the way they manage to get such a bad complexity is quite creative.

Hello codeforcers, today you I will show how to order pizza through CSES. It is really cool!

Step 1 — Accessing the link

The first step is to access the link. The link is : this

Step 2 — Ordering the pizza

After you log in, you can select the flavor of pizza you want. However, it is in Finnish, so here is a translation of the menu:

Step 3 — Enjoying the delicious pizza

After you order, all you have to do is to enjoy the delicious pizza from CSES!

Hello guys, today I will do a tutorial on how to clean a vector, structure or something else in c++ really fast.

Naive Approach

-A newbie may see this problem and try to solve it in linear time, for that we could just use the resources the C++ libraries offer us. In this particular case, the function clear() would do it. However, it is an $$$ O(length) $$$ function and considering N can be very big, until $$$ 10^9 $$$, for an example, it cannot solve every problem of this type.

Smart Approach

-A more experienced coder, like Errichto, will see this problem and immediately think about the smart approach. This approch consists of doing the following:

vector<vector<int>> auxiliary; //vector full of empty vectors
vector<int> v; //full of stuff (a lot) and we want to clear it fast

auxiliary.push_back({});
swap(auxiliary.back(),v);

• Boom!, the complexity fell from ~$$$O(N)$$$ to ~$$$O(1)$$$. On my machine clearing vector of size $$$10⁸$$$ with the dumb approach took $$$0,789s$$$ and with the smart approach it took $$$0,438s$$$. Thus, in the next time you need to clear a lot of vectors, use the smart approach, your code will be much faster.

• P.S: this idea can easily be expanded for other structures, just substitute the 'vector' in the code for the structure you want and make the necessary changes to it.

Co-authors: tourist, Um_nik, Errichto.

Recently I got invested in learning Portuguese, so, to better learn the language, I started coding in Portuguese, so that my memory of words in this beautiful language could get better. However, I was really upset when I could not submit problems in codeforces in Portugol, the coding language in portuguese. Why is there no support for this? I really want to improve my language skills both in programming and irl.

As tourist's biggest fan, it was inevitable that I collected a substantial amount of tourist's pictures as the years went by. So now, I think I have enough of them and want to share them with the community.

Very Young Tourist

Young Tourist

Happy Tourist

Very Happy Tourist

Awkward Tourist

Anime Antagonist Tourist

Impostor Tourist(No fucking way that's him)

Teenager Tourist

Anime MC Tourist

Pool Master Tourist

Rich Tourist

Relaxed Tourist

Tourist looking up Tourist

Model Tourist

As you all know, I am very grateful for what tourist has inspired me to do and for what he has done to the community, inspiring not only me, but thousands of coders to go beyond what they previously thought they were capable of. So, lastly, my favorite version of tourist, and my way to show, as a member the Competitive Programming community, how important and grand this man is:

Thank you Tourist

I started coding after discovering about tourist's history in cp, so, to honor him, I made a drawing of him. Thank you tourist for inspiring me to begin learning such an incredible subject.

On my second day, I finished step 1 from the two pointers section from the ITMO course and then went on to segment tree and, just wow, didn't know such a cool data structure existed! It was great to learn about it. I am impressed at the number of ways you can model it to fit different purposes and problems. Now, with my motivation at a new high, I hope to keep on progressing in CP and discovering more about such a beautiful side of programming. I will keep updating my blog to keep me motivated and eventually inspire more people to learn more about CP. Thanks for everyone who is supporting me and to the contest creators and developers for maintaining such a good website and community!

I recently started my journey here on codeforces and today I did my first contest ( of many to come, hopefully ). The idea for the problems I did (A and B) are really cool, so I want to share it with whoever wants to see them.

A - The observation needed for this problem is that, given an optimal subarray, we have two cases. Let's assume you want to expand it to the right ( it's the same case if it's for the left ), if the next number is already on the array, r-l-c(l,r) increases by one, since c(l,r) stays the same and r increases by 1, so overall, the value increases by 1. If the next value is not on the array, c(l,r) increases by one and so does r, so overall, the value stays the same. That is, if you expand an optimal subarray, the value we want to maximize either stays the same or increases by 1. Then, all you need to do for a given test is to print 1 n.

B - I am still not sure how to prove that this idea is correct, but what I thought on this problem is that the optimal answer has all the multiples of the gcd of everyone.

Those are the ideas I had on this contest! The ideas, although simple, were not trivial to be seen, and that is where I think the beauty of CP and math problems are. I would like to thank the developers of the contest, Cocoly1990, waaitg and Imakf for the good time I had trying to solve it!

I am doing the ITMO course and the ideas are really cool. Glad I began doing CP!

I am starting my journey on this wonderful website and just did my first problem after learning two pointers. I am very happy! I hope I like Cp!